Conficker, RSA and RC4

I was reading the excellent paper An Analysis of Conficker's Logic and Rendezvous Points from SRI and was surprised to learn that Conficker botnet updates are distributed at its rendezvous points as encrypted and signed binaries using RC4 and RSA (the “R” in both cases here stands for Ron Rivest). Both the A and B variants of Conficker use these checks to ensure that the updates have been created by the Conficker authors – just like any other software vendor issuing updates and patches. The paper depicts the update process as follows

So each Conficker client carries an RSA public key E for signature verification. A Windows binary file F is encrypted and signed as follows

• Hash F to produce a 512-bit hash M
• Encrypt F with RC4 using M as the key
• Sign M using private key D

A Conficker client authenticates the encrypted binary as follows

• Using the embedded public key E, compute the signature verification to recover M
• Decrypt the encrypted binary using RC4 and M as the key
• Verify that the hash of F is in fact M

For Conficker A, the RSA key is 1024-bits and 2048-bits for Conficker B, both of which are listed in the paper. That’s a large public key for Conficker B but it is dwarfed by the 512-bit symmetric key used in RC4. Yes RC4 can support such huge key sizes, and I will explain in a future post how this is possible.

Some Clarification on the RSA Power Attack

I recently posted on the some new work by researchers at the University of Michigan which showed how an RSA private key can be recovered by sifting through a collection of faulty signatures. The faults are created by lowering the power to the chip computing the signature, causing bits to be flipped in the signature multiplication chain. 

I remarked that the coverage from The Register was a bit unfair in its headline of OpenSSL being broken, which was just the cryptographic library used in the proof-of-concept experiment to test the private key recovery procedure. But as pointed out by Bradley Kuhn, the researchers seemed to stress the weakness of OpenSSL against the attack by mentioning it both the abstract and the conclusion of their paper.

But there have been some other posts bordering on the hysterical. Techie Buzz, 1024 Bit Cracked, New Milestone, leads the chorus of RSA’s demise

The RSA encryption was believed to be quite safe and this level of a crack was not achieved, until now. The methods used here are pretty low level and have given results in 100 hours. The crack which was assumed to take a lifetime with brute force, has taken a mere four days. This breaks the very backbone of RSA which believes that as long as the private key is safe, it is impossible to break in, unless guessed.

The post celebrates the fault-based factoring as an advance on the 768-bit factoring record achieved late last year. However the factoring of the RSA 768-bit modulus was unaided by any tricks, and the researchers used modern factoring methods in a distributed computation amounting to over 10^{20} operations. The results are simply not comparable since the fault-based attack is so advantageous to the attacker.

A more sober review is presented by Phil Brass, of Accuvant Insight, in his post Recent Encryption Research Demystified, where he describes the publicity of the attack as “headline hyperbole”. You should not be too worried about your online banking service since

to carry out this attack on an online banking server, the attacker would need physical access to the online banking server’s power supply, which means they would need to be inside the bank’s data centre.  Given the “wealth” of other targets available to an attacker standing inside of a bank’s data centre, theft of the online banking web server private SSL key by a difficult and time-consuming voltage regulation attack seems rather unlikely.

And as to the key recovery experiment itself

The really strange thing about this paper is that while the researchers claim to have implemented the attack on a full-size SPARC/Linux/OpenSSL workstation, the actual hardware was a Xilinx Virtex2Pro FPGA, which was emulating a SPARC CPU, and which the researchers claim is representative of an off-the-shelf commercial embedded device. It seems as if they are trying to have it both ways – i.e. it is an attack against a full-size workstation, and by the way it also is an attack against something you might see in a typical embedded system.

He provides a good summary of the attack and offers that a better headline would be “Obscure bug in OpenSSL library poses little risk to consumers.”  A similar reality check for the hoopla is given by Nate Lawson of Root Labs Rdist, who begins by recalling that the brittleness of the RSA signature operation was identified in 1997 (referenced by the Michigan researchers), with the advice to verify all signatures very carefully before returning them. Lawson provides some more details on the error checking steps taken for signature computations in OpenSSL and he concludes that a much better job could have been done. He is also a bit sceptical of the experimental environment but finally concludes “this was a nice attack but nothing earth-shattering”.

Finally, there is another de-hyped review by Luther Martin at Voltage, where he refers to the PBA Attack after the initials of the three Michigan authors. He states that

Devices that are designed to be secure, like HSMs and smart cards, filter the power so that you can't do attacks like the PBA attack, and with devices that aren't designed to be secure, there's always an easier way to recover a key from them than doing something like the PBA attack. This means that we won't be seeing hackers using the PBA attack any time soon, but you'd never think this from seeing the way it was reported by the media.

Fortunately for this incident Voltage products use DSA rather than RSA for signatures, so advanced debunking for customers will not be required.

All in all, most everyone agrees (and is happy to say) that the work is clever and worthwhile to undertake, adding to our operational knowledge of cryptography. The publicity was a bit overdone, and probably too many hours were spent by security professionals explaining the circumstances and implications of the attack.

Related articles by Zemanta

• 1024-bit RSA encryption cracked by carefully starving CPU of electricity (engadget.com)
• RSA 1024-bit Private Key Encryption Cracked (q-ontech.blogspot.com)
• 'Severe' OpenSSL vuln busts public key crypto (go.theregister.com)
• The PBA attack on RSA (superconductor.voltage.com)
• Boffins Crack OpenSSL Library Using Power Fluctuations (darknet.org.uk)

Recovering RSA Private Keys using Faulty Signatures

Researchers at University of Michigan recently devised a method for recovering the RSA private key used for signing by sifting through a collection of faulty signatures produced by the key. A faulty signature is one where the attacker has caused bits in the signature computation to be flipped from one to zero, or zero to one. Fault patterns that consist of just a single flipped bit permit an attacker to guess and verify a small piece of the private key (called a window), and to eventually recover the entire private key given a sufficient number of such faulty signatures. The researchers ran proof-of-concept experiments to demonstrate that a 1024-bit RSA private key can be recovered from a sample of just under 9,000 faulty signatures created by manipulating the voltage level to the processor computing the signatures.

There are two main ingredients to the attack: a method to recover information about the private key given some faulty signatures, and then a method to actually generate or induce the faulty signatures. We deal with the second point first.

Generating Faults Through Power Fluctuations

The researchers chose to exploit vulnerabilities in modern circuitry to changes in environmental conditions (such as temperature or power fluctuations) that inhibit signal propagation, which lead to faults in computations. The researchers experimented with varying the voltage on a SPARC-based Leon3 server running Debian, using OpenSSL for signing operations. Using runs of 10,000 multiplications the researchers discovered that 1.25V was the optimal value to induce single fault errors, and that reducing the voltage much further resulted in an exponential increase in faults (totally spurious results).

At this optimal voltage level the researchers found that from a sample of 10,000 signatures about 90% would contain at least one fault, and 12% contained exactly one fault. Note that the attacker can distinguish between faulty and non-faulty (correct) signatures by verifying with the public exponent, but cannot distinguish a priori between faulty signatures that contain one fault as opposed to those that contain multiple faults. As explained below, the most computationally intensive part of recovering the private key is performing repeated searches over the pool of faulty signatures looking for a particular single fault pattern.

Guessing and Verifying Exponentiation Windows

The signature of a message M is computed as the exponentiation M^D mod N where D is the private RSA exponent, and N the corresponding modulus. Exponentiation is computationally intensive, and is achieved through repeated (modular) multiplication. The well-known binary method computes M^d mod N by processing D bit-by-bit from left-to-right (most significant to least significant bit) in a series of squarings and multiplications. The binary method can be improved upon by processing the exponent in groups of bits, say 4 bits at a time. This approach is called the m-ary method and the groups of exponent bits are called windows (the binary method can be thought of as the 1-ary method, processing 1-bit windows).

At each step in the signature computation, m squarings are performed followed by a single multiplication if the window is non-zero. The attack devised by the researchers works by recovering the bits in the most significant window, followed by the next most significant window, until the entire private key is recovered. If the current window targeted for recover is window W, then the attacker requires a faulty signature on M such that a single fault was induced during the processing of the exponent bits represented by W.

The researchers derive an equation that involves the message to be signed M, the faulty signature S, the value of the window W, the position of the fault, and the sign of the fault (add or subtract). By equation here we mean an expression that has a left-hand side and a right-hand side which can be compared for equality. The attacker can then plug all possible values of W, the position fault and fault sign into this equation and collects solutions. There will either be no solutions, one (unique) solution, or more than one (multiple) solution. In the first and last cases, no information about D can be extracted since either the fault did not occur during the multiplication for W, or there are multiple faults in S. and another pair (M, S) must be examined. If the solution is unique then the bits of W are determined and the attacker can move on to breaking the next window using the same guess-and-verify approach.

The search for a given pair (M, S) that has a single fault in a position covered by a specified window W is computationally intensive. If S is a faulty signature then the attacker cannot easily determine the number or position of the faults in the signature. The researchers generated 10,000 signatures, of which 8,800 were faulty, and tried to recover the 1024-bit exponent. Using an 81-processor cluster this took 104 hours, with the guess-and-verify step for each window taking 2.5 seconds. The private key was recovered after 650 single fault signatures processed.

Conclusion

The Register has headlined the announcement as breaking OpenSSL, but this unfair. OpenSSL was used in the experiments but other libraries are also likely to be vulnerable to restricting voltage to induce hardware faults. As to the practicality, the attacker is required to have physical access to the device housing the private key, and be able to request or observe 10,000 or so signatures, computed under reduced voltage. These seem to be quite generous circumstances for the attacker, and given such proximity the attacker may prefer to try for a Cold Boot Attack instead. In any case, the attack shows the importance of verifying the correctness of signing operations – all the faulty signatures could be detected by merely checking that M = S^E before returning any results. Apparently this is what OpenSSL developers are doing at the moment.

RSA-512 factoring service: two weeks effort for $5,000

Ron Kane is offering a service to factor 512 RSA keys for a cost of about $5,000, taking two weeks or so. He describes the service as

Estimation on calculating the private key is 2 weeks (we have 2 separate clusters running, sometimes its rented to another company) .

We will be calculating on our private cluster / super computer, no groups / companies / other individuals involved, your private key will not be exposed to the internet anywhere!

Your private key will be sold once, only to you. In case someone else asks us to factor the same numbers, we will decline the request.

How we work:

• You make a down payment
• We will start calculating the key
• When the private key is ready, we will sign something with it and send it to you to verify it
• You pay us the remaining sum we agreed
• We give you plain numbers, or we can embed the private key in a smartcard (multos or JCOP)

You can contact him here, but if you are a bit more patient you can do it yourself. Some recent sampling results showed that a few percent of web servers are still running 512-bit keys.

RSA is 30, and counting

This year is the 30th anniversary of the journal publication for the RSA cryptosystem:

R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120–126. 1978.

This is one of the most cited papers in all of computer science. The authors are pictured above around the time their RSA paper was published (Shamir, Rivest, Adleman - left to right). I learned about the mathematics of RSA in 1985 as part of a cryptography course based on Dorothy Denning's excellent introductory text Cryptography and Data Security. Over the years quite a few security professionals have confided in me that they do not really understand the basic mathematics of how RSA works. In this post I hope that I can tell the RSA story one more time, in a way that makes it easier to understand.

Background

Let E be a generic encryption operation, and let D be its corresponding decryption operation. For any message M, a basic property of any cryptosystem is that

M = D(E(M))

or in words, that decrypting an encrypted message yields the original message. We can then think of D(E( )) as a self-mapping, taking messages M to themselves under the action of some key. To explain RSA we are going to look at several well-known self-mapping functions from number theory, and then show how we can decompose these self-maps into two parts, which can be thought of as encryption and decryption.

All references below to numbers will mean non-negative integers: 0, 1, 2, 3 and so on. Number theory is mainly concerned with these numbers and their properties. Also, we will use the terms number and message interchangeably, since any message has a binary representation that can be interpreted as a number (see the standard PKCS #1 on a specific method for doing this).

Modular Exponentiation

Our source of self-mappings will be derived from modular exponentiation, the fundamental operation in many public key systems including RSA, DSA, Diffie-Hellman, and El Gamal systems.

We start with the simpler notion of exponentiation. Exponentiation is the operation of raising a base M to an exponent e, written as M^e, which simply means to multiply M by itself e times. When e = 2 exponentiation is called squaring, and called cubing when e = 3. For larger values of e we also describe M^e as "raising M to the e-th power".

There are two rules which can be used to simplify exponentiations, both of which are used in RSA: the product rule

M^(e*d) = (M^e)^d

and the sum rule

M^(e + d) = (M^e) * (M^d).

In modular exponentiation we are given an additional parameter m and we need to compute M^e mod m. For any value x , x mod m means to return the remainder of dividing x by m. So 17 mod 5 = 2 since 17 = 3*5 + 2, or in words, 5 goes into 17 three times with 2 left over (the remainder). Here m is called the modulus. So M^e mod m means to first compute M^e and then return the remainder upon dividing by m.

Flawed RSA v1

After that introduction, we need one simple result to take us forward, called Fermat's Little Theorem: let p be a prime and let M be any value in the range 0 < M < p, then

M^(p - 1) = 1 mod p

Since M^p = M^(p-1) * M by the exponentiation sum rule, and M^(p-1) = 1 mod p it then follows that

M^p = M mod p.

This is good news since we have now found a self-mapping function. Can we somehow decompose this self-map into two parts, one that we can call encryption and the other decryption?

Well imagine that Alice can find two values e and d such that e*d = p, and let Alice publish the pair (e, p) as her public exponent and her public modulus, respectively. If Bob wants to send her a message M she instructs him to encrypt it using the following modular exponentiation

C = M^e mod p

and Bob then sends C to Alice. When Alice receives C she recovers M by the following modular exponentiation

M = C^d mod p.

But why does this operation return M to Alice? Well its because

C^d = (M^e)^d = M^(e*d) = M^p = M.

Here we have used the exponentiation product rule: the exponentiation applied by Bob is itself exponentiated by Alice to return the original message.

But we have a snag. We said that Alice found e and d such that e*d = p, but since p is prime then the only possible solutions for e and d are 1 and p. But if e = 1 or e = p then the encryption operation M^e mod p applied by Bob has no effect on M since

M^1 = M^p = M mod p.

Encryption would be doing nothing.

But here is the key observation.

The property that permits Alice to recover M is not e*d = p but rather that

e*d = (p - 1) + 1 = 1*(p-1) + 1

and Alice can still recover M if e*d is equal to 2*(p-1) + 1, or 3*(p-1) + 1, or k*(p-1) + 1 for any k > 0. Why? Well using the product rule we have that

M^(k*(p-1)) = M^((p-1)*k) = (M^(p-1))^k = 1^k = 1 mod p,

and then using the sum rule

M^(k*(p-1) + 1) = M^(k*(p-1)) * M = M.

So we are back in business if we can find e and d such that e*d = k*(p-1) + 1, for some k > 0. But using modular arithmetic, this is the same as saying that

e*d = 1 mod (p - 1).

As it turns out there is something called the Euclidean algorithm which is a method for efficiently solving for x in modular equations of the form a*x = b mod m. So we can just pick a random value for e in the range 1 < e < p and then use the Euclidean algorithm to find the corresponding value of d for which e*d = 1 mod (p - 1).

Let's see an example of this. Let p = 61 and then select e as e = 17. Then we have that d = 53 since 17 * 53 = 1 mod 60, or more specifically, 17 * 53 = 15 * 60 + 1. So encryption would then be defined as C = M^17 mod 61 and decryption defined as M = C^53 mod 61. Here our messages would need to be less than 6 bits in length.

But now we have another snag - quite a serious one this time. When Alice publishes her public key (e, p), what distinguishes her from other people is her knowledge of her decryption key d. But since e*d = 1 mod (p - 1) then another person Carol can easily determine d by simply using the Euclidean algorithm to solve e*d = 1 mod (p - 1) since e and p - 1 can be directly derived from the public (e, p).

To fix this snag we need to change our tactics and move from a public modulus that is a prime p to a value n = p*q that is the product of two primes p and q.

Correct RSA v2

The importance of Fermat's Little Theorem in the last section is that it gave us a self-mapping modulo a prime p. There is a generalisation of this result for composite numbers known as Euler's Theorem: For any n let a be any value in the range 0 < a < n, that shares no factors with n then

a^phi(n) = 1 mod n

where phi(n) is the number of values in the range 1 to n that share no factors with n. Note here that for a prime p that phi(p) = p - 1 so that Euler's criterion includes the result of Fermat's Little Theorem.

If we let n = p*q for two primes p and q then it is easy to show that phi(n) = (p-1)*(q-1). Now we can repeat the construction in the previous section by replacing computations with p - 1 (derived from Fermat's Little Theorem) with computations based on phi(n). To this end we select a random e in the range 1 < e < phi(n) and use the Euclidean algorithm to solve for d such that

e*d = 1 mod phi(n) or e*d = 1 mod (p-1)(q-1).

Alice's public key becomes (e, n) and Bob can encrypt a message M for her as M^e mod p. Alice decrypts the message as M = C^d mod p which works because

C^d = (M^e)^d = M^(e*d) = M^(k*phi(n)+1 ) = 1^k * M = M mod n.

Let's illstrate these principles with the RSA example from Wikipedia. Let Alice choose as her two primes p = 61 and q = 53. Then n = 61 * 53 = 3233 and phi(n) = (61 - 1)*(53 - 1) = 3120. If Alice selects her public exponent to be e = 17 then d = 2753 since

17 * 2753 = 46801 = 15 * 3120 + 1.

So the public key of Alice is then (17, 3233) and anyone can encrypt a message for Alice by computing C = M^17 mod 3233. Alice recovers the message by computing M = C^2753 mod 3233.

By now you should be able to follow this T-shirt description of RSA.

Let's think about Carol again. Can she easily determine Alice's private key d from her public parameters (e, n)? Well if she could determine phi(n) from n then she could use the Euclidean algorithm to solve for d in the equation e*d = 1 mod phi(n). But as was shown in the original RSA paper, if Carol could derive phi(n) from n then this would be equivalent to Carol having the power to factor n, which is known to be a computationally hard problem.

We have a left out many technicalities in this description of RSA, and to implement RSA in practice you need to solve many other issues, such as how to find large primes. For RSA to be secure it must be the case that n is sufficiently large to defeat the best known factoring algorithms. Using current estimates p and q should be at least 500 bits in length, and often over 1000 bits for additional security. The construction for RSA as outlined above is totally general - you can pick the primes as small or large as you like - the math still all goes through. However, larger keys takes longer times to process.