LibTomCrypt [horrible bug]

[Tom St Denis]

Seems I didn't really put much thought into the ECC code in
LibTomCrypt. The existing signature system wasn't secure at all.
Furthermore, I'm surprised nobody noticed until I was laying in bed
working on the math. In my defense I wrote it when I was just learning
about ECC and was hoping it would be just like DH...I don't know what
to say other than I'm really embarassed.

I've since replaced the ecc_sign function and replaced it with ECDSA
using the ASN.1 DER encoding recommended by ANSI. [Will be in 1.03 to
be released May 7th]. The rest of the ECC code uses my LTC-brew packet
formats.

In the grand scheme of things RSA has been top-dog in terms of priority
and the others have been neglected. I hope to start re-writing the ECC
code towards X9.62 compliance in the future given the time.

This is a good indication that some serious scrutiny of the code base
is required. Ideally I'd like to get some independent review of my
PKCS #1 code [oaep/pss] at the very least.

So the changes didn't require an API change but the binaries aren't
compatible [which is a good thing]. On a positive front I've automated
quite a bit of the testing which helps find build troubles. I've also
added ASN.1 BIT and OCTET string routines. I've added some more flags
to make configuring the library easier from the shell and I've cleaned
up a few typos.

Tom

[Scott "Poncho" Fluhrer]

"Tom St Denis" <tomst...@gmail.com> wrote in message
news:1115006531.0...@z14g2000cwz.googlegroups.com...

>
> Tom St Denis wrote:
>> Seems I didn't really put much thought into the ECC code in
>> LibTomCrypt. The existing signature system wasn't secure at all.
>> Furthermore, I'm surprised nobody noticed until I was laying in bed
>> working on the math. In my defense I wrote it when I was just
> learning
>> about ECC and was hoping it would be just like DH...I don't know what
>> to say other than I'm really embarassed.
>

> Maybe I was a bit too hasty in my sleeptime analysis... the previous
> signature scheme was
>
> m = message
> x = secret
> k = random
> G = base
> Y = xG = public key
>
> a = (m - x)/k
> B = kG
> Signature = (a, B)
>
> Verification is
> aB + Y = mG
>
> What I was thinking was the problem is an attacker can fix k [say k=1]
> then generate valid "a" such that the verification works.
>
> An attacker can find point C such that C+Y = mG by simply computing C =
> mG - Y. However that doesn't yield them "x" and the protocol requires
> computing aB, you can't just give it a point C to use as aB.
>
> So the attacker would have to find some "a" such that aG + Y = mG [by
> fixing k=1]. Of course if an attacker could find "a" then they can
> find "x" from Y. By "I should have gone to bed an hour ago" logic ...
> this is reducible to the EC DLP.
>
> The protocol as I now think about it wasn't insecure.

Yes, it is insecure -- the signature pair (1, C) would verify. Even if you
disallow that case, the attacker can create a valid random signature by
selecting a random value for a, and then computing (a^-1)C (where the
inverse is modulo the order of the curve). This is not a key recovery
attack, in the sense that the attacker cannot reconstruct the private key
(x), but it does allow the attacker to sign arbitrary messages (which is the
entire reason for him wanting the private key in the first place)

>
> Of course now I've replaced the code with ECDSA ... hehehe I could
> revert but I guess this was just a way the some users tricked me into
> coding it [I've had some demand for ECDSA ...]. Since I an
> entertaining an ECC key format that follows X9.62 I think I'll stick
> with ECDSA [even though it's technically slower].
>
> Tom
>

[Tom St Denis]

Scott Poncho Fluhrer wrote:
> Yes, it is insecure -- the signature pair (1, C) would verify. Even
if you
> disallow that case, the attacker can create a valid random signature
by
> selecting a random value for a, and then computing (a^-1)C (where the

> inverse is modulo the order of the curve). This is not a key
recovery
> attack, in the sense that the attacker cannot reconstruct the private
key
> (x), but it does allow the attacker to sign arbitrary messages (which
is the
> entire reason for him wanting the private key in the first place)

That's what I was trying to get to. Arrg. So my hunch was right.
Well not much I can do at this point. I've replaced the code with
ECDSA.

Tom

[Tom St Denis]

Tom St Denis wrote:
> That's what I was trying to get to. Arrg. So my hunch was right.
> Well not much I can do at this point. I've replaced the code with
> ECDSA.

I've put a notice on my website. If anyone is on bugtraq or other
vulnerability mailing lists can you get the word out?

The May 7th release will sport ECDSA [ANSI X9.62] and prior releases
should be considered highly insecure for ECC signatures.

Tom