Subject: Stupid hash question?

From: Ben Laurie <[email-masked]>
Date: Mon, 30 May 2005 10:19:32 +0100

I've been working on signatures recently, and I'm puzzled. As I
understand it, the form of a decrypted signature is:

01 FF FF ... FF FF 00 <ASN.1 nonsense> <hash>

However, every signature I look at decrypts to:

00 01 FF FF ... FF FF 00 <ASN.1 nonsense> <hash>

Before I hurt my head trying to figure out why, I wonder if there's
something obvious I missed?

Cheers,

Ben.

---

From: "Konrad Rosenbaum" <[email-masked]>
Date: Mon, 30 May 2005 12:10:28 +0200 (CEST)

> something obvious I missed?

Hi Ben,

leading zeros can be left out while it is still a large integer. Eg. for
RSA signatures it is pretty normal that the signature is a) one byte
smaller than the RSA-n or b) contains a leading zero. This pretty much
depends on your implementation of large integers. Or to give you an
example in C:

It does not matter whether you assign
int a=0x01;
or:
int a=0x000001;
or.... whatever, it is still a "1".

Really, leave the leading zero out. Even the former east-block states got
rid of their leading zeros - it works pretty well... ;-)

    Konrad

---

From: Ben Laurie <[email-masked]>
Date: Mon, 30 May 2005 13:14:43 +0100

> or.... whatever, it is still a "1".

I realise that, but if I do that, then I have one less FF than I (think)
I should have.

Cheers,

Ben.

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 31 May 2005 00:24:57 +1200

Ben Laurie <[email-masked]> writes:

>I have one less FF than I (think) I should have.

You don't count the FF's, you just continue along them until you find a non-
FF.

Peter.

---

From: Ben Laurie <[email-masked]>
Date: Mon, 30 May 2005 15:36:46 +0100

> You don't count the FF's, you just continue along them until you find a non-

This is incorrect.

However, further research answers my own question and reveals a bug in
d-i-o-r-13. RFC 2437 specifies RSA signing in section 8.1.1 - and this
uses (for some reason, any idea why?) an EMSA-PKCS1-V1_5 encoding of
length k-1 (where k is the keylength in octets). I presume that OpenPGP
uses this algorithm. The I-D does not specify the length of the
encoding, which is a bug: it should either specify it is of length k-1
or refer to RFC 2437 8.1.1.

However, I'm still left with a question, since 2437 only specifies RSA
signatures. What lengths should be used with DSA and Elgamal?

Of course, since these will have to be specified, it would make more
sense to specify the length in the I-D than to refer to 2437 for it.

Cheers,

Ben.

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 31 May 2005 03:58:14 +1200

>>You don't count the FF's, you just continue along them until you find a non-

Since the data payload (i.e. the ASN.1 wrapper and hash) is variable-length
and not known in advance, how are you expecting to know in advance how many
FF's are present without walking along them until you find a non-FF?  ESP?
Magic?

Peter.

---

From: Konrad Rosenbaum <[email-masked]>
Date: Mon, 30 May 2005 20:25:55 +0200

> signatures. What lengths should be used with DSA and Elgamal?

That's trivial: with DSA there is no such thing as an encoding length, since 
the Hash is used directly and has to be of the correct length (with 1024 
bit DSA you SHOULD use SHA-1, which is 160 bit wide, which (ohh wonder!) 
matches the requirement of DSA).

Elgamal is also trivial: don't use it for signatures. It's insecure. (Or 
rather: it is so hard to make it secure that it is not worth it.)

	Konrad

---

From: Ben Laurie <[email-masked]>
Date: Tue, 31 May 2005 08:54:03 +0100

> rather: it is so hard to make it secure that it is not worth it.)

As I have previously stated, my keyring contains Elgamal signatures. I'm
sure I'm not alone in this. I want to be able to check them. I think its
fine to deprecate them, but refusing to describe them is just annoying.

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 31 May 2005 08:48:47 +0100

> FF's are present without walking along them until you find a non-FF?  ESP?

It is known in advance.

Cheers,

Ben.

---

From: "Konrad Rosenbaum" <[email-masked]>
Date: Tue, 31 May 2005 10:52:03 +0200 (CEST)

> fine to deprecate them, but refusing to describe them is just annoying.

As far as I recall it is PKCS#1-v1.5 - just like RSA.

However, these signatures are not worth anything, since they leak the key
and are easily forgable after the first signature. So bothering with
verifying them is nonsense in my opinion. Cryptographically an Elgamal
signature on something tells you as much about that something as a coffee
stain on a printout of it.

    Konrad

---

From: Ben Laurie <[email-masked]>
Date: Tue, 31 May 2005 10:16:31 +0100

> stain on a printout of it.

This is a reason to deprecate them, not a reason not to describe them.

---

From: Jon Callas <[email-masked]>
Date: Tue, 31 May 2005 03:07:28 -0700

> This is a reason to deprecate them, not a reason not to describe them.

They're more than deprecated, they're disallowed. All of the keys have 
been declared invalid. The documents don't say you MUST or even SHOULD 
consider them all broken, but no one would bat an eyelash if you did.

Nonetheless, if you wanted to look inside one anyway, a lawyerly 
reading of the document doesn't disallow it.

I believe Konrad Rosenbaum is correct, that it's a PKCS1/1.5 content. 
The GnuPG guys would be best to comment, as they're the only ones who 
ever implemented them.

	Jon

---

From: Werner Koch <[email-masked]>
Date: Tue, 31 May 2005 13:36:33 +0200

On Tue, 31 May 2005 03:07:28 -0700, Jon Callas said:

> I believe Konrad Rosenbaum is correct, that it's a PKCS1/1.5
> content. The GnuPG guys would be best to comment, as they're the only
> ones who ever implemented them.

Frankly, I don't know this anymore because we have removed all Elgamal
signature code from GnuPG.  Old versions are still available and it
should be easy to figure out the format.

Shalom-Salam,

   Werner

---

From: Ian G <[email-masked]>
Date: Tue, 31 May 2005 13:24:50 +0100

> stain on a printout of it.

If they are as dangerous as you say - "leak the key" and "forgeable" -
then perhaps they should be more than deprecated, they should be
marked as "SHOULD NOT be verified and should be marked in some
negative fashion to indicate broken tech to the user" ?

Just because something exists is not a sufficient argument for including
it in the ID.  If we are of the opinion that something should not be
done and not be promulgated then leaving it out and marking the
allocated numbers as "reserved" should be sufficient.  A standard is
a document describing what we want people to do, not what we want
people not to do.

iang
-- 
Advances in Financial Cryptography:
   https://www.financialcryptography.com/mt/archives/000458.html

---

From: Werner Koch <[email-masked]>
Date: Tue, 31 May 2005 14:50:55 +0200

> and are easily forgable after the first signature. So bothering with

That is not correct.  They leak the key only when used with broken
software or when the key has been created with such software.  Certain
versions of GnuPG (1.0.2 - 1.3.3) were broken and thus one should
better assume that the key has been broken. See
http://lists.gnupg.org/pipermail/gnupg-announce/2003q4/000160.html for
details.

Salam-Shalom,

   Werner