Re: Question about Shamir secret sharing scheme
Kevin W. Wall asks about Shamir sharing: The question that a colleague and I have is there any cryptographic purpose of computing the independent coefficients over the finite field, Zp ? Yes, you do have to be careful to do that. You want to make sure the shares don't leak any information about the secret S. Consider the simplest case where two people are involved. Call the single random coefficient c, with secret S, then the two shares are: S + c S + 2c Now if this is mod p, and c is chosen at random mod p, then both c and 2c will be random mod p, and each perfectly hides the value of S when it is added mod p, similarly to a one-time-pad. Neither share leaks any information about the value of S. But suppose for convenience you did the math mod some power of 2 (or even just over the integers). Then 2c is going to be even, regardless of c. And seeing S + 2c will then reveal whether S is even or odd, defeating the privacy of the scheme. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: AES-GMAC as a hash
Darren J Moffat darren.mof...@sun.com asks: Ignoring performance for now what is the consensus on the suitabilty of using AES-GMAC not as MAC but as a hash ? Would it be safe ? The key input to AES-GMAC would be something well known to the data and/or software. No, I don't think this would work. In general, giving a MAC a fixed key cannot be expected to produce a good hash. With AES-GMAC in particular, it is unusual in that it has a third input (besides key and data to MAC), an IV, which makes your well-known-key strategy problematic. And even as a MAC, it is very important that a given key/IV pair never be reused. Fixing a value for the key and perhaps IV would defeat this provision. But even ignoring all that, GMAC amounts to a linear combination of the text blocks - they are the coefficients of a polynomial. The reason you can get away with it in GMAC is because the polynomial variable is secret, it is based on the key. So you don't know how things are being combined. But with a known key and IV, there would be no security at all. It would be linear like a CRC. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Small-key DSA variant
While thinking about Zooko's problem with needing small keys, I seem to have recalled an idea for a DSA variant that uses small keys. I can't remember where I heard it, maybe at a Crypto rump session. I wonder if anyone recognizes it. Let the DSA public key be y = g^x mod p. DSA signatures are defined by: r = g^k mod p mod q s satisfies sk - rx = h mod q Let's define R = g^k mod p. Then r = R mod q. The verification raises both sides of the s equation to the g power: g^(sk) / g^(rx) = g^h mod p, or equivalently: R^s / y^r = g^h mod p The old ElGamal signature would have been (R,s) (and maybe wouldn't have used a subgroup). Then this second equation would be the verification (substituting R for r in the y exponentiation works because the exponent arithmetic is implicitly mod q). But DSA improved this by using (r,s) which is smaller. We can't substitute r for R globally in the verification equation, it won't work. But we can solve for R: R = g^(h/s) * y^(r/s) mod p and take this mod q: r = R mod q = g^(h/s) * y^(r/s) mod p mod q which is the conventional DSA verification equation. The small-key variant I'm asking about goes back to the ElGamal verification equation: R^s / y^r = g^h mod p but instead of solving for R, we solve for y in a similar way: y = R^(s/r) / g^(h/r) mod p This means that with an ElGamal style (R,s) signature, the verifier can derive y = g^x mod p. So he doesn't have to know the public key. Instead of letting the public key be y, we can make it H(y) for some hash function H. Then the verification is: H(y) = H( R^(s/r) / g^(h/r) mod p ) We have increased the signature size from twice the size of q to the sum of the sizes of p and q (which is much bigger, for typical non-EC DSA groups). But we have decreased the public key from the size of p to the size of H. Now the interesting question is whether H can be the size of the security parameter, rather than twice the size like q. Maybe we could use an 80 bit H. This would make for a very small public key (again at the expense of a much larger signature). The idea would be that y is a fixed target, and a forger needs to come up with an R,s whose hash matches the hash of y. It's a second preimage problem, not a collision problem. One issue is that there are many keys in the world, and perhaps a forger is happy to forge anyone's signature. (Or more to the point, a verifier really wants to trust all signatures out there.) Then the forger only needs to match one of H(y) for any of potentially millions or billions of y values, and this reduces his work by a factor equal to the number of keys. So we probably do have to boost the key size up to accommodate this issue. But it could still probably be smaller than for even ECDSA keys. Anyway, that's the concept. Does anyone recognize it? Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Certainty
Paul Hoffman wrote: Getting a straight answer on whether or not the recent preimage work is actually related to the earlier collision work would be useful. I am not clueful enough about this work to give an authoritative answer. My impression is that they use some of the same general techniques and weaknesses, for example the ability to make modifications to message words and compensate them with modifications to other message words that cancel. However I think there are differences as well, the preimage work often uses meet in the middle techniques which I don't think apply to collisions. There was an amusing demo at the rump session though of a different kind of preimage technique which does depend directly on collisions. It uses the Merkle-Damgard structure of MD5 and creates lots of blocks that collide (possibly with different prefixes, I didn't look at it closely). Then they were able to show a second preimage attack on a chosen message. That is, they could create a message and have a signer sign it using MD5. Then they could create more messages at will that had the same MD5 hash. In this demo, the messages started with text that said, Dear so-and-so and then had more readable text, followed by binary data. They were able to change the person's name in the first line to that of a volunteer from the audience, then modify the binary data and create a new version of the message with the same MD5 hash, in just a second or two! Very amusing demo. Google for trojan message attack to find details, or read: www.di.ens.fr/~bouillaguet/pub/SAC2009.pdf slides (not too informative): http://rump2009.cr.yp.to/ccbe0b9600bfd9f7f5f62ae1d5e915c8.pdf Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Ultimate limits to computation
[Note subject line change] Jerry Leichter writes: Since people do keep bringing up Moore's Law in an attempt to justify larger keys our systems stronger than cryptography, it's worth keeping in mind that we are approaching fairly deep physical limits. I wrote about this on this list quite a while back. If current physical theories are even approximately correct, there are limits to how many bit flips (which would encompass all possible binary operations) can occur in a fixed volume of space-time. You can turn this into a limit based solely on time through the finite speed of light: A computation that starts at some point and runs for n years can't involve a volume of space more than n light years in radius. (This is grossly optimistic - if you want the results to come back to the point where you entered the problem, the limit is n/2 light years, which has 1/8 the spacial volume). I made a very approximate guess at how many bit-flips you could get in a time-space volume of a 100 light- year sphere; the answer came out somewhere between 2^128 and 2^256, though much closer to the former. So physical limits prevent you from doing a brute force scan - in fact, you can't even enumerate all possible keys - in 100 years for key lengths somewhere not much more than 128 bits. Things may not be quite as favorable as this. Here is a posting I made to cypherpunks in 2004: To: cypherpu...@al-qaeda.net Date: Wed, 4 Aug 2004 11:04:15 -0700 (PDT) From: h...@finney.org (Hal Finney) Subject: Re: On what the NSA does with its tech MV writes: Yes. They can't break a 128 bit key. That's obvious. (if all the atoms in the universe were computers... goes the argument). Not necessarily, if nanotechnology works. 128 bits is big but not that big. Eric Drexler, in Nanosystems, section 12.9, predicts that a nanotech based CPU fitting in a 400 nm cube could run at 1000 MIPS and consume 60 nanowatts, performing 10^16 instructions per second per watt. Let's design a system to break a 128 bit cipher. Let's suppose it has to do 2^10 instructions per test, so this is 2^138 instructions total, or about 10^41. Let's let it run for four months, which is 10^7 seconds, so our necessary processing rate is 10^34 instructions per second. This means we need 10^34 IPS / 1000 MIPS or 10^25 of Drexler's gigahertz cubes, call it 10^25 cubic microns or 10^7 cubic meters, a cube about 220 meters on a side. The system will consume 10^25 * 60 nanowatts or about 6 * 10^17 watts. Now, that's a lot. It's four times what the earth receives from the sun. So we have to build a disk four times the area (not volume) of the earth, collect that power and funnel it to our computers. Probably we would scatter the computers throughout the disk, which would be mostly composed of solar collectors. (Keeping the disk gravitationally stable is left as an exercise for the student, as is the tradeoff involved in making it smaller but moving it closer to the sun.) Fortunately, exhaustive key search is perfectly parallelizable so there is no need for complex communications or synchronizations between the processors. As you can see, breaking 128 bit keys is certainly not a task which is so impossible that it would fail even if every atom were a computer. If we really needed to do it, it's not outside the realm of possibility that it could be accomplished within 50 years, using nanotech and robotics to move and reassemble asteroids into the necessary disk. Now, 256 bit keys really are impossible, unless the whole contraption above can be made to operate as an enormous, unified quantum computer, in which case it could theoretically break even 256 bit keys. 512 bit keys... now those really are impossible. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Zooko's semi-private keys
Zooko's proposal for semi-private keys is worthy of discussion here I think. The full idea is in http://allmydata.org/~zooko/lafs.pdf but I will present it here for your enjoyment (I should emphasize that I played no part in any of the development of this idea, I just read his PDF). Apologies in advance for any misunderstandings or misrepresentations I make. I also want to apologize for using the term secret key rather than Zooko's preferred private key so that we can call it SK and then the public key is PK. The semi-private key will be SPK. Below, ^ refers to repeated iteration of the group operation, in a given group. With most public key systems, knowing the SK allows you to deduce the PK, but of course you can't go the other direction: SK - PK PK /- SK Zooko wishes to introduce an intermediate data structure, the semi-private key or SPK, which fits in between: SK - SPK SPK - PK PK /- SPK SPK /- SK From the SK you can deduce the SPK, and from the SPK the PK, but you can't go backwards. The reason for this is he wants to issue signatures with the SK which can be verified by people holding the SPK and by (different) people holding the PK; and further he wants to be able to create an encryption key from the SPK, which will (therefore) also be known to the holder of the SK, but not to holders of the PK. In this way the holder of an SK can have two groups of verifiers: PK holders can check signatures but not read data, while SPK holders can both check signatures and read data. The part that makes this interesting is that it is desired that all of SK, SPK and PK are as small as possible for a given security level. This is because of the goal in the Tahoe object-capability distributed file system of using these keys as identifiers for files. There would be 3 different identifiers for a file in this system, corresponding to the SK, SPK and PK associated with that file, and each identifier would give the different levels of cryptographic access described above. If we didn't have this requirement, we could solve it trivially by augmenting the SK with an ordinary encryption key k, and defining SPK as (PK,k). Then the information arrows above would be met. But we have increased the SK and SPK key sizes by the size of k, which may be a very substantial percentage when we are dealing with EC keys. Zooko proposes a specific alternative in his paper, a modification of DSA (equivalently, ECDSA). In ordinary DSA, SK is a secret exponent x in some group, and PK is g^x for some generator g of the group. Zooko defines: y = H(g^x) using hash function H and proposes that: SK is xy SPK is g^x PK is g^(xy) It is easy to see that this satisfies the information arrows SK - SPK - PK. There are no obvious ways to go the other way, but analysis is needed to verify that. As far as key size, neither SK nor PK gets any bigger, and SPK is the same size as PK. DSA signatures are then done in the usual way, using xy in place of the usual secret exponent x. For reference, and slightly simplified, the usual DSA formulas are: r = g^k for some random k; s is derived from sk * rx = h (mod the group order) where h is the message hash. Then Zooko's modification merely replaces x by xy (keep in mind that sometimes y is defined as the public key g^x in DSA descriptions, but here y is different, y = H(g^x)): r = g^k for some random k; s is derived from sk * rxy = h (mod the group order) Zooko asks for cryptographic community review of this proposal. I believe I can sketch a couple of simple proofs in the random oracle model that being able to forge signatures, knowing either SK or SPK, would allow forging ordinary DSA. This message is getting pretty long though, so perhaps others will wish to chime in. The remaining questions are whether PK /= SPK holds, and SPK /= SK. The second part is easily shown to reduce to discrete log. Suppose we have an oracle which, given g^x, produces x*H(g^x). Then we can just divide by H(g^x) and get x, turning it into a discrete log oracle. The first is equivalent to: knowing g^(xy) is it impossible to deduce g^x, where y = H(g^x). Define Y = g^x, then y = H(Y) and g^(xy) = Y^H(Y). The question is then: Given Y^H(Y) can we deduce Y? Ideally we'd like to show that an oracle that could solve this could be used to find arbitrary discrete logs or break some other standard assumption, but I can't see how to do it. (I also can't see how to go the other way, from a discrete log oracle to something that can solve this - seems like a hard problem.) Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: MD6 withdrawn from SHA-3 competition
Rivest: Thus, while MD6 appears to be a robust and secure cryptographic hash algorithm, and has much merit for multi-core processors, our inability to provide a proof of security for a reduced-round (and possibly tweaked) version of MD6 against differential attacks suggests that MD6 is not ready for consideration for the next SHA-3 round. But how many other hash function candidates would also be excluded if such a stringent criterion were applied? Or turning it around, if NIST demanded a proof of immunity to differential attacks as Rivest proposed, how many candidates have offered such a proof, in variants fast enough to beat SHA-2? Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 in 2**52
Differential Path for SHA-1 with complexity O(2**52) Cameron McDonald, Philip Hawkes, and Josef Pieprzyk Macquarie University http://eprint.iacr.org/2009/259.pdf I wonder now with this new improved differential path if any distributed computations may be forming to finally create a SHA-1 collision? (I have a small side bet resting on the outcome...) I checked http://boinc.iaik.tugraz.at/ this morning, a distributed SHA-1 collision search whichhad been going on since 2007 based on a method with an estimated cost of 2^60+. However I see that the project page announces that the effort has been suspended as of May 12, 2009 due to lack of progress. I wonder if the suspension may also be related to this new method, reports of which had begun to leak out by that time. 2^52 work should lower the bar substantially, although it would still be a major task for a single organization. It would be great if the authors of the improved path could be the ones to announce a collision, but it sounds like they are more theoretically than practically oriented: We believe that practical collisions are now within reach of a dedicated system. We are continuing our search for more differential paths with a maximum number of auxiliary paths. (Rather than, we are abandoning our search for more differential paths and working to try to find a real collision using this one. ;) Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Popular explanation of fully homomorphic encryption wanted
Udhay Shankar N quotes wikipedia: The question was finally resolved in 2009 with the development of the first true fully homomorphic cryptosystem. The scheme, constructed by Craig Gentry, employs lattice based encryption and allows evaluation of both addition and multiplication operations without restriction.[2] 2. ^ Craig Gentry. On homomorphic encryption over circuits of arbitrary depth. In the 41st ACM Symposium on Theory of Computing (STOC), 2009. A URL for this paper is http://portal.acm.org/citation.cfm?id=1536414.1536440 but you will have to be an ACM member to download it. I was able to get a copy this morning and quickly skimmed it. This is IMO one of the most remarkable crypto papers ever. Not only does it solve one of the oldest open problems in cryptography, the construction of a fully homomorphic encryption system, it does so by means of a self-embedding technique reminiscent of Godel's theorem. Craig Gentry starts off by inventing a limited homomorphic encryption system based on lattice encryption. For full homomorphism you want to do both add and multiply - or expressed on bits, XOR and AND. Think of your operation as a circuit made up of XOR and AND gates, then the limiting factor in previous work has been the number of ANDs. While many schemes have been found that do just XORs, and at least one that could do a very limited number of ANDs, the new scheme allows you to go deeper. In lattice encryption, there is a multi-dimensional lattice of points that have a hidden structure. Encryption puts you near a point on the lattice, and decryption involves finding that point. But without knowing the hidden structure, attackers can't tell which one is closest. In the new homomorphic lattice encryption, AND operations cause the error term to increase. After too many of them, too deep a circuit, the error term grows up to roughly half the distance between lattice points, and decryption is no longer possible. So you have a limited depth homomorphic encryption system. By itself this is a substantial advance. But now for the amazing Godelian trick. The error term has grown and any more operations will make decryption impossible. So Craig Gentry proposes to allow the server (which is working on data encrypted under a key controlled by the client) to decrypt the data - *homomorphically*. If the data is encrypted by client key pk1, the client has also supplied the server a second key pk2, and also a version of the pk1 *secret key* encrypted under pk2. Since pk2 is homomorphic, the server can compute a circuit using the encrypted secret pk1 key just like it can compute any other circuit on encrypted data. The result is that the server ends up with an encryption of the original ciphertext under pk2 instead of under pk1, and because lattice decryption in effect performs error correction, the error term is reduced and we are ready for more. The key idea here is that the homomorphic encryption system has to allow enough homomorphic depth that *its own decryption algorithm* can be expressed as a circuit that fits within what can be handled homomorphically. This is quite difficult and most of the paper is taken up with constructing such a cryptosystem and proving its properties. The resulting scheme is apparently not practical (at one point he mentions that the secret key bits have to be expressed in *unary*) but it is still amazing that it is even possible. Again I have to go back to Godel's and Turing's work to think of a comparable example exploiting the power of self-embedding. In its most basic form, then, the client must supply a set of public keys pk1, pk2, ... with each key's private part encrypted under the next key; the number of such keys would be proportional to the depth of the circuit to be evaluated. However the paper then points out that given reasonable assumptions, you can dispense with the whole set and make it a loop, even a loop of one: that is, you encrypt pk1's private key under pk1, and stick with pk1 through the whole encryption, including the magical homomorphic decryption circuit evaluation. In this form it is the pure, fully homomorphic encryption system which has been so long sought. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Shamir secret sharing and information theoretic security
Is it possible that the amount of information that the knowledge of a sub-threshold number of Shamir fragments leaks in finite precision setting depends on the finite precision implementation? For example, if you know 2 of a 3 of 5 splitting and you also know that the finite precision setting in which the fragments will be used is IEEE 32-bit floating point or GNU bignum can you narrow down the search for the key relative to knowing no fragments and nothing about the finite precision implementation? No, not really. Think of this simple example. We will have two shares, x and y. Let's work mod 10 to make it simple. The secret value v will be x + y mod 10. The shares are created by choosing a random value for x, and then setting y to be v - x mod 10. So for example if you want to share v = 5, and x is 9, then y will be 6: 9 + 6 = 5 mod 10. Suppose that you happen to know from other information that the secret value v is either 1 or 2. Now you learn a share value x = 5. How much have you learned about v? Nothing: you can deduce that y is either 6 or 7, but you have no way of knowing which. Whatever x had turned out to be, there would be a y value corresponding to each possible v value. Learning a share tells you nothing about v, and in general Shamir sharing, learning all but one of the needed shares similarly tells you nothing about the secret. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Proof of Work - atmospheric carbon
certificate of validity. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Bitcoin v0.1 released
Jonathan Thornburg writes: In the modern world, no major government wants to allow untracable international financial transactions above some fairly modest size thresholds. (The usual catch-phrases are things like laundering drug money, tax evasion, and/or financing terrorist groups.) To this end, electronic financial transactions are currently monitored by various governments their agencies, and any but the smallest of transactions now come with various ID requirements for the humans on each end. But if each machine in a million-node botnet sends 10 cents to a randomly chosen machine in another botnet on the other side of the world, you've just moved $100K, in a way that seems very hard to trace. To me, this means that no major government is likely to allow Bitcoin in its present form to operate on a large scale. Certainly a valid point, and one which has been widely discussed in the debates over the years about electronic cash. Bitcoin has a couple of things going for it: one is that it is distributed, with no single point of failure, no mint, no company with officers that can be subpoenaed and arrested and shut down. It is more like a P2P network, and as we have seen, despite degrees of at least governmental distaste, those are still around. Bitcoin could also conceivably operate in a less anonymous mode, with transfers being linked to individuals, rather than single-use keys. It would still be useful to have a large scale, decentralized electronic payment system. It also might be possible to refactor and restructure Bitcoin to separate out the key new idea, a decentralized, global, irreversible transaction database. Such a functionality might be useful for other purposes. Once it exists, using it to record monetary transfers would be a sort of side effect and might be harder to shut down. I also worry about other domestic ways nasty people could exploit a widespread Bitcoin deployment: * Spammer botnets could burn through pay-per-send email filters trivially (as usual, the costs would fall on people other than the botnet herders spammers). * If each machine in a botnet sends 1 cent to a herder, that can add up to a significant amount of money. In other words, Bitcoin would make botnet herding and the assorted malware industry even more profitable than it already is. It's important to understand that the proof-of-work (POW) aspect of Bitcoin is primarily oriented around ensuring the soundness of the historical transaction database. Each Bitcoin data block records a set of transactions, and includes a hash collision. Subsequent data blocks have their own transactions, their own collisions, and also chain to all earlier hashes. The result is that once a block is buried under enough new blocks, it is essentially certain (given the threat model, namely that attackers cannot muster more than X% of the compute power of legitimate node operators) that old transactions can't be reversed. Creating new coins is indeed currently also being done by POW, but I think that is seen as a temporary expedient, and in fact the current software phases that out over several years. Hence worries about botnets being able to manufacture large quantities of POW tokens are only a temporary concern, in the context of Bitcoin. There have been a number of discussions in the past about POW tokens as anti spam measures, given the botnet threat. References are available from Proof-of-work system on Wikipedia. Analyses have yielded mixed results, depending on the assumptions and system design. If POW tokens do become useful, and especially if they become money, machines will no longer sit idle. Users will expect their computers to be earning them money (assuming the reward is greater than the cost to operate). A computer whose earnings are being stolen by a botnet will be more noticeable to its owner than is the case today, hence we might expect that in that world, users will work harder to maintain their computers and clean them of botnet infestations. Countermeasures by botnet operators would include moderating their take, perhaps only stealing 10% of the productive capacity of invaded computers, so that their owners would be unlikely to notice. This kind of thinking quickly degenerates into unreliable speculation, but it points out the difficulties of analyzing the full ramifications of a world where POW tokens are valuble. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Bitcoin v0.1 released
Satoshi Nakamoto writes: Announcing the first release of Bitcoin, a new electronic cash system that uses a peer-to-peer network to prevent double-spending. It's completely decentralized with no server or central authority. See bitcoin.org for screenshots. Download link: http://downloads.sourceforge.net/bitcoin/bitcoin-0.1.0.rar Congratulations to Satoshi on this first alpha release. I am looking forward to trying it out. Total circulation will be 21,000,000 coins. It'll be distributed to network nodes when they make blocks, with the amount cut in half every 4 years. first 4 years: 10,500,000 coins next 4 years: 5,250,000 coins next 4 years: 2,625,000 coins next 4 years: 1,312,500 coins etc... It's interesting that the system can be configured to only allow a certain maximum number of coins ever to be generated. I guess the idea is that the amount of work needed to generate a new coin will become more difficult as time goes on. One immediate problem with any new currency is how to value it. Even ignoring the practical problem that virtually no one will accept it at first, there is still a difficulty in coming up with a reasonable argument in favor of a particular non-zero value for the coins. As an amusing thought experiment, imagine that Bitcoin is successful and becomes the dominant payment system in use throughout the world. Then the total value of the currency should be equal to the total value of all the wealth in the world. Current estimates of total worldwide household wealth that I have found range from $100 trillion to $300 trillion. With 20 million coins, that gives each coin a value of about $10 million. So the possibility of generating coins today with a few cents of compute time may be quite a good bet, with a payoff of something like 100 million to 1! Even if the odds of Bitcoin succeeding to this degree are slim, are they really 100 million to one against? Something to think about... Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: MD5 considered harmful today
Re: http://www.win.tue.nl/hashclash/rogue-ca/ Key facts: - 6 CAs were found still using MD5 in 2008: RapidSSL, FreeSSL, TC TrustCenter AG, RSA Data Security, Thawte, verisign.co.jp. Out of the 30,000 certificates we collected, about 9,000 were signed using MD5, and 97% of those were issued by RapidSSL. RapidSSL was used for the attack. - The attack relies on cryptographic advances in the state of the art for finding MD5 collisions from inputs with different prefixes. These advances are not yet being published but will presumably appear in 2009. - The collision was found using Arjen Lenstra's PlayStation Lab and used 200 PS3s with collectively 30 GB of memory. The attack is in two parts, a new preliminary birthdaying step which is highly parallelizable and required 18 hours on the PS3s, and a second stage which constructs the actual collision using 3 MD5 blocks and runs on a single quad core PC, taking 3 to 10 hours. - The attack depends on guessing precisely the issuing time and serial number of the good certificate, so that a colliding rogue certificate can be constructed in advance. The time was managed by noting that the cert issuing time was reliably 6 seconds after the request was sent. The serial number was managed because RapidSSL uses serially incrementing serial numbers. They guessed what serial number would be in use 3 days hence, and bought enough dummy certs just before the real one that hopefully the guessed serial number would be hit. - The attacks were mounted on the weekend, when cert issuance rates are lower. It took 4 weekends before all the timing and guessing worked right. The cert was issued November 3, 2008, and the total cert-purchase cost was $657. - The rogue cert, which has the basicConstraints CA field set to TRUE, was intentionally back-dated to 2004 so even if the private key were stolen, it could not be misused. My take on this is that because the method required advances in cryptography and sophisticated hardware, it is unlikely that it could be exploited by attackers before the publication of the method, or the publication of equivalent improvements by other cryptographers. If these CAs stop issuing MD5 certs before this time, we will be OK. Once a CA stops issuing MD5 certs, it cannot be used for the attack. Its old MD5 certs are safe and there is no danger of future successful attacks along these lines. As the paper notes, changing to using random serial numbers may be an easier short-term fix. Therefore the highest priority should be for the six bad CAs to change their procedures, at least start using random serial numbers and move rapidly to SHA1. As long as this happens before Eurocrypt or whenever the results end up being published, the danger will have been averted. This, I think, is the main message that should be communicated from this important result. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Bitcoin P2P e-cash paper
this in its stride. A very good point, and a more complete specification is necessary in order to understand how the network will respond to imperfections like this. I am looking forward to seeing more detail emerge. One thing I might mention is that in many ways bitcoin is two independent ideas: a way of solving the kinds of problems James lists here, of creating a globally consistent but decentralized database; and then using it for a system similar to Wei Dai's b-money (which is referenced in the paper) but transaction/coin based rather than account based. Solving the global, massively decentralized database problem is arguably the harder part, as James emphasizes. The use of proof-of-work as a tool for this purpose is a novel idea well worth further review IMO. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Bitcoin P2P e-cash paper
Bitcoin seems to be a very promising idea. I like the idea of basing security on the assumption that the CPU power of honest participants outweighs that of the attacker. It is a very modern notion that exploits the power of the long tail. When Wikipedia started I never thought it would work, but it has proven to be a great success for some of the same reasons. I also do think that there is potential value in a form of unforgeable token whose production rate is predictable and can't be influenced by corrupt parties. This would be more analogous to gold than to fiat currencies. Nick Szabo wrote many years ago about what he called bit gold[1] and this could be an implementation of that concept. There have also been proposals for building light-weight anonymous payment schemes on top of heavy-weight non-anonymous systems, so Bitcoin could be leveraged to allow for anonymity even beyond the mechanisms discussed in the paper. Unfortunately I am having trouble fully understanding the system. The paper describes key concepts and some data structures, but does not clearly specify the various rules and verifications that the participants in the system would have to follow. In particular I don't understand exactly what verifications P2P nodes perform when they receive new blocks from other nodes, and how they handle transactions that have been broadcast to them. For example, it is mentioned that if a broadcast transaction does not reach all nodes, it is OK, as it will get into the block chain before long. How does this happen - what if the node that creates the next block (the first node to find the hashcash collision) did not hear about the transaction, and then a few more blocks get added also by nodes that did not hear about that transaction? Do all the nodes that did hear it keep that transaction around, hoping to incorporate it into a block once they get lucky enough to be the one which finds the next collision? Or for example, what if a node is keeping two or more chains around as it waits to see which grows fastest, and a block comes in for chain A which would include a double-spend of a coin that is in chain B? Is that checked for or not? (This might happen if someone double-spent and two different sets of nodes heard about the two different transactions with the same coin.) This kind of data management, and the rules for handling all the packets that are flowing around is largely missing from the paper. I also don't understand exactly how double-spending, or cancelling transactions, is accomplished by a superior attacker who is able to muster more computing power than all the honest participants. I see that he can create new blocks and add them to create the longest chain, but how can he erase or add old transactions in the chain? As the attacker sends out his new blocks, aren't there consistency checks which honest nodes can perform, to make sure that nothing got erased? More explanation of this attack would be helpful, in order to judge the gains to an attacker from this, versus simply using his computing power to mint new coins honestly. As far as the spending transactions, what checks does the recipient of a coin have to perform? Does she need to go back through the coin's entire history of transfers, and make sure that every transaction on the list is indeed linked into the timestamp block chain? Or can she just do the latest one? Do the timestamp nodes check transactions, making sure that the previous transaction on a coin is in the chain, thereby enforcing the rule that all transactions in the chain represent valid coins? Sorry about all the questions, but as I said this does seem to be a very promising and original idea, and I am looking forward to seeing how the concept is further developed. It would be helpful to see a more process oriented description of the idea, with concrete details of the data structures for the various objects (coins, blocks, transactions), the data which is included in messages, and algorithmic descriptions of the procedures for handling the various events which would occur in this system. You mentioned that you are working on an implementation, but I think a more formal, text description of the system would be a helpful next step. Hal Finney [1] http://unenumerated.blogspot.com/2005/12/bit-gold.html - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: privacy in public places
It is hard to argue with Perry's point that privacy in public is an endangered species at best. Suggesting that one confine one's illegal actions to the virtual world is not a particularly appealing response. Robin Hanson considered the problem in this article from back in the 1990s, a response to the heyday of the Cypherpunks: http://hanson.gmu.edu/privacy.html He argued that virtual privacy would not be an adequate substitute for the loss of physical privacy, that people would not be willing to make the sacrifices necessary for a fully anonymous (or pseudonymous) online existence. It's possible nevertheless that online substitutes for many questionable physical activities may arise. People don't need to shop at adult bookstores any more, porn being widely available online. Instructions on making or growing your own drugs can also be found. Not everything we do in the physical world can yet be virtualized but perhaps with increased recognition of the problem, more substitutes will become available. You don't have to buy into the Cypherpunk picture of a set of fully protected nyms using Chaumian credentials to transfer attributes, in order to benefit still from the relatively large degree of anonymity and privacy available online. It may also be helpful to focus more directly on specific harms and specific limitations rather than the rather vague and general issue of privacy and its intangible benefits. Scientific American has a number of articles on this topic in its most recent issue. http://www.sciam.com/sciammag (Also includes a nice article by Anna Lysyanskaya on cryptographic credentials BTW. Her work with Jan Camenisch on this topic remains state of the art for those who still retain hope for the technology. TPM DAA is based on CL signatures and ironically may become the first widely fielded use of anonymous credentials.) Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
I wrote: Looking a little more closely, I found this paper by Patarin from Crypto 2005 which describes security bounds for higher round Feistel constructions: http://www.springerlink.com/content/gtcabev3ucv8apdu/ I was wrong, this was from Crypto 03. And as Eric Rescorla has already pointed out, Patarin had an improved the result the following year where he showed that 6 rounds was sufficient for security. Greg Rose wrote: So, you don't have a 133-bit block cipher lying around? No worries, I'll sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit block cipher like AES. To encrypt, do: 1. Encrypt the first 128 bits (ECB mode) 2. Encrypt the last 128 bits (also ECB mode). Hal Finney wrote: I am not familiar with the security proof here, do you have a reference? Or is it an exercise for the student? It's a degenerate case of Rivest's All-or-nothing transform (which applies to larger, multi-block blocks, if you know what I mean :-) ). I believe he gave a security proof, some 6ish years ago. But I could be confabulating. Hmmm, looking at Rivest's package transform which was his original proposal for an AONT, that seems to be different and actually expanded the message size. I haven't been able to find an AONT which is quite like this. One limitation with this proposal is that it appears that it will only be as strong as the size of the overlapping region. However in this case the overlap is 128-5 or 123 bits, so the birthday bound will be about 2^62 rather than the ideal 2^64, and that is hardly noticeable. So it does seem like it could be a good choice here. Doing a little over 3 AES encryptions will be much better than the 6 which seem to be necessary for the Feistel approach. However such a substantial improvement certainly makes a proof of security more interesting. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Philipp Gühring writes: I am searching for symmetric encryption algorithms for decimal strings. Let's say we have various 40-digit decimal numbers: 2349823966232362361233845734628834823823 3250920019325023523623692235235728239462 0198230198519248209721383748374928601923 As far as I calculated, a decimal has the equivalent of about 3,3219 bits, so with 40 digits, we have about 132,877 bits. Right, although as an American I was confused for a moment until I remembered the European convention of using comma for the decimal point, while we use period. But you are right and it was my mistake. Now I would like to encrypt those numbers in a way that the result is a decimal number again (that's one of the basic rules of symmetric encryption algorithms as far as I remember). Since the 132,877 bits is similar to 128 bit encryption (like eg. AES), I would like to use an algorithm with a somewhat comparable strength to AES. But the problem is that I have 132,877 bits, not 128 bits. And I can't cut it off or enhance it, since the result has to be a 40 digit decimal number again. This is a very common question. Unfortunately the state of the art in cryptography does not as far as I know have a good answer. The most recent analysis I found is http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf from CT-RSA 2002 by Black and Rogaway. Basically they propose what is called a Luby-Rackoff construction, related to another construction called a Feistel network. Unfortunately their analysis does not show that this is secure, but I believe that by adding more steps it can be made so. The idea is to start with your 40 digit number and split it into two parts of 20 digits. Call the left part L and the right part R. Then repeatedly execute the following steps: L = (L xor AES(R)) mod 10^20 (L,R) = (R,L) (i.e. interchange L and R) After doing this a certain number of steps, interchange L and R one last time, and concatenate L and R to get your output. (Equivalently, skip the interchange of L and R on the last step.) Now, it is important in doing this that AES have a different key for each round or step. You can start with a single key K, and generate the round keys as K0 = AES(K,0), K1 = AES(K,1), K2 = AES(K,2), and so on. To decrypt, the same basic process is used. But this time, use the round keys in the reverse order. Instead of K0, K1, K2, use K2, K1, K0. Black and Rogaway analyzed for just 3 rounds, and they found basically that for your case, this construction would only have about 32 bits of strength; that is, after encrypting about 4 billion numbers, you would be losing security. If you are only ever encrypting many fewer numbers than this (with a given key), it should probably be OK. The other possibility is to increase the number of rounds. The paper hints that this will help but does not offer any specific analysis. I saw a speculative comment online that 8 rounds would be strong. I believe that going back to the Luby-Rackoff paper may offer some guidance, but I don't have time to do that now. Note that this unfortunately does not get the benefit you were hoping for from being so close to the AES block size. While there are some known tricks for dealing with being a little shorter than the cipher block, I couldn't find any good ones for being a few bits longer. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
I like Greg Rose's solution best: There is a fairly standard technique for handling things like this. 1. encode your number N into a 133-bit string S 2. encrypt S with your favourite 133-bit block cipher (see below) 3. decode S to a number N' 4. if N' = 10^40, goto 2 (that is, re-encrypt until it is in range) 5. N' is your answer. This is Rich Schroeppel's trick from his Hasty Pudding cipher, a somewhat under-rated AES submission IMO. HPC originated not only this trick, but also the idea of tweakable encryption, which has turned out to be important for disk encryption. The Black-Rogaway paper referenced earlier has a proof of security of this construction. So, you don't have a 133-bit block cipher lying around? No worries, I'll sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit block cipher like AES. To encrypt, do: 1. Encrypt the first 128 bits (ECB mode) 2. Encrypt the last 128 bits (also ECB mode). I didn't understand this at first, but I finally saw that the point is to do the encryptions in-place; step 1 replaces the first 128 bits of the data with the encryption, and similarly for step 2. This is equivalent to doing CBC mode with a fixed IV of 0, and ciphertext stealing for the final partial block of 5 bits. To decrypt, do decryptions in the reverse order, obviously. It's easy to see that this is a secure permutation if AES itself is, depending on your definition of secure; if you add a third step, to re-encrypt the first 128 bits, it is truly secure. (Without the third step, tweaking a bit in the first 5 bits will often leave the last 5 unchanged on decryption, which is clearly a distinguishing attack; the third encryption makes it an all-or-nothing transform.) I am not familiar with the security proof here, do you have a reference? Or is it an exercise for the student? Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
The MD6 hash function (rough notes)
. However Adi Shamir stood up and expressed concern that his new Cube attack might apply. Rivest seemed confident that the degree of MD6 would be several thousand, which should be safe from Shamir's attack, but time will tell. Apologies again to the enormous number of authors if I have any serious errors above. And thanks to Ron Rivest for publicizing this hash design several months before the due date (October 31), potentially giving an advantage to his competitotrs. He emphasized that his goal is to produce the best possible outcome for the whole process. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: OpenID/Debian PRNG/DNS Cache poisoning advisory
[I feel a little uncomfortable replying with such a wide distribution!] Getting browsers, or OpenID installations, to check CRLs or use OCSP to check for freshness is likely to be slow going. At this point I think the momentum still favors fixing the remaining DNS systems that are vulnerable to cache poisoning. This turnkey-MITM bug makes OpenSSL bad certs far more exploitable, as Dan Kaminsky pointed out in his report. OpenID is just one example of many where this is going to keep happening as long as DNS is unpatched. I thought of one possible mitigation that can protect OpenID end users against remote web sites which have not patched their DNS. OpenID providers who used weak OpenSSL certs would have to change their URLs so that their old X.509 CA certs on their old URLs no longer work on the new ones. This will require all of their clients (users who log in with their OpenID credentials) to change their identifiers. DNS based MITMs will not be able to forge messages related to the new identifiers. Customers can be alerted to this requirement as soon as they log in to a web site (relying party) whose DNS is NOT hacked; the redirection to the OpenID provider will give opportunity to notify the customer of the name change. Making this change may be somewhat inconvenient, but since OpenID is a relatively new standard, at least it is easier than would be the case with a more established protocol. In the other direction of attack, the end user's DNS is poisoned and he gets redirected to a bogus site in place of the OpenID provider; that site is then able to provide a valid SSL certificate due to the OpenSSL weakness, thereby stealing whatever authentication credentials the user normally sends to his OpenID provider. This is one instance of the general attack where a user is DNS-misdirected to a bogus copy of a secure site which unfortunately used weak OpenSSL based certs. Again, I see fixing the DNS as the path of least resistance here, especially so since the end user is the one bearing most of the risk, typically DNS is provided by an ISP or some other agency with a formal legal relationship, and there is the possibility of liability on the part of the lax DNS provider. Hopefully we will continue to see rapid uptake of the DNS fix over the next few weeks. That still leaves weak-cert OpenID users vulnerable to DNS-unpatched service providers (OpenID relying parties), and that is where my proposed mitigation above comes in. By renaming its URLs, an OpenID provider who had the misfortune to create a weak OpenSSL cert (through no fault of its own) can save its end users considerable potential grief. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On the randomness of DNS
Ben Laurie writes: Oh, and I should say that number of ports and standard deviation are not a GREAT way to test for randomness. For example, the sequence 1000, 2000, ..., 27000 has 27 ports and a standard deviation of over 7500, which looks pretty GREAT to me. But not very random. That's a good point, Ben. Dan Kaminsky's DNS tester at http://www.doxpara.com/ does include output like this: Your name server, at 1.2.3.4, appears to be safe, but make sure the ports listed below aren't following an obvious pattern (:1001, :1002, :1003, or :3, :30020, :30100...). Requests seen for dae687514c50.doxdns5.com: 1.2.3.4:34023 TXID=64660 1.2.3.4:50662 TXID=51678 1.2.3.4:55984 TXID=49711 1.2.3.4:17745 TXID=12263 1.2.3.4:26318 TXID=59610 This shows only the last 5 ports so it won't detect an LCG, but at least it can detect some of the more obvious patterns. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Strength in Complexity?
There are, of course, obstacles that must still be overcome by EKMI proponents. For example, the proposed components are somewhat simple by design, which concerns some encryption purists who prefer more complex protocols, on the logic that they're more difficult to break into. Let me first say that from the discussion here I now get the impression that this is how criticism of the EKMI spec is being characterized by its supporters. Their critics are encryption purists. I'm not sure what that means but it sounds kind of like people who believe in security over simplicity. An example where this concern might arise would be an overly simplistic protocol that used AES in ECB mode - simple by design, while the encryption purist advocated GCM, more difficult to break into but more complex. Now, I'm sure EKMI is not doing things this way but it is an example where simple would not look good to encryption purists. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The perils of security tools
Ben Laurie alerts us to the recent bug in Debian distributions of OpenSSL which caused the RNG to have almost no entropy. The distribution mistakenly commented out the call that added seeding and most other sources of entropy to the RNG state. This is requiring many keys to be re-issued. One of the more unfortunate aspects of this bug is that it affects not only keys generated on systems with the weak RNG, but also even securely generated DSA keys, if the keys were used for signing on systems with the bug. DSA keys are vulnerable to weak RNGs not only at keygen time but at any later time that signatures are created. This causes those keys to be far more vulnerable to problems in RNGs. The reason is the DSA signature equation sk - xr = h, where h is the message hash, r and s are signature components, x is the private key, and k is a random value chosen uniquely per message. If k is guessable, as potentially was the case with this recent bug, then x can be deduced since the other values are typically sent in the clear. A simple trick can be used to help immunize DSA signatures against these kinds of failures. I first learned of this idea many years ago from Phil Zimmermann, and a varient has been used for a long time in PGP and probably other code, but aparently not OpenSSL. The idea is to base the random k not just on the output of your RNG, but also on the private key x. Something like: k = hash (x, rng()). Of course it is still necessary that k be uniformly distributed mod q (the DSA subgroup prime order), so this can't be just a straight hash. It might be a separate PRNG instance which gets seeded with the data values shown. But the idea is to mix in the secret key value, x, in addition to data from the RNG. In this way, if the rng data is predictable but the secret key is unknown, k should still be unguessable. And if your mixing function is good then this should not leak any information about x, especially in the usual case where the rng is of good quality. A variant on this idea protects against a separate problem, where k is unguessable but somehow the same k value is used for two separate signatures. This again lets the attacker deduce x because he will observe two instances of the DSA signature equation above, with all values known except k and x, and since k is the same, this is two equations with two unknowns and allows recovering both values. To immunize against this failure, include the message hash h in the mixing function that generates k: k = hash (x, h, rng()). Now, if the RNG does produce identical output, h will typically differ among signatures, again producing unique and unguessable k values. And if h is the same for two messages in this form, k will be the same, but then r and s will be the same as well, and the second signature will be an exact match of the first and not leak new information. I think these techniques are widely known among implementors but I did not see them in HAC so I thought it was worth reminding the community here. OpenSSL is such a widely used crypto library that it would be especially valuable for it to consider incorporating these mechanisms. It would have saved some considerable pain as administrators who use OpenSSH (which depends on OpenSSL) DSA keys now are forced to consider whether they may be vulnerable to the bug even if their primary servers were not exposed to it, since any client out there may have generated insecure signatures and inadvertantly revealed secret keys. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RNG for Padding
Mr Pink writes: In Applied Crypto, the use of padding for CBC encryption is suggested to be met by ending the data block with a 1 and then all 0s to the end of the block size. Is this not introducing a risk as you are essentially introducing a large amount of guessable plaintext into the ciphertext. Is it not wiser to use RNG data as the padding, and using some kind of embedded packet size header to tell the system what is padding? Back in 2001, there was a discussion of the general issue of altering data structures to avoid known plaintext on sci.crypt, under the subject of Known Plaintext Considered Harmless. A surprising diversity of opinions were expressed. http://groups.google.com/group/sci.crypt/browse_thread/thread/f1aae3a2d10dbcd4?tvc=2q=known+plaintext+considered+harmless Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Jeff Hodges wrote: It turns out the supplied default for p is 1024 bit -- I'd previously goofed when using wc on it.. DCF93A0B883972EC0E19989AC5A2CE310E1D37717E8D9571BB7623731866E61EF75A2E27898B057 F9891C2E27A639C3F29B60814581CD3B2CA3986D2683705577D45C2E7E52DC81C7A171876E5CEA7 4B1448BFDFAF18828EFD2519F14E45E3826634AF1949E5B535CC829A483B8A76223E5D490A257F0 5BDFF16F2FB22C583AB This p is a strong prime, one where (p-1)/2 is also a prime, a good property for a DH modulus. The generator g=2 generates the entire group, which is an OK choice. It means that one bit of the shared secret is leaked (whether or not it is a quadratic residue, i.e. whether the discrete log of the number is even or odd). But that shouldn't matter, the shared secret should be hashed and/or used as the seed of a PRNG to generate further keys. The main problem as I said is that 1024 bit moduli are no longer considered sufficiently safe for more than casual purposes. Particularly with discrete logs that use a widely-shared modulus like the one above, it would not be surprising to see it publicly broken in the next 5-10 years, or perhaps even sooner. And if a public effort can accomplish it in a few years, conservatively we should assume that well funded secret efforts could already succeed today. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Hi Jeff - How wise (in a real-world sense) is it, in a protocol specification, to specify that one simply obtain an ostensibly random value, and then use that value directly as the signature key in, say, an HMAC-based signature, without any further stipulated checking and/or massaging of the value before such use? I think it's OK, as long as it is understood that the random number generator should be of good quality. If it is not, I don't know that checking and/or massaging will help much. E.g., here's such a specfication excerpt and is absolutely everything said in the spec wrt obtaining said signature keys: When generating MAC keys, the recommendations in [RFC1750] SHOULD be followed. One point, RFC1750 has been superceded by RFC4086. ... The quality of the protection provided by the MAC depends on the randomness of the shared MAC key, so it is important that an unguessable value be used. How (un)wise is this, in a real-world sense? It seems pretty reasonable to me. They are referring to an RFC with lots of good advice about random number generators, and they emphasize that the key value should be unguessable. It's probably out of scope to go into a lot more detail than that. Referring to other standards like RFC1750/4086 is the right way to handle this kind of issue. [yes, I'm aware that using a only a SHOULD here leaves a huge door open compliance-wise, but that's a different issue] I am the co-author of the OpenPGP Standard, RFC4880. All we say is: The sending OpenPGP generates a random number to be used as a session key for this message only. and * Certain operations in this specification involve the use of random numbers. An appropriate entropy source should be used to generate these numbers (see [RFC4086]). Not all that different in thrust than the spec you are looking at. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Jeff Hodges writes: If a purportedly secure protocol employing a nominal DH exchange in order to establish a shared secret key between a requester and responder, employs widely known published (on the web) fixed values for g (2) and p (a purportedly prime 1040 bit number) for many of it's implementations and runtime invocations, what are the risks its designers are assuming with respect to the resultant properties of ZZ? This can be reasonably safe, if p is chosen properly. There is no problem with using g=2, with the right p. The main issue is that with current technology, a 1040 bit p stands a substantial chance of being broken. A 1024 bit special-form number was factored last year, with claims that the technique might apply to general RSA moduli of that size. Finding discrete logs takes similar work. A widely reused p value would be a fat target for such an effort. I suspect that many implementations will simply use the equivalent of whatever rand() function is available to get the bits for their private keys directly, and will likely not reallocate private keys unless the implementation or machine are restarted. So if the random number generator has known flaws, then there may be some predictability in both the public keys and in ZZ, yes? Additionally there's the previously noted issue with the values of static private keys slowly leaking. I'm not sure about this leaking, I asked Ashwood for clarification. Certainly if the secret exponents are poorly chosen, the system will be insecure. I would not necessarily assume that rand() is being used; I would hope in this day and age that people would know better than that. /dev/random on LinuxMac and CryptGenRandom on Windows should provide adequate security for this use, and hopefully the implementors would be aware of the need for secure random numbers. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: questions on RFC2631 and DH key agreement
Joseph Ashwood writes, regarding unauthenticated DH: I would actually recommend sending all the public data. This does not take significant additional space and allows more verification to be performed. I would also suggest looking at what exactly the goal is. As written this provides no authentication just privacy, and if b uses the same private key to generate multiple yb the value of b will slowly leak. I'm not familiar with this last claim, that the value of b's private key (presuming that is what you mean) would slowly leak if it were reused for many DH exchanges. Can you explain what you mean? Are you talking about LimLee style attacks where the recipient does not check the parameters for validity? In that case I would say the private exponent would leak quickly rather than slowly. But if the parameters are checked, I don't see how that would leak a reused exponent. You can then use the gpb trio for DSA, leveraging the key set for more capabilities. Presuming here you mean (g,p,q) as suitable for reuse. This raises the question, is the same set of (g,p,q) parameters suitable for use in both DH exchange and DSA signatures? From the security engineering perspective, I'd suggest that the goals and threat models for encryption vs signatures are different enough that one would prefer different parameters for the two. For DSA signatures, we'd like small subgroups, since the subgroup size determines the signature size. This constraint is not present with DH encryption, where a large subgroup will work as well as a small one. Large subgroups can then support larger private exponents in the DH exchange. Now it may be argued that large subgroups do not actually increase security in the DH exchange, because index calculus methods are independent of subgroup size. In fact, parameters for DSA signatures are typically chosen so that subgroup based methods such as Shanks that take sqrt(q) cost are balanced against estimates of index calculus work to break p. However, this balancing is inherently uncertain and it's possible that p-based attacks will turn out to be harder than ones based on q. Hence one would prefer to use a larger q to provide a margin of safety if the costs are not too high. While there is a computational cost to using a larger subgroup for DH exchange, there is no data cost, while for DSA there are both computational and data costs. Therefore the tradeoffs for DH would tend to be different than for DSA, and a larger q would be preferred for DH, all else equal. In fact it is rather common in DH parameter sets to use Sophie-Germain primes for q. We may also consider that breaking encryption keys is a passive attack which can be mounted over a larger period of time (potentially providing useful information even years after the keys were retired) and is largely undetectable; while breaking signatures, to be useful, must be performed actively, carries risks of detection, and must be completed within a limited time frame. All these considerations motivate using larger parameter sets for DH encryption than for DSA signatures. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Possible backdoor in FIPS SP 800-90 PRNG
Slashdot this morning has a posting about the possibility of a back door in the elliptic curve random number generator in FIPS SP 800-90. http://it.slashdot.org/article.pl?sid=07/11/15/184204 has links to an article by Bruce Schneier at wired.com, the standard, and the presentation with the new result. The work is by Dan Shumow and Niels Ferguson and was presented at the Crypto 2007 rump session. Basically there are two elliptic curve points, and if you know the discrete logarithm of one relative to the other, you can reverse engineer the internal state just from the RNG outputs. It's a very nice piece of analysis. The problem is that NIST publishes a pair of points that they suggest you use, in Appendix A.1, without giving any hint of how they were derived. This leaves open the possibility that they were selected in such a way as to exploit the Shumow/Ferguson back door. Now, here's the strange thing. In Appendix A.2 NIST says that you can use your own pair of points if you want to. But, they caution very strongly that in that case, anyone relying on the PRNG should verify that the pair of points were generated randomly. They describe a specific procedure for generating random points in a provable way (via hashing some other data) and require that the seeds that were used be saved and made available to the verifier. They don't say anything about why this is important, but the work by Shumow and Ferguson now makes it clear. Otherwise there is the possibility of a very serious back door. So this raises the obvious question, why didn't NIST publish the seeds that were used to generate the default points from Appendix A.1? It seems odd that they are so insistent about using a verifiable procedure to create points, and then they don't say whether they followed it themselves. If they did use that procedure, NIST could simply publish the seeds for the point generation and everyone will be able to verify that the points are random and there is no back door. Unfortunately there is a complication, which is that one of the pair of points is inherited from FIPS 186-3, the Digital Signature Standard. The EC PRNG uses the curve and base point from EC DSS. It then chooses another point, and the two points are used for the PRNG. It's not particularly likely that the base point from EC DSS was generated via the randomizing technique prescribed for the EC RNG. And even if the 2nd point for the EC RNG is in fact generated randomly and they can prove it, it would not rule out the possibility that the base point from EC DSS had actually been pre-selected to allow for a back door. It is crucial that both points be generated randomly for the EC RNG to be secure. Ironically, the EC DSS standard does publish a seed used for a PRNG to generate the elliptic curves, so as to assure that they are random. However based on my reading of IEEE P1363 which tells how to do this, it does not appear that the seed constrains the base point, only the curve parameters. Unless NIST did use a verifiably random method to generate the base points in EC DSS and the 2nd points in EC PRNG then there is no foundation for security. Therefore the only reasonable way forward is for NIST to either publish the seeds that were used for these points, if they exist, or to revise the standard to use new points and publish the seeds for both of them. There is no need to re-use the points from FIPS 186-3, a new pair of points should be chosen for the PRNG via the specified randomization. Hal Finney PGP Corporation - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: interesting paper on the economics of security
Steven M. Bellovin forwards a pointer to: http://www.cl.cam.ac.uk/~rja14/Papers/econ_crypto.pdf Ross Anderson gave his invited talk at Crypto yesterday on this topic of the economics of crypto and security. It was an excellent talk, showcasing a new way to look at problems that sheds light on a number of otherwise odd behaviors. At the same time economics is inherently fuzzier than the kind of mathematical precision we aim for in crypto results. It often seems that every economic claim has an opposing one with arguments on each side. Along these lines, I felt that many of the points Ross made were open to debate and interpretation. One example was his comparison between the security business and the used-car lemons market. The idea is that lemons dominate the used-car market due to asymmetric information: only the sellers know which cars are lemons, hence these are the ones that are mostly made available, hence buyers assume all cars are likely to be lemons, hence good cars can't be sold for a higher price and are largely kept off the market. However security products are not really that much like used cars. Used cars are individually unique and it is impossible to know in advance how well they will work. That's where the asymmetric information comes from. But security products are more like other retail products; each one has its own characteristics, strengths and weaknesses, and there are ways consumers can find out about them in advance. There was considerable publicity a couple of weeks ago about a side-by-side test at the LinuxWorld conference which compared ten anti-virus products, with highly differentiated results: http://it.slashdot.org/article.pl?sid=07/08/09/2243229 Information on the quality of AV and other security products is widely available on the net, in magazines and other places that consumers might look for reviews and comparisons. This is completely unlike the situation with individual used cars. I don't see this analogy as particularly accurate. I certainly do fully support the concept behind Ross's program of investigating the role economics plays in the crypto and security field. The mere fact that so many of the conclusions are provocative indicates that there is much fertile work yet to be done. Ross is a major pioneer of this effort and I am looking forward to further interesting results. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: remote-attestation is not required (Re: The bank fraud blame game)
Adam Back [EMAIL PROTECTED] writes: I do not believe the mentioned conflict exists. The aim of these calculator-like devices is to make sure that no malware, virus etc can create unauthorized transactions. The user should still be able to debug, and inspect the software in the calculator-like device, or virtual software compartment, just that installation of software or upgrades into that area should be under direct explicit user control. (eg with BIOS jumper required to even make any software change!) The ring -1 and loss-of-control aspects of TPM are different, they are saying that you are not really root on your own machine anymore! In the sense that if you do load under a debugger the remote party can tell this and refuse to talk with you. I agree with Adam that the unique and defining aspect of TPM technology is this property that users can prove their machine state without being able to lie about it (modulo hardware attacks etc). This can easily work to the user's detriment - lying is often useful - but could sometimes be to the user's advantage as well - being able to provably tell the truth is useful too. In the case of bank security, the question is whether there is any point in trying to keep users from being able to falsify information about their system configuration and software status. Generally, the user has no incentive to do so. The question is whether attackers could somehow exploit the ability of users to make undetected changes to their secure computing base via social engineering and similar hacks. In the case of the calculator-like device, for example, if it is fully reprogrammable by the user, is there a risk that he could be fooled into hooking it up to his computer in that mode and letting attackers change its workings? Or in the case of a TPM-like chip with an owner override, could he be manipulated into using the override so as to make fake banking software look real? Such questions have two sides to them: the case of a user who does get fooled into taking these actions and is harmed by them; and the case of a user who merely pretends to have gotten tricked like this in order to escape liability for transactions he truly did originate. Defending against the latter class of frauds may give the bank incentive to prefer systems where users cannot override their security, so as to reduce the chance of false repudiations. Looking at the system as a whole, then, there may indeed be a case for financial security systems that cannot be overridden by end users. If such measures reduce the overall costs of fraud in the system, then users do benefit at least indirectly from giving up this degree of control. Sometimes in life, paradoxically, you do better by being able to give up certain options, in a verifiable way. TPM technology's benefits to the user would arise from such paradoxical situations. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The bank fraud blame game
[EMAIL PROTECTED] (Peter Gutmann) writes: (The usage model is that you do the UI portion on the PC, but perform the actual transaction on the external device, which has a two-line LCD display for source and destination of transaction, amount, and purpose of the transaction. All communications enter and leave the device encrypted, with the PC acting only as a proxy. Bill of materials shouldn't be more than about $20). In theory the TPM was supposed to allow this kind of thing. The idea was that the OS would support secure applets that could not be molested by legacy software. Only such an applet would have access to your payment information. Some specialized, perhaps customized screen would be displayed by the applet to get you to authorize the final transfer. This was one of the main goals of the TPM as I understood the concept. Unfortunately everyone got focused on the DRM aspect and that largely torpedoed the whole idea. Still we might see it eventually. Research in this direction is still going on, particularly in IBM's Integrity Measurement Architecture[1] and some of the new security extensions to the Xen virtualization software[2]. Hal Finney [1] http://domino.research.ibm.com/comm/research_people.nsf/pages/sailer.ima.html [2] http://xensource.com/files/xs0106_security_print.pdf , also http://www.hpl.hp.com/techreports/2007/HPL-2007-69.pdf - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Free Rootkit with Every New Intel Machine
Peter Gutmann writes: BitLocker just uses the TPM as a glorified USB key (sealing a key in a TPM is functionally equivalent to encrypting it on a USB key). Since BitLocker isn't tied to a TPM in any way (I'm sure Microsoft's managers could see which way the wind was blowing when they designed it), it's not going to be TPM's killer app. Actually BitLocker can use the TPM's measured boot capability for additional security. This requires a TPM-aware BIOS, which hashes the disk's Master Boot Record into the TPM Platform Configuration Registers before executing it, as well as measuring other system software components. The disk encryption key is sealed to the TPM PCR values and the chip won't release it if the boot sequence is different. This means that if you want to attack by, for example, booting from a Linux Live CD or an external USB drive, the chip won't relase the encryption key even if you guess the PIN right. (Some) details at the BitLocker Drive Encryption Technical Overview page: http://technet2.microsoft.com/WindowsVista/en/library/ba1a3800-ce29-4f09-89ef-65bce923cdb51033.mspx?mfr=true Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Free Rootkit with Every New Intel Machine
Ian Farquhar writes: [Hal Finney wrote:] It seems odd for the TPM of all devices to be put on a pluggable module as shown here. The whole point of the chip is to be bound tightly to the motherboard and to observe the boot and initial program load sequence. Maybe I am showing my eternal optimist side here, but to me, this is how TPM's should be used, as opposed to the way their backers originally wanted them used. A removable module whose connection to a device I establish (and can de-establish, assuming the presence of a tamper-respondent barrier such as a sensor-enabled computer case to legitimize that activity) is a very useful thing to me, as it facilitates all sorts of useful applications. The utility of the original intent has already been widely criticised, so I won't repeat that here. :) Would that basically be the same as a removable smart card or crypto token? Those do exist and I agree that they have many useful applications. However their purpose is somewhat different from the TPM, which is more specialized. It also shows those interesting economics at work. The added utility of the TPM module (from the PoV of the user) was marginal at best despite all claims, yet it facilitated functionality which was contrary to most user's interests. The content industry tried to claim that the TPM module would facilitate the availability of compelling content - which they tried to sell as it's user utility - but like most of their claims it was a smoke and mirrors trick. At this point we are reduced to speaking hypothetically. The TPM has not provided either much benefit or much harm so far. It has not (AFAIK) been used to protect any content, for good or evil. It has instead only been used as a sort of glorified, non-removable smart card, which indeed does not provide much utility. Consequently, the razor-edged economics of the motherboard and desktop industry has comprehensively rejected TPM except in certain specialized marketplaces where higher profit margins are available (eg. Servers, corporate desktops). The chipset manufacturers have also failed to add this functionality to their offerings to date. Now Vista has added Bitlocker, which arguably adds a user valuable feature for which a TPM module is needed (yes, you can run it without TPM, but it's painful). I wonder if we'll start to see more TPM connectors appearing, or even full TPM modules on motherboards and cores on south bridge dies? I think the focus is likely still to be on laptop systems where the benefits of an encrypted file system are especially high. However if Bitlocker comes down to the lower level Vistas then we may see TPMs start to appear on lower end laptops. Personally, I'd like to see a TPM implemented as a tamper-respondent (ie. Self-powered) module mounted on the motherboard in a socket which allows removal detection. That way you get the flexibility of moving the module, with the safety of a programmed response to an unauthorized removal. Interesting idea, although it's not clear what you would do with it. The TPM architecture is enormously complex but it is entirely focused on binding a TPM to a platform. Breaking that rule would invalidate so much of the TPM design that you might do better starting with a new chip with its own functions and purpose. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Free Rootkit with Every New Intel Machine
at the last minute. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Public key encrypt-then-sign or sign-then-encrypt?
James A. Donald writes: The flaw in the protocol that you point out is that Carol can allow Alice to use her public key without having to reveal the public key to Alice, so that Alice can pretend to be Carol. Thus the flaw is that with prearrangement, Carol may prove to one other person, but to no one else, that Bob is saying such and such to Carol, provided she knows in advance that Bob is going to say it. ... Is there any way to fix this without introducing an additional exponentiation? Perhaps by introducing an additional multiplication? It does not seem worth while introducing an additional public key operation, for such a low value attack. In theory there is no way to prevent this, because Carol can always do whatever she needs to do to decrypt using her secrets, and then prove in zero knowledge to Alice that she did it correctly. As long as Alice sees via physical surveillance that the packets come from Bob, Carol can convince her of what is inside of them. In practice a full ZK proof is often not needed, as in the example you give of defeating sign-then-encrypt in a hybrid encryption scheme. Note that it is easy to prove that an RSA or ElGamal/DH decryption is valid even without revealing your long term secret keys. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More info in my AES128-CBC question
Earlier someone asked about comparisons between full-width CFB and CBC. They are very similar in certain ways. For example, the sequence of operations for both are the same: xor the next block of plaintext; encrypt the result; xor the next block of plaintext; encrypt the result; and so on. The difference relates to the handling of the IV and the last block; and more importantly, to where in this chain we define the output to be. For CBC the output is after the encrypt steps; for CFB the output is after the xor teps. This also implies that, except for the first and last blocks, you can transform a CBC encryption into a CFB encryption by xoring the plaintext into the ciphertext, and vice versa. In terms of IV, CFB encrypts the IV and then xors with the first block of plaintext. CBC xors the IV with the plaintext and then encrypts. So you have a little more flexibility in terms of choosing your IV, with CFB mode. A simple counter should be good enough. However the penalty for erroneously reusing an IV is worse; it reveals the XOR of the respective plaintexts, whereas in CBC mode it will only reveal whether the plaintexts are identical. Hal Finney PGP Corporation - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Was a mistake made in the design of AACS?
Allen [EMAIL PROTECTED] writes: I know I'm in over my head on this so my apologies, but if the key is used in one machine in a product line - Sony DVD players say - then if they find the one machine that it came from and disable it, wouldn't figuring out the key for the next machine in the production run be relatively trivial as the algorithm and hardware implementation used by all machines of a give run be the same? Therefore, couldn't one buy several of them and use them one after another as they are discovered and disabled? Perhaps so, depending on the nature of the crack. It may require unsoldering chips from the machine motherboard or other rather difficult to perform operations that would not be possible for average users. Keep in mind that each machine costs several hundred dollars, and they will be turned into bricks once revoked. This raises the question of who is bankrolling this effort and what his motivations are. So, in order to prevent any of those machines from being used they'd have to disable a whole lot of machines owned by ordinary individuals, right? What are the downside risks for Sony in doing this? I imagine it is safe to say that this is not a step that AACSLA would take lightly. If they ever did this then I suppose the machine manufacturer would have to provide owners of the affected models with upgrades to newer machines. It's very hard to predict the future and it is not clear to me that we will get into a scenario where a very small number of sacrificial machines are the source of every HD movie being uploaded to the pirate nets, such that when these few machines are revoked, immediately another few machines are swapped in to replace them. It would require a relatively large degree of coordination among what I would imagine is a generally loose affiliation of attackers with diverse motivations. But as I said, my crystal ball is foggy. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Yet a deeper crack in the AACS
Article AACS cracks cannot be revoked, says hacker http://arstechnica.com/news.ars/post/20070415-aacs-cracks-cannot-be-revoked-says-hacker.html Excerpt: The latest attack vector bypasses the encryption performed by the Device Keys -- the same keys that were revoked by the WinDVD update -- and the so-called 'Host Private Key,' which as yet has not been found. This was accomplished by de-soldering the HD DVD drive's firmware chip, reading its contents, and then patching it. Once that was done, the firmware was soldered back onto the drive. This article was not too accurate, and further progress has been made. At this point it is possible to remotely patch the firmware of a particular kind of HD-DVD drive so that it will provide certain information without the usually required authentication. This makes it easy to retrieve the per-disk Volume ID, which must be combined with the widely-published Processing Key to generate the media keys that can decrypt content. If this Processing Key is invalidated on future releases, this hack will not be useful until new keys are discovered. It provides only part of the picture. The hack was a real accomplishment because firmware updates had to be authenticated with what was apparently something like an AES-based CBC-MAC. The hackers had to figure this out without much background in cryptography and working only with dumps of the firmware that used a somewhat obscure embedded CPU. They had to figure out what CPU was being used, find a disassembler for it, and examine assembly language dumps to deduce that crypto was involved, recognize AES, and see how to create their own checksums that would make their firmware updates succeed. Just goes to show the motivation and hard work that hackers bring to these efforts, largely for the love of the challenge. It's possible that the ability to modify firmware will lead to more successes for the hackers in the future, perhaps helping them to break into future versions of software players to extract their embedded keys. I peruse the doom9.org forums from time to time, where this work took place right out in the open, before the public eye. Definitely some smart people involved there. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
AACS and Processing Key
much information about which device was cracked in order to extract the key. This might leave AACSLA in a quandary about what to revoke in order to fix the problem. However in this particular case the attackers made little attempt to conceal their efforts and it was clear which software player(s) were being used. This may not be the case in the future. AACSLA has announced that they will be changing the processing keys used in disks which will begin to be released shortly. Software players have been updated with new device keys, indicating that the old ones will be revoked. In the context of the subset-difference algorithm, there will now probably be a few encryptions necessary to cover the whole tree while revoking the old software player nodes as well as the pre-revoked node. This will make the processing key which has been published useless for decrypting new disks. Because processing keys do not unambiguously point to their source, AACSLA may choose to set up subset-difference encryptions in which each software player is part of a different subtree and therefore uses a different processing key. This might require a few more encryptions than the minimal number that subset-difference allows, but it would reduce the chance that AACSLA would find themselves unable to determine the source of a published processing key. This will only work as long as attackers restrict themselves to the relatively few software players. If some group were to succeed in extracting keys from a hardware player and publish a processing key that might apply to the majority of hardware players in use, AACSLA would seemingly have no way to determine how to address the problem. Now I must confess that this already long message has oversimplified the AACS system in certain respects. First, the subset-difference system is only carried on for the lowest 22 levels of the 31 level tree. There are effectively 512 independent trees where the algorithm is applied, each with a single pre-revoked leaf node. However at this time it appears that only one is in use. Second, the processing key is not actually the same as the node's device key, but rather is a hash of the device key. Further, the exact details of how you go from the processing key to the various disk content keys involve several levels of indirection and encryption. Third, even given the processing key, some of the information needed to derive all of the disk's content is not easily available. One piece needed is a per-title Volume ID which is not readable from the disk in a straightforward way. Volume IDs have been discovered by eavesdropping on the USB bus connected to a disk player, or by hacking disk player firmware. At this point it is hard for typical end users to read Volume IDs, so knowing the processing key is not generally sufficient to read disks. Databases of Volume IDs have been published online, but disk media keys could just as easily have been published. Speculating now, the AACS system is flexible but it is possible that publication of processing keys may not have been fully anticipated by the designers. The difficulty of tracing processing keys to their source in an environment in which new disks may require many weeks or even months of lead time may interfere with the planned revocation system. The current processing key will soon be rendered invalid for new releases, so AACSLA's aggressive legal tactics seem disproportionate compared to the relative unimportance of this particular key. Perhaps these legal actions are primarily intended to limit distribution of future processing keys that are found on the next set of disk releases. That would further point to technical difficulties in revocation strategy when a new processing key is published. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Was a mistake made in the design of AACS?
Perry Metzger writes: I will again solicit suggestions about optimal strategies both for the attacker and defender for the AACS system -- I think we can learn a lot by thinking about it. It would be especially interesting if there were modifications of the AACS system that would be more hardy against economic attacks -- can you design the system so that slow key revelation is not an economic disaster while still maintaining an offline delivery model with offline players entirely in the enemy's control? I don't think you can, but it would be very interesting to consider the problem in detail. Ed Felten has blogged a number of ideas along these lines: http://www.freedom-to-tinker.com/?p= By this point in our series on AACS (the encryption scheme used in HD-DVD and Blu-ray) it should be clear that AACS creates a nontrivial strategic game between the AACS central authority (representing the movie studios) and the attackers who want to defeat AACS. Today I want to sketch a model of this game and talk about who is likely to win... Felten focuses on the loss of revenue due to extraction of device keys and subsequent file sharing of decrypted content. AACS has a mechanism called sequence keys to watermark content and allow it to be traced back to the player that created it. Felten assumes that attackers would publish decrypted movies, AACSLA would then trace them back to the broken device, and revoke that device in future releases. The optimal strategy depends on his parameters C, the cost in time it takes for attackers to break into new devices and extract keys; and L, the commercial lifetime of a new disk. Felten writes: It turns out that the attacker's best strategy is to withhold any newly discovered compromise until a 'release window' of size R has passed since the last time the authority blacklisted a player. (R depends in a complicated way on L and C.) Once the release window has passed, the attacker will use the compromise aggressively and the authority will then blacklist the compromised player, which essentially starts the game over. The studio collects revenue during the release window, and sometimes beyond the release window when the attacker gets unlucky and takes a long time to find another compromise. He estimates that C is measured in weeks and L in months, which bodes ill for the studios, as his model predicts that studios will receive the fraction C/(C+L) of their potential revenues if no piracy occured, and CL makes this fraction small. I see a couple of problems with his model. First, it may be that by publishing processing keys instead of device keys or movie content, it will be harder to make the traitor tracing algorithm work and AACSLA may be thwarted in their attempt to revoke the broken device. I'm not sure I understand the system well enough to know whether there are effective countermeasures for AACSLA against this attacker strategy. Threats of legal action do not appear to be achieving much success. Second, there is a long lead time between when AACSLA determines to update the processing keys and other components of the subset difference scheme, and when the disks actually reach the public. This is bad for the studios and probably effectively increases L. On the other hand I suspect his L estimate of months is excessive; 8 of the Amazon's 10 top selling DVDs were released since April 24. As with other media like CDs, it is likely that the bulk of revenues arrive during the first few weeks of release. If they can protect that window then they might view the system as achieving at least some of its goals. But these other considerations will work against them. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: can a random number be subject to a takedown?
My question to the assembled: are cryptographic keys really subject to DMCA subject to takedown requests? I suspect they are not copyrightable under the criterion from the phone directory precedent. A sample demand letter from the AACS Licensing Authority appears at: http://www.chillingeffects.org/notice.cgi?sID=03218 From what I can see, there is no claim that the key is copyrighted. Rather, the letter refers to the provisions of the DMCA which govern circumvention of technological protection measures. It demands that the key be taken down in order to avoid legal liability. This seems odd to me because my understanding of the DMCA's anti-circumvention provisions is that they are criminal rather than civil law. Violations would lead to charges from legal authority and not from a copyright owner. So it's not clear that AACSLA has any power to enforce these demands, other than trying to get some government agency involved. The letter specifically cites 17 USC 1201(a)2 and (b)1, which can be read here: http://cyber.law.harvard.edu/openlaw/DVD/1201.html#a2 Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Governance of anonymous financial services
Steve Schear writes: Here is the situation. An on-line financial service, for example a DBC (Digital Bearer Certificate), operator wishes his meat space identity, physical whereabouts, the transaction servers and at least some of the location(s) of the service's asset backing to remain secret... Pretty tough to do much with crypto in this situation. My rpow.net software was an attempt to create what Nick Szabo called bit gold, transferrable certificates that had intrinsic rarity. It uses trusted computing concepts to create RSA signatures that are backed by hash collisions. Unfortunately rarity does not automatically translate into value, so even though the system was highly inflation-resistant it was not too successful in attracting users. The service provides frequent, maybe even real-time, data on its asset backing versus currency in circulation. The operator wishes to provide some assurance to his clients that the backing and the amount of currency in circulation are in close agreement. The mint's backing need not be in a single location nor in the sole possession of the operator. Maybe he could publish a picture of the backing commodities, and design the system so that everyone could see how much money was in circulation? Keep in mind that this is only part of the trust picture. Showing that the backing is there won't prevent this anonymous operator from absconding with the funds in the future. That would be one of my concerns if I were a user. If the backing is distributed among a multitude of holders (e.g., in a fashion similar to how Lloyds backs their insurance empire), who's identities are kept secret until audit time and then only a few, randomly selected, names and claimed deposit amounts are revealed to the auditors, might this statistical sampling and the totals projected from the results be a reasonable replacement for 'full asset' audit? To protect the identities of the holders could a complete list of the hashes of each name and claimed deposit be revealed to the auditors, who then select M of N hashes whereupon the operator reveals only those identities and claimed deposits work cryptographically? One problem is the holders could collude and play a shell game. Suppose that 30% of the holders were going to be asked to reveal their assets, then the company could back only 30% of the currency, and redistribute the assets to the selected holders before the auditors come. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: virtualization as a threat to RNG
Dan Geer wrote: Quoting from a discussion of threat posed by software virtualization as found in Symantec's ISTR:xi, released today: The second type of threat that Symantec believes could emerge is related to the impact that softwarevirtualized computers may have on random number generators that are used inside guest operating systems on virtual machines There was related discussion a couple of months ago on the IRTF Crypto Forum Research Group mailing list. The question is what security problems might arise with increased use of virtualization, in particular state rollbacks causing reuse of nonces and other values that are required to be unique. Wei Dai summarized suggestions from the thread at: http://www1.ietf.org/mail-archive/web/cfrg/current/msg01387.html : There have been several specific and practical suggestions, but they were : spread over several messages in the discussion. I'll summarize here: : : 1. Use random IVs instead of counter or state-derived IVs. : : 2. For any crypto scheme that uses random numbers or IVs, generate the : random numbers/IVs after the message to be encrypted and/or authenticated is : fixed. : : 3. Use the operating system's secure RNG to generate these random : numbers/IVs and hash in the current time and/or the message to make sure : random numbers are not reused on different messages. : : 4. As an alternative to 1-3 above, switch to a crypto scheme such as SIV : that is specifically designed to tolerate nonce reuse. The thread index will allow reading more of the discussion at http://www1.ietf.org/mail-archive/web/cfrg/current/threads.html under the title, how to guard against VM rollbacks. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: News.com: IBM donates new privacy tool to open-source Higgins
John Gilmore forwards: http://news.com.com/IBM+donates+new+privacy+tool+to+open-source/2100-1029_3-6153625.html IBM donates new privacy tool to open-source By Joris Evers Staff Writer, CNET News.com Published: January 25, 2007, 9:00 PM PST IBM has developed software designed to let people keep personal information secret when doing business online and donated it to the Higgins open-source project. The software, called Identity Mixer, was developed by IBM researchers. The idea is that people provide encrypted digital credentials issued by trusted parties like a bank or government agency when transacting online, instead of sharing credit card or other details in plain text, Anthony Nadalin, IBM's chief security architect, said in an interview. ... I just wanted to note that the idemix software implements what we sometimes call Camenisch credentials. This is a very advanced credential system based on zero knowledge and group signatures. The basic idea is that you get a credential on one pseudonym and can show it on another pseudonym, unlinkably. More advanced formulations also allow for credential revocation. I don't know the specifics of what this software implements, and I'm also unclear about the patent status of some of the more sophisticated aspects, but I'm looking forward to being able to experiment with this technology. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: analysis and implementation of LRW
To clarify a couple of points with regard to IEEE P1619 and LRW. The original proposal which P1619 called LRW was actually a particular concrete instantiation of a general construction from the LRW paper (Liskov, Rivest and Wagner, Tweakable Block Ciphers, Crypto 02, http://www.cs.berkeley.edu/~daw/papers/tweak-crypto02.pdf ). The LRW construction was C = E_k(P xor h(T)) xor h(T) where E_k is a block cipher with key k, T is the tweak and h(T) is a keyed almost-xor-universal function. P1619 instantiated E as AES and h as galois field multiplication by a secret constant value: h(T) = k2*T where T is the block number. This is what they called LRW and it has the weakness described, that if you have two consecutive blocks containing k2 and zero, P xor h(T) can be the same for both of them. This is what the group called a collision, meaning two blocks whose input to the AES is the same. For this simple definition of h(T) as k2*T a collision can reveal k2. However this is not a general flaw in LRW, it is merely a problem with this very simple instantiation of the construction. In fact the replacement, which the group calls XTS, is also an instance of LRW. Based on work by Rogaway, the construction is the same as above but the universal hash h(T) = E_k2(T1) * alpha^T2, where T1 are the leftmost bits of the block number T and T2 are the rightmost bits (alpha is a primitive root, and the math is finite field). Rogaway proved that this hash is universal and hence this is an instance of LRW and is secure. So it is an over-simplification to say that P1619 found LRW insecure and replaced it. P1619 found that a particularly simple instantiation of LRW had this problem when encrypting part of its key, and substituted a more complicated version of LRW which appears to be largely immune to the problem. P1619 is still using LRW and it should still be considered a very seminal and useful cryptographic construction. It should be noted that almost no cryptographic proofs of security work when arbitrary functions of the key are allowed as inputs to other parts of the cipher, and at this point we must largely rely on heuristic and informal arguments to see whether any weaknesses are real or merely theoretical. Hal Finney PGP Corporation P1619 Member - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Exponent 3 damage spreads...
Anton Stiglic writes: I tried coming up with my own forged signature that could be validated with OpenSSL (which I intended to use to test other libraries). ... Now let's look at s^3 1FFF\ \ FFF003021300906052B0E03021A05000\ 4145D89B46034E0F41A920B2FA964E230EBB2D040B00\ \ 02A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\ 1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\ 743B52BBFA7B9697DA285694CD9347AB7528\ D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\ 85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\ 81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E5324000\ 0 This has the form we are looking for, the 01 FF FF ... FF header that ends with 00, and then we have 03021300906052B0E03021A050004145D89B46034E0F41A920B2FA964E230EBB2D040B0 which is the d we started out with, and the rest is the GARBAGE part. Only one problem, s^3 is larger than m, so if we computed modexp(s, 3, m) the result would be rounded out modulo m and we would loose the above structure. This is not correct. I counted, and the number shown above has 762 hex digits. It is 3057 bits long, compared to m which is 3072 bits. It is not bigger than m, and does not need to be adjusted. 3057 is precisely the correct number of bits for a PKCS-1 padded value for a 3072 bit exponent. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why the exponent 3 error happened:
For another example of just how badly this kind of thing can be done,
look at this code excerpt from Firefox version 1.5.0.7, which is the
fixed version. There are two PKCS-1 parsing functions, one which returns
the hash and its prefix, the other of which is given the hash and asked
whether it matches the RSA-signed value. This is from the latter one:
/*
* check the padding that was used
*/
if (buffer[0] != 0 || buffer[1] != 1)
goto loser;
for (i = 2; i modulus_len - hash_len - 1; i++) {
if (buffer[i] == 0)
break;
if (buffer[i] != 0xff)
goto loser;
}
/*
* make sure we get the same results
*/
if (PORT_Memcmp(buffer + modulus_len - hash_len, hash, hash_len) != 0)
goto loser;
PORT_Free(buffer);
return SECSuccess;
Here, buffer holds the result of the RSA exponentiation, of size
modulus_len, and we are passed hash of size hash_len to compare.
I don't think this code is used, fortunately. It will accept anything
of the form 0, 1, 0, garbage, hash. Just goes to show how easy it is
to get this kind of parsing wrong.
(Note, this is from
mozilla/security/nss/lib/softoken/rsawrapr.c:RSA_CheckSign())
Hal Finney
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Real World Exploit for Bleichenbachers Attack on SSL from Crypto'06 working
Erik Tews writes: At least 3 major webbrowsers on the marked are shipped by default with CA certificates, which have signed other intermediate CAs which use rsa1024 with exponent 3, in their current version. With this exploit, you can now sign arbitary server certificates for any website of your choice, which are accepted by all 3 webbrowsers without any kind of ssl-warning-message. Is that true, did you try all 3 web browsers to see that they don't give a warning message? It's not enough that they accept a CA with exponent 3, they also have to have the flaw in verification that lets the bogus signature through. If it is true, if three different widely used webbrowsers are all vulnerable to this attack, it suggests a possible problem due to the establishment of a cryptographic monoculture. If it turns out that the same cryptographic library is used in all three of these browsers, and that library has the flaw, then this reliance on a single source for cryptographic technology could be a mistake. Now in practice I don't think that Internet Explorer and Mozilla/Firefox use the same crypto libraries, so either these are not two of the three, or else they have independently made the same error. It would be nice to know which it is. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why the exponent 3 error happened:
James Donald writes: There is no need, ever, for the RSA signature to encrypt anything other than a hash, nor will their ever be such a need. In this case the use of ASN.1 serves absolutely no purpose whatsoever, other than to create complexity, bugs, and opportunities for attack. It is sheer pointless stupidity, complexity for the sake of complexity, an indication that the standards process is broken. Actually there is something besides the hash there: an identifier for which hash algorithm is used. The ASN.1 OID was, I suppose, a handy and already-existant mechanism for universal algorithm identification numbers. Putting the hash identifier into the RSA signed data prevents hash substitution attacks. Otherwise the hash identifier has to be passed unsigned, and an attacker could substitute a weak hash algorithm and find a second preimage that matches your signed hash. Maybe that is not part of a threat model you are interested in but at least some signers don't want their hash algorithms to be changed. BTW I want to mention a correction to Peter Gutmann's post: as I understand it, GnuPG was not vulnerable to this attack. Neither was PGP. The OpenPGP standard passes the hash number outside the RSA signed data in addition to using PKCS-1 padding. This simplifies the parsing as it allows hard-coding the ASN-1 prefix as an opaque bit string, then doing a simple comparison between the prefix+hash and what it should be. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Exponent 3 damage spreads...
Peter Gutmann writes: But wait, there's more! From what I understand of the attack, all you need for it to work is for the sig.value to be a perfect cube. To do this, all you need to do is vary a few of the bytes of the hash value, which you can do via a simple brute-force search. So even with a perfect implementation that does a memcmp() of a fixed binary string for all the data present but the hash, the attack still works. I don't think this works. I tried with a 1024 bit key. We want a cube root of something between: 0x1003021300906052B0E03021A05000414 and 0x1003021300906052B0E03021A05000414 But actually the nearest cube root is: 0x1428A2F98D728AE223DDAB715BE250D0C288F10291631FBC061800CC36FA2DD3A60B7D03DA26F0840F25C Cubing this gives: 0x1FFFC66E7388AFD22947A600FB19230A3162AB4A53B003B80F979B8E97D7DB74891A5769312C88639E645DD3DB79E32561BD7FF661977573AF888EF025ED0608245DE7048210C94AC32731DD6B19B2F25722E951F41C0 and cubing the next higher value gives: 0x200012A06F78681CDECFB70DC81AEE9F1B2FF7CBB6140D9A07D97209E81A4A2D957560CB04CF8F504EF90797FEBD799E9A64841F1168C13EC938E0D109610B8CC43EF3FDA8B374E3AD57AF2A0E084B15E8BB328384C05 So no variation on the hash value will produce something that is a perfect cube. Now, this is specific to 1024 bit keys, but larger keys should be even more unfavorable. As a general rule we can only force the top 1/3 of the bits to be 1s as required, and the chances of getting lucky will be worse for larger keys. We could start adding in multiples of the modulus and look for perfect cubes again, but basically the odds against are 1 in N^(2/3) so there is no point. Hal Finney PGP Corporation - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Raw RSA
Alexander Klimov asks: If an attacker is given access to a raw RSA decryption oracle (the oracle calculates c^d mod n for any c) is it possible to extract the key (d)? This is equivalent to asking whether factoring reduces to RSA inversion. That is, given access to an RSA inversion oracle, can you factor the modulus? (Factoring the modulus is equivalent to finding d.) Then see Breaking RSA May Not Be Equivalent to Factoring by Boneh and Venkatesan, Eurocrypt 98. Abstract (with my added emphasis): We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. THUS, IN EFFECT AN ORACLE FOR BREAKING RSA DOES NOT HELP In FACTORING INTEGERS. Our result suggests an explanation for the lack of progress in proving that breaking RSA is equivalent to factoring. We emphasize that our results do not expose any specific weakness in the RSA System. So the answer would appear to be no, an oracle for RSA does not help in factoring and therefore will not reveal d. See also http://citeseer.ist.psu.edu/bellare01onemorersainversion.html The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme by Bellare et al for some discussion of this issue. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Bleichenbacher's RSA signature forgery based on implementation error
At the evening rump session at Crypto last week, Daniel Bleichenbacher gave a talk showing how it is possible under some circumstances to easily forge an RSA signature, so easily that it could almost be done with just pencil and paper. This depends on an implementation error, a failure to check a certain condition while verifying the RSA signature. Daniel found at least one implementation (I think it was some Java crypto code) which had this flaw. I wanted to report on his result here so that other implementers can make sure they are not vulnerable. Be aware that my notes were hurried as Daniel had only a few minutes to talk. The attack is only good against keys with exponent of 3. There are not too many of these around any more but you still run into them occasionally. It depends on an error in verifying the PKCS-1 padding of the signed hash. An RSA signature is created in several steps. First the data to be signed is hashed. Then the hash gets a special string of bytes in ASN.1 format prepended, which indicates what hash algorithm is used. This data is then PKCS-1 padded to be the width of the RSA modulus. The PKCS-1 padding consists of a byte of 0, then 1, then a string of 0xFF bytes, then a byte of zero, then the payload which is the ASN.1+hash data. Graphically: 00 01 FF FF FF ... FF 00 ASN.1 HASH The signature verifier first applies the RSA public exponent to reveal this PKCS-1 padded data, checks and removes the PKCS-1 padding, then compares the hash with its own hash value computed over the signed data. The error that Bleichenbacher exploits is if the implementation does not check that the hash+ASN.1 data is right-justified within the PKCS-1 padding. Some implementations apparently remove the PKCS-1 padding by looking for the high bytes of 0 and 1, then the 0xFF bytes, then the zero byte; and then they start parsing the ASN.1 data and hash. The ASN.1 data encodes the length of the hash within it, so this tells them how big the hash value is. These broken implementations go ahead and use the hash, without verifying that there is no more data after it. Failing to add this extra check makes implementations vulnerable to a signature forgery, as follows. Daniel forges the RSA signature for an exponent of 3 by constructing a value which is a perfect cube. Then he can use its cube root as the RSA signature. He starts by putting the ASN.1+hash in the middle of the data field instead of at the right side as it should be. Graphically: 00 01 FF FF ... FF 00 ASN.1 HASH GARBAGE This gives him complete freedom to put anything he wants to the right of the hash. This gives him enough flexibility that he can arrange for the value to be a perfect cube. In more detail, let D represent the numeric value of the 00 byte, the ASN.1 data, and the hash, considered as a byte string. In the case of SHA-1 this will be 36 bytes or 288 bits long. Define N as 2^288-D. We will assume that N is a multiple of 3, which can easily be arranged by slightly tweaking the message if neccessary. Bleichenbacher uses an example of a 3072 bit key, and he will position the hash 2072 bits over from the right. This improperly padded version can be expressed numerically as 2^3057 - 2^2360 + D * 2^2072 + garbage. This is equivalent to 2^3057 - N*2^2072 + garbage. Then, it turns out that a cube root of this is simply 2^1019 - (N * 2^34 / 3), and that is a value which broken implementations accept as an RSA signature. You can cube this mentally, remembering that the cube of (A-B) is A^3 - 3(A^2)B + 3A(B^2) - B^3. Applying that rule gives 2^3057 - N*2^2072 + (N^2 * 2^1087 / 3) - (N^3 * 2^102 / 27), and this fits the pattern above of 2^3057 - N*2^2072 + garbage. This is what Daniel means when he says that this attack is simple enough that it could be carried out by pencil and paper (except for the hash calculation itself). Implementors should review their RSA signature verification carefully to make sure that they are not being sloppy here. Remember the maxim that in cryptography, verification checks should err on the side of thoroughness. This is no place for laxity or permissiveness. Daniel also recommends that people stop using RSA keys with exponents of 3. Even if your own implementation is not vulnerable to this attack, there's no telling what the other guy's code may do. And he is the one relying on your signature. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: switching from SHA-1 to Tiger ?
Zooko writes: By the way, the traditional practice of using a hash function as a component of a MAC should, in my humble opinion, be retired in favor of the Carter-Wegman alternative such as Poly-1305 AES [7]. This is a great topic where there are lots of pros and cons. The CW MACs like UMAC and Poly1305-AES have advantages including speed and provable security. However the recent result Perry cited by Bellare, http://eprint.iacr.org/2006/043, argues that HMAC relies only on the compression function being a PRF, and the CW MACs also need a PRF. So perhaps their security properties will not turn out to be so different. From the security implementor's POV, the speed of the CW MACs must be balanced against potentially greater difficulty in using them. They are not black-box drop-in replacements for HMAC. CW MACs rely on the presence of a unique nonce per message (and per key). This can be as simple as a sequence number, or perhaps a random string. But either one may require adding state and/or environmental access to what is a simple stateless function with HMAC. CW MACs also have the property that they may allow single brute-force forgeries to be easily extended to multiple forgeries. The ease or difficulty of this extension will depend on details of the MAC design, but in principle, the CW security properties allow for it. This means that MACs of moderate length, like 64 bits or less, need to be evaluated much more critically with a CW MAC implementation. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: NIST hash function design competition
James Donald writes: My understanding is that no actual vulnerabilities have been found in Rijndael. What has been found are reasons to suspect that vulnerabilities will be found. Yes, I think that's correct on the theoretical side. I was also thinking of some of the implementation issues which have shown up, particularly timing and cache attacks. AES is proving to be difficult to immunize against these problems. A good discussion by Bernstein is presented in http://cr.yp.to/antiforgery/cachetiming-20050414.pdf, where he asks, regarding this AES issue, How did this happen?: : Was the National Institute of Standards and Technology unaware of : timing attacks during the development of AES? No. In its âReport on the : development of the Advanced Encryption Standard, NIST spent several pages : discussing side-channel attacks, specifically timing attacks and power : attacks. It explicitly considered the difficulty of defending various : operations against these attacks. For example, NIST stated in [19, : Section 5.1.5] that MARS was âdifficult to defend against these attacks. : : Did NIST decide, after evaluating timing attacks, that those attacks : were unimportant? No. Exactly the opposite occurred, as discussed below. : : So what went wrong? Answer: NIST failed to recognize that table lookups : do not take constant time. âTable lookup: not vulnerable to timing : attacks, NIST stated in [19, Section 3.6.2]. NIST's statement was, : and is, incorrect. : : NIST went on to consider the slowness of AES implementations designed : to protect against side-channel attacks. For example, NIST stated : that providing âsome defense for MARS meant âsevere performance : degradation. NIST stated in [19, Section 5.3.5] that Rijndael gained a : major speed advantage over its competitors when such protections are : considered. This statement was based directly on the incorrect notion : that table lookups take constant time. NIST made the same comment in : its summary assessments of the finalists, and again in its concluding : paragraph explaining the selection of Rijndael as AES. See [19, Section : 6.5] and [19, Section 7]. This is an example of a case where there doesn't seem to have been enough time during the AES process for people to notice this oversight. It probably didn't help that analysts had to spread their effort over five main candidates. Maybe it would be a good idea for NIST to add an extra phase where they announce their proposed finalist, and ask everyone to focus all their attention on potential weaknesses in this one function. Since this is exactly what will happen anyway immediately after the selection is made, it might make sense to build a buffer period into the process to let people take their final shots. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
NIST hash function design competition
I was registering today for the Crypto conference and discovered that immediately afterwards, and at the same site in Santa Barbara, CA, NIST is holding a two-day workshop on hash function design. The information is here: http://www.csrc.nist.gov/pki/HashWorkshop/index.html In response to the SHA-1 vulnerability that was announced in Feb. 2005, NIST held a Cryptographic Hash Workshop on Oct. 31-Nov. 1, 2005 to solicit public input on its cryptographic hash function policy and standards. NIST continues to recommend a transition from SHA-1 to the larger approved hash functions (SHA-224, SHA-256, SHA-384, and SHA-512). In response to the workshop, NIST has also decided that it would be prudent in the long-term to develop an additional hash function through a public competition, similar to the development process for the block cipher in the Advanced Encryption Standard (AES). I had not heard that there had been an official decision to hold a new competition for hash functions similar to AES. That is very exciting! The AES process was one of the most interesting events to have occured in the last few years in our field. Seemed like one of the lessons of that effort was that, even though it was successful in terms of attracting the interest and hard work of some of the top researchers in the field, in the end we have learned considerably more about Rijndael's vulnerabilities only after the process was over. Perhaps the intrinsic difficulty of cryptography makes this kind of outcome inevitable. But hopefully the hashing competition will learn from the AES experience and make sure that it takes as much time as it needs to take. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Use of TPM chip for RNG?
A few weeks ago I asked for information on using the increasingly prevalent built-in TPM chips in computers (especially laptops) as a random number source. I got some good advice and want to summarize the information for the benefit of others. The TPM chip as spec'd by the Trusted Computing Group (www.trustedcomputinggroup.org) is a complex and controversial device. Despite (or perhaps because of) all the fuss over it when the technology was introduced, nothing much has happened with it and they are mostly used to add a bit of security to encrypted files and such. TPMs do have hardware RNGs and I wanted to find out how to access this capability. On Windows, there are several APIs available which can work. The native API for the TPM is the Trusted Software Stack (TSS). https://www.trustedcomputinggroup.org/groups/software/ This provides a wide range of TPM-specific functions, including ones to access the RNG. Another alternative is Microsoft's Crypto API (MS-CAPI). CAPI uses a plug-in architecture where Crypto Service Providers (CSPs) provide the required functionality. TPM-based CSPs allow access to TPM functions via CAPI. Third, the PKCS-11 (Cryptoki) API is designed for access to smart cards, but TPM manufacturers often deliver PKCS-11 compatible libraries for access to the chips. Both CAPI and PKCS-11 have random number functionality which can be used to access the TPM RNG. The main problem in practice with using this functionality on Windows is that there is as yet no standard for naming or locating the DLL's which supply the necessary functions. I am testing on an IBM Thinkpad with an Atmel TPM, and it comes with DLL's that provide TSS, CAPI and PKCS-11 interfaces. But all are supplied with non-standard names and located in non-standard places. Software to use these functions has to know where the DLLs are and what they are called in order to load them explicitly. The exception is MS-CAPI. CAPI provides an interface to enumerate all the CSPs, so if you can figure out which one is the TPM CSP you can then use that one to generate random numbers. One of the CAPI functions lets you query to see if the CSP has hardware RNG support. On my system, this returns TRUE for the TPM CSP. However, a colleague has a Dell system with a different TPM and different software, and that TPM's CSP does not set this bit. So I don't have a foolproof method of figuring out which CSP to use in order to access the TPM. It might be possible to hard-code the names of all known TPM CSPs but that would not be very flexible going forward. At this point MS-CAPI still looks like the best choice for machine-independent access to the TPM RNG on Windows. The ability to reliably enumerate all the CSPs is much easier than hunting through the disk to try to find a DLL to implement the TSS or PKCS-11 APIs. OTOH if you are building the software for a particular system and can build in the location of the necessary DLL, one of the other APIs could work too. On Linux systems, as I mentioned earlier, the standard appears to be an open-source TSS implementation called Trousers, at http://trousers.sourceforge.net . This requires the Linux kernel to have a TPM device driver built-in or as a loadable module. This has been available in the kernel since 2.6.12, but many distributions do not enable it, even as a module, so some work is needed to make a kernel with TPM support. Then the Trousers software builds a daemon process, tcsd, which opens /dev/tpm exclusively, and a library, libtspi, for remote access to tcsd and the TPM. If you want a cross-platform solution, TSS is probably the best approach going forward. As noted, at present the software support is a little immature and some local configuration will be necessary - locating the TSS DLL on Windows, and installing the TPM kernel support and Trousers software on Linux. Once this is done, the TSS API should provide for cross-platform capability. And of course it has additional functionality if you want to use the TPM for more than just random number generation. Intel Macs have TPM chips as well but I don't know of any software yet that can access them. Eventually I would expect a TSS solution to be available on that platform as well. Thanks again to the people who provided me information about these various solutions! Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Use of TPM chip for RNG?
Finding a good source of random bits is a frequent problem in cryptographic applications. Recently many computers have begun shipping with a TPM chip, which among other things includes a hardware RNG. Does anyone know of Windows software which can use the TPM for this purpose? Perhaps via MS CAPI, or some other API? On Linux, the Trousers library, http://trousers.sourceforge.net/, provides access to TPM functions including RNG. Basically I'm looking for something similar for Windows. Given all the questions about trusted computing technology, it would be nice to get some straightforward operational benefit from all those TPM chips being installed. I'll be happy to summarize results back to the list if people want to contact me privately. Thanks - Hal Finney [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: picking a hash function to be encrypted
Travis H. writes: Excellent point. When I wrote that I had strongly universal hashes in mind, like UMAC, where the hash is chosen from a family of functions based on some secret data shared by sender and recipient. I mistakenly conflated them with ordinary hashes (which they are, once you pick one). Thanks for catching that. A point of terminology, strong universal hash functions are different than what you are probably thinking of. UMAC is a MAC, not a SU hash function. It uses an almost-SU hash function in its construction, but that's different. Universal hashes and their variants (see http://www.cacr.math.uwaterloo.ca/~dstinson/universalhashingdefinitions.html for a bibliography) are actually *weaker* than conventional hashes. They can, in fact, be completely linear. While you are right that the hash is typically part of a parameterized family, once you pick one you do not get an ordinary hash. You are more likely to get an ordinary polynomial that will not serve at all well as a crypto hash. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: what's wrong with HMAC?
Travis H. writes: Ross Anderson once said cryptically, HMAC has a long story attched to it - the triumph of the theory community over common sense He wouldn't expand on that any more... does anyone have an idea of what he is referring to? I might speculate, based on what you write here, that he believed that the simpler, ad hoc constructions often used in the days preceding HMAC were good enough in practice, and that the theoretical proofs of security for HMAC were given too much weight. The original HMAC paper is at http://www-cse.ucsd.edu/~mihir/papers/kmd5.pdf and the authors show in section 6 various attacks on ad hoc constructions, but some of them are admittedly impractical. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Unforgeable Blinded Credentials
John Gilmore writes: I am aware of, Direct Anonymous Attestation proposed for the Trusted Computing group, http://www.zurich.ibm.com/security/daa/ . DAA provides optionally unlinkable credential showing and relies on blacklisting to counter credential sharing. Hmm, why doesn't this blacklisting get mentioned in IBM's DAA page? They don't use that term, rather they refer to rogue TPMs. This means TPM keys which have been compromised in some way. The implication is that such keys would, once identified, be shut out from the system, and presumably this would be done by a blacklist. What sort of blacklist would this be? What actions would being listed on it trigger? I don't think the operational details of this are worked out, but I don't follow this area closely. No doubt this is part of why none of these systems have been fielded. (Computers do get sold with TPMs in them but the enormous infrastructure envisioned by the Trusted Computing group is not in place.) In principle, if your TPM's key got put on this blacklist, it would prevent you from access to whatever resources require a valid TPM. What resources those might be would depend on how and where this technology is used, if it ever is. But having a blacklisted TPM would be like not having a TPM at all, in terms of access to network resources. It may be a little more complex than this, because the DAA protocol has a couple of different modes in which it may be used. Rather than a global blacklist, each TPM-requiring service might maintain its own local blacklist of rogue TPM identifiers. Actually I would expect there to be both kinds of blacklists: a global one based on TPM private keys which have been scraped and published; and a local one based on TPM public identifiers (zeta^f values where f is the TPM private key and zeta is a unique per-site constant) that the site decides are being used suspiciously often, suggesting that they are being shared by a group. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Unforgeable Blinded Credentials
Ben Laurie writes: If I have understood your description correctly it seems to me that this is defeated if, rather than sharing the master certificate, the bad guy allows their friend to proxy to them for whatever proofs are required. That way they never have to give up the precious master cert, but the friend's slave cert's still work. That's a good point, proxies are another way to get around limitations on credential sharing. Attempts to embed sensitive secrets in credentials don't work because there are no sensitive secrets today. You could use credit card numbers or government ID numbers (like US SSN) but in practice such numbers are widely available to the black hat community. Someone getting a credential using a stolen identifier won't be deterred from sharing it, if the only deterrence is fear of the identifier becoming public. Blacklisting seems to me to be the only good solution, and in fact it is the one proposed for the only proposed deployment of this technology I am aware of, Direct Anonymous Attestation proposed for the Trusted Computing group, http://www.zurich.ibm.com/security/daa/ . This is based on the CL signatures I referenced earlier. Trusted Computing systems have a credential which they are supposed to show to prove they are legit. But if these showing instances are linkable it is a privacy violation. (In practice IP address is normally going to provide just as much linkability, so for the most part this is all political posturing IMO, but in principle this would let you authenticate over TOR and retain your privacy.) DAA provides optionally unlinkable credential showing and relies on blacklisting to counter credential sharing. Actually the credentialed keys are supposed to be protected by hardware, so this is a second layer of defense in case someone figures out how to extract them from the chips. I'm skeptical that this will actually go forward; we are all familiar with the arguments against Trusted Computing proposals. But it is still of theoretical interest as a case study for unlinkable credentials which might actually be fielded in the near future. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Unforgeable Blinded Credentials
Ben Laurie writes: It is possible to use blind signatures to produce anonymity-preserving credentials It seems to me quite obvious that someone must have thought of this before - the question is who? Is it IP free? David Chaum did a great deal of work in this area in the 80s and 90s. He pretty much invented the idea of anonymous credentials. Stefan Brands used slightly different techniques a few years later to create improved versions. More recently, Camenisch and Lysyanskaya have created a number of anonymous credential systems based (roughly) on group signatures. Some work was obstructed by the patent on the Chaum blind signature technique, but that expired last year. I think your basic concept is IP free, but you should review the patents by these researchers to be sure. Obviously this kind of credential could be quite useful in identity management. Note, though, that this scheme doesn't give me unlinkability unless I only show each public/private key pair once. What I really need is a family of unlinkable public/private key pairs that I can somehow get signed with a single family signature (obviously this would need to be unlinkably transformed for each member of the key family). There is an operational difficulty with this goal as stated. To demonstrate it, consider a trivial way of achieving the goal. The credential issuer creates a special public/private key pair that is associated with the credential. To everyone who earns the credential, he reveals the private key (which is the same for everyone who has the credential). To show that he holds the credential, the key holder issues a signature using the private key corresponding to the publicly-known credential public key. Now he can show credential ownership as often as desired, without linkability, because all such demonstrations look the same, for all members. This illustrates a problem with multi-show credentials, that the holder could share his credential freely, and in some cases even publish it, and this would allow non-authorized parties to use it. To avoid this, more complicated techniques are needed that provide for the ability to revoke a credential or blacklist a credential holder, even in an environment of unlinkability. Camenisch and Lysyanskaya have done quite a bit of work along these lines, for example in http://www.zurich.ibm.com/%7Ejca/papers/camlys02b.pdf . Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Cfrg] HMAC-MD5
I (Hal Finney) wrote: 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? I have to apologize for that message; I was totally confused particularly in the second part where I discussed the impact of an MD5 preimage break on HMAC-MD5. What I described was completely wrong and had nothing to do with an attack on HMAC-MD5. Luckily the message was so long and poorly written that hopefully few people were able to follow it well enough to be misled. Again, apologies. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
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]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
This is getting pretty far afield from cryptography but it is a topic I find very interesting so I can't resist jumping in. John Denker writes: OK, in a moment we will have gone through four plies of no-it-isn't yes-it-is no-it-isn't yes-it-is. Let's get serious. The axiomatic definition of a measure is -- a mapping from sets to numbers -- positive -- additive on the countable union of disjoint sets And a probability measure has the further property of being -- bounded above I have checked that -- with due attention to trivial details -- .5 ^ (program length) satisfies this definition. If you wish to renew the assertion that there is no such probability measure, please explain which of the axiomatic requirements is not met. Please be specific. This is true, in fact it is sometimes called the universal distribution or universal measure. In more detail, it is a distribution over all finite-length strings. The measure for a particular string X is defined as the sum over all programs that output X of 1/2^L_i, where L_i is the length of each such program. Often the algorithmic complexity of a string is defined as the length of the shortest program to output the string. The universal measure is based on the same idea, but takes into consideration that there may be multiple programs that output the same string. Each program of length L_i contributes 1/2^L_i to the string's measure. If there is only one short program and all others are much longer, then the probability measure is essentially 1/2^C where C is the length of this shortest program, i.e. the algorithmic complexity. The universal measure for a string can also be thought of as the probability that, given a fixed Universal Turing Machine (UTM), a randomly chosen input program will output that string. So this is clearly a probability distribution (with some technicalities regarding issues of program lengths being glossed over here) as John Denker says. However to go from this to a notion of entropy is more questionable. There are a countably infinite number of finite strings, and all of them have non-zero probabilities under this distribution. This means that for most strings, the probability must be very low, asymptotically approaching zero. In fact you can show that for most strings of length n, their measure is 1/2^n; this is equivalent to saying that most strings are effectively random and have no shorter program to output them. Shannon entropy is defined over a probability distribution. That is, given a probability distribution we can find its Shannon entropy by summing -p_i / log2(p_i) over all members of the distribution. If we approximate the universal distribution by 1/2^n for strings of length n, this sum is clearly divergent. So there is not really a meaningful Shannon entropy for this probability distribution, or in other words the entropy is infinite. John Kelsey asked: Indeed, what's the probability distribution of the sequence of bits defined by Chaitin's Omega? This probability distribution is defined only over finite strings and so Omega is not within the universe of this distribution. It should also be noted that it is impossible for an n bit program to output more than n bits of Omega (plus or minus an additive constant specific to the UTM). Hence even if we consider successive approximations to Omega of ever increasing length, their measures would tend asymptotically to zero. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Fermat's primality test vs. Miller-Rabin
Ron Rivest reported on some theoretical and practical experimental work in Crypto 90, Finding Four Million Large Random Primes, http://theory.lcs.mit.edu/~rivest/Rivest-FindingFourMillionLargeRandomPrimes.ps A number n is a (base two) pseudoprime if it is composite and satisfies the identity 2^(n-1) = 1 mod n How rare are pseudoprimes? We performed an experiment that attempts to provide an answer... They tested 718 million random 256-bit values. First they performed a small divisor test using divisors up to 10^4. 43,741,404 numbers passed. These were then tested using the equation above (the Fermat test with base 2). 4,058,000 passed that further test. These were then subjected to 8 iterations of Miller-Rabin to see which were pseudoprimes. None of them were pseudoprimes. All of the numbers in this sample which passed the small divisor and base-2 Fermat test passed all subsequent MR tests and were presumably all prime. Rivest goes on and uses a conjecture of Pomerance to argue that the number of pseudoprimes 2^256 is at most 4 x 10^52, while the number of true primes is 6.5 x 10^74. Hence your chance of running into a pseudoprime is less than 1 in 10^22. I'm not sure the role of the small-divisor tests but I think that may make the odds even better. The larger primes in use today should also have improved odds. Based on this kind of result, RSAREF, the free library available from RSA back in the 90s, did not use MR and did not do multiple tests. It performed a small divisor test (only testing 3, 5, 7 and 11 as divisors!) and a single base 2 Fermat test, for its RSA keygen. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Fwd: Tor security advisory: DH handshake flaw
Ben Laurie writes: Apologies, slightly at cross-purposes here. For a start, Sophie Germain primes are needed for D-H (or rather, safe primes), and secondly, I was talking about proving arbitrary primes, rather than constructing provable primes. Dan Bernstein has lots of good information on the state of the art in general primality (and compositeness) proving. http://cr.yp.to/primetests.html points to his recent survey paper and has a table of the various algorithms. Interestingly there are considerable tradeoffs between proving time and verification time. There are some methods that create instant proofs but then take a long time to verify. http://cr.yp.to/ntheory.html has some of Dan's own work, including an algorithm which creates a certificate in time quadratic in length, with verification costing time proportional to the 4th power of the length. He suggests that at this point the best practical algorithm is based on elliptic curves, which is conjectured to have running time proportional to the 4th power of length for finding proofs and to the 3rd power for verifying them. I don't know what the actual numbers are for prime sizes of interest (presumably 1K-8K bits or so). References are available from his papers. Several programs to implement ECPP can be found from http://primes.utm.edu/links/programs/seeking_large_primes/. I don't know about source code however. It might be interesting to run these over some of the Oakley primes and publish the certs - I vaguely recall seeing something like that in an RFC. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Fwd: Tor security advisory: DH handshake flaw
Ben Laurie writes: Related to this is a project I keep considering and never quite getting around to is to include a prime proof verifier in OpenSSL. It would be pretty cool to have modes which only work when all relevant primes come with proofs. I've looked into this a few times, but have always ended up at a slight brick wall: I'd like to use proofs for which there's efficient (yes, I know efficient means only takes a few months to run) code to produce the proofs, as well as (obviously) efficient (where efficient means really fast) verifiers. This is, of course, so new proven primes can be produced without having to wait for someone with proprietary code to feel so inclined. If you look at Wei Dai's Crypto++ library, www.cryptopp.com, you will see two implementations of provable prime generators, called MihailescuProvablePrime and MaurerProvablePrime. The first in particular was quite fast and took only about 10 seconds to generate a 1024 bit prime on my laptop (1GHz Mac G4). However 2048 bit primes took more like 6 to 8 minutes, so it does slow down quite a bit for larger primes. These functions don't output the certificate that proves it to be prime, but they have a recursive structure and if you preserve the intermediate values then there is a fast way of verifying the resulting primes. The Mihailescu version is from his Crypto 94 paper which is available from his web site, http://www-math.uni-paderborn.de/~preda/ and also discusses verification. I googled and found a someone more recent paper by Mihailescu, http://grouper.ieee.org/groups/1363/P1363a/contributions/mihailescu.pdf. Oh, BTW, bonus points if the prover can be run on large numbers of processors in parallel. Even more points if communication between the CPUs are low bandwidth. Unless you're looking for primes with a special format, like Sophie Germain primes or ones with lots of 1's up front and/or in the back, or primes considerably larger than 2048 bits, current methods should be fast enough for most applications even on sequential processors. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Fwd: Tor security advisory: DH handshake flaw
- Forwarded message from Roger Dingledine [EMAIL PROTECTED] -
In Tor, clients negotiate a separate ephemeral DH handshake with each
server in the circuit, such that no single server (Bob) in the circuit
can know both the client (Alice) and her destinations. The DH handshake
is as follows. (See [1,2] for full details.)
Alice - Bob: E_{Bob}(g^x)
Bob - Alice: g^y, H(K)
Encrypting g^x to Bob's public key ensures that only Bob can learn g^x,
so only Bob can generate a K=g^{xy} that Alice will accept. (Alice, of
course, has no need to authenticate herself.)
The problem is that certain weak keys are unsafe for DH handshakes:
Alice - Mallory: E_{Bob}(g^x)
Mallory - Bob: E_{Bob}(g^0)
Bob - Mallory: g^y, H(1^y)
Mallory - Alice: g^0, H(1^y)
Now Alice and Bob have agreed on K=1 and they're both happy. In fact,
we can simplify the attack:
Alice - Mallory: E_{Bob}(g^x)
Mallory - Alice: g^0, H(1)
I was just at Crypto yesterday and Hugo Krawczyk in his talk emphasized
the difficulty of securely designing key exchange protocols. He was
talking about implicit authorization protocols where the exponentiation
involves the long term public key(s). This protocol is different but
there are still many ways things can go wrong.
This attack is an example of a small subgroup attack where the derived
value is forced into a small subgroup mod p, in this case the trivial
subgroup with one element. Sometimes other subgroups can be used,
such as the group with order two (consisting of 1, p-1), or potentially
other groups. But I checked the source code and Tor is using an Oakley
prime from RFC2409, with a generator g = 2. The prime p is such that
q = (p-1)/2 is prime also, and g generates the prime order subgroup of
size q. The only subgroups of such a p have order 1, 2, q, and 2q==(p-1).
By checking the received bignum is not 1, -1, or 0 (good catch, I forgot
about that one) and also not = p, you should be okay.
Oh, I just thought of another small-subgroup related attack. Very minor,
but a leak. Mallory lets Alice's message goes through but negates Bob's
g^y value:
Alice - Mallory: E_{Bob}(g^x)
Mallory - Bob: E_{Bob}(g^x)
Bob - Mallory: g^y, H(K)
Mallory - Alice: -g^y, H(K)
Now, the exchange will complete successfully only if x is even.
So Mallory learns this fact.
You also want to think about replay attacks with these protocols, but
I don't see much of an issue there. As long as x is fresh each time
then a replay shouldn't be possible. And if you're re-using x values
you probably have a lot more serious problems than replay attacks.
I'm not in love with publishing H(K), especially with the iffy state
of hash functions these days. Theoretically it provides another avenue
of attack to find the key. Granted, K is 1024 bits and H(K) only 160,
so even if H were invertable, K would still be unguessable, and we're a
long, long ways from inverting any modern hash functions.
Another way to accomplish the same thing would be to encrypt a known
value under the derived encryption key. Since you're going to be
encrypting lots of other stuff with the key, some of which you have to
pretty much assume is going to be known plaintext, you aren't exposing
any new weaknesses by doing that.
If you do want to use a hash, it's usually a good idea to throw as much
stuff into it as you have lying around. I would include g^x and g^y in
the hash. This would solve the attack you're worried about right there,
because Mallory doesn't know g^x. Probably include p and g as well,
and Bob's identity. It may be overkill but you never know when it will
stop an attack you didn't think of.
Ideally, I think Tor should switch to a different key exchange
protocol, one which has some degree of provable security, but
I am hesitant to recommend one. Looking at your docs I gather
that you have some pretty severe space constraints. Your article
http://tor.eff.org/doc/design-paper/tor-design.html#subsec:circuits says
that you didn't want to use a signature because you didn't have room
for it in your packet. It also says, Preliminary analysis with the
NRL protocol analyzer [35] shows this protocol to be secure (including
perfect forward secrecy) under the traditional Dolev-Yao model.
It's interesting that these attacks exist given this security analysis.
Maybe it was treating the arithmetic as something of a black box?
Chalk it up as another example of the limitations of these kinds of tools.
Hal Finney
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Possibly new result on truncating hashes
John Kelsey writes: The high order bit is that you can't generally guarantee that truncating your hash (chopping off some bits) won't weaken it. That is, if you chop SHA256 off to 160 bits as a replacement for SHA1 (something I'm working on with Niels Ferguson for X9 right now), it's possible that there's no attack on SHA256, but there is an attack on SHA160. This is a good point, but I think the lesson is that all the bits of a hash have to be strong, for it to be considered strong. If you have a 2^64 attack to find a collision in 160 bits of SHA256, then SHA256 is broken. It should not be possible to identify any subset of k bits in the output of a hash function, or more generally any function mapping the hash output to a k bit result, which can have collisions found in less than 2^(k/2) work. Whether hash functions like SHA256 can meet this standard is far from clear, unfortunately. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Menezes on HQMV
Eric Rescorla wrote, on July 1: There's an interesting paper up on eprint now: http://eprint.iacr.org/2005/205 Another look at HMQV Alfred Menezes ... In this paper we demonstrate that HMQV is insecure by presenting realistic attacks in the Canetti-Krawczyk model that recover a victim's static private key. We propose HMQV-1, a patched version of HMQV that resists our attacks (but does not have any performance advantages over MQV). We also identify the fallacies in the security proof for HMQV, critique the security model, and raise some questions about the assurances that proofs in this model can provide. Obviously, this is of inherent interest, but it also plays a part in the ongoing debate about the importance of proof as a technique for evaluating cryptographic protocols. I notice that Hugo Krawczyk has now responded by updating his HMQV paper at http://eprint.iacr.org/2005/176. The details are a little complicated; basicaly he agrees with Menezes about some things but disagrees on others. However he then goes on to address the underlying issue, the nature and use of proofs of security. [Krawczyk writes:] A personal perspective. I would like to thank Alfred Menezes for identifying the oversight in the HCR proof and the need for group membership verification in the one-pass protocol. At the same time, I must strongly disagree with the attempt in [32] to discredit the effort of the cryptographic community dedicated to improving our understanding and design of protocols. True, we make mistakes (and I do not justify my own); and proofs (even if correct) are never stronger than the model and assumptions they are based on. But with all its imperfection, this form of analysis is an essential tool for gaining confidence in the soundness of a cryptographic design. Moreover, as clearly shown here, the proof process itself serves as a guide in choosing the right design elements. At a time when we demand the best (almost perfect) security from basic encryption and hash functions, and having witnessed the effects of initially-mild attacks, we can only hope that the applied-cryptography community and its representing standard bodies will see formal analysis as a requirement, and main source of confidence, when adopting protocols for wide use. These analyses can (and must) be verified by the community at large (in contrast, ad-hoc designs do not even provide the 'luxury' of judging well-defined security properties). This is all the more significant in the case of a protocol such as MQV which is not only intended for wide commercial use but also to protect 'classified or mission critical national security information'. [End of Krawczyk comments] The question of the usefulness and value of proof techniques in cryptography will continue to be debated. Hugo Krawczyk is going to present his HMQV technique at Crypto next month, so perhaps there will be additional discussion there. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why Blockbuster looks at your ID.
Perry Metzger writes: So, what is to be done? I would propose that the replacement of the credit card infrastructure is needed. Fraud is prevalent because of a massive inherent security flaw in the current system, to whit, the account number is identical to the payment authenticator, and you can make a payment merely through possession of a piece of stolen plastic. A system in which the credit card was replaced by a small, calculator style token with a smartcard style connector could effectively eliminate most of the in person and over the net fraud we experience, and thus get rid of large costs in the system and get rid of the need for every Tom, Dick and Harry to see your drivers license when you make a purchase. It would both improve personal privacy and help the economy by massively reducing transaction costs. Have you ever used an ATM/debit card for a purchase? You swipe it and then the merchant hands you a keypad to enter your PIN. Yes, an insider could hack the device and steal your PIN along with your card, or use various other attacks to get the PIN, but it's much more complicated than using an opportunistically stolen credit card. These have come into common use in the past several years. I don't understand the commentary here which seems oblivious to the existence of this widely used alternative payment system in the U.S. All I am reading is oh, we can't switch, no one will ever switch from credit cards. People are switching; it's happening everywhere. A video game chain store in town, I think it's EBX, only accepts these cards, they won't take credit cards. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Peter Gutman writes:
[EMAIL PROTECTED] (Hal Finney) writes:
Steven M. Bellovin writes:
Dan Bernstein has a new cache timing attack on AES:
http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
This is a pretty alarming attack.
It is? Recovering a key from a server custom-written to act as an oracle for
the attacker? By this I don't even mean the timing-related stuff, but just
one that just acts as a basic encryption oracle.
Does it though? Take a look at the code at the end of Dan's paper,
server.c in Appendix A, which I have reproduced below. It does not appear
to act as an encryption oracle. It takes the input, which is *random*
(visible in Appendix C), encrypts it and returns the timing it took to
encrypt it. However, it does not return the encrypted result.
The one extra piece of information it does return is the encryption of
an all-zero packet. So there is a small element of chosen plaintext
involved.
But for all the rest, as far as I can see a passive eavesdropper on an
encrypted channel with a good timer could make it work.
Hal Finney
===
server.c:
#include sys/types.h
#include sys/socket.h
#include netinet/in.h
#include openssl/aes.h
unsigned int timestamp(void)
{
unsigned int bottom;
unsigned int top;
asm volatile(.byte 15;.byte 49 : =a(bottom),=d(top));
return bottom;
}
unsigned char key[16];
AES_KEY expanded;
unsigned char zero[16];
unsigned char scrambledzero[16];
void handle(char out[40],char in[],int len)
{
unsigned char workarea[len * 3];
int i;
for (i = 0;i 40;++i) out[i] = 0;
*(unsigned int *) (out + 32) = timestamp();
if (len 16) return;
for (i = 0;i 16;++i) out[i] = in[i];
for (i = 16;i len;++i) workarea[i] = in[i];
AES_encrypt(in,workarea,expanded);
/* a real server would now check AES-based authenticator, */
/* process legitimate packets, and generate useful output */
for (i = 0;i 16;++i) out[16 + i] = scrambledzero[i];
*(unsigned int *) (out + 36) = timestamp();
}
struct sockaddr_in server;
struct sockaddr_in client; socklen_t clientlen;
int s;
char in[1537];
int r;
char out[40];
main(int argc,char **argv)
{
if (read(0,key,sizeof key) sizeof key) return 111;
AES_set_encrypt_key(key,128,expanded);
AES_encrypt(zero,scrambledzero,expanded);
if (!argv[1]) return 100;
if (!inet_aton(argv[1],server.sin_addr)) return 100;
server.sin_family = AF_INET;
server.sin_port = htons(1);
s = socket(AF_INET,SOCK_DGRAM,0);
if (s == -1) return 111;
if (bind(s,(struct sockaddr *) server,sizeof server) == -1)
return 111;
for (;;) {
clientlen = sizeof client;
r = recvfrom(s,in,sizeof in,0
,(struct sockaddr *) client,clientlen);
if (r 16) continue;
if (r = sizeof in) continue;
handle(out,in,r);
sendto(s,out,40,0,(struct sockaddr *) client,clientlen);
}
}
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: AES cache timing attack
Steven M. Bellovin writes: Dan Bernstein has a new cache timing attack on AES: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf This is a pretty alarming attack. Bernstein was actually able to recover the AES key using a somewhat artificial server which reported its own timing to do an AES operation. In principle the same attack would be possible on a typical remote server, using a larger number of requests to average out timing variations. He also had some critical things to say about the AES selection process, which apparently dropped the ball on this issue. Other ciphers got dinged for nonconstant execution time, but no one thought that cache misses would be that significant. Dan has more information at http://cr.yp.to/mac.html, including graphs showing the variability in timings for various implementations at http://cr.yp.to/mac/variability1.html and http://cr.yp.to/mac/variability2.html, and his own attempt at a (nearly) constant-time AES implementation as part of his poly1305-aes MAC function. It would be interesting to see how the speed of his AES implementation compares to that of other widely used versions like Brian Gladman's. How much speed penalty do you pay to get the constant speed? As Dan notes, you can easily make a slow AES that runs at constant speed, but a fast one is far more difficult. I also wonder how it would compare to take something like Gladman's (supposing it is faster than Bernstein's), estimate its worst case running time, and then add a delay using a high-res timer from the operating system to make it always take the same time. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: expanding a password into many keys
Ian Grigg wrote: I'd like to take a password and expand it into several keys. It seems like a fairly simple operation of hashing the concatonatonation of the password with each key name in turn to get each key. The recommended technique I've seen for this (I think David Wagner suggested it on sci.crypt years ago) is to use a MAC: key = MAC (password, keyname) The security property of a MAC is that you can get as many messages MAC'd as you want, and you won't be able to guess a MAC on any new messages. That's exactly what you want here, that an attacker can learn keys when he knows or chooses keynames, but be unable to guess any keys for any other keynames. It's a good fit to the security requirements for your problem. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [IP] SHA-1 cracked?
Steve Bellovin writes: Note that finding a hash function collision by brute force is inherently harder, because it requires some communication: two widely-separated machines may have produced matching outputs, but they need to know about the other one. That's not necessarily true, although we don't know the details yet about the new attacks so we can't say for sure. (The new cert collision paper suggests that the details will be presented at Eurocrypt.) Some of the work in this area finds the collisions in a different way than might be expected. They start with a linear or nearly linear approximation to the hash function. On this basis they find an XOR or additive difference that will produce a collision. Then they look for an input for which this pre-chosen difference will produce a collision in the actual hash. That amounts to finding a text for which the nonlinearities cancel out in the proper way, so that the chosen difference works to produce a collision. In the case of MD5, the differential was only 6 (carefuly chosen!) bits. The hard part was to find a plaintext where the nonlinearities associated with those bits did not prevent the collision from occuring. http://eprint.iacr.org/2004/264.pdf presents some musings on the Wang attack and estimates that they could find a suitable text for this differential in 2^42.2 work, which is a couple of orders of magnitude more than what Wang apparently needs, indicating that she has more tricks up her sleeve. This method does not require comparing hashes from different plaintexts. Rather, each independent search engine is given the pre-chosen differential and tries to find a plaintext which satisfies the conditions that will allow a collision to occur. A machine to do this would be highly parallelizable and would not require any special communication capabilities. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
Ian Grigg writes: Stefan Brands just posted on my blog (and I saw reference to this in other blogs, posted anon) saying that it seems that Schneier forgot to mention that the paper has a footnote which says that the attack on full SHA-1 only works if some padding (which SHA-1 requires) is not done. http://www.financialcryptography.com/mt/archives/000355.html First, that's not quite what it says. According to what I have seen the language is, in reference to a pair of collisions exhibited for a weakened SHA, Note that padding rules were not applied to the messages. But that is irrelevant. The padding for SHA, aka Merkle Damgard strengthening, involves padding it up a a multiple of 512 bits, while appending a 1 bit and a 64 bit length field. If you have two messages M and M' which collide without this padding, they must by definition be a multiple of the block length. So you add one extra block which is a 1 bit, all zeros, and then the length of M. Now you have a legally padded pair of SHA messages which collide. In fact, you can add anything at all after the blocks which collide (the same thing to both messages). Once you have a collision it stays collided as long as the suffix is identical. None of the hashes exhibited by Wang et al at http://eprint.iacr.org/2004/199.pdf have the padding! That doesn't matter. They are still valid collisions and can be extended or padded any way we want while retaining the colliding property. Presumably the text in the footnote was a reference to this fact. Don't try to interpret it as meaning that the attack won't work against SHA. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Your source code, for sale
Enzo Michelangeli writes: In the world of international trade, where mutual distrust between buyer and seller is often the rule and there is no central authority to enforce the law, this is traditionally achieved by interposing not less than three trusted third parties: the shipping line, the opening bank and the negotiating bank. Interesting. In the e-gold case, both parties have the same bank, e-gold ltd. The corresponding protocol would be for the buyer to instruct e-gold to set aside some money which would go to the seller once the seller supplied a certain receipt. That receipt would be an email return receipt showing that the seller had sent the buyer the content with hash so-and-so, using a cryptographic email return-receipt protocol. You could imagine a trusted third party who would inspect the code and certify it, saying the source code with hash XXX appears to be legitimate Cisco source code. Then they could send you the code bit by bit and incrementally show that it matches the specified hash, using a crypto protocol for gradual release of secrets. You could simultaneously do a gradual release of some payment information in the other direction. But it's hard to assess the value of partially-released code. If the gradual transfer bits-against-cents is aborted, what is left to the buyer is likely to be unusable, whereas the partial payment still represents good value. Actually you can arrange it so that neither the partially-released code nor the partially-transferred ecash is of any value until the whole transfer finishes. For example, send the whole thing first in encrypted form, then release the encryption keys bit-by-bit. If someone aborts the protocol early, the best each side can do is a brute force search over the untransferred bits to try to find the key to unlock the data they received. A more general issue is that source code is not a commodity, and intellectual property is not real property: so the traditional cash on delivery paradigm just doesn't work, and looking for protocols implementing it kind of moot. If the code is treated as trade secret, rather than licensed, an anonymous buyer may make copies and resell them on the black market more than recovering his initial cost, at the same time undercutting your legitimate sales (see e.g. the cases of RC4 and RC2). This can cause losses order of magnitude larger than refusing to pay for his copy. That's a good point. Maybe you could use some kind of DRM or trusted computing concept to try to force the buyer to lock up his received data. For source code that would be pretty difficult though, it needs to be handled in flexible ways. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Your source code, for sale
Tyler Durden writes: So my newbie-style question is, is there an eGold that can be verified, but not accessed, until a 'release' code is sent? In other words, say I'm buying some hacker-ed code and pay in egold. I don't want them to be able to 'cash' the gold until I have the code. Meanwhile, they will want to see that the gold is at least there, even if they can't cash it yet. Is there a way to send a 'release' to an eGold (or other) payment? Better yet, a double simultaneous release feature makes thing even more interesting. I've been thinking about how to do this kind of thing with ecash. One project I'm hoping to work on next year is a P2P gambling game (like poker or something) using my rpow.net which is a sort of play-money ecash. You'd like to be able to do bets and have some kind of reasonable assurance that the other guy would pay up if he loses. In the case of your problem there is the issue of whether the source code you are buying is legitimate. Only once you have inspected it and satisfied yourself that it will suit your needs would you be willing to pay. But attaining that assurance will require examing the code in such detail that maybe you will decide that you don't need to pay. You could imagine a trusted third party who would inspect the code and certify it, saying the source code with hash XXX appears to be legitimate Cisco source code. Then they could send you the code bit by bit and incrementally show that it matches the specified hash, using a crypto protocol for gradual release of secrets. You could simultaneously do a gradual release of some payment information in the other direction. If you don't have a TTP, one idea for using ecash is Markus Jakobsson's Ripping Coins for a Fair Exchange. Basically you withdraw ecash from your account and in effect rip it in half and give half to the seller. Now he gives you the product and you give him the other half of the coin. The idea is that once you have given him the ripped ecash (torn would be a better word because ripping means something else today), you are out the value of the cash. You have no more incentive to cheat, as giving him the other half won't cost you anything additional. (Even without ecash, a service like egold could mimic this functionality. You'd create an escrow account with two passwords, one known to each party. Only with both passwords could data be withdrawn from the account. Then the buyer would transfer funds into this account. After receiving the goods, the buyer would send his password to the seller.) The problem is that if the source code you are purchasing is bogus, or if the other side doesn't come through, you're screwed because you've lost the value of the torn cash. The other side doesn't gain anything by this fraud, but they harm you, and if they are malicious that might be enough. And likewise you might be malicious and harm them by refusing to give them your half of the coin even after you have received the goods. Again, this doesn't benefit you, you're still out the money, but maybe you like causing trouble. Another idea along these lines is gradual payment for gradual release of the goods. You pay 10% of the amount and they give you 10% of the source code. You pay another 10% and you get the next 10% of the source, and so on. (Or it could be nonlinear; maybe they give out half the code for free, but the final 10% requires a large payment.) The idea is that you can sample and make sure they do appear to have the real thing with a fairly small investment. If there is some mechanism for the seller to have a reputation (like Advogato's perhaps, with some spoofing immunity) then the problem is easier; the seller won't want to screw buyers because it hurts his rep. In that case it may be reasonable to ask the buyer to pay in advance, perhaps using the partial payment system just discussed. These various ideas all have tradeoffs, and in general this kind of problem is hard to solve because of the complexity of what constitutes a successful transaction. A reputation system helps a great deal to resolve the issues, but opens up problems of its own. The betting problem I want to work on is relatively easy because there is no ambiguity about who wins, but even then it is hard to make sure that neither party can maliciously harm the other. Hal F. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Financial identity is *dangerous*? (was re: Fake companies, real money)
James Donald writes: On 19 Oct 2004 at 21:30, Ian Grigg wrote: we already have the answer, and have had it for a decade: store it on a trusted machine. Just say no to Windows XP. It's easy, especially when he's storing a bearer bond worth a car. What machine, attached to a network, using a web browser, and sending and receiving mail, would you trust? I would suggest pursuing work along the lines of a Virtual Machine Monitor (VMM) like VMWare. This way you can run a legacy OS, even Windows, alongside a high security simplified OS which handles your transactions. You run your regular buggy OS as usual, then hit a function key to switch into secure mode, which enables access to your financial data. The VMM does introduces some performance overhead but for typical web browsing and email tasks it will not be significant. This seems more promising than waiting for Windows to become secure, or for everyone to switch to Linux. I believe there are a number of academic projects along these lines, for example the Terra project, http://www.stanford.edu/~talg/papers/SOSP03/abstract.html , which uses a hardware security chip to try to protect one VM's data from another. I don't know if the extra complexity buys you much in this application though. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Crypto blogs?
Does anyone have pointers to crypto related weblogs? Bruce Schneier recently announced that Crypto-Gram would be coming out incrementally in blog form at http://www.schneier.com/blog/. I follow Ian Grigg's Financial Cryptography blog, http://www.financialcryptography.com/. Recently I learned about Adam Shostack's http://www.emergentchaos.com/, although it seems to be more security than crypto. Any other good ones? Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Time for new hash standard
Bruce Schneier wrote: Luckily, there are alternatives. The National Institute of Standards and Technology already has standards for longer - and harder to break - hash functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already government standards, and can already be used. This is a good stopgap, but I'd like to see more. Russell Nelson suggested: http://cr.yp.to/antiforgery.html#hash127 I believe this is a MAC, despite the name. It seems to be easier to create secure MACs than secure hash functions, perhaps because there are no secrets in a hash, while in a MAC there is a secret key that makes the attacker's job harder. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: potential new IETF WG on anonymous IPSec
The IETF has been discussing setting up a working group for anonymous IPSec. They will have a BOF at the next IETF in DC in November. They're also setting up a mailing list you might be interested in if you haven't heard about it already. ... http://www.postel.org/anonsec To clarify, this is not really anonymous in the usual sense. Rather it is a proposal to an extension to IPsec to allow for unauthenticated connections. Presently IPsec relies on either pre-shared secrets or a trusted third party CA to authenticate the connection. The new proposal would let connections go forward using a straight Diffie-Hellman type exchange without authentication. It also proposes less authentication of IP message packets, covering smaller subsets, as an option. The point has nothing to do with anonymity; rather it is an attempt to secure against weaknesses in TCP which have begun to be exploited. Sequence number guessing attacks are more successful today because of increasing bandwidth, and there have been several instances where they have caused disruption on the net. While workarounds are in place, a better solution is desirable. This new effort is Joe Touch's proposal to weaken IPsec so that it uses less resources and is easier to deploy. He calls the weaker version AnonSec. But it is not anonymous, all the parties know the addresses of their counterparts. Rather, it allows for a degree of security on connections between communicators who don't share any secrets or CAs. I don't think anonymous is the right word for this, and I hope the IETF comes up with a better one as they go forward. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Joux attack against multipreimages
I was looking at Joux's paper again and I noticed that he also had some comments regarding preimage resistance. I believe these imply a weakness even in the construction I proposed of using a double width hash and then collapsing the output down to single width at the end. My argument was that if the hash output size was n bits, so the internal width is 2n, then it would take 2^n work to find a collision on an internal block, but that was more work than it would take to break the hash function by brute force, hence it was not an attack. However I forgot that there are some problems which an n-bit hash should resist with even stronger than 2^n force. Specifically, the problem of finding multiple preimages, say 2^k preimages of some fixed value, should take about 2^k * 2^n work for an ideal hash function. There is no shortcut beyond trying random values and seeing if you get lucky, and for each value the chance of success is 1 in 2^n. However, Joux shows how to do better than this. He uses his trick of setting up k blocks and finding a collision in each. Even with my double width construction that takes k*2^n work. This gives us a 2^k multicollision. Now comes the new idea. Add one more block. Do an exhaustive search on that block to map the output from the multicollision to the desired hash function output, the one we are trying to find preimages of. That should take about 2^n work because the chance of success for any input is 1 in 2^n, since the actual hash output size is n bits after folding. Now this gives us 2^k preimages. For each of the 2^k possible choices in the multicollision, the extra block maps us to the desired output. We did (k+1)*2^n work and got 2^k preimages, but it should have taken us 2^k * 2^n work. This means that even the double-width hash construction is not as secure as an ideal hash. It is safe against multicollisions but not against multipreimages. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Seth Schoen's Hard to Verify Signatures
Hi, Adam - Yes, that's interesting. Seth Schoen's posting and
subsequent blog entries do compare his goals with hashcash and similar
stamp minting systems; where hashcash wants to make minting expensive
and verification easy, Seth's HTV signatures aim to make signing easy
and verifying expensive.
I think maybe you have observed an additional simplification. In my
case I use sender chooses x randomly (actually hash output of random
value and resource string), and computes y = x^{x^w} mod n as the work
function (expensive operation); and z = x^w mod phi(n), y =? x^z mod
n as the cheap operation (verification).
I think your approach could be applied on the encryption side too
resulting in simpler, faster verification. Instead it would be:
x is random, compute y = x^{2^t+1} mod n; verify x =? y^d mod n
The main advantage here I think is that d can be precomputed. However you
could do the same by using y = x^{2^w} instead of x^{x^w}. Then you could
precompute z = 2^w mod phi and you would have a single exponentiation
to verify just like in my scheme. The RSW time-lock-puzzle paper does
it this way, they use 2^w as the exponent where w is the work factor.
Hal
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: ?splints for broken hash functions
John Kelsey critiques the proposal from Practical Cryptography:
We do not know of any literature about how to fix the hash functions,
but here is what we came up with when writing this book. ... Let h be
one of the hash functions mentioned above. Instead of m-h(m), we use
m-h(h(m) || m) as hash function.
I believe this falls to a generalization of the Joux attack, as well. (Someone may
have already noticed this.)
a. I build a 2^{80} multicollision on h(m) using Joux' attack, requiring 80*2^{80}
work.
b. I now have 2^{80} different messages which are being hashed with the same IV. I
expect one pair of them to give me a collision.
You did 80*2^80 work to create a collision. But you could create a
collision without all this effort in only 2^80 work, by a conventional
birthday attack. Just ignore the internal structure and treat it as
a 160 bit hash function and you can collide in 2^80 work. You worked
harder than you needed to, so this is not a break.
Hal
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A splint for broken hash functions
Bear writes: This construction takes slightly more than twice as much work and twice as much internal state as a conventional hash function (embrace it guys, I don't think there's a way around it). H2(H1) = H1( H1(M) xor H1( TT( M))) TT denotes some trivial transformation (I propose swapping high and low halves of the first block). H1 is a conventional hash function and H2 is, I believe, fully resistant to the Joux attack. Keep in mind that there are two different attacks here. One is Joux's multicollision weakness in iterated hash functions, which is primarily of theoretical interest. The other is the recent work by Wang et al, Joux, and Biham which shows genuine attacks on weakened and full versions of presently-used hash functions. I think John Denker's suggestion was originally intended to make the class of practical attacks harder, by requiring them to solve two problems at once which interact with each other. Then he showed how to accomplish this while allowing incremental hashing, and indeed that construction appears to resist the Joux multicollision attack as well. It is that multicollision attack that we are focusing on here. I would suggest a further generalization of your approach: Hash ( Hash1(M) || Hash2(M) ) where Hash1 and Hash2 are different n-bit hash functions, and the outer Hash() takes a 2n-bit input to an n-bit output. As I suggested in my previous mail, I propose that Hash1 and Hash2 can be as similar as SHA-1 with two different IV's. This model captures John Denker's idea, yours above, as well as my suggestion in the previous mail. It is somewhat ironic to propose this, since Joux's paper had two main results: first, that iterated hash functions have too many multicollisions; and second, that as a result, parallel iterated hash functions are no stronger than the individual components. Yet here I have proposed exactly that construction, parallel iterated hash functions in the form of Hash1 || Hash2. The difference is that I don't try to get 2n strength out of it, I accept that it has only n bits of strength, and in fact collapse it down to n bits to make that explicit. So I have used Joux's forbidden construction to avoid Joux's attack. That it avoids his attack is seen as I argued before: (IV1) - B1 - B2 - B3 - ... Bk - H1 (IV2) - B1 - B2 - B3 - ... Bk - H2 The state functions that chain between the blocks will be different between the two lines, hence a block collision on one line will not be a collision on the other and Joux's multicollision construction will not work. The exception would be if a collision between the lines can be found, so that the top and bottom state functions become identical at some point. From that point on, the subsequent blocks can collide on both lines and the multicollision construction could work. To find such a collision between the lines we must find a block which maps two different chaining inputs to the same output. But a random compression function with two chaining inputs is like two different random functions. So we must find an input which causes two different n-bit random functions to collide. The chance of this happening for any input is 1/2^n so it will take about 2^n work to find one. This is the work necessary to find a collision between the lines. This level of work is greater than that needed to invert the overall hash construction hence does not represent an attack. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How thorough are the hash breaks, anyway?
Dan Carosone wrote: There is one application of hashes, however, that fits these limitations very closely and has me particularly worried: certificates. The public key data is public, and it's a random bitpattern where nobody would ever notice a few different bits. If someone finds a collision for microsoft's windows update cert (or a number of other possibilities), and the fan is well and truly buried in it. A more likely attack along these lines would be to create two certificates which collided and had identical keys but different identification information or other attributes. If you could create a situation where a cert on microsoft.com collided with one on jf8l23fzq.com, you could easily get the second one certified, and the signature on it would also validate when you substituted microsoft.com. Presto, you could successfully masquerade as Microsoft. This is a collision attack rather than a second preimage attack as you propose and so should be far easier to mount. The attack requires being able to predict the exact form of the cert, including validity dates and serial number. The latter is chosen by the CA and depending on its policies, may be easy or hard to predict. The name serial number suggests a degree of sequentiality and some CAs may follow such a policy, which could allow a motivated attacker to predict the value with considerable accuracy. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
Jerry Leichter writes: However ... *any* on-line algorithm falls to a Joux-style attack. An algorithm with fixed internal memory that can only read its input linearly, exactly once, can be modeled as an FSM. A Joux-style attack then is: Find a pair of inputs M1 and M1' that, starting from the fixed initial state, both leave the FSM in state S. Now find a pair of inputs M2 and M2' that, starting from S, leave the FSM in state S'. Then for the cost of finding these two collisions, we have *four* distinct collisions as before. More generally, by just continuing from state S' to S'' and so on, for the cost of k single collision searches, we get 2^k collisions. That's an interesting point. One counter example I can offer is my earlier suggestion to use a wide path internally between the stages. The analysis suggested that if the internal path was twice the width of the output of the hash, the Joux attack was avoided. Basically if the hash output width is n, and the internal width is 2n, then it will take 2^n to find an internal collision. And the overall hash strength is never more than 2^n against any attack, since you can exhaustively invert the function for that effort. So nothing based on internal collisions can weaken a hash built around this principle. It's not a particularly appealing design strategy due to its apparent inefficiency. But if you're right about the general vulnerability of hashes that support incremental hashing, as any useful hash surely must, then perhaps it is worth exploring. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
Jerry Leichter writes:
It all depends on how you define an attack, and how you choose to define your
security. I explored the outer edge: Distinguishability from a random
function. For a random function from {0,1}*-{0,1}^k, we expect to have to do
2^k work (where the unit of work is an evaluation of the function) per
collision. The collisions are all independent - if you've found N, you have
... N. The next one you want still costs you 2^k work.
I don't believe this correct. Joux said that for a true random function,
finding a multicollision of degree j, i.e. j distinct values which hash
to the same thing, takes 2^((j-1)*k/j) for a k-bit hash. He mentioned
a Crypto paper by David Wagner from a few years ago which showed how
to do this. See http://www.cs.berkeley.edu/~daw/papers/genbday.html .
This means that the work for a (j+1)-collision is about 2^(k/j^2) times
harder than for a j-collision, not 2^k times harder.
Now, this is not done by first finding a j-collision and then looking
for a new value that matches; that would, as you say, take 2^k times
the work. Rather, one collects enough hashes and then matches them up
in an efficient way to find the (j+1)-collision.
The wide-internal-path proposal will therefore satisfy the constraints
about multicollisions. With a 2k bit wide internal path for a k bit hash,
it will take 2^k work to find an internal collision. With some multiple
of this, Joux's attack finds large multicollisions. But as the paper by
Wagner shows, you can find arbitrarily large multicollisions in a true
random k-bit function with less than 2^k work. Since Joux's attack
takes more than this, it does not distinguish this hash construction
from a random function.
Hal
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
Bear writes: One interesting idea which I came up with and haven't seen a way past yet is to XOR each block with a value computed from its sequence number, then compute the hash function on the blocks in a nonsequential order based on the plaintext of the blocks. In concrete terms, you have a message of n blocks, p1 through pn. you xor each block with a value computed by a nonlinear function from its sequence number to get q1 through qn. Now rearrange q1 through qn by imposing a total ordering on p1 through pn: for example if p4 sorted before p7, you put q4 in front of q7. Finally, you compute the hash value on the blocks q1 through qn in their new order. This is an interesting idea, but it does not fully prevent the Joux attack. This is seen most obviously in the two block case, where your method can at most increase the attacker's work by a factor of 2. Joux shows how to find a 4-collision using 2*2^(n/2) work, while it should take 2^(3n/4) work. In the case of a 160 bit hash this is the difference between 2^81 and 2^120. Doubling the work to find the 4-collision will not do much to address this discrepency. Even in the more general case, where Joux puts k blocks together to generate 2^k multicollisions, I can see a way to attack your method, with an increase in the work by only a factor of k^2. The attacker could choose an ordering of the blocks ahead of time, and find collisions which preserve that order. Specifically, he can start searching for collisions in the first one, which WOLOG we will call q1. He can continue to search until he finds a collision which puts p1 into the first 1/k of block address space, which will guarantee that this block will sort first. This will increase his work by a factor of k^2 (because only 1/k of the time will he get lucky, for each of the two blocks in the collision). Then he can find a collision in q2 which puts p2 into the 2nd 1/k of block-address space, guaranteeing that p2 will sort as the second block. Again this increases the work by k^2. Proceeding down the line he produces a collision which leaves the blocks in his pre-chosen order, at a cost of k^2 more work. Joux shows that finding an 2^k collision takes k times the work to find a single block collision. Among other things he shows how this reduces the work to find a collision in the output of two independent n-bit hashes from 2^n to n*2^(n/2). Your approach effectively makes this (n^3)*2^(n/2) which is an improvement, but still not attaining the exponential security increase expected from ideal hash functions. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
Jerry Leichter writes: It strikes me that Joux's attack relies on *two* features of current constructions: The block-at-a-time structure, and the fact that the state passed from block to block is the same size as the output state. Suppose we did ciphertext chaining: For block i, the input to the compression function is the compressed previous state and the xor of block i and block i-1. Then I can no longer mix-and-match pairs of collisions to find new ones. Here's how I understand what you are suggesting. Presently the hash compression function takes two inputs: a state, and an input data block. For SHA-1 the state is 160 bits and the input data block is 512 bits. It outputs a state-size block of 160 bits, which gets fed into the next block: IV --- COMP --- COMP --- COMP --- Output ^ ^ ^ | | | | | | Block 1 Block 2 Block 3 I think you are proposing to increase the output of each block by 512 bits in this case, so as to provide some data that can be xored into the input data block of the next stage, a la CBC: IV --- COMP --- COMP --- COMP --- Output ^ \ ^ \ ^ |\-- X\-- X | | | Block 1 Block 2 Block 3 By itself, adding an xor step doesn't do anything. The attacker would still have full control of the output of the xor, since he has full control of one of its two inputs. So I think it is more appropriate to merely think of the compression function block as taking a wider state input from the previous stage, and not specify how the input data block is mixed with the previous state. This might lead to a construction in which the state passed from block to block is, say, 512 bits, rather than 160. The compression function still takes two inputs, the state and the input block, and now produces a 512 bit output. IV === COMP === COMP === COMP --- Output ^ ^ ^ | | | | | | Block 1 Block 2 Block 3 (Here, the == are meant to depict wide paths.) For the final output of the hash, we would presumably derate the output of the last stage down to 160 bits and not claim the full 512 bits of security. If we didn't do this step, then the construction is precisely SHA-512 and Joux's attack still applies. This approach does appear to defeat the Joux attack. Finding a collision in a sub-block which takes a 512 bit input to a 512 bit output will take 2^256 work rather than the 2^80 in the SHA-1 compression function. So you will never find a multicollision in less work than this. And the most strength SHA-1 can provide against anything is 2^160 since that it what it takes to invert it. Since 2^256 is greater than 2^160, the construction is strong against this attack. We can also see from this analysis that making the paths 512 bits wide is overkill; they only need to be twice the claimed hash strength, or 320 bits wide in this case. Or in other words, if we took SHA-512 and only claimed it to have 256 bits of strength, it would avoid the Joux attack. However, the problem with this construction is that the inner blocks now genuinely need to have 512 bits of strength, and that may not be that easy to provide. SHA-512's compression function does claim to have that amount of collision resistance, but it is difficult to analyze such strong claims, and adding this much strength may make for a slow hash. Plus, given that we have managed to create a block with 512 bits of security, it seems a shame to throw away half of the strength to produce an output that avoids the Joux attack. I think cryptographers will look harder to try to find a way of combining sub-blocks which will retain the strength of the individual pieces rather than throwing half of it away. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
Jerry Leichter writes: Joux's attack says: Find single block messages M1 and M1' that collide on the blank initial state. Now find messages M2 amd M2' that collide with the (common) final state from M1 and M1'. Then you hav four 2-block collisions for the cost of two: M1|M2, M1'|M2, and so on. But even a simple XOR breaks this. M1 and M1' have the same hash H, but the state being passed is now very different: H,M1 in one case, H,M1' in the other. So M1|M2 and M1'|M2 are completely different: Both started the second step with the compression function in state H, but the first compressed M1 XOR M2, and the second M1' XOR M2. Okay, I misunderstood your earlier suggestion. Sorry. Rereading it: Suppose we did ciphertext chaining: For block i, the input to the compression function is the compressed previous state and the xor of block i and block i-1. Then I can no longer mix-and-match pairs of collisions to find new ones. It sounds like you're saying that that the input to the second compression function should be M1 XOR M2 instead of just M2. Like this: IV --- COMP --- COMP --- COMP --- Output ^ ^ ^ |/-- X/-- X | / | / | Block 1 Block 2 Block 3 But this is easily compensated for: if you wanted the input to the 2nd compression stage to be M2, you'd just input M1 XOR M2 instead. Then when this gets XOR'd with M1, M1 will will cancel out in the XOR and you'll have a nice clean M2 going into COMP, just as you wanted. So if you found a compression-function collision starting with IV on M1 and M1', and you found a collision starting with the common output of that stage on M2 and M2', your four collisions would be: M1 || (M1 xor M2) M1 || (M1 xor M2') M1' || (M1' xor M2) M1' || (M1' xor M2') In each case the actual input to the 2nd block compression function (after xoring with the first block input) would be M2 or M2', as desired. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: On hash breaks, was Re: First quantum crypto bank transfer
Joe Ashwood writes: Except for RIPEM there were known to be reasons for this, MD5 was known to be flawed, SHA-0 was replaced because it was flawed (although knowledge of the nature of the flaw was hidden). Even with RIPEM (and SHA-1 for the same reason) I have plans in place (and have had for some time) the move away from 160-bit hashes to larger ones, so the attack on RIPEM had little effect on me and my clients... A minor terminology correction: the hash is RIPEMD, the more recent (and still unbroken) version being RIPEMD-160. RIPEMD is the RIPE Message Digest, where RIPE is the EU's RACE Integrity Primitives Evaluation project, and I haven't been able to find out what RACE stands for. RIPEM was an old implementation by Mark Riordan of the PEM (Privacy Enhanced Email) standard which preceded S/MIME. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RPOW - Reusable Proofs of Work
Matt Crawford writes: If you think of POW as a possible SPAM mitigation, how does the first receiving MTA assure the next MTA in line that a message was paid for? Certainly the mail relay doesn't want to do new work, but the second MTA doesn't know that the first isn't a spambot. The first MTA would exchange the received RPOW for a new one of equal value, and pass it along with the message to the next MTA in line. Hal - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RPOW - Reusable Proofs of Work
Bear writes: I'm wondering how applicable RPOW is. Generally speaking, all the practical applications I can think of for a proof-of-work are defeated if proofs-of-work are storable, transferable, or reusable. Once they're storable, tranferable, and reusable, aren't we restricted to applications already nailed down by digital cash schemes? Well, there are no digital cash implementations that I am aware of. I think of RPOWs as a sort of play money that might be usable in some applications that would otherwise use digital cash. I have some code to play online games with cryptographic protection, cards and dice, and I am planning to modify it to let people make bets with RPOWs as the betting chips. Another way to think of RPOWs is as an implementation of Nick Szabo's concept of bit gold. These are made of bits but have the rarity and verifiable costliness of a commodity like gold. Of course they lack gold's appeal and attractiveness. Perhaps they could be better thought of as bit copper. Why doesn't this scheme give rise to a POW server that just sits there, generating proofs-of-work in advance of need and dispensing them at request? Or even to a company that sells POW's to people who can't be bothered to run their own server? And doesn't such a device or service defeat the use of POWs for real-time load balancing, traffic control, etc? It's possible that these things could happen, but that's not necessarily bad. After all, if people ever got to where they would buy and sell RPOWs for money, they could serve in place of ecash. The main question is whether there will be any use for them so compelling that people would buy them. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: HMAC?
More on the question of HMAC. As mentioned before, the potential attack
would be to find a collision on the inner hash, even without knowing the
key. Since the key is exactly one hash block in length, the effect is
identical to finding a hash collision without knowing the IV.
Discussing this issue with Niels Ferguson, he pointed out that it
might turn out that the new attacks do provide some slight advantage for
guessing a hash collision even without knowing the IV values. There might
be some differential, and conceivably even some choice of inputs, which
would have an enhanced collision probability. If that were greater than
the one in 2^64 chance of a collision one would ordinarily expect with,
say, MD5, then technically that would be called a break of HMAC-MD5,
even if it were not possible to exploit it in practice.
Another point that was mentioned in the presentation on the new MD4
collisions was that they were so easy to find that the work factor was in
the range from 4 to 64. It's not entirely clear what that means, but the
claim was that the work was so simple that it could be completed by hand.
I thought it was conceivable that this meant that some substantial
fraction of random inputs to MD4 would collide when using the differential
described in the eprint posting, so I tested that. I wrote some code
to choose a random 512 bit block and then hash both it and a block
with the published differentials using MD4, and check for a collision.
I let it run for 1.7 billion tries without finding any. The code is
below, but note that it will only run on a little-endian machine since
their differentials are for 32-bit blocks in that form.
So at least it's not just a matter of finding the right differential.
You've got to be somewhat smart in choosing the data values, which would
make it harder to attack HMAC since you presumably would not be able to
choose the data without knowing the IV. It may still be that you could
do something with HMAC built on one of the broken ciphers, but we will
have to wait for a fuller description of the technique.
Hal Finney
===
/* Experiment with random MD4 values to see if the Wang differentials
* work just getting lucky.
*/
#include stdio.h
#include string.h
#include openssl/rand.h
#include openssl/md4.h
typedef unsigned char uchar;
unsigned wang[16] = {
0x4d7a9c83, 0x56cb927a, 0xb9d5a578, 0x57a7a5ee, 0xde748a3c, 0xdcc366b3,
0xb683a020, 0x3b2a5d9f,
0xc69d71b3, 0xf9e99198, 0xd79f805e, 0xa63bb2e8, 0x45dd8e31, 0x97e31fe5,
0x2794bf08, 0xb9e8c3e9
};
unsigned buf1[16];
unsigned buf2[16];
uchar md1[16];
uchar md2[16];
void
memdump (unsigned char *buf, int buflen)
{
int i;
for (i=0; ibuflen; i++)
printf (%02x%s, buf[i], ((i+1)%16)==0?\n: );
if (buflen%16)
printf (\n);
}
main ()
{
int i;
int d1, d2, d12;
d1 = 1UL31;
d2 = (1UL31) - (128);
d12 = -(116);
/* Try an actual Wang collision the first time through for testing */
memcpy (buf1, wang, sizeof(buf1));
for (i=0; ; i++)
{
memcpy (buf2, buf1, sizeof(buf1));
buf2[1] += d1;
buf2[2] += d2;
buf2[12] += d12;
MD4 ((unsigned char *)buf1, sizeof(buf1), md1);
MD4 ((unsigned char *)buf2, sizeof(buf2), md2);
if (memcmp (md1, md2, sizeof(md1)) == 0)
{
printf (Collision on iteration %d\n, i);
memdump ((unsigned char *)buf1, sizeof(buf1));
printf (\n);
memdump ((unsigned char *)buf2, sizeof(buf2));
if (i 0)
exit (0);
}
if (i % 10 == 0)
{
printf (Iteration %d\n, i);
}
RAND_bytes ((unsigned char *)buf1, sizeof(buf1));
}
}
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
