Re: PlayStation 3 predicts next US president
>The financial industry has actually created its own system - I forget >the name, some like a Gold Bond Certification - that it requires for >certain "high-importance" transactions (e.g., a document asserting you >own some stock for which you've lost the certificates). That's a medallion signature guarantee provided by a bank or similar institution. Unlike a notary, the guarantee means something, with the institution accepting liability for forgery. Not surprisingly, it's a rare bank bank who will do this for anyone who isn't already a customer. At my bank, the same person happens to be a notary and the guarantee officer and she knows me, so she just asks which stamp I want. http://en.wikipedia.org/wiki/Medallion_signature_guarantee http://www.sec.gov/answers/sigguar.htm - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
* William Allen Simpson: > Assuming, > Dp := any electronic document submitted by some person, converted to its > canonical form > Cp := a electronic certificate irrefutably identifying the other person > submitting the document > Cn := certificate of the notary > Tn := timestamp of the notary > S() := signature of the notary > > S( MD5(Tn || Dp || Cp || Cn) ). > > Of course, I'm sure the formula could be improved, and there are > traditionally fields identifying the algorithms used, etc. -- or something > else I've forgotten off the top of my head -- but please argue about the > actual topic of this thread, instead of incessant strawmen. The problem is not the outer MD5 (explicitly mentioned in your description), but that Dp is typically (well, to the extent such services have been deployed) some kind of hash. This has got the advantage that the timestamping service does not need to know the contents of the document. On the other hand, if the timestamping service archives Dp and can reveal it in a dispute, evil twins can be identified and analyzed -- which undermine the submitting party's claim that it submitted the second document instead of the first. Of course, this is actually cheating by substituting proven protocols for fragile cryptography. And the result is still open to interpretation, but all evidence is. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
William Allen Simpson wrote: > The whole point of a notary is to bind a document to a > person. That the person submitted two or more > different documents at different times is readily > observable. After all, the notary has the > document(s)! The notary does not want to have the documents, or to have the necessary apparatus to produce them on demand. Actually existent notaries do not keep the documents. Again, you are trying to invent a protocol that works around the flaws in MD5. No doubt a competent engineer can create such a protocol, but a competent engineer would much prefer not to have flaws he needs to work around. Further, there is a long history of cryptographic disasters, such as WiFi, where supposedly competent engineers set to working around flaws, and instead created more and bigger flaws. Even if someone really is a competent engineer, and perfectly capable of producing a protocol that works around the known flaws, it is hard for anyone else to tell if he really is competent enough to work around the flaws, or has produced, like WiFi and so many Microsoft projects, an even bigger hole than that which he was trying to fix. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
| > The whole point of a notary is to bind a document to a person. That | > the person submitted two or more different documents at different | > times is readily observable. After all, the notary has the | > document(s)! | | No, the notary does not have the documents *after* they are notarized, | nor do they keep copies. Having been a notary I know this | personally. When I stopped being a notary all I had to submit to the | state was my seal and my record books. | | If I had to testify about a document I would only be attesting that | the person who presented themselves adequately proved, under the | prudent businessman's standard, that they were the person that they | said they were and that I saw them sign the document in | question. That's it. No copies at all. What would anyone have to | testify about if a legal battle arose after the notary either died or | stopped being a notary? | | Think for a minute about the burden on a notary if they had to have a | copy of every document they notarized. What a juicy target they would | make for thieves and industrial spies. No patent paperwork would be | safe, no sales contract, no will, or other document. Just think how | the safe and burglar alarm companies would thrive. Now ask yourself | how much it costs to notarize a document. Would that pay for the | copying and storage. I don't know what the current fees are in | California but 20 years ago they were limited to $6.00 per person per | document and an extra buck for each additional copy done at the same | time. My average was about $14.00 per session. My insurance was | $50/year. Nowhere near enough to cover my liability if I was to This whole discussion has an air of unreality about it. Historically, notary publics date from an era when most people couldn't read or write, and hardly anyone could afford a lawyer. How does someone who can't read a document and can perhaps only scrawl an X enter into a contract? In the old days, he took the written contract to a notary public, who would read it to him, explain it, make sure he understood it, then stamp his scrawled "X". The notary's stamp asserted exactly the kind of thing that we discuss on this list as missing from digital signatures: That the particular person whose "X" was attached (and who would be fully identified by the notary) understood and assented to the contents of the contract. Today, we assume that everyone can read, and where a contract is at all complex, that everyone will have access to a lawyer. (Of course, this assumption is often invalid, but that's another story.) The requirement for a notary public's stamp is a faded vestige. For certain important documents, we still require that a notary sign off, but what exactly that proves any more is rather vague. Yes, in theory it binds a signature to a particular person, with that signature being on a particular document. That latter is why the notary's stamp is a physical stamp through the paper - hard(er) to fake. Of course, most of the time, the stamp is only applied to the last page of a multi-page contract, so proves only that that last page was in the notary's hands - replacing the early pages is no big deal. I think I've seen notaries initial every page, but I've also seen notaries who don't. In practice, whenever I've needed to have a document notarized, a quick look at some basic ID is about all that was involved. It's quite easy to get fake ID past a notary. Given the trivial fee paid to a notary - I think the limit is $2 in Connecticut - asking the notary to actually add much of value is clearly a non-starter. The financial industry has actually created its own system - I forget the name, some like a Gold Bond Certification - that it requires for certain "high-importance" transactions (e.g., a document asserting you own some stock for which you've lost the certificates). I've never actually needed to get this - it's appeared as a requirement for some alternative kinds of transactions on forms I've had to fill out over the years - so I don't know exactly how it works. However, it's completely independent of the traditional notary public system, and is run through commercial banks. Trying to justify anything based on the current role of notary publics - at least as it exists in the US - is a waste of time. -- Jerry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Allen wrote: William Allen Simpson wrote: [snip] The whole point of a notary is to bind a document to a person. That the person submitted two or more different documents at different times is readily observable. After all, the notary has the document(s)! No, the notary does not have the documents *after* they are notarized, nor do they keep copies. Having been a notary I know this personally. Thanks, Allen. Interestingly, digital signatures do provide what notaries can't provide in this case. Even though a digital signature binds a document to a key, there are known legal frameworks that can be used to bind the key to a person. Cheers, Ed Gerck - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Francois Grieu wrote: >> That's because if Tn is known (including chosen) to >> "some person", then (due to the weakness in MD5 we >> are talking about), she can generate Dp and Dp' such >> that >> S( MD5(Tn || Dp || Cp || Cn) ) = S( MD5(Tn || Dp' >> || Cp || Cn) ) >> whatever Cp, Cn and S() are. William Allen Simpson wrote: > First of all, the weakness in MD5 (computational > feasibility over time) that "we are talking about" is > not (yet) a preimage or second preimage attack. > Please don't extrapolate your argument. I don't think you know what a preimage or second preimage attack is. A preimage attack is a method of finding a document that hashes to an arbitrary given hash. A second preimage attack is a method of finding a document that hashes to the same hash as arbitrary given document. Your proposed workaround protocol fails because the adversary can construct multiple documents containing some arbitrary text and some chosen text that hash to the same hash - the fact that some of the arbitrary text comes from the good guys is irrelevant. The fact that the bad guys get to choose some of the text in all of the documents makes it fail. > Second of all, you need to read my messages more > carefully. No good canonical format allows random > hidden fields or images. There is no canonical format that suppresses human ignorable data, other than plain ascii or suchlike which is unlikely to be acceptable. Any format capable of displaying arbitrary well formatted documents is capable of containing data that humans are likely to ignore. What is ignorable is necessarily a human judgment. A canonical format is in practice going to be PDF or RTF, which does allow hidden fields and images. Further, even a visible image can be made to work. Further, it is quite subtle to decide what constitutes "hidden" - for example a gently irregular low intensity background on HTML pages is quite pleasing to the eye, so surely our format should allow such backgrounds. Further, what you propose is strengthening the protocol to work around known weaknesses in MD5. Whenever we strengthen a protocol to get around known weaknesses in an algorithm, we rarely do it right - consider the long succession of debacles surrounding RC4. SSH uses RC4 correctly, but consider all the protocols that used it incorrectly, and then issued incompatible updates to fix the flaws, updates that were even more flawed than the protocol they supposedly fixed. Further, if you want your protocol to work around the known weaknesses of MD5, "canonicalizing" the document is not the way to go. Instead, allow arbitrary documents, but precede them by salt which is randomly determined after the document is submitted. That will work a lot better than canonicalization, but it is still a workaround for a known weakness. Far better to avoid the weakness. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
silky wrote: On Dec 11, 2007 5:06 AM, Allen <[EMAIL PROTECTED]> wrote: What puzzles me in all this long and rather arcane discussion is why isn't the solution of using a double hash - MD5 *and* SHA whatever. The odds of find a double collision go way up. Some open source software people are already doing this. I've played around with the sample files that are out there and find an easy way to do this but I don't have either the horsepower or skill to be at all definitive. My gut tells me that using two processes that use different algorithms, even though compromised, will raise the bar so high that it would be secure for a long time. At my skill level and horsepower I can't find even a single way to do this with CRC32 and MD5. Granted, that certainly doesn't mean a whole lot. Work has actually been done on this exact topic. One link is here: http://cryptography.hyperlink.cz/2004/otherformats.html I think there may be more; I'm not sure. Thanks for the pointer. Very interesting and it proves that I don't have the horsepower at this point. (Just wait until I build that Microwulf! With the new quad core chips I should hit about 50 GigaFLOPS. And cheeep - less than 4K) But my real point is that CRC32 while has only 2^16 possibilities, even SHA 1 with its degraded state has (IIRC) 2^55 and if we go to SHA 256 it has 2^256 possibilities. Since MD5 and SHA 256 use two different algorithms the odds of creating a double collision are tiny at this point. So take your enhanced Tripwire like program and have it compute two different hashes. Yes, you can create a collision in the MD5, but can you also create a simultaneous collision in the SHA 256? This is my point. Best, Allen - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
On Dec 11, 2007 5:06 AM, Allen <[EMAIL PROTECTED]> wrote: > What puzzles me in all this long and rather arcane discussion is > why isn't the solution of using a double hash - MD5 *and* SHA > whatever. The odds of find a double collision go way up. > > Some open source software people are already doing this. I've > played around with the sample files that are out there and find > an easy way to do this but I don't have either the horsepower or > skill to be at all definitive. > > My gut tells me that using two processes that use different > algorithms, even though compromised, will raise the bar so high > that it would be secure for a long time. > > At my skill level and horsepower I can't find even a single way > to do this with CRC32 and MD5. Granted, that certainly doesn't > mean a whole lot. Work has actually been done on this exact topic. One link is here: http://cryptography.hyperlink.cz/2004/otherformats.html I think there may be more; I'm not sure. > But to take a real world example, a safety deposit box, the two > keys have to work together to open the box. It really does not > matter is one is a Yale and the other a combination, either one > of which are easily compromised by themselves, but together you > would have to find both at the same time to open the box, a lot > tougher problem. > > Best, > > Allen > > > Francois Grieu wrote: > > [EMAIL PROTECTED] wrote: > > > >> Dp := any electronic document submitted by some person, converted to its > >>canonical form > >> Cp := a electronic certificate irrefutably identifying the other person > >>submitting the document > >> Cn := certificate of the notary > >> Tn := timestamp of the notary > >> S() := signature of the notary > >> > >> S( MD5(Tn || Dp || Cp || Cn) ). > > > > In this context, the only thing that guards agains an attack by > > "some person" is the faint hope that she can't predict the Tn > > that the notary will use for a Dp that she submits. > > > > That's because if Tn is known (including chosen) to "some person", > > then (due to the weakness in MD5 we are talking about), she can > > generate Dp and Dp' such that > > S( MD5(Tn || Dp || Cp || Cn) ) = S( MD5(Tn || Dp' || Cp || Cn) ) > > whatever Cp, Cn and S() are. > > > > If Tn was hashed after Dp rather than before, poof goes security. > > > > > > Francois Grieu > > > > - > > The Cryptography Mailing List > > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] > > > > - > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] > -- mike http://lets.coozi.com.au/ - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
William Allen Simpson wrote: [snip] The whole point of a notary is to bind a document to a person. That the person submitted two or more different documents at different times is readily observable. After all, the notary has the document(s)! No, the notary does not have the documents *after* they are notarized, nor do they keep copies. Having been a notary I know this personally. When I stopped being a notary all I had to submit to the state was my seal and my record books. If I had to testify about a document I would only be attesting that the person who presented themselves adequately proved, under the prudent businessman's standard, that they were the person that they said they were and that I saw them sign the document in question. That's it. No copies at all. What would anyone have to testify about if a legal battle arose after the notary either died or stopped being a notary? Think for a minute about the burden on a notary if they had to have a copy of every document they notarized. What a juicy target they would make for thieves and industrial spies. No patent paperwork would be safe, no sales contract, no will, or other document. Just think how the safe and burglar alarm companies would thrive. Now ask yourself how much it costs to notarize a document. Would that pay for the copying and storage. I don't know what the current fees are in California but 20 years ago they were limited to $6.00 per person per document and an extra buck for each additional copy done at the same time. My average was about $14.00 per session. My insurance was $50/year. Nowhere near enough to cover my liability if I was to retain a copy of the document. Best, Allen - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
What puzzles me in all this long and rather arcane discussion is why isn't the solution of using a double hash - MD5 *and* SHA whatever. The odds of find a double collision go way up. Some open source software people are already doing this. I've played around with the sample files that are out there and find an easy way to do this but I don't have either the horsepower or skill to be at all definitive. My gut tells me that using two processes that use different algorithms, even though compromised, will raise the bar so high that it would be secure for a long time. At my skill level and horsepower I can't find even a single way to do this with CRC32 and MD5. Granted, that certainly doesn't mean a whole lot. But to take a real world example, a safety deposit box, the two keys have to work together to open the box. It really does not matter is one is a Yale and the other a combination, either one of which are easily compromised by themselves, but together you would have to find both at the same time to open the box, a lot tougher problem. Best, Allen Francois Grieu wrote: [EMAIL PROTECTED] wrote: Dp := any electronic document submitted by some person, converted to its canonical form Cp := a electronic certificate irrefutably identifying the other person submitting the document Cn := certificate of the notary Tn := timestamp of the notary S() := signature of the notary S( MD5(Tn || Dp || Cp || Cn) ). In this context, the only thing that guards agains an attack by "some person" is the faint hope that she can't predict the Tn that the notary will use for a Dp that she submits. That's because if Tn is known (including chosen) to "some person", then (due to the weakness in MD5 we are talking about), she can generate Dp and Dp' such that S( MD5(Tn || Dp || Cp || Cn) ) = S( MD5(Tn || Dp' || Cp || Cn) ) whatever Cp, Cn and S() are. If Tn was hashed after Dp rather than before, poof goes security. Francois Grieu - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Francois Grieu wrote: That's because if Tn is known (including chosen) to "some person", then (due to the weakness in MD5 we are talking about), she can generate Dp and Dp' such that S( MD5(Tn || Dp || Cp || Cn) ) = S( MD5(Tn || Dp' || Cp || Cn) ) whatever Cp, Cn and S() are. First of all, the weakness in MD5 (computational feasibility over time) that "we are talking about" is not (yet) a preimage or second preimage attack. Please don't extrapolate your argument. Second of all, you need to read my messages more carefully. No good canonical format allows random hidden fields or images. Third of all, that's not a weakness of a notary protocol -- it's a trap! The whole point of a notary is to bind a document to a person. That the person submitted two or more different documents at different times is readily observable. After all, the notary has the document(s)! Remember, the notary is not vouching for the validity of the content of the document. A notary only certifies that something was submitted by some person at some time. And that cannot be broken by making multiple submissions, or submissions that themselves have the same hash. That's one reason I'm much more interested in the attack on X.509. If Tn was hashed after Dp rather than before, poof goes security. But since it's not, that's a ridiculous strawman. I was remembering PGP off the top of my head. Fairly certain that Kerberos does, too. Not everybody is naive! And since the timestamp is "predictable" (within some range, although picoseconds really aren't very predictable), the protocols that I've designed include message identifiers, nonces, and sequence numbers, too. As you may recall, I mentioned that there were other fields He asked for an explanation about how a document is identified, he got one. Don't expect me to redesign an entire notary (or even a timestamp) protocol on a Sunday evening for a mailing list Really, there are fairly secure standards already available. However, the actual topic of this thread is code distribution. In that case, there is no "other" party certifying the documents. The code packager is also the certifier. There is (as yet) no weakness in the MD4 family (including MD5 and SHA1) that allows this attack by another party. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
[EMAIL PROTECTED] wrote: > Dp := any electronic document submitted by some person, converted to its >canonical form > Cp := a electronic certificate irrefutably identifying the other person >submitting the document > Cn := certificate of the notary > Tn := timestamp of the notary > S() := signature of the notary > > S( MD5(Tn || Dp || Cp || Cn) ). In this context, the only thing that guards agains an attack by "some person" is the faint hope that she can't predict the Tn that the notary will use for a Dp that she submits. That's because if Tn is known (including chosen) to "some person", then (due to the weakness in MD5 we are talking about), she can generate Dp and Dp' such that S( MD5(Tn || Dp || Cp || Cn) ) = S( MD5(Tn || Dp' || Cp || Cn) ) whatever Cp, Cn and S() are. If Tn was hashed after Dp rather than before, poof goes security. Francois Grieu - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
William Allen Simpson wrote: >> > The notary would never sign a hash generated by >> > somebody else. Instead, the notary generates its >> > own document (from its own tuples), and signs its >> > own document, documenting that some other document >> > was submitted by some person before some >> > particular time. James A. Donald: > > And how does it identify this "other document"? William Allen Simpson wrote: > Sorry, obviously I incorrectly assumed that we're > talking to somebody skilled in the art > > Reminding you that several of us have told you that a > notary has the document in her possession; and binds > the document to a person; and that we have rather a > lot of experience in identifying documents (even for > simple things like email), such as the PGP digital > timestamping service. > > Assuming, > Dp := any electronic document submitted by some > person, converted to its > canonical form > Cp := a electronic certificate irrefutably > identifying the other person > submitting the document > Cn := certificate of the notary Tn := timestamp of > the notary S() := signature of the notary > > S( MD5(Tn || Dp || Cp || Cn) ). Assuming that the attacker knows or can guess Tn, and that the canonical form allows images, then the attack still works. The attacker can create several documents, D1, D2, D3, D4, D5, such that MD5(Tn || D1 || Cp || Cn) is equal to MD5(Tn || D2 || Cp || Cn), which is equal to MD5(Tn || D3 || Cp || Cn), etc. He then gets the notary to sign MD5(Tn || D1 || Cp || Cn), and then uses whichever of D1, D2, D3, D4, and D5 is convenient. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Personally, I thought this horse was well drubbed, but the moderator let this message through, so he must think it important to continue James A. Donald wrote: William Allen Simpson wrote: > The notary would never sign a hash generated by > somebody else. Instead, the notary generates its own > document (from its own tuples), and signs its own > document, documenting that some other document was > submitted by some person before some particular time. And how does it identify this "other document"? Sorry, obviously I incorrectly assumed that we're talking to somebody skilled in the art Reminding you that several of us have told you that a notary has the document in her possession; and binds the document to a person; and that we have rather a lot of experience in identifying documents (even for simple things like email), such as the PGP digital timestamping service. Assuming, Dp := any electronic document submitted by some person, converted to its canonical form Cp := a electronic certificate irrefutably identifying the other person submitting the document Cn := certificate of the notary Tn := timestamp of the notary S() := signature of the notary S( MD5(Tn || Dp || Cp || Cn) ). Of course, I'm sure the formula could be improved, and there are traditionally fields identifying the algorithms used, etc. -- or something else I've forgotten off the top of my head -- but please argue about the actual topic of this thread, instead of incessant strawmen. The notary is only safe from this flaw in MD5 if you Another statement with no proof. As the original poster admitted, there is not a practical preimage or second preimage attack on MD5 (yet). assume he is not using MD5 for its intended purpose. As to "its intended purpose", rather than making one up, I've always relied upon the statement of the designer: ... The MD5 algorithm is intended for digital signature applications, where a large file must be "compressed" in a secure manner before being encrypted with a private (secret) key under a public-key cryptosystem such as RSA. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
William Allen Simpson wrote: > The notary would never sign a hash generated by > somebody else. Instead, the notary generates its own > document (from its own tuples), and signs its own > document, documenting that some other document was > submitted by some person before some particular time. And how does it identify this "other document"? The notary is only safe from this flaw in MD5 if you assume he is not using MD5 for its intended purpose. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
[EMAIL PROTECTED] wrote: If on the one hand, the correct procedure is sign-encrypt-sign, then why, on the other hand, is the parallel not sign-hash-sign ? What is "correct" depends on requirements and semantics, and neither is well addressed in that paper nor in standards, w.r.t. email and signing. https://financialcryptography.com/mt/archives/000905.html Ditto, in terms of your question. As an example (Ricardian Contract [1]), we might say that a signed contract is done as hash-digsig-hash [2] With this procedure, the first hash-digsig is a human signing (classical cleartext openpgp signature) and the last hash is a signature that causes sharing of the exact document [3]. iang [1] To complete the picture, even this evidence is distributed by means of transactions over the document; to be extreme, the end result is this: hash-digsig(hash-digsig(hash-digsig-hash)) [2] a public key signature is normally done hash-digsig, right? So your sign-hash-sign might really be: hash-digsig-hash-hash-digsig but that's a guess. [3] http://iang.org/papers/ricardian_contract.html --dan = http://world.std.com/~dtd/sign_encrypt/sign_encrypt7.ps Donald T. Davis, "Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.", Proc. Usenix Tech. Conf. 2001 (Boston, Mass., June 25-30, 2001), pp. 65-78.(180 Kbytes) (PDF, 200 Kbytes) (HTML, 80 Kbytes) Summary of the paper. Abstract: Simple Sign & Encrypt, by itself, is not very secure. Cryptographers know this well, but application programmers and standards authors still tend to put too much trust in simple Sign-and-Encrypt. In fact, every secure e-mail protocol, old and new, has codified naïve Sign & Encrypt as acceptable security practice. S/MIME, PKCS#7, PGP, OpenPGP, PEM, and MOSS all suffer from this flaw. Similarly, the secure document protocols PKCS#7, XML- Signature, and XML-Encryption suffer from the same flaw. Naïve Sign & Encrypt appears only in file-security and mail-security applications, but this narrow scope is becoming more important to the rapidly-growing class of commercial users. With file- and mail-encryption seeing widespread use, and with flawed encryption in play, we can expect widespread exposures. In this paper, we analyze the naïve Sign & Encrypt flaw, we review the defective sign/encrypt standards, and we describe a comprehensive set of simple repairs. The various repairs all have a common feature: when signing and encryption are combined, the inner crypto layer must somehow depend on the outer layer, so as to reveal any tampering with the outer layer. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
I had intended to stop posting, but with the request for history and a few misguided postings later, please indulge me. I'll try not to be too long. We've been talking about "collision" and "preimage" resistance at least since 1989. We didn't use those terms (I'm not fond of "preimage"). We merely had a clever bit of design by Rivest, and were eager to use the tools in our network protocols, but had the usual qualms about new things. If anything, being security minded, we were somewhat paranoid! Remember, at the time we had 80286s in deployment, and MD2 was considered too slow! So, MD4 came along (1990), and its little-endian design was fast enough to use on a server with 24 incoming connections. Not only was it "computationally infeasible" to find a collision, it was barely feasible to use the functions at (56 Kbps) line speed! There was some concern that MD4 would not be sufficiently resistant in the future. To be "safe", PPP CHAP was originally specified with either MD2 or MD4. Later, by 1994, we had settled upon MD5 as the compromise. To answer Benne's question, I was introduced to chosen-prefix collisions (again, we didn't use that term) by Dave Balenson after the Common Authentication Technology (CAT) Working Group meeting in Santa Fe circa mid-1991, and changed the PPP CHAP hash field order to protect against the possibility. The original drafts hashed the packet in field order. Splitting the Identifier from Challenge (with the secret between) protects against prefix calculations (and provides a modicum of replay protection). Within a couple of years, I would have included the Length as well, and additional MD-strengthening after the secret. The current CHAP design depends upon the final MD-strengthening to protect against appending attacks on the secret. Actually, PPP CHAP is probably not vulnerable, as the Challenge is short and fixed size for a particular connection. We added length for IPv6 in 1993, what I retrospectively call the L-MAC algorithm. That evolved in 1994 to the "envelope" method (secret before and after the data), and again in 1995 after the "On the Security of Two MAC Algorithms" paper presented at the rump session of Crypto '95. Within days, we adopted the recommended additional MD-strengthening between the data and the trailing secret, presented at the next IETF (and later published) as the "interleaved padding" IP-MAC algorithm. Sadly, the slower and weaker H-MAC (even though developed after IP-MAC) is the currently used specification. Sometimes, folks just assume that something published later is better. A reminder that the pressure of commerce, lobbying, and politics often trumps our best efforts. To reiterate, when designing security systems, there is a continuum of possibilities, and we choose those that fit the threat model. Even today, with laptop processors that out-perform the supercomputers of that era, PPP CHAP with MD5 is still resistant to such limited time-frame attacks over a serial link. As our understanding improves, it is perfectly reasonable to evolve our designs. That's why it is so important to specify flexible protocols from the very beginning! Dirk-Willem van Gulik wrote: And on unsealing day, which for tax reasons can be months later, the govt. entity just checks the MD5's versus the RFC3161 attest. ... An in-house Mallory (at the bidder) may well want to tweak things a bit and make several doctored copies with different bid levels; and send in the one joint MD5 through the RFC3161 service. Reminding you that this is something like a notary function, *not* a code distribution or signing function. And the attack requires (as I've shown repeatedly) the original document generator to be compromised. Folks on this list seem to forget that the legal purpose of a notary is not to protect the bidder/contractor/deed/etc. It is to protect the *public* against *fraudulent* bidders/contractors/deeds/etc. As we all agree (except for one increasingly phlegmatic person), the only purpose of a notary is to bind a person to a document at a particular time. The notary would never sign a hash generated by somebody else. Instead, the notary generates its own document (from its own tuples), and signs its own document, documenting that some other document was submitted by some person before some particular time. As in code distribution, every certifier *MUST* *ALWAYS* generate their own document. Then, there is no chosen-prefix collision, and the attack does not apply. In your hypothetical, the certifier virtually guarantees that Mallory will be caught! When Mallory tries to assert the claim, the bids can easily be compared. When the verifier compares the original documents and hashes with the later hashs, it will become readily apparent that two documents have the same hash. And then the trial judge will appoint a special master (such as me) to review the documents. It would be no problem to show that the documents re-t
Re: PlayStation 3 predicts next US president
On Dec 3, 2007, at 2:47 PM, William Allen Simpson wrote: Dirk-Willem van Gulik wrote: Keep in mind that the notary is still 'careful' -- effectively they sign the hash -- rather than the document; and state either such (e.g. in the case of some software/code where you do not hand over the actual code) or state that _a_ document was presented with said hash. And that makes all the difference. The digital notary is not certifying the original document. You described the notary generating its own tuples (credentials as presented, the hash, a timestamp, and a notarized declaration that such was presented). There is no problem, and the described attack does not apply. Not sure - lets take a similar example - the role of Chamber of Commerce in repetitive/renewal public tender/bid processes - who essentially makes you use an RFC 3161 service to sign any MD5 (Well - SHA1 is the actual default) for companies; typically a PDF or Word document of a bid for the purpose of 'locking' in the date of sumbission. And on unsealing day, which for tax reasons can be months later, the govt. entity just checks the MD5's versus the RFC3161 attest. (The reason for this time-stamping is threefold a) make it fair between entities regardless as to how good their postal system is, b) 'date of postoffice' is a bit buyable in some places of the world and c) some bid processes require the digital document to be hand delivered on sealing day to alleviate the confidentially burden of the govt. of keeping the bids secure). An in-house Mallory (at the bidder) may well want to tweak things a bit and make several doctored copies with different bid levels; and send in the one joint MD5 through the RFC3161 service. And then depending on the information leaking/gossip of the industry - choose later than the others which one to 'really' submit. As its competitors, as is common in the industry, tend to get a lot less tight lipped once the deadline has passed. What is new is that Mallory can generate several documents with the same MD5 with a few days of 'work'. That endagers workflows where you assume that a party cannot intentionally create more than one asset with has the same MD5. Dw - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Dirk-Willem van Gulik wrote: >> Keep in mind that the notary is still 'careful' -- >> effectively they sign the hash -- rather than the >> document; and state either such (e.g. in the case of >> some software/code where you do not hand over the >> actual code) or state that _a_ document was presented >> with said hash. William Allen Simpson wrote: > And that makes all the difference. The digital notary > is not certifying the original document. You > described the notary generating its own tuples > (credentials as presented, the hash, a timestamp, and > a notarized declaration that such was presented). > There is no problem, and the described attack does not > apply. The described attack does apply: The notary has complied with normal procedures and with the rules, but the rules and procedure fail to have the desired effect, because an MD5 hash lacks the desired properties. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
James A. Donald wrote: Not true. Because they are notarizing a signature, not a document, they check my supporting identification, but never read the document being signed. William Allen Simpson wrote: This will be my last posting. You have refused several requests to stick to the original topic at hand. Apparently, you have no actual experience with the legal system, or are from such a different legal jurisdiction that your scenario is somehow related to MD5 hashes of software and code distribution. Because human beings often try to skirt the rules, there's a long history of detailed notarization requirements. How it works here: (1) You prepare the document(s). They are in the form prescribed by law -- for example, Michigan Court Rule (MCR 2.114) "SIGNATURES OF ATTORNEYS AND PARTIES; VERIFICATION; EFFECT; SANCTIONS" (2) The clerk checks for the prescribed form and content. (3) You sign and date the document(s) before the notary (using a pen supplied by the notary, no disappearing ink allowed). (4) The notary signs and dates their record of your signature, optionally impressing the document(s) with an embossing stamp (making it physically difficult to erase). You have now attested to the content of the documents, and the notary has attested to your signature (not the veracity of the documents). Note that we get both integrity and non-repudiation The only acceptable computer parallel would require you to bring the documents to the notary, using a digital format supplied by the notary, You mean *specified* by the notary - which would presumably be PDF or RTF. generate the digital signature on the notary's equipment, and then the notary indempotently certify your signature (on the same equipment). And if the format is PDF or RDF, none of this will prevent the problem with MD5 - the problem being that a notarization of one document will also notarize as many other of my documents as I please. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
If on the one hand, the correct procedure is sign-encrypt-sign, then why, on the other hand, is the parallel not sign-hash-sign ? --dan = http://world.std.com/~dtd/sign_encrypt/sign_encrypt7.ps Donald T. Davis, "Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.", Proc. Usenix Tech. Conf. 2001 (Boston, Mass., June 25-30, 2001), pp. 65-78.(180 Kbytes) (PDF, 200 Kbytes) (HTML, 80 Kbytes) Summary of the paper. Abstract: Simple Sign & Encrypt, by itself, is not very secure. Cryptographers know this well, but application programmers and standards authors still tend to put too much trust in simple Sign-and-Encrypt. In fact, every secure e-mail protocol, old and new, has codified naïve Sign & Encrypt as acceptable security practice. S/MIME, PKCS#7, PGP, OpenPGP, PEM, and MOSS all suffer from this flaw. Similarly, the secure document protocols PKCS#7, XML- Signature, and XML-Encryption suffer from the same flaw. Naïve Sign & Encrypt appears only in file-security and mail-security applications, but this narrow scope is becoming more important to the rapidly-growing class of commercial users. With file- and mail-encryption seeing widespread use, and with flawed encryption in play, we can expect widespread exposures. In this paper, we analyze the naïve Sign & Encrypt flaw, we review the defective sign/encrypt standards, and we describe a comprehensive set of simple repairs. The various repairs all have a common feature: when signing and encryption are combined, the inner crypto layer must somehow depend on the outer layer, so as to reveal any tampering with the outer layer. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Dirk-Willem van Gulik wrote: Keep in mind that the notary is still 'careful' -- effectively they sign the hash -- rather than the document; and state either such (e.g. in the case of some software/code where you do not hand over the actual code) or state that _a_ document was presented with said hash. And that makes all the difference. The digital notary is not certifying the original document. You described the notary generating its own tuples (credentials as presented, the hash, a timestamp, and a notarized declaration that such was presented). There is no problem, and the described attack does not apply. Note that the notary bears no responsibility for presentation of false credentials. Here, in a case with which I'm personally familiar, somebody with the SAME NAME as his father got a new driver's license, signed it in the same fashion as his father, then went to banks and presented the driver's license and signature, causing all his father's deposits to be transferred to his wife's name, and adding his son to the house deed (and then mortgaging the house). It was certainly not the several notaries' fault that identical names were used. The "certificate" (same name driver's license and signature) appeared valid. All the cryptography in the world will not prevent false certification, where the underlying information is already compromised. To reiterate the topic at hand: trust is not transitive! - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
On Dec 2, 2007, at 3:09 AM, William Allen Simpson wrote: There are no circumstances in which any reputable certifier will ever certify any of the "multitude" containing a hidden pdf image, especially where generated by another party. It is getting fairly common for notaries in for example the Netherlands to timestamp or otherwise attest that an (asset with) hash (e.g. MD5 an) was presented to them by a person or company with such and such credentials. E.g. NotarSign (diginotarl.nl) its email service will attest such in an automated fashion. Essentially what you are getting is a notarized statement containing the credentials as presented, the hash, a timestamp and a notarized (backed with an Appostille of the Hague if to be used internationally) declaration that such was presented. Note presentation of the asset is quite optional in this process. And for practical reasons it is quite common now in certain trade- environments to _not_ sent the actual document to NotarSign but just the statement with an MD5* and a https URL to the Purchase Order (where the biz. partner needs his x509 or a physical RSA token to pick it up) - to be forwarded to the trading partners. THIS is what makes this "tongue in cheek" example 'somewhat' relevant for day to day workflows for those who are still using MD5s. 'Somewhat' - as ultimately in this example it is hard to argue entirely accidental tampering. However - in some biz. sealed-bid processes the damage is done by that time. The attack requires the certifier to be compromised, either to certify documents that the certifier did not generate, or to include the chosen text (hidden image) in its documents in exactly the correct location. While there are plenty of chosen text attacks in cryptography, this one is highly impractical. The image is hidden. It will not appear, and thus would not be accidentally copied by somebody (cut-and-paste). Keep in mind that the notary is still 'careful' -- effectively they sign the hash -- rather than the document; and state either such (e.g. in the case of some software/code where you do not hand over the actual code) or state that _a_ document was presented with said hash. The _assumption_ that there is a 1:1 mapping is one left to the reader. Compare it to the passport/personalia -- the statement of fact usually says that a person appeared in front of the notary which presented... rather than Mr X submitted himself to... Dw. *) The above example falls somewhat apart as the current message contains an 'at&t 'sum', md5, SHA-256, SHA-512 and the length - and almost all ERP systems check all but the AT&T checksum. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: PlayStation 3 predicts next US president
I'd be interested in seeing references to older work on chosen-prefix multicollisions. This has been on the web since at least July. http://www.cits.rub.de/MD5Collisions/ I'm sure it's not the only one either. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
William Allen Simpson wrote: [snip] Actually, I deal with notaries regularly. I've always had to physically sign while watched by the notary. They always read the stuff notarized, and my supporting identification, because they are notarizing a signature (not a document). And yes, they always generate the stamp or imprint they sign. To do otherwise would be irresponsible (and illegal). Having been a notary in the State of California (Shocked myself, got 100% on the test!) I can attest that the contents of the document are looked at, but only so that I could record what *type* of document I was notarizing, not the exact textual meaning of the content or whether it might or might not allege something that is untrue. The description of the document in my log book was always relatively short as there was only space for about 20 words. The requirements are simple, see that the document you are notarizing has as many pages it says it does so that the count can't be changed without arousing suspicion, and the the person who is signing the paper is identified by enough documentation that I could be assured, within the limits of my ability to give a superficial, not expert, less than ten minutes perusal of the identification documents presented match the person presenting them to the best of my ability to judge. Best, Allen It always was a good faith certification, not a proof beyond challenge. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
James A. Donald wrote: A notary is a certifier. Have you ever seen a notary read the stuff he notarizes, let alone generate it? William Allen Simpson wrote: Actually, I deal with notaries regularly. I've always had to physically sign while watched by the notary. They always read the stuff notarized, and my supporting identification, because they are notarizing a signature (not a document). But they don't read the document, let alone generate it. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Weger, B.M.M. de wrote: See http://www.win.tue.nl/hashclash/TargetCollidingCertificates/ ... Our first chosen-prefix collision attack has complexity of about 2^50, as described in our EuroCrypt 2007 paper. This has been considerably improved since then. In the full paper that is in preparation we'll give details of those improvements. Much more interesting. Looks like the death knell of X.509. Why didn't you say so earlier? (It's a long known design flaw in X.509 that it doesn't provide integrity for all its internal fields.) Where are MD2, MD4, SHA1, and others on this continuum? And based on the comments in the page above, the prefix is quite large! Optimally, shouldn't it be <= the internal chaining variables? 512 bits for MDx. So, the attacks need two values for comparison: the complexity versus the length of the chosen prefix. Let me know when you get the chosen prefix down to 64-bits, so I can say "I told you so" to Bellovin again. I was strongly against adding the "random" IV field to IPsec - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
James A. Donald wrote: Not true. Because they are notarizing a signature, not a document, they check my supporting identification, but never read the document being signed. This will be my last posting. You have refused several requests to stick to the original topic at hand. Apparently, you have no actual experience with the legal system, or are from such a different legal jurisdiction that your scenario is somehow related to MD5 hashes of software and code distribution. Because human beings often try to skirt the rules, there's a long history of detailed notarization requirements. How it works here: (1) You prepare the document(s). They are in the form prescribed by law -- for example, Michigan Court Rule (MCR 2.114) "SIGNATURES OF ATTORNEYS AND PARTIES; VERIFICATION; EFFECT; SANCTIONS" (2) The clerk checks for the prescribed form and content. (3) You sign and date the document(s) before the notary (using a pen supplied by the notary, no disappearing ink allowed). (4) The notary signs and dates their record of your signature, optionally impressing the document(s) with an embossing stamp (making it physically difficult to erase). You have now attested to the content of the documents, and the notary has attested to your signature (not the veracity of the documents). Note that we get both integrity and non-repudiation The only acceptable computer parallel would require you to bring the documents to the notary, using a digital format supplied by the notary, generate the digital signature on the notary's equipment, and then the notary indempotently certify your signature (on the same equipment). In the real world, the emphasis is on binding a document to a person, and vice versa. Any digital system that does not tie the physical person to the virtual document is not equivalent. This is simply not equivalent to a site producing its own software and generating a hash of its own content. There should be no third party involved as a certifier. If they were to generate an MD5 hash of documents prepared by someone else, then the attack described (eight different human readable documents with the same MD5 hash) works. If a notary were to do that, they'd be looking at a fairly severe penalty. By definition, such a notary was compromised. But nothing like the prison sentence that you'd be facing for presenting the false documents to the court. And I'd be pushing the prosecutor for consecutive sentences for all 8 fraudulent documents, with enhancements. Nobody has given any examples of "human readable documents" that will produce the same hash when re-typed into the system. All those proposed require an invisible component. They are "machine readable" only. That's why we, as security analysts, don't design or approve such systems. We're not (supposed to be) fooled by parlor tricks. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
William Allen Simpson wrote: [snip] There are no circumstances in which any reputable certifier will ever __^ certify any of the "multitude" containing a hidden pdf image, especially where generated by another party. Given what we know about the limitations of people, their response to ethics, and the endemic nature of ego and bribery around the world (See list of a few samples below) I would very much doubt that this method won't be used one day. When? Who knows. But as someone who rarely bets, this is one I'd bet on. How about the Teapot Dome Scandal, Enron, WorldCom, Michael Milken and all the others we find in our daily papers? Or to move into an area where no money changed hands, look at: http://innocenceproject.org/ and look at the corruption of public officials which put people to death based on lies. Read up on why the Governor of Illinois pardoned everyone on Death Row a few years back. See: http://www.msnbc.msn.com/id/19031423/ http://www.signonsandiego.com/news/politics/cunningham/ http://valleypolitics.blogspot.com/2007/03/conspiracy-extortion-bribery-oh-my.html http://www.thebostonchannel.com/politics/13438616/detail.html http://news.bbc.co.uk/1/hi/uk_politics/1259957.stm http://www.usdoj.gov/ criminal/ npftf/ pr/ press_releases/ 2007/ may/ 05-11-07lucas.pdf http://www.usatoday.com/money/companies/2005-11-08-titan-usat_x.htm http://www.msnbc.msn.com/id/3340697 http://www.corpwatch.org/article.php?id=8649 http://www.pbs.org/now/shows/347/ Then, of course, there is the Transparency International Corruption Perceptions Index: http://www.infoplease.com/ipa/A0781359.html Then, too, there is the Internet Center for Corruption Research: http://www.icgg.org/ Ego/bribery/corruption is so common, and it effects most commonly found after the fact, that to expect that a now "reputable certifier," won't become corrupted in some manner, like the notaries in Southern California in the elder fraud scandal, is placing trust in a system without verification. It takes periodic external audit to ensure the continued honesty of all certifiers. This is what SOX in the US is attempting, but like most things, never perfect the first time. (BTW, I don't recall when or where, but recently there was a comment on a list dealing in and around cryptography that went approximately, "Who would of thought that this list would be about philosophy?" (Not a quote, just an aging memory if I got the essence wrong.) Best, Allen - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
James A. Donald wrote: >> A notary is a certifier. Have you ever seen a notary >> read the stuff he notarizes, let alone generate it? William Allen Simpson wrote: > Actually, I deal with notaries regularly. I've always > had to physically sign while watched by the notary. > They always read the stuff notarized, and my > supporting identification, because they are notarizing > a signature (not a document). Not true. Because they are notarizing a signature, not a document, they check my supporting identification, but never read the document being signed. > And yes, they always generate the stamp or imprint > they sign. To do otherwise would be irresponsible (and > illegal). If they were to generate an MD5 hash of documents prepared by someone else, then the attack described (eight different human readable documents with the same MD5 hash) works. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: PlayStation 3 predicts next US president
Hi William, > > ... We say so on > > the website. We did show this hiding of collisions for other data > > formats, such as X.509 certificates > > More interesting. Where on your web site? I've long abhorred the > X.509 format, and was a supporter of a more clean alternative. See http://www.win.tue.nl/hashclash/TargetCollidingCertificates/ > > Our real work is chosen-prefix collisions combined with > > multi-collisions. This is crypto, it has not been done before, > > Certainly it was done before! I was referring to MD5. Apart from that, I'd be interested in seeing references to older work on chosen-prefix multicollisions. > What *would* be crypto is the quantification of where MDx > currently falls on the computational spectrum. Our first chosen-prefix collision attack has complexity of about 2^50, as described in our EuroCrypt 2007 paper. This has been considerably improved since then. In the full paper that is in preparation we'll give details of those improvements. Grtz, Benne - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Weger, B.M.M. de wrote: The parlor trick demonstrates a weakness of the pdf format, not MD5. I disagree. We could just as easy have put the collision blocks in visible images. Parlor trick. ... We could just as easy have used MS Word documents, or any document format in which there is some way of putting a few random blocks somewhere nicely. Parlor trick. ... We say so on the website. We did show this hiding of collisions for other data formats, such as X.509 certificates More interesting. Where on your web site? I've long abhorred the X.509 format, and was a supporter of a more clean alternative. ... and for Win32 executables. Parlor trick. So far, all the things you mention require the certifier to be suborned. Our real work is chosen-prefix collisions combined with multi-collisions. This is crypto, it has not been done before, Certainly it was done before! We talked about it more than a decade ago. We knew that what was "computationally infeasible" would become feasible. Every protocol I've designed or formally reviewed is protected against the chosen prefix attack. (To qualify, where I had final say. I've reviewed badly designed protocols, such as IKE/ISAKMP. And I've been overruled by committee from time to time) What *would* be crypto is the quantification of where MDx currently falls on the computational spectrum. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
James A. Donald wrote: A notary is a certifier. Have you ever seen a notary read the stuff he notarizes, let alone generate it? Actually, I deal with notaries regularly. I've always had to physically sign while watched by the notary. They always read the stuff notarized, and my supporting identification, because they are notarizing a signature (not a document). And yes, they always generate the stamp or imprint they sign. To do otherwise would be irresponsible (and illegal). Suppose you sign a contract - by signing the MD5 hash of the contract. Unfortunately the guy who prepared the contract prepared two slightly different contracts, one of which is more favorable to him and less favorable to you than the one you actually signed. Both contracts have the same MD5 hash. I've digitally signed contracts, that I prepared and verified, on plaintext documents using PGP. So far, I've seen no such exploit described nor quantified. There's this silly idea that's been floating around that a digital signature is somehow equivalent to a human signature. Or worse, somehow better?!?! Heck, current U.S. law counts a digitized sound as a signature!?!? (Folks have lost money on this snake oil. They deserved it.) Anyway, this is irrelevant to the original topic. That is: This implies a vulnerability in software integrity protection and code signing schemes that still use MD5. Please quantify your spurious allegations (and stay on topic). - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
RE: PlayStation 3 predicts next US president
Hi William, > > The attack was to generate a multitude of predictions for the US > > election, each of which has the same MD5 hash. If the certifier > > certifies any one of these predictions, the recipient can use the > > certificate for any one of these predictions. > > > That's a mighty big "if" -- as in infinite improbability. > Therefore, a parlor trick, not cryptography. That's an "if" indeed, we say so on the website. How big it is, you all form your own opinion. > There are no circumstances in which any reputable certifier > will ever certify any of the "multitude" containing a hidden > pdf image, especially where generated by another party. This I read as a definition of 'reputable'. > While there are plenty of chosen text attacks in > cryptography, this one is highly impractical. The image is > hidden. It will not appear, and thus would not be > accidentally copied by somebody (cut-and-paste). > > The parlor trick demonstrates a weakness of the pdf format, not MD5. I disagree. We could just as easy have put the collision blocks in visible images. We could just as easy have used MS Word documents, or any document format in which there is some way of putting a few random blocks somewhere nicely. We say so on the website. We did show this hiding of collisions for other data formats, such as X.509 certificates and for Win32 executables. Our real work is chosen-prefix collisions combined with multi-collisions. This is crypto, it has not been done before, this is as far as we can get in MD5 cryptanalysis, and we think it's relevant. To sell it to the world we wrapped it up nicely. You just throw away the wrapper. Grtz, Benne de Weger - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
William Allen Simpson wrote: > Apparently, you never read the original rationale for > MD5. It still does what it was intended to do MD5 was intended to identify the thing being hashed uniquely. If it is possible to produce multiple plausible human readable texts that say different things yet give the same MD5 hash, it does not do what it was intended to do. James A. Donald: >> If it is a certifier, these are not "its" documents. William Allen Simpson: > If it is a certifier, it damn well better be its own > documents! A notary is a certifier. Have you ever seen a notary read the stuff he notarizes, let alone generate it? > Look at the original message: > > This implies a vulnerability in software integrity > protection and code signing schemes that still use > MD5. Suppose you sign a contract - by signing the MD5 hash of the contract. Unfortunately the guy who prepared the contract prepared two slightly different contracts, one of which is more favorable to him and less favorable to you than the one you actually signed. Both contracts have the same MD5 hash. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
James A. Donald wrote: So the certifier is going to go through each thing he certifies, to make sure there is nothing funny about it? Yes. The whole point of MD5 is to automate that stuff. If an actual human has to go through it, and understand what it means, and certify the *meaning* then there is no reason to take an MD5 hash. Apparently, you never read the original rationale for MD5. It still does what it was intended to do If it is a certifier, these are not "its" documents. If it is a certifier, it damn well better be its own documents! Look at the original message: This implies a vulnerability in software integrity protection and code signing schemes that still use MD5. Anybody that's "certifying" software and code that they didn't personally generate and vet is selling snake oil. Trust is *not* transitive! Neither is reputation. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
> There are no circumstances in which any reputable > certifier will ever certify any of the "multitude" > containing a hidden pdf image, especially where > generated by another party. So the certifier is going to go through each thing he certifies, to make sure there is nothing funny about it? The whole point of MD5 is to automate that stuff. If an actual human has to go through it, and understand what it means, and certify the *meaning* then there is no reason to take an MD5 hash. > The attack requires the certifier to be compromised, > either to certify documents that the certifier did not > generate That is what certifiers do. It is what they are supposed to do. You seem to have confused certification with signing. > or to include the chosen text (hidden image) in its > documents in exactly the correct location. If it is a certifier, these are not "its" documents. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
James A. Donald wrote: This attack does not require the certifier to be compromised. You are referring to a different page (that I did not reference). Never-the-less, both attacks require the certifier to be compromised! The attack was to generate a multitude of predictions for the US election, each of which has the same MD5 hash. If the certifier certifies any one of these predictions, the recipient can use the certificate for any one of these predictions. That's a mighty big "if" -- as in infinite improbability. Therefore, a parlor trick, not cryptography. There are no circumstances in which any reputable certifier will ever certify any of the "multitude" containing a hidden pdf image, especially where generated by another party. The attack requires the certifier to be compromised, either to certify documents that the certifier did not generate, or to include the chosen text (hidden image) in its documents in exactly the correct location. While there are plenty of chosen text attacks in cryptography, this one is highly impractical. The image is hidden. It will not appear, and thus would not be accidentally copied by somebody (cut-and-paste). The parlor trick demonstrates a weakness of the pdf format, not MD5. This attack renders MD5 entirely worthless for any use other than as an error check like CRC - and CRC does it better and faster. To be as weak as CRC, the strength would be 2**8. I've seen no papers that reduce MD5 complexity to 2**8. Please present your proofs and actual vulnerabilities, including specific examples of actual PPP CHAP compromised traffic -- and for extra credit, actual compromise of netbsd and/or openbsd software distribution. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
William Allen Simpson wrote: > Weger, B.M.M. de wrote: >> See http://www.win.tue.nl/hashclash/Nostradamus if >> you want to know the details of what this has to do >> with cryptography. >> > It always bothers me as these things are announced, > but are based on presumptions that have absolutely no > relevance in the real world > > Therefore, nothing to do with cryptography (which is > not a parlor trick). > >> This implies a vulnerability in software integrity >> protection and code signing schemes that still use >> MD5. See >> http://www.win.tue.nl/hashclash/SoftIntCodeSign for >> details. >> > There is no such MD5 vulnerability implied. As the > paper itself states: > > In cryptographic terms: our attack is an attack on > collision resistance, not on preimage or second > preimage resistance. This implies that both > colliding files have to be specially prepared by the > attacker, before they are published on a download > site or presented for signing by a code signing > scheme. Existing files with a known hash that have > not been prepared in this way are not vulnerable. > > Since this "attack" requires the certifier be > compromised, the attacker could also modify the > program data itself undetectably. That is, this > theoretical problem actually is more effort than the > obvious attack! This attack does not require the certifier to be compromised. The attack was to generate a multitude of predictions for the US election, each of which has the same MD5 hash. If the certifier certifies any one of these predictions, the recipient can use the certificate for any one of these predictions. > In summary, there are exactly zero instances where > this use of MD5 would actually present a > vulnerability. This attack renders MD5 entirely worthless for any use other than as an error check like CRC - and CRC does it better and faster. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Weger, B.M.M. de wrote: See http://www.win.tue.nl/hashclash/Nostradamus if you want to know the details of what this has to do with cryptography. It always bothers me as these things are announced, but are based on presumptions that have absolutely no relevance in the real world Therefore, nothing to do with cryptography (which is not a parlor trick). This implies a vulnerability in software integrity protection and code signing schemes that still use MD5. See http://www.win.tue.nl/hashclash/SoftIntCodeSign for details. There is no such MD5 vulnerability implied. As the paper itself states: In cryptographic terms: our attack is an attack on collision resistance, not on preimage or second preimage resistance. This implies that both colliding files have to be specially prepared by the attacker, before they are published on a download site or presented for signing by a code signing scheme. Existing files with a known hash that have not been prepared in this way are not vulnerable. Since this "attack" requires the certifier be compromised, the attacker could also modify the program data itself undetectably. That is, this theoretical problem actually is more effort than the obvious attack! In summary, there are exactly zero instances where this use of MD5 would actually present a vulnerability. As many discussions in this community have amply demonstrated, trust is not transitive. At some point, you have to "know" (usually by reputation) the chip-vendor, compiler-writer, et alia, are not compromised. Therefore, many of us compile our own systems and packages (as much as practical). Over the many years we have designed protocols using MDx, we were always aware that a mere hashing function could never perfectly protect against prefix or suffix data extension. Therefore, (I for one) always design with a prefix chosen by the certifier, and a suffix nonce or counter publicly shared with (preferably chosen by) the verifier. For example, see PPP CHAP (originally written circa 1991). The only cryptographic question is how to quantify the strength of the collision resistance. CRC, FCS, MD2, MD4, MD5, SHA1, SHA256 -- they all have some level, and that is useful to determine the practical application for the function. The base complexity assumptions are (have always been) 2 to the: 8 CRC 16 FCS 64 MDx 80 SHA1 None of these have ever been out of the realm of possibility. Yet we all have long known that SHA1 is stronger than MD2, which is stronger than MD5, which is stronger than MD4. We also have long known that FCS and CRC are perfectly acceptable for many integrity applications. How much stronger is an interesting result. The rest is merely academic. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: PlayStation 3 predicts next US president
Weger, B.M.M. de wrote: > We also announce two different Win32 executables that > have identical MD5 hash values. This can be made to > happen for any two executable files. This implies a > vulnerability in software integrity protection and > code signing schemes that still use MD5. See > http://www.win.tue.nl/hashclash/SoftIntCodeSign for > details. That MD5 is broken is of course old news. I observe that US authorities have decided on a hash, found it was broken, decided on a new hash, found it was broken also, and are now where we are. Russian authorities decided on a 256 bit hash in 1990: GOST R 34.11-94. It is still good as far as anyone knows, and has never needed to be changed. This entirely confirms my prejudices about the US government cryptographers. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
PlayStation 3 predicts next US president
Hi all, We (Marc Stevens, Arjen Lenstra and me) have used a Sony PlayStation 3 to correctly predict the outcome of the 2008 US presidential elections. See http://www.win.tue.nl/hashclash/Nostradamus if you want to know the details of what this has to do with cryptography. We also announce two different Win32 executables that have identical MD5 hash values. This can be made to happen for any two executable files. This implies a vulnerability in software integrity protection and code signing schemes that still use MD5. See http://www.win.tue.nl/hashclash/SoftIntCodeSign for details. Grtz, Benne de Weger - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]