Crypto from Tesco

You can now order the new Block Cipher Companion book from Tesco’s, just published this month. I have seen an earlier draft and the text is very detailed and comprehensive, as you would expect from authors of this caliber.

These aren’t the key management systems you are looking for

This is a nice presentation on enterprise key management issues from Anthony Stieber given at the 2nd IEEE (KMS 2010) Key Management Summit. The main message is that KMS is tricky and don’t roll your own. By the way if you are looking for examples of Powerpoint that breaks all the rules for good presentations, then you will find them here.

Also there is a very polished and informative presentation from Chris Kostick of E & Y on an enterprise key management maturity model, and below is a comprehensive diagram on the life-cycle management of keys.

Evidence that the McEliece Cryptosystem is resistant to Quantum Computing Attacks

A paper was posted on the preprint server Physics arXiv showing that the McEliece public key cryptosystem is resistant to efficient quantum algorithms based on the ideas of Shor’s algorithm, which famously yielded an efficient method for factoring integers. From the abstract

Quantum computers can break the RSA and El Gamal public-key cryptosystems, since they can factor integers and extract discrete logarithms. If we believe that quantum computers will someday become a reality, we would like to have post-quantum cryptosystems which can be implemented today with classical computers, but which will remain secure even in the presence of quantum attacks. In this article we show that the McEliece cryptosystem over rational Goppa codes resists precisely the attacks to which the RSA and El Gamal cryptosystems are vulnerable---namely, those based on generating and measuring coset states.

Shor’s algorithm is a general method for computing the period of certain functions, and it can be applied to computing the orders of elements modulo a composite number for example (see my post Quantum Computing: are you Shor? for some details). Shor’s algorithm is not directly applicable to the McEliece cryptosystem since it is based on a hard problem from coding theory, and is not obviously solvable by computing periods of functions. The new paper seems to demonstrate that no connection will be found.

However the authors caution that there may be another quantum approach distinct from the principles of Shor’s algorithm that efficiently breaks the McEliece cryptosystem. On the other hand, there is a growing consensus that NP-complete problems do not have efficient quantum algorithms (see the diagram in this post), and the McEliece cryptosystem is based on an NP-hard problem (which means it is at least as hard as an NP-complete problem).

There is also a nice background post on the physics arXiv blog.

Related articles by Zemanta

• 1978 Cryptosystem Resists Quantum Attack (science.slashdot.org)
• Thirty-Year-Old Encryption Formula Can Resist Quantum-Computing Attacks That Defeat All Common Codes [Encryption] (gizmodo.com)

Short cryptography lecture from Scott Aaronson

Here is a short cryptography lecture from Scott Aaronson, delivered as part of his Quantum Computing Since Democritus course given at the University of Waterloo, Fall 2006. The lecture gives a short text-based overview of crypto from mainly a complexity point of view, and discusses some of the implications of the “P = NP?” question for crypto.

Elliptic Curves in ASCII

There is a new Internet draft on Fundamental Elliptic Curve Cryptography Algorithms by D. McGrew of CISCO and K. Igoe of the NSA. The NSA author might seem out of character for that particular 3-letter agency, but it's no secret that elliptic curves are the NSA’s preferred form of public key system over RSA. It is somewhat impressive that the authors would even attempt to write up such a complex mathematical topic using the ASCII formatting that the Internet Society has insisted on for several decades now. ASCII used to be the lowest common denominator for formatting in the 70’s, but surely now it is HTML or PDF.

Be that as it may, the document is well written and builds up elliptic curves from the basics of modular arithmetic, groups, finite fields before defining elliptic groups. Of course not all types of curves are examined – the document would need to be much longer than 20 pages – but it is self-contained. The section on the security of elliptic curves is a quite short however. After developing the required terminology and background, the authors focus on defining a method for elliptic curve signatures based on the work of two Japanese researchers Koyama and Tsuruoka. This signature variant was probably chosen to avoid any intellectual property issues with more well-known methods that are heavily patented, particularly with respect to efficient implementations.

An interesting read as long as you can handle sustained Courier font. If you are looking for some more background on elliptic curves for security please take a look at Luther Martin’s posts at Voltage, and 4 are listed below ASCII girl

Related articles by Zemanta

• The j-invariant of an elliptic curve (superconductor.voltage.com)
• An example of bad reduction mod p (superconductor.voltage.com)
• Divisors on elliptic curves revisited (superconductor.voltage.com)
• Isomorphic elliptic curves (superconductor.voltage.com)

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)

The Re-Keying Conundrum

Eric Rescorla recently posted his view on including a re-keying function in security protocols, and he concluded that on cryptographic grounds re-keying is unnecessary. Re-keying here means refreshing or renegotiating a session key (say an AES key) after a certain amount of traffic has been encrypted under the same key, or a given amount of time has elapsed (say several weeks or months). Rescorla opens his post with the statement that “in my opinion, rekeying is massively overrated, but apparently I've never bothered to comprehensively address the usual arguments”. Re-keying is probably something of a preoccupation for Rescorla at the moment as he is reviewing several IETF proposals that include this functionality, and he is also fresh from completing a proposal for circumventing the well-publicised TLS Renegotiation Attack.

Regularly changing critical parameters  is part of the conventional wisdom of security, based on the general principle that reliance on a given security parameter must decrease over time with its use. Extended usage leaks more and more information to an attacker, and security parameters don’t improve with age. But need we be so cautious with the bulk encryption keys of a modern cipher like AES? Do long sessions or large encrypted transfers really give an attacker an advantage that outweighs the additional complexity of including a re-keying sub-protocol?

The Unicity Distance

Let’s begin with the observation that only a small amount of data needs to be encrypted under a given key before the key is uniquely determined. This threshold measure is called the unicity distance of a cipher, and for symmetric key ciphers it is proportional to the entropy of the key. So for example, DES and AES each only require a handful of encryptions to be produced for the corresponding key to be uniquely determined. Therefore, given just a few plaintext and ciphertext pairs an attacker has sufficient information in principle to mount a brute force attack. In the case of public key systems, the unicity distance is in fact zero since a certificate contains all the information required to determine the corresponding private key.

More General Attacks

One aspect of the re-keying issue is therefore to determine whether attacks more efficient than brute force become available as the amount of data encrypted under a given key is permitted to increase. A general upper bound is provided by the birthday paradox which, under the assumption that encryption acts as a random mapping, states that ciphertext blocks will start repeating for purely statistical reasons when the amount of encrypted data is approximately the square root of the number of possible ciphertexts. At this point the attacker gains advantages (not directly in key breaking), and a basic requirement of the new AES cipher was to have a block size of at least 128 bits. On the other hand,  linear and differential cryptanalysis are attacks that directly use large amounts of encrypted data to amplify small statistical biases in the structure of a cipher to determine certain key bits. In general there is no simple relation between the block size of a cipher and the data requirements of these attacks, since the number of rounds is also important. For DES, linear cryptanalysis was the more efficient of the two attacks, and it still required 2^{44} ciphertexts, amounting to about 280 terabytes of encrypted data. Even under more favourable circumstances, the data requirements for mounting this type of attack on AES-256 are considerably higher.

Rescorla quotes two IETF submissions where re-keying is justified on the grounds of limiting the time to perform cryptanalysis or the amount of ciphertext that a attacker can collect. While such precautions sound prudent, they make little sense with respect to AES with 128- or 256-bit keys since the corresponding key and ciphertext spaces are so vast. In short, any attacks based on counting, enumerating, or storing encrypted data are not expected to be feasible. The recent so-called Luxembourg Attacks on AES, and their variants, are very data intensive but limiting traffic encrypted under a given key to (say) 1 Petabyte would thwart these attacks.

But Expect Re-Keying

Even so, cryptographic arguments are most convincing to cryptographers, and cryptographic protocols are implemented within systems that are not engineered to the same level of security as say AES, and nor can they be. The manager responsible for approving the transfer of sensitive financial data across the internet will probably feel better knowing all possible precautions are taken to prevent data loss, and that will include re-keying. It is simply viewed as a prudent operational security practice no matter how convincing the cryptographic arguments are to the contrary. Perhaps the most convincing argument for re-keying – if not the only argument – is to limit the consequences of a key compromise. The manager mentioned above will probably be reassured to know that an accidentally exposed key only compromises 4 hours worth of transmitted data, and none of the data sent before or after that. Of course you need more than just re-keying to guarantee such a property, but no amount of strong cryptography will give it to you either. So we may agree with Eric that re-keying is overrated, but it is certainly rated.

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.

The USB Password Vulnerability

In early January Heise Security reported that a German security firm had discovered a vulnerability in the password authentication process of several USB sticks that are rated as being highly secure. The discovery has been widely reported, and led to various responses from USB vendors Sandisk, Verbatim and Kingston, including patching and recalling their devices from the field. The full list of effected sticks has been reported by Simon Hunt for example. Steve Ragan of the TechHerald has commented that the whole incident is “"quickly becoming the first FUD-based news cycle for 2010”.

What was the vulnerability?

Well when a user plugs in a password-protected USB stick their desktop starts the stick by launching a popup application prompting the user for their password. You would expect that the user supplied password is then transferred to the stick for verification, and the stick grants access if the password is correct.

What German security company SySS, discovered is that the password verification is actually performed in the popup application itself , and an acknowledgment code is sent back to the stick indicating if the candidate password is correct or not. By sniffing this traffic SySS determined that the acknowledgment code granting access is static, and in particular does not depend on the password entered by the user. Essentially the desktop popup verifies the user supplies password and then returns "yes" or "no" to the stick.

SySS captured the acknowledgment code, and then wrote  proof-of-concept exploit which injects the acknowledgement code into the memory space of the desktop popup so that the value returned to the stick is always the positive acknowledgement code. Thus regardless of what password the user enters the hack ensures that the stick will always grant access.

What was the impact?

Given the injection code, the password-protection can be defeated on sticks susceptible to the attack, which turns out to be a reasonably large class of commercial sticks that are marketed as being highly secure. All things being equal, the risk of a data breach from lost sticks is therefore increased, since the password-protection of the sticks can be bypassed with the right software. And losing sticks is increasing. CSO Online recently reported on a UK survey conducted by Credant which revealed that 4,500 memory sticks have been forgotten in people's pockets as they take their clothes to be washed at the local dry cleaners.

The impact is not limited to a single vendor product. The vulnerability exists in several families of secure USB devices across the major USB vendors because they all rely on a common USB chipset whose security properties have not been properly vetted.

FIPS Certification

The incident is all the more telling in that the vulnerability impacts devices that use AES 256-bit encryption and are rated as secure by the FIPS 140-2 certification process. Users are paying quite a premium over vanilla sticks for the advertised additional assurance that their data are protected by a certified device using strong cryptography, and for some US government agencies such purchases are mandatory. The relative ease with which the password protection was bypassed calls into question the value of the FIPS 140-2 process.

In Computerworld NIST is quoted as saying "From our initial analysis, it appears that the software authorizing decryption, rather than the cryptographic module certified by NIST, is the source of this vulnerability", and then also "Nevertheless, we are actively investigating whether any changes in the NIST certification process should be made in light of this issue”.

To be fair, the FIPS 140-2 focuses on verification of cryptographic modules and not the supporting software, however the incident highlights the narrowness of the approach and the expectation that certification is more than secure cryptography. Chris Merrit at Lumension has a good post on the fine print of the certification FIPS 140-2 process, and he concludes

So, bottom line: while this discovery seems to suggest an area to which NIST might want to bring some clarity and rigor, it does not mean that FIPS 140-2 is fatally flawed. It’s up to you, as the buyer, to understand what (potentially critical) functions occur inside & outside the cryptographic boundary, and how that might impact the security of the device in your case. And since what you’re looking for is what’s not certified, it might be useful to have an expert review the vendor security policy (posted with the certification on the NIST website) to help you understand the nuances.

AES-256 and Passwords

As I explained in Are AES 256-bit keys too Large? it is very unrealistic to equate password security with the security of AES-256. To achieve the equivalent of 256-bit security users would need to select 40 character passwords at random, and we are a long way from that. In fact so far away that we will never get there. So USB devices that protect their data using AES-256 encryption sound impressive, but when access control to those devices and the underlying keys is controlled by a password, then this setup sounds a lot less secure. The SySS vulnerability now shows that the whole AES-256 encryption process can be bypassed in the presence of weak password handling.

Conclusion?

Is there a useful conclusion from this incident? There is a lot of embarrassment all round and we have little confidence that a similar issue will not arise in the future. Security is just done poorly in general, and blatant examples are uncovered whenever someone takes the time to look under the hood. Some  articles and posts have focussed on verifying passwords in software as the culprit, which is partly true, but the real issue is not software but insecure programming of software - the password verification should never have been done on the desktop, and a static acknowledgement code should never have been used to unlock the USB device.

A trusted path should be established between the desktop keyboard and the USB device, and for smart cards this needs to be done with a secure reader. But this is at odds with the plug-and-play semantics of USB sticks where the portability of the ubiquitous USB connector is the selling point.

The Crypto Year in Review from Bart Preneel

Bart Preneel is a professor at the Katholieke Universiteit Leuven, in Brussels, and leader of COSIC, one of the largest security and cryptography research groups in Europe. This is the research group that produced Rijndael, which eventually became the AES. Preneel is a frequent speaker on security and cryptography, and in this post we will review a recent presentation on the topic of the Crypto Year in Review.

Preneel begins by observing that cryptographic research is alive and well, with over 600 papers published on the pre-print server of the IACR, amounting to over 10,000 pages of written research. Not all of these papers will be published, but it does give you some idea of the reading load to keep abreast of new ideas and developments.

His attention then turns to AES, which still remains secure despite the publication of several theoretical attacks. AES now runs at 110 MB/seconds in software, and Intel has announced direct hardware support beginning with its Westmere line of chips. Referring to the security of AES-256, Preneel states that for $5 billion USD, a key cracking device could be built to search a 120-bit key space that would take a billion years. This was about the same work required by the so-called Luxembourg Attack announced in June, which was the first attack against full AES-256 that saved significant time over exhaustive search (though a large amount of ciphertext is required).

Preneel calls this an academic weakness, since it relies on a related key attack which is hard to arrange in practice and can be easily avoided by making the AES key schedule more non-linear. The slide below shows that relationship between AES key size and the number of rounds. There are several feasible attacks when the number of rounds is 10 or less with small key sizes. The 2^{119} effort of the Luxembourg Attack is located far above what is considered practical.

Preneel then considers hash functions, the topic of his PhD thesis. He gives a benchmark slide showing the complexity of collision attacks against well-known hash functions, assuming a $100K USD funded adversary using special hardware (equivalent to 4 million PCs).

The downward trend of the graphs is suggestive of a meltdown for hash functions, with the worst implications for protocols and signatures yet to play out. The transition path to a better hashing standard via the SHA-3 hash contest of NIST in underway, and a new standard by will be selected by 2012. However Preneel is concerned that the design of SHA-3 will be based on state-of-the-art from 2008 – that is, all of the additional insights and learnings produced in the evaluation of the SHA-3 candidates will not be exploited until SHA-4.

It was a relatively quite year for public key cryptography, with no factoring records announced, but a lot of fretting over the coming upgrade of RSA-1024 keys in 2010 in compliance with US standards. Elliptic curves are rising in importance due to support from the NSA, and quantum computers remain a very long term threat to the security of public key systems.

There are some additional topics considered by Preneel, mainly around protocols and deploying cryptography. His summary is that 2009 was a relatively unexciting year on the surface but you may find interesting details when you look closer. Also, always remember that cryptography is a building block for information security, an essential block but far from the whole story.