Hi, I've been thinking a lot about something written by Nate Lawson on the subject of breaking DSA: http://rdist.root.org/2009/05/17/the-debian-pgp-disaster-that-almost-was/
To recap what Ian and most others know - if the RNG goes badly, a single message signed with DSA will leak enough information for an attacker to recover the private key. The theory goes that the RNG won't go badly and so, we're all good. I am not a fan of this strategy. Nate's suggestion is to make the k DSA related to the message - I like this idea. It suggests that if we make k related to the message but still entropic, the chances of things going bad by chance is more throughly negated. One way might be to take a MAC over the message and to take some random bits and ensure that k is derived from the two. Another way is perhaps to take a time stamp hashed with k and then hashed with the MAC of the message. Clearly some cryptographers like Nate have come up with a good way to fix the repeating k problem when the RNG goes badly but such changes are not in libgcrypt... So - a few things come up for me - one is that DSA as it is used in OTR could be dangerous if things go badly with the RNG, we could "fix" DSA but then we're not really DSA, we're a modified DSA (random k vs deterministic k) - at best with a semi-deterministic k ( k = H( MAC(message), H(random bits + time stamp))) or however it might be called. So is modified DSA better? Do we really care about NIST and their thoughts on the subject when there is a real problem to be dealt with? Is one of the choices better than the other? I think so. I think a totally random K with a bad RNG is deadly, so we could try to detect such a bad RNG but well, who does that? And how shall it be done anyway? It seems that no one really has answered those questions in the Free Software world. The best anyone came up with was some blacklists after the RNG was found to be broken - hardly useful people who are already in trouble. But what is the right way to ensure that k has some safety without being weaker by being predictable? I imagine a lot of OTR conversations start with pretty well known plaintext such as "hi" or "hello" or some variant. So a hash or a MAC over that message as part of k isn't really well, unpredictable. I guess this is an open question but one that as it is left unanswered, I worry that it could open people up to problems. I think it would take an active MITM to even begin to collect the data needed for starting to try to attack the messages. That is unless alice is being attacked by bob, her frequent chatting partner - then a conversation is all that it would take - I think. This of course leads me to ECDSA - which unless I'm totally off base would have the exact same issue. So if we want to move to ECDSA at some point - which seems pretty great - what happens? Do we want to tackle the k problem? I wonder then if the right answer is to extend libotr to use RSA - certainly on devices with likely crappy entropy under load and certainly in say, web browsers with highly suspect RNG properties... My first thought is that it would be good to hack up a patch for libgcrypt to have a sign() function in dsa.c that has a k with some relation to the message. I would say that using that would be good if someone like Nate or Ian felt that it would protect against a bad RNG bug, like the Debian bug or such as the recent Usenix security paper by Nadia. My second thought is that it would be interesting to add RSA as a key type to libotr. If so, what key size is reasonable? I'd wager that 1024 for RSA is dead now for some attackers - what seems reasonable if it was to be used for the next ten years? 2048 bits? I'd welcome a converstaion on these topics as I'd like to add an RSA key type at the very least. I want to reach a consensus on how to improve libgcrypt's dsa sign() function or to make a different sign() function that is slightly "improved" in this specific case. I think that would improve the chances of Werner accepting the patch and others using it. I haven't started on the RSA work in libotr yet. I have already written some basic libgcrypt patches such as checking for cases of 0 where it can't be but I haven't really decided on how to modify k yet. All the best, Jake _______________________________________________ OTR-dev mailing list OTR-dev@lists.cypherpunks.ca http://lists.cypherpunks.ca/mailman/listinfo/otr-dev
