Re: [Cfrg] HMAC-MD5
I agree with Steven´s I'd rather avoid HMAC-MD5, just as a matter of future-proofing. And more. In am nearly sure that a preimage attack (MD5) will be found in the next two or three years. Vlastimil Klima http:/cryptography.hyperlink.cz - PŮVODNÍ ZPRÁVA - Od: Steven M. Bellovin [EMAIL PROTECTED] Komu: Russ Housley [EMAIL PROTECTED] Předmět: Re: [Cfrg] HMAC-MD5 Datum: 29.3.2006 - 1:11:25 On Tue, 28 Mar 2006 16:20:59 -0500, Russ Housley [EMAIL PROTECTED] wrote: At the SAAG session last week, Sam and I were asked about HMAC-MD5. Is it safe to keep using it? Should we encourage people to use HMAC-SHA1 or HMAC-SHA256 instead? Why? Please provide advice on this matter in the next two weeks. We have on working group that needs this advice very soon. There are no risks from HMAC-MD5 from collision attacks. Hash function design has suddenly become a very hot topic, though. Collision- finding attacks on MD5 have gotten a lot faster, and people are starting to look very hard at the basic design. I personally will not be surprised if a preimage attack is found in the next two or three years, in which case all bets are off. (I've made this statement before; others have disagreed with me on the likelihood of collision attacks.) I'd rather avoid HMAC-MD5, just as a matter of future-proofing. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb ___ Cfrg mailing list [EMAIL PROTECTED] https://www1.ietf.org/mailman/listinfo/cfrg - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
[EMAIL PROTECTED]: Fwd: Re: Any idea of who could help? Thanks!]
From: Tommy Poggio [EMAIL PROTECTED] Subject: Fwd: Re: Any idea of who could help? Thanks! Date: Tue, 28 Mar 2006 16:42:53 -0500 This is a question from a Globe reporter...anybody with useful pointers to relevant experts/people? thanks! t 03/27/2006 04:23:13 PM Dear Tommy -- I am wondering if you know anyone who might be able to help me with this? I wrote a while ago about a fascinating project focussed on deciphering the Incan khipu (see below). The basic idea is that they are collections of knots used in the Incan empire to record information. It is known that some of them contain numbers, perhaps recording census data or tax information for the empire. But some believe that the knots records language -- perhaps histories or other narratives. Cracking this code would be hugely important, not to mention interesting, because it would open up the still very mysterious Incan empire the same way that ancient Egypt has been opened up. All this is a rather long-winded prelude to my question, which is whether there are people out there who are working on computational techniques to decipher ancient scripts, not necessarily the khipu problem. I am thinking of doing a story on this. Any thoughts or leads at all would be most appreciated. It would even be a help to talk to someone who has done cryptography who could explain how the ancient scripts problem would be similar to, and different from, the problem of cracking a present-day encryption scheme. Let me know if you have any thoughts. Best, Gareth SCHOLAR SEES STRANDS OF ANCIENT SECRETS Author: By Gareth Cook, Globe Staff Date: 07/04/2003 Page: A1 Section: National/Foreign CAMBRIDGE - For centuries, the mighty Incan empire has confounded researchers. The Incas controlled territory up and down the spine of South America, with a sophisticated system of tributes and distribution that kept millions fed through the seasons. They built irrigation systems and stone temples in the clouds. And yet they had no writing. For scholars, this has been like trying to imagine how the Romans could have administered their vast empire without written Latin. Now, after more than a decade of fieldwork and research, a professor at Harvard University believes he has uncovered a language of binary code recorded in knotted strings - a writing system unlike virtually any other. The strings are found on khipus, ancient Incan objects that look something like mops. About 600 khipus (also spelled quipu) survive in museums and private collections, and archeologists have long known that the elaborately knotted strings of some khipus recorded numbers like an abacus. Harvard's Gary Urton said the khipus contain a wealth of overlooked information hidden in their construction details, like the way the knots are tied - and that these could be the building blocks of a lost writing system which records the history, myths, and poetry of the Incas. The theory has Incan scholars abuzz. The discovery of true Incan writing would revolutionize their field the same way that deciphering the Egyptian hieroglyphics or Mayan glyphs lifted a veil from those civilizations. But it also has broader interest because the khipus could constitute what is, to Western eyes, a very unorthodox writing system, using knots and strings in three dimensions instead of markings on a flat expanse of paper, clay, or stone. What makes this work so interesting is that what is being expressed is being conceptualized in such a different way than we conceptualize, said Sabine MacCormack, a historian of the Romans and the Incas who is a professor at the University of Notre Dame. This is about an expression of the human mind, the likes of which we don't have elsewhere. The only way to prove Urton's theory correct would be to translate the khipus, which no one has yet done. In his new book, he proposes a new method for transcribing the knotted strings which he believes could lead to breakthroughs. And his work, funded in part by a genius grant from the MacArthur Foundation, has helped fuel a resurgence of scholarly interest in khipus. Later this month, the Chilean Museum of Pre-Columbian Art in Santiago is opening the world's first exhibit dedicated to the khipu. We are on the cusp of a very hot period, said Frank Salomon, a professor of anthropology at the University of Wisconsin who has studied khipus extensively. The khipu mystery dates to the early 16th century, when the Incas were conquered by Francisco Pizarro and the Spanish set about destroying their culture. The missionaries sent to South America tried to eliminate all touches of the old gods, including the strange stringed textiles that the Incas said held their histories. The Spanish chroniclers often exaggerated, but they did record histories of
Enigma for sale on EBay
http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItemitem=6265092168ruhttp%3A%2F%2Fsearch.ebay.com%3A80%2Fsearch%2Fsearch.dll%3Ffrom%3DR40%26satitle%3D6265092168%26fvi%3D1 http://www.theregister.co.uk/2006/03/29/enigma_for_sale/ --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Cfrg] HMAC-MD5
On Wed, Mar 29, 2006 at 10:51:08AM +0200, [EMAIL PROTECTED] wrote: In am nearly sure that a preimage attack (MD5) will be found in the next two or three years. Is there already evidence of progress in that direction? -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Deciphering Incan khipu
Boston Globe reporter Gareth Cook [EMAIL PROTECTED] was awarded the 2005 Pulitzer Prize for Explanatory Journalism for explaining, with clarity and humanity, the complex scientific and ethical dimensions of stem cell research. He's an unusually talented writer. _Vin R. Hirschfeld [EMAIL PROTECTED] quoted Gareth Cook, who wrote: snip I am wondering if you know anyone who might be able to help me with this I wrote a while ago about a fascinating project focused on deciphering the Incan khipu (see below). The basic idea is that they are collections of knots used in the Incan empire to record information. It is known that some of them contain numbers, perhaps recording census data or tax information for the empire. But some believe that the knots records language -- perhaps histories or other narratives. Cracking this code would be hugely important, not to mention interesting, because it would open up the still very mysterious Incan empire the same way that ancient Egypt has been opened up. All this is a rather long-winded prelude to my question, which is whether there are people out there who are working on computational techniques to decipher ancient scripts, not necessarily the khipu problem. I am thinking of doing a story on this. Any thoughts or leads at all would be most appreciated. It would even be a help to talk to someone who has done cryptography who could explain how the ancient scripts problem would be similar to, and different from, the problem of cracking a present-day encryption scheme. Let me know if you have any thoughts. Best, Gareth SCHOLAR SEES STRANDS OF ANCIENT SECRETS Author: By Gareth Cook, Boston Globe Date: 07/04/2003 CAMBRIDGE - For centuries, the mighty Incan empire has confounded researchers. The Incas controlled territory up and down the spine of South America, with a sophisticated system of tributes and distribution that kept millions fed through the seasons. They built irrigation systems and stone temples in the clouds. And yet they had no writing. For scholars, this has been like trying to imagine how the Romans could have administered their vast empire without written Latin. Now, after more than a decade of fieldwork and research, a professor at Harvard University believes he has uncovered a language of binary code recorded in knotted strings - a writing system unlike virtually any other. The strings are found on khipus, ancient Incan objects that look something like mops. About 600 khipus (also spelled quipu) survive in museums and private collections, and archeologists have long known that the elaborately knotted strings of some khipus recorded numbers like an abacus. Harvard's Gary Urton said the khipus contain a wealth of overlooked information hidden in their construction details, like the way the knots are tied - and that these could be the building blocks of a lost writing system which records the history, myths, and poetry of the Incas. The theory has Incan scholars abuzz. The discovery of true Incan writing would revolutionize their field the same way that deciphering the Egyptian hieroglyphics or Mayan glyphs lifted a veil from those civilizations. But it also has broader interest because the khipus could constitute what is, to Western eyes, a very unorthodox writing system, using knots and strings in three dimensions instead of markings on a flat expanse of paper, clay, or stone. What makes this work so interesting is that what is being expressed is being conceptualized in such a different way than we conceptualize, said Sabine MacCormack, a historian of the Romans and the Incas who is a professor at the University of Notre Dame. This is about an expression of the human mind, the likes of which we don't have elsewhere. The only way to prove Urton's theory correct would be to translate the khipus, which no one has yet done. In his new book, he proposes a new method for transcribing the knotted strings which he believes could lead to breakthroughs. And his work, funded in part by a genius grant from the MacArthur Foundation, has helped fuel a resurgence of scholarly interest in khipus. Later this month, the Chilean Museum of Pre-Columbian Art in Santiago is opening the world's first exhibit dedicated to the khipu. We are on the cusp of a very hot period, said Frank Salomon, a professor of anthropology at the University of Wisconsin who has studied khipus extensively. The khipu mystery dates to the early 16th century, when the Incas were conquered by Francisco Pizarro and the Spanish set about destroying their culture. The missionaries sent to South America tried to eliminate all touches of the old gods, including the strange stringed textiles that the Incas said held their histories. The Spanish chroniclers often exaggerated, but they did record histories of tributes and other stories they said were read to them
Re: [Cfrg] HMAC-MD5
A couple of (rather uninformed) thoughts regarding HMAC-MD5: First, how could collision attacks be extended to preimage attacks? And second, how would preimage attacks affect HMAC-MD5? For a preimage attack, consider the simplest case, a single input block of 64 bytes. Then Hash = IV + Compress(IV,Input). We can try to run this backwards: Decompress(Hash-IV,Input). We need to choose Input such that the result of this backwards run equals IV, the fixed magic number that MD5 starts with. This is the hard part. One idea is to split the compression function into two halves: Compress1 and Compress2, such that Compress() = Compress2(Compress1()). Then Decompress, which is backwards, is Decompress1(Decompress2()). We could aim for a meet-in-the-middle attack, where we would run Compress1(IV,Input) and Decompress2(Hash-IV,Input) and try to get them to match. Then this value of Input would be a preimage of the desired Hash. The problem is that Input affects both Compress1 and Decompress2 in complicated ways. The solution would perhaps be to aim to find a family of Input values which caused only moderate changes to the outputs of Compress1 and Decompress2. This is similar to what happens now with the hash collision attacks. They find pairs of Inputs that have almost no change through the various sub-parts of the compression functions. If this could be extended so that there were not just a pair of Inputs, but larger numbers of them that produced almost-collisions after halfway through the compression function, then this could be a direction towards making this MITM work. At the most extreme case, if we could find 2^64 inputs which all collided through half the compression and half the decompression functions, then we'd have success, we'd have a preimage in 2^64 work. In practice we would not reach this extreme perfection, but perhaps we could approximate it enough that with much more work and good ideas, a preimage could still be found with substantially less than 2^128 work. As for the other question, the impact of preimages on HMAC-MD5: The goal of breaking a MAC is, given a bunch of known or chosen MAC'd inputs, but not knowing the MAC key, generate a valid MAC on a new input. Using preimages we would aim to generate an input which matched an output value we chose. The structure of HMAC is to hash one block (64 bytes) of the secret key xored a fixed repeated pad value, then the block(s) of the message. We take the output of that hash and do it again, hashing one block of the secret key xor a (different) fixed pad, then the output of the first hash. This is the HMAC. To reverse this, we would first need to invert the outer (second) hash. The tricky part here is that the input block (after the key) has a special form, consisting of the hash from the first step, padded per the MD5 spec. This padding will force fixed values (mostly zeros) into most of the input block and only give us 16 bytes to manipulate. So probably we would just fix the value from the input hash, fix the IV that results from hashing the outer key block, and find the output from this second block as the MAC value we will show an input for. Then we will turn our attention to the first block, which is key xor pad. We have its output value (the fixed intermediate IV we just chose) and so we would apply the inversion algorithm to find the input. This can be xored with the pad to get the key. Note that this is not the user's key, this is just a key that works for the outer hash. Now we do the inner hash. We use the key we found, xor with the appropriate fixed pad value, and hash to do the first block of the inner MD5. This gives us the IV for the second block, and we have the output for that block - it is the fixed value we chose above. We apply the inversion function again to get an Input value that works. Now we have succeeded: this Input value, along with the key we found in the first step, will produce the MAC we also found in the first step. It is not a MAC we have seen before so we have an official break. Therefore the ability to invert single blocks of MD5 will likely lead to an effective break of HMAC-MD5. Whether the current attacks against MD5 can be advanced to that point remains to be seen. If it works it will certainly be one of the premier cryptographic accomplishments of recent years. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Your secrets are safe with quasar encryption
http://www.newscientisttech.com/article.ns?id=dn8913print=true Your secrets are safe with quasar encryption * 16:00 29 March 2006 * NewScientist.com news service * Will Knight Intergalactic radio signals from quasars could emerge as an exotic but effective new tool for securing terrestrial communications against eavesdropping. Japanese scientists have come up with a method for encrypting messages using the distant astronomical objects, which emit radio waves and are thought to be powered by black holes. Ken Umeno and colleagues at the National Institute of Information and Communications Technology in Tokyo propose using the powerful radio signals emitted by quasars to lock and unlock digital communications in a secure fashion. The researchers believe quasars could make an ideal cryptographic tool because the strength and frequency of the radio pulses they emit is impossible to predict. Quasar-based cryptography is based on a physical fact that such a space signal is random and has a very broad frequency spectrum, Umeno told New Scientist. One-time pad Randomness provides a simple means of high-security information encryption, providing two communicating parties have access to the same source of random information. For example, a randomly generated one-time pad shared by two parties can be used to encrypt and decrypt a message by simply transposing each individual bit of a message for bits on the pad. Genuine randomness is hard to generate artificially and the “pseudo-randomness” which most computers use is unsuitable for use in cryptography as patterns will be revealed over time. In addition, it is also tricky for two parties to share a source of randomness securely. Umeno and his colleagues suggest using an agreed quasar radio signal to add randomness to a stream cipher - a method of encrypting information at high speed. Each communicating party would only need to know which quasar to monitor and when to start in order to encrypt and decrypt a message. Without knowing the target quasar and time an eavesdropper should be unable to decrypt the message. Umeno believes astronomical cryptography could appeal to anyone who requires high-security communications. He adds that the method does not require a large radio antenna or that the communicating parties be located in the same hemisphere, as radio signals can be broadcast over the internet at high speed. Concerning potential users, I suggest international financial institutions, governments and embassies, Umeno says. The researchers used quasar signals collected by Very Long Baseline Interferometry antenna at the institute to encrypt messages and have filed two patents covering quasar-based cryptography: one for locking and unlocking messages and another for generating digital signatures that can be used to match messages or files to a person. However, some cryptography researchers question the need for such an unusual means of securing messages. This is interesting research, but there's no reason for anyone to use it in a practical application, says Bruce Schneier of Counterpane Security. Furthermore, this is a brand new idea. Why would anyone want to use something new and untested when we've already got lots of good cryptography? Markus Kuhn from the University of Cambridge, UK, adds that the physical set-up could have potential weaknesses. It is easy to play tricks with reception antennas, he says. For example, he suggests that an attacker could mimic a radio signal and gain a lot of control over the signal that the receiver can see. Related Articles * Photon detector is precursor to broadband in space * http://www.newscientisttechnology.com/article/dn8877 * 21 March 2006 * Busted! A crisis in cryptography * http://www.newscientisttechnology.com/article/mg18825301.600 * 17 December 2005 * Let chaos keep your secrets safe * http://www.newscientisttechnology.com/article/mg18825262.000 * 19 November 2005 Weblinks * National Institute of Information and Communications Technology * http://www.nict.go.jp/ * Quasar Encryption patent * http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2Sect2=HITOFFp=1u=%2Fnetahtml%2FPTO%2Fsearch-bool.htmlr=1f=Gl=50co1=ANDd=PG01s1=20050242987OS=20050242987RS=20050242987 * Quasar Authentication patent * http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2Sect2=HITOFFp=1u=%2Fnetahtml%2FPTO%2Fsearch-bool.htmlr=1f=Gl=50co1=ANDd=PG01s1=20030145202OS=20030145202RS=20030145202 Close this window - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
