Tom Saves MicroTails

Tom Saves MicroTails

Here’s a little fictional story …

As a Security Analyst at MicroTails, Tom’s day started in the usual way. He logged-in and viewed the trillions of alerts coming from systems all over the world. His current task was to monitor the new release of MicroTails’s new operating system: MT-OS 10. As it was a pre-release, Tom had a whole lot of new tools at his fingertip, and which analysed the alerts as they came in. Luckily, his trusted machine learning tools did most of the work for him, and for Tom, it was a matter of looking for things that either trigged lots of alerts, or were unusual — an anomaly. The machine could often spot standard patterns of things that were a problem, but it was Tom’s experience and skills that could truly spot things that had never been seen before. His eyes and brain were better than any piece of software ever created and could spot issues where most people would see garbled text. He didn’t quite understand how it happened, but he could spot a needle in a million haystacks.

But, something was different on this day. His eyes were primed on the scrolling alerts, but there was one alert that kept jumping out at him:

“Error in encryption. RSA decryption in error on object: X”.

Tom had been trained that anything to do with encryption was something that should be looked at. It was either a sign of a major problem, or that there was a configuration error. But, the alerts were patchy, and not consistent. So, he fired up with Python console and gathered a sample from the millions of alert files.

“Let’s look for the alert, and find the hit rate”, he mumbled to himself. “False”, “False”, “False” … and so he went on, until “True”, and “False”, “False”. The script showed him: “Alert rate: 0.003%”. “Mmm. Is that significant or not?”. As a Security Analyst, it was his call, as to whether it was just little localized thing, or was the sign of a bug. For MicroTails, some bad releases of software in the past had resulted in a new motto was:

“A stitch in time saves nine”

So for Tom, a bug found at this stage could save MicroTails a great deal of money, especially in the resources required to bugs at a later stage. But something worried Tom. “What happens if I work out the chances of the alert happening on each machine?”. So he inverted the value and got:

1-in-32,768

“That looks a bit like a binary value!”, he thought. And quickly typed in a Python script:

>>> bin(32768)
‘0b1000000000000000

“And if I multiply by two. I get 65,536”. The number jumped out at him, as he’d just been studying the basics of RSA with his Professor at university, and where the e value was typically 65,537. He thought: “Surely, it is strange to see a 1-in-32,768 chance for all the logs, and something that look like a single bit value of 1”.

So his training had shown him that he should segment the data into a number of clusters, and then analyse, and see if there was a trend across each of the clusters. With Python, it was so easy: gather random samples from millions of machines into clusters, and then analyse for each cluster. The results looked conclusive — each cluster showed a vulnerability rate of around 1-in-32,768 of the machines had the issue.

Tom flicked the significant event switch on his console, and typed in his initial findings, and requested an exception analysis, and scored it 5 out of 5 and added the keys words of “RSA”, “Encryption Bug”, and “1-in-32,768”. Within minutes, the machine learning program approved his request. He smiled to himself, as this is what he loved about his job … solving problems that no one had ever seen before. A complex set of puzzles to solve, and each revealing more of the puzzle each time.

There was now only one place to look for Tom … MicroTails GitHub for their code respository. So, with a pen and a piece of paper, he jotted down the basics of RSA as he remembered from his university classes:

• Pick p — a prime number.
• Pick q — another prime number.
• Calculate N=p times q. That’s the public modulus.
• Calculate PHI=(p-1)(q-1)

In his head, he could hear his Professor saying:

“Remember that e must be co-prime to PHI”.

But, it didn’t go in at the time, so he thought … “Ah, there’s no shared factor between them. That’s a mod operation in Python, and where the result is zero.” So he continued on with his doodle:

• Pick e so that it does share a factor with PHI, if it does, go back to the start.
• Pick d for the inverse of e mod PHI.
• The encryption keys are then (e,N) for the public key and (d,N) for the private key.
• You encrypt your message (M) with M^e (mod N) to give a cipher (C) and decrypt with C^d (mod N).

“But, what if we didn’t check that e was co-prime to PHI? That would be bad!” He quickly tried the code with a couple of simply prime numbers, and the red text of an exception appeared at the point that d was computed.

“If we didn’t catch this and regenerate our prime numbers, this would mean that all of the data encrypted with the public key, would not be able to be decrypted. And that would be a disaster for MicroTails, and for our customers”.

And there it was in front of him on the GitHub code. There was no checking of the value of PHI against e, and the developer has put in an exception to catch it, so that the code could continue. Alongside there was a comment:

# Sometimes causes an exception, so catch it here
try:
 p= newprime(2**512)
 q= newprime(2**512)
 N = p*q
 PHI = (p-1)*(q-1)
 e= 65537
 d = invmod(e,PHI)
except:

The “sometimes” rang clear to Tom. The “sometimes” was actually quite precise, was whenever e shared a factor with p-1 or q-1. The chance was 2-in-65,357, and just the same as he saw.

This was serious! One in around 32,000 customers would be creating data which could not be decrypted and was lost forever. Tom imagined the damage done to systems across the world - health records lost, control systems crashing, and all those the legal claims for lost data:

“Dear MicroTails, 
All my photos of my family have been lost! I cannot put a value on these, and you have made them disappear. You will hear from my solicitor.”

Tom flicked the serious alert switch, and within seconds, the shift manager was on the phone. “We are in big trouble”, Tom said. “We need to stop all the prerelease updates, and get onto the development team to update the code, and add a check for the generation of the keys. Now! Then re-enable the updates. But make sure the development teach test this time, and generate billions of keys, and validate every one of them. And I want to see the results before we go live again”. outlined Tom, and “And I need time to work on the code to see if I can find a decryption key for each of the affected customers.”. Almost instantly his shift manager approved, “The time is yours. I will enable all of this for you. Please find a solution, soon.”

There was only one place to look … his research paper library, and the place he kept all his research. He searched for “e sharing factor with PHI”, and out popped a paper which focused on this, and outlined two algorithms to catch the exception for the incorrect generation of d, and then code for something that could be used to decrypt the data. So, Tom kept it simple, and tried [code]:

from libnum import invmod
import sys

M = 10

p=13
q=7


e=5

if (len(sys.argv)>1):
	M=int(sys.argv[1])
if (len(sys.argv)>2):
	p=int(sys.argv[2])
if (len(sys.argv)>3):
	q=int(sys.argv[3])

N=p*q
PHI=(p-1)*(q-1)

print ("N=",N)
print ("PHI=",PHI)


cipher=pow(M,e,N)

print ("\nCipher=",cipher)

# d e mod (PHI) = 1

if ((p-1)%e==0 and (q-1)%e==0):
  print ("\nCannot recover. e is a factor of (p-1) and (q-1).")
  sys.exit()

try:
  d= invmod(e,PHI)
  plain=pow(cipher,d,N)
  print ("\nPlain=",plain)
except:
  print ("\nDanger!!!!")
  phi=int( ((p-1)*(q-1) )//e)
  g=1
  ge=1
  while (ge==1):
    g=g+1
    ge = pow(g,phi,N)
  print ("Ge=",ge)
  d = invmod(e,phi)
  a = pow(cipher,d,N)

  print ("Recovered d=",d)
  l = 1 % N
  print ("\nPossible contenders:")
  for i in range(0,e-1):
    x = (a * l) % N 
    if (x==M): print (x,"***")
    else: print (x)
    l = (l * ge) % N

It worked! There were contenders for the keys, but the padding in the encryption would sort that out, and where we had a very high chance of finding the decryption key (d).

Now MicroTails had a solution. Luckily the prime numbers (p and q) were stored on each machine, so that anyone with a problem, would basically just require a patch. As the logs showed the machines, it would be easy for MicroTails to follow-up. Tom had saved a disaster for the company, and for many of their customers. In his report, Tom outlined that the development team need to make sure that they looked at exceptions, and reviewed them carefully and that they should test, test and test. And, they should be someone external to their team to do a review, and Tom could think of no better person than his Professor at university. And in conclusions, “Go and get our devs to do a crypto course at the university”.

Fiction? Yes, of course. But, read this: