dmolnar writes: > On Sat, 1 Jul 2000, William Rowden wrote: > > > * What are the advantages and disadvantages of these algorithm > > changes?: > > RSA -> ElGamal > > After September 20, patents will be a non-issue for both systems. > Discrete logs are thought to be slightly harder than factoring, because > current best known algorithms require the final matrix elimination > step to be done mod a large number instead of mod 2. > > I would call this a wash with a slight nod to Elgamal in terms of > security. Except for message expansion. The overhead is huge compared with the nested approach I suggested for RSA. I got it down to 4 bytes per hop of additional public key overhead (or whatever the minimum RSA padding one prefers minus 16 bytes of mixmaster padding seed if you reuse the padding for that). You'd be looking at 256 bytes per hop, or still 128 bytes per hop with Bodo's suggestion of Elgamal encryption. (Hash DH secret and XOR with message). > > PKCS #1 v1.5 -> v2 (OAEP) w/MGF1 > > PKCS #1 v1.5 is known to be broken since Bleichenbacher's attack. Given > enough answers to the question "is this ciphertext well-formed?" an > adversary can recover the plaintext from a ciphertext. While the current > best known form of the attack takes 2^20 queries, there are two things to > consider > 1) a remailer is a pretty good target for a chosen ciphertext > kind of attack -- it decrypts pretty much everything coming in > 2) we can do better. > > OAEP is not patented and so far seems to resist the attack. I haven't > considered message expansion of v1.5, but OAEP loses only the size > of a random padding value. I don't think Bleichenbacher's attack is directly relevant to mixmaster: mixmaster does not send you a message saying: "that one had a bad asymmetric padding value", as many web servers were doing; your chances of getting a message to leave the remailer after modifying it are slim if you didn't create it. > > MD5 -> SHA-1 > > I would prefer SHA1. Larger hash, not so many "almost" attacks as on MD5. > Maybe we should also consider RIPEMD-160 ? I wouldn't recommend adding more than necessary. Complexity is the enemy of security; SHA1 by itself should be sufficient, RIPEMD-160 isn't adding anything over that other than complexity of supporting another hash. > > Some considerations might be patents (for a little while), message > > size, and known attacks. > > * Should version 3 consider ECC? AES candidates? > > ECC would allow a smaller public key block size. I don't think this adds anything if you use my nested RSA suggestion. > Whether that's good or bad depends on how much you want to stuff > into the public key. You put whatever fits, and you nest them, and then it doesn't matter what fits in the public key part beyond the minimum of the symmetric key to continue encrypting with and any padding overhead. > The efficiency gains may not be as important unless we want to build > embedded or wireless Mixmaster nodes... :) ECC may be a fair bit faster -- are there any fast open source free ECC libraries anyone has performance figures for? But even speed is becoming less relevant too -- entry level machines can burn through RSA modexps these days. Adam
