[OTR-dev] DSA, RSA, ECDSA, etc

[Jacob Appelbaum]

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