Subject: Re: Algorithm Specific Fields for DSA secret keys

From: [email-masked]
Date: Wed, 21 Mar 2001 15:54:04 -0800

If you look at the whole section, it says,

5.5.3. Secret Key Packet Formats

   The Secret Key and Secret Subkey packets contain all the data of the
   Public Key and Public Subkey packets, with additional algorithm-
   specific secret key data appended, in encrypted form.

   The packet contains:

     - A Public Key or Public Subkey packet, as described above

     - One octet indicating string-to-key usage conventions.  0
       indicates that the secret key data is not encrypted.  255
       indicates that a string-to-key specifier is being given.  Any
       other value is a symmetric-key encryption algorithm specifier.

     - [Optional] If string-to-key usage octet was 255, a one-octet
       symmetric encryption algorithm.

     - [Optional] If string-to-key usage octet was 255, a string-to-key
       specifier.  The length of the string-to-key specifier is implied
       by its type, as described above.

     - [Optional] If secret data is encrypted, eight-octet Initial
       Vector (IV).

     - Encrypted multi-precision integers comprising the secret key
       data. These algorithm-specific fields are as described below.

     - Two-octet checksum of the plaintext of the algorithm-specific
       portion (sum of all octets, mod 65536).

and then it goes on to explain the algorithm-specific fields mentioned
in the second to last paragraph.  But note that the very first entry
is a whole Public Key packet.  This has the p, q, g and y values.
Then come the other entries: string-to-key usage octet, encryption octet,
string-to-key specifier, iv, and then the algorithmic-specific private
fields you saw.  Finally a checksum.

Hal

---

From: Florian Weimer <[email-masked]>
Date: 22 Mar 2001 11:47:14 +0100

>      - A Public Key or Public Subkey packet, as described above

Okay, I missed this one.  I thought the public key components were
also cryptographically protected.  May I assume that the i.cz attack
is target against the unprotected public key part of the secret key
packet?  Such an attack seems feasible.

-- 
Florian Weimer 	                  [email-masked]
University of Stuttgart           http://cert.uni-stuttgart.de/
RUS-CERT                          +49-711-685-5973/fax +49-711-685-5898

---

From: [email-masked] (Lutz Donnerhacke)
Date: 22 Mar 2001 10:54:39 GMT

* Florian Weimer wrote:
>Okay, I missed this one.  I thought the public key components were also
>cryptographically protected.  May I assume that the i.cz attack is target
>against the unprotected public key part of the secret key packet?  Such an
>attack seems feasible.

If they do so, the attack will be /very/ interesting.

---

From: Florian Weimer <[email-masked]>
Date: 22 Mar 2001 12:49:04 +0100

> If they do so, the attack will be /very/ interesting.

They seem to, see http://www.i.cz/pdf/pgp/OpenPGP_attack_CZ.pdf.  It's
informative even if you cannot read Czech (there's one diagram showing
the secret key packet modification, which is quite instructive).  Was
this information available to the Minneapolis meeting?  What were
their conclusions?

The attack is rather obvious, I have to say.  Before I read Hal's
reply, I assumed that all data needed for signature generation was
protected by the passphrase.  I was really surprised when I discovered
that it wasn't (at least in the DSA case, however, if you do RSA using
the Chinese Remainder theorem, it is), and I was far less surprised
when I finally found the paper and confirmed that the attack is
mounted against the unprotected portion of the secret key.

I'm still working on a fix.  The basic question is: Is it possible to
create a set of public DSA parameters which are consistent with the
secret one, without knowing the latter?  If the answer is yes, we have
to modify the OpenPGP format, otherwise, a consistency check is
sufficient to protect against this attack.  (The consistency check
performed by GnuPG is probably not sufficient.)

---

From: Lutz Donnerhacke <[email-masked]>
Date: Thu, 22 Mar 2001 13:19:39 +0100

[This message has also been posted.]
>They seem to, see http://www.i.cz/pdf/pgp/OpenPGP_attack_CZ.pdf.  It's

Great work.

>the secret key packet modification, which is quite instructive).  Was

Yes, it is.

>The attack is rather obvious, I have to say.

Of course, every good idea is obvious afterwards.

>I'm still working on a fix.

Assuming a bellcore attack I suggested to check it against the public key,
but there is a problem: If the major modulus of the public key is shrinked
and access to the files is assumed, there is no real reason to modify the
public key accordingly in order to fool even all the certificate checks on
my own keys. So this solution does not work.

For RSA we can fix it by regenerating the public part from the encrypted
private ones and stop working if this check failes. Afterwards we should
check the signature by the verified public key. I'll do so for PGP2.6.3(i)n.

>The basic question is: Is it possible to create a set of public DSA
>parameters which are consistent with the secret one, without knowing the
>latter?

We could check if y = g**x mod p. If p and g are not trivial (check this!)
and x is assumed to be not published before this signing attempt, there
might be a chance to prevent a format modification.

OTOH, we do not relay on a modifiction anyway, the programms are free to
choose any secret key storage format the like.