My latest Math Review on Quantum Keys

Click MR2921421 to download my review of Skobelev’s article On the Computational Security of Quantum Algorithms. Hint: Eve wins if she can control the classical channel and have good stats on the pseudo-random number generator.

2011 at its Prime

The fact that 2011 is a prime number didn’t escape the mathematical inclined minds. Moreover, as tweeted @mathematicsprof 2011 can be expressed as the sum of the 11 consecutive primes 157+163+167+173+179+181+191+193+197+199+211.

This already sets the stage for a year that, I will dare to predict, will not be easily forgotten. A confluence of processes already in motion may result in drastic changes for the world and in particular the Internet. To wit:

  • Cyber-attacks can get ‘physical’ as the stuxnet virus proved,
  • There is a struggle to control the internet at all levels,
  • Privacy and mobile computers have compatiblility issues,
  • All this against the backdrop of economical and political turmoil.

 

As the Chinese say “May you live in interesting times” ….

 

The book gets excellent review at Amazon.com

A very nice surprise from the comment pages at Amazon.com, a 5 star rating for the Cryptography book authored by A. Bruen and myself.

The reviewer consider the book a Insightful Interdisciplinary Orientation on the subject, and gave this book the highest rating among similar books.

Thanks.

 

Bonus:

We are in good company too!

image

Power-up of a SRAM as a source of Entropy and Identification

Many years ago I was involved in a research project looking to use tiny differences in processing time inside a computer as a way to fingerprint the device. The idea was not unique, I guess that at the same time many were busy looking for similar things.

The reason was that in the framework of Internet security protocols such as SSL, if each party can fingerprint the other party’s computer, that will add another dimension to the development of a strong authentication scheme. Eventually the company supporting the research run out of interest and money and I forgot all about the idea until I recently read the news.

Enter the Fingerprint Extraction and Random Numers in SRAM (FERNS) method developed by Holcomb,  Burleson and Fu of the University of California Berkeley. They analyzed the initial state of the cells of a 512 kb Static Random Access Memory (SRAM) after power up and discovered that the stable states of some cells representing the bits were random, that is they have equal probability to be 1 or 0, while others cells were skewed to start as a 1 or as a 0. This property of the cells is due to imperfections of the fabrication process and are impossible to control.

A paper describing Burleson’s group work is going to appears in the IEEE Transactions on Computers.

From the Abstract
…..  We use experimental data from high performance SRAM, and the WISP UHF RFID tag to validate the principles behind FERNS. We demonstrate that 8 byte fingerprints from an SRAM chip are sufficient for uniquely identifying circuits among a population of 5,120 and extrapolate that 16 to 24 bytes of SRAM would be sufficient for uniquely identifying every instance of the SRAM ever produced. Using a smaller population, we demonstrate similar identifying ability from the embedded SRAM microcontroller memory of the WISP. In addition to identification, we show that SRAM fingerprints capture noise, enabling true random number generation. We demonstrate that the initial states of a 256 byte SRAM can produce 128 bit true random numbers capable of passing the NIST approximate entropy test.

The possibilities for the application of this technology to authentication and key generation schemes are enormous, specially in the field of portable devices. To have an entropy generator “in a chip” is great, if you get that together with a fingerprint of the chip is wonderful news. Certainly we’ll hear more about it.

 

Related reading: Quirks of RFID Memory Make for Cheap Security Scheme

 

ENIGMA encryption cracker Heroes

ENIGMA crackers reunite at Bletchley Park

I had the honour to meet one of them, now an emeritus math professor.

Check this article for pictures of the Turing Bombe the electronic-mechanical code-breaking machine used by the British to crack 3,000 Enigma messages a day during the Second World War.

Cryptool ver 1.4 has a very well done simulator of the ENIGMA machine encryption.

 

 

Collisions, a secure hash function killer (MD5, SHA1, SHA2)

The trouble with the use of MD5 in digital signatures recently uncovered by Sotirov et al. is common to other hash functions.

NIST has been discouraging people to use MD5 and even SHA 1 since many years ago. A good account of this was posted by Dustin Trammell here.

Because the output of a hash function is of a fixed length, usually smaller that the input, there will necessarily be collisions. The collision-free property for hash is thus defined by:

A function H that maps an arbitrary length message M to a fixed length message digest MD is a collision-free hash function if:

1. It is a one-way hash function.

2. It is hard to find two distinct messages (M', M) that hash to the same result H(M')=H(M).

Cryptographers talk about “relatively collision free” hash functions. A good hash function should be designed with the Avalanche Criterion in mind.

The Avalanche Criterion (AC) is used in the analysis of S-boxes or substitution boxes. S-boxes take a string as input and produce an encoded string as output.

The avalanche criterion requires that if any one bit of the input to an S-box is changed, about half of the bits that are output by the S-box should change their values. Therefore, even if collisions are unavoidable, there is no way to generate two strings with the same hash value other than brute force.

 

The end of the road for MD5 signed SSL Certificates

X.509 certificates signed by Certificate Authorities that use MD5 function are certainly going to disappear form the Internet as flaws on the MD5 were successfully exploited to generate a rogue certificate that would be considered as valid by all browsers.

The proof of concept was recently published by A. Sotirov et al. , although the basis for the hack has been know for a few years know. The researchers exploited collisions (two different strings that hash to the same value) in the MD5 and the fact that CAs use a sequential numbering of certificates upon issuance.

News that SSL is broken are exaggerated as many CA are already using SHA-1 (a stronger hash function) and the ones that were using MD5 are switching quickly after publication of the flaw.  

See also:

Another review for the AMS

Here is my review of an article on a new zero knowledge identification protocol.

The “Evolution” of Security

The great mathematician Stanislaw Ulam once said that the question was not what mathematics can do for biology, but what biology can do for mathematics.
Reading an article about Digital Evolution[1], I become curious about up to what point the link between evolutive computer software and the field of computer security has progressed. It seems obvious to think in terms of biological concepts such as immune systems and mutating entities when you think about viruses, troyans and other current and future threats to security.
It looks like there is a wealth of research already conducted on such connection. A good starting point is the work of Prof. Forrest[2] from the University of New Mexico. There seems to be also some attempts at using genetic algorithms for intruder detection such as [3].
Without doubt this is a promising area. The traditional approach of trying to guess and hard code against external attackers is not going to work as the complexity of systems and applications grows, seemingly unbound.
I am planning to start doing more research about this, as this touches many fields in which I have worked in the past. Any insight or advice is going to be welcome and greatly appreciated!

[1] Harnessing Digital Evolution, P. McKinley, B. Cheng, C. Ofria, D. Knoester, B. Beckmann and H. Goldstein, Computer Jan 2008.

[2] Principles of a Computer Immune System A. Somayaji, S. Hofmeyr, & S. Forrest

[3] Using Genetic Algorithm for Network Intrusion Detection, W. Li

AMS – Mathematical Reviews

I was invited by the AMS to write reviews for the Mathematical Review Database, invitation that I proudly accepted. As the copyright agreement allows the reviewers to post the reviews on a website, I will be posting the relevant ones in this blog. When possible I will also explain the relevant points of the articles being reviewed.