Tuesday, May 17, 2005 - Posts
It would appear that there has been a successful side-channel attack on AES.
For the uninitiated, let's dissect this:
AES (Advanced Encryption Standard) is the government standard for symmetric ciphers. The AES cipher chosen by the government is Rijndael. It is called AES as a successor to the the popular, and for many years useful cipher, DES. A symmetric cipher is a device, usually an algorithm, that hides information by running that information through the algorithm. The information before it is given to the algorithm is called plaintext. After the algorithm is applied, the plaintext becomes ciphertext. The information is considered encrypted (or sometimes referred to as encoded) and may be freely transported to a destination. Upon arrival at the destination, the algorithm is applied once again and the ciphertext is converted back into plaintext. The cipher is considered symmetric because the same algorithm may be applied for both transformations, i.e. from plaintext to ciphertext and from ciphertext to plaintext and because the same key is used for each operation. An important note about the key is that it is the information which actually protects the plaintext. Both the sender and the receiver of the information must have access to the same key for this process to work. The key is private, the algorithm is public (this principle, referred to as Kerckhoff's principle, from Kerckhoff's desiderata, I promise to write on this at another time). The combination of these things provide for protection of the data. The algorithm is considered one-way hard if it can be shown that the search space for key discovery over the algorithm cannot be reduced significantly by means other than a reduction in key size.
Wow, crypto in a paragraph. There is a lot more than I've described here on the subject. Let's continue now with the side-channel attack.
A side-channel attack is an attack that observes the information about a cryptographic algorithm, in this case an instance of the AES running in OpenSSL, in an implementation. There are many forms of side-channel attacks. The side-channel attack in this instance was a timing attack. The attack sent known information into the OpenSSL software and observed the different events and corresponding elapsed time for the execution of the encryption algorithm. From this information, the attacker could reconstruct information from the implementation, in this case, the fully recovered key. There are many reasons why this attack is significant. Most notably is the fact that the algorithm from above, the one-way hard problem, was not even considered in the attack. It's as if the attacker came to the front door of a house (in this case, a big steel door with lots of deadbolts), found it locked, but discovered that the walls were thin and provided reasonable means of entry. The attacker could acquire entry through the other means just by this one observation.
As I'm not an analyst for this discipline in any significant measure, I'll leave the consequences of this discovery to others. As I find further useful infomation, I'll let you know.
Cryptology and Security Resources:
If you've never been here before, this guy is the "R" in RSA. Professor Rivest is considered one of the premier cryptology theorists in the world. He's also in the Theory of Computation Group at MIT (TOC is one of the disciplines that I LOVE). I have the book "Introduction to Algorithms" that was co-written by Professor Rivest. Its a first edition, so I plan on getting the second edition in the near future.
I've been reading schneier for a while (longer than I care to admit). If you haven't been to his site and blog, I'd recommend it. Mr. Schneier takes a practical approach to matters of security in many disciplines. While he may have detractors (and who doesn't), I for one find his commentary useful and on point. As a practitioner of cryptanalysis (only in the lab and the math theory part mostly), I really enjoy his "doghouse" entries about firms that purport to sell crypto, but instead have garbage.
I have a few of his books. For the beginner in cryptology, "Applied Cryptography" is a good read. While the material is technical and now a bit dated, it provides a platform for the beginner. What is first-rate about this book is that Mr. Schneier actually gives the reader a perspective. You must adopt the mindset of a professional cryptographer or cryptanalyst. I also have "Secrets and Lies". This again is an example of where Mr. Schneier makes the case for security in practical terms. It's a good read for the layman and for the security professional. I've learned a great deal and have shortened the cost to learn this discipline in part from my readings of Mr. Schneier.
For the uninitiated, these three terms have succinct meanings. Let's start with practical definitions:
Cryptology - The study of the hiding information of and the discovery of hidden information. Any activity that allows for the hiding of information (not just in computer or written form) or that allows for the discovery of this hidden information is cryptology.
Cryptography - The study and the practice of hiding information.
Cryptanalysis - The study of the discovery of hidden information.
Cryptography and cryptanalysis are subsets of cryptology. A cryptographer practices cryptography and is in the cryptology profession. A cryptanalyst practices the discovery of hidden information and also is in the cryptology profession.
A cryptographer is someone who is charged with making certain that information is hidden for the practical duration (or horizon) of its value and hardened from discovery by unknown adversaries.
A cryptanalysis is someone who is charged with discovering hidden information (i.e. hidden by cryptographers).
Cryptographers and cryptanalysts are adversaries. The degree to which they may protect or discover is called determination.
A determined adversary commonly refers to the cryptanalyst who has the means, usually in computing resources and knowledge, to discover hidden information before its practical duration is met.
Let's take an example:
Let's say that I'm a government agency that works on some special projects in the defense of the USA. If the XYZ project has useful value in the battlefield, say a special protective device for soldiers, the value of this information must be estimated by an analyst. Let's assume that the analyst believes that the useful life of this device in the field provides an advantage for 20 years. During the research phase for this device, communications and documents are generated that describe what the device is, how it works, and other intellectual property. This information must be protected for at least 20 years. Furthermore, even after the device is no longer effective in the field, the knowledge about the device, the knowledge about the research on the device or the knowledge of projects related to the device may have longer value, or may require further protection. So another analyst may find that this adjunct information will give visibility into useful information for an adversary and provide an additional estimated 15 years of protection for the information.
At this point, the cryptographer or an analyst must construct a threat model. This threat model must include a number of things. It must first estimate an expiration date for the information. That has been provided by the analysts at 35 years (20 + 15 years from above). Next the cryptographer must estimate what current adversaries exist, what methods of discovery are available and what means (usually computational power) that they have available to discover the information. The cryptographer must then look into the future and determine what possible methods and means might become available. After doing a lot of estimating on these matters, the cryptographer will decide on the algorithm and typically attributes of the algorithm (key size, methods of the algorithm, etc.) to protect the information. The algorithm is applied and the information is protected.
While this is a layman's view of this discipline, there is significant information on this subject in the public domain. What I have described above occurs regularly for many activities in the government. Many standards are set by NIST and advice is given by the NSA (very rarely for a number of reasons) that streamline this process and provide for management of information as part of comman daily practices.
The previous post on RSA-200 is a measure of the means of a determined adversary.
The slang crypto, commonly refers to cryptography, but is not always definite for this aspect.
Summary: Rated 8 out of 10 possible points. Excellent exposition on "the" experimental approach to mathematics. The practice of mathematics and the acquisition of mathematical solutions has been the domain of the academic thinker. This book proposes that experimentation should be considered as a valid research approach.
This book, "Mathematics by Experiment", is the first of a series by Dr. David H Bailey and Dr. Jonathan Borwein. As I lay in agony in the fetal position in the corner of my basement, I find myself reaching in the darkness for something to dull the pain in my head, hoping for some relief from the forced expansion of the scope of understanding that this book has forced onto my brain (ok, I admit this is dramatic). This book truly requires a great deal of focus and concentration (especially for amateurs like me).
While there is an uprising in the Mathematics community over the use of experimental methods in the acquisition of solutions (and I suppose the knowledge of the solutions) to difficult problems, the authors embrace this ideology. As an amateur practitioner of AI, I find myself agreeing with many of the principles and mandates set forth in this book. Mathematics is not just the domain of deep thinkers, but for those who choose to experiment. With the advent of significant improvements in computational horsepower, the experimental approach in the discovery of mathematical truths can be assisted by means other than those in the human mind.
For those unaware, David H. Bailey along with Peter Borwein and Simon Plouffe, provided (and published in 1997) a means to determine the nth digit of pi independent of any previous digits of pi. The significance of this work is many-fold. The approach used was experimental mathematics; the result of the work was simple and elegant.
This book is a fantastic piece of work. As I own the next book in the series, "Experimentation in Mathematics: Computational Paths to Discovery", I look forward to the work of these authors with their new co-author Roland Girgensohn. Stay tuned for a review here after I find my way up the basement steps.
Currently, The Scalper is reading the following:
- Aspects on the Theory of Syntax - Chomsky, Noam
- Experimentation in Mathematics: Computational Paths to Discovery - Borwein, Bailey and Girgensohn
- Advances in Genetic Programming Volume 2 - Angeline and Kinnear (eds.) (re-reading chapters 2, 5, 6, 13, 19, 20 and 24).
- On Linear Genetic Programming – Markus Brameier (dissertation from February 2004). Note: Brameier and researchers Banzhaf, Nordin and Francone appear to be the only significant publishers of imperative GP.
- Various works of Tony Hoare found on the Microsoft research site.
My areas of focus for the next three months are:
- Lambda Calculus, intermediate level work with interests in lambda reductions.
- Hoare Calculus, intermediate level work. I have not found a significant body of work on this topic and could use some direction from competent sources.
- Grammar, prescriptive, declarative, generative. I'm interested in furthering GP models for grammar discovery.
Please drop me a line if you have further suggestions on materials that may be useful in these categories.
JJBR researchers Boris, ivan and bigH all are up. Most of the research at JJBR is NONPUBLIC, but these guys should talk a bit in PUBLIC about some of the stuff that we address daily. I've got other team members that don't want exposure, so we'll refer to them as the termites and try to coax them out into the open eventually.
FYI, Boris hangs out in Crypto theoryland usually in the midst of extremely loud music (good thing you don't live in town). Ivan's the disorganization specialist. Ivan's work in GP goes hand in hand with mine. Add entropy, mix and model. More degrees, more dimensions, etc. bigH is one of the LINGO boys. He fancies Foundation Ontology, where I constantly remind him to skip that silliness and move to real ontology in natural language synthesis and computer science. (Look ma, no physicists on the team).
The group is .Net everything, everywhere. Why mess with anything else?
I'm guessing the JJBR guys will be shy for a while (yeah right).
BTW, Ivan and I are KPS guys, bigH and Boris are CPS guys. One JJBR requirement is that you must take a stance on the KPS/CPS controversy. Rodentuals are taboo.
Copyright (c), JJB Research. All Rights Reserved.