Subject: Re: Agree with PRZs MDC suggestion

From: [email-masked]
Date: Tue, 11 May 1999 16:52:58 -0700

Werner Koch, <[email-masked]>, writes:
> We should invent a new encrypted data packet which is used for
> encrypted messages with MDC.  Suggestion:
>
>    Packet number ???
>
>    1 byte version  (should be 1)
>    1 byte MDC method (should be 2 to match SHA, or 0 to disable MDC)
>    1 byte number of extra bytes (m) at the end of the encrypted text
>           From now on CFB encrypted with an IV of all zeroes without
>           any strange syncing.
>    n byte random data used as IV (n=blocksize of the cipher)	
>    2 byte the last two bytes of the random data.
>    k byte message
>    m byte hash used for MD

In my other message I pointed out the problem that an attacker could
perturb some of these header values.  With that in mind let us look at
these fields:

>    1 byte version  (should be 1)

This is probably a good idea.  If perturbed by an attacker to a later
version, the software will refuse to process the packet.  We need
to consider though whether, if we later move to a higher version, an
attacker could execute a rollback attack by changing a V2 to a V1.
We can deal with that at that time by making sure that V2 and V1 look
very different (assuming we ever need to create a V2).

>    1 byte MDC method (should be 2 to match SHA, or 0 to disable MDC)

This one worries me.  It allows an attacker to turn a 2 into a 0.  Also,
is there an implication that it can be something other than 2 or 0?  Like,
1 means MD5?  If so, this again offers an attacker more opportunities to
mess with the receiver.  The attacker could change the hash algorithm to
something like 6.  Now the receiver doesn't know if this is a legitimate
message from a later version of PGP that supports hash algorithm 6, or
whether it is a messed up message by an attacker.  If we choose a fixed
hash algorithm this ambiguity cannot arise.

I would prefer to leave this field out.  If you use the new packet format
at all, you get the MDC, using a fixed hash of SHA-1.

>    1 byte number of extra bytes (m) at the end of the encrypted text
>           From now on CFB encrypted with an IV of all zeroes without
>           any strange syncing.

We would then not need this, as the value would always be 20.

>    n byte random data used as IV (n=blocksize of the cipher)	

OK.  I continue to believe that a *conventional* IV is most desirable in
terms of explaining what we are doing to others in the field.  The "pseudo
IV" we have now is hard to explain.  I had to go to some lengths in
getting our FIPS 140 certification (a standard security certification)
to show that our way was just as good as the regular way.

>    2 byte the last two bytes of the random data.

You have not shown whether these are encrypted.  I presume that they are,
and that these are meant to be check bytes used to detect when we have the
right session key.  This way of doing it does not work well when the IV
is unencrypted, as is done in virtually every other cipher in the world
except PGP.  With an unencrypted IV the two check bytes are known, thus
putting two bytes of known plaintext right at the start of the message.
Since one of the goals of the new encryption packet is to regularize our
methods and bring them into conformance with the practices used by other
professionals, I believe we should do check bytes slightly differently.

My proposal was that we have four bytes, two random ones and then those
same two random ones repeated.  These would all be encrypted.  It's not
known plaintext although there is a certain amount of redundancy in the
data, which redundancy is necessary for them to serve as check bytes.

>    k byte message
>    m byte hash used for MD

These, too, would both presuambly be encrypted.  The hash size should be
fixed if we fix a hash algorithm.

> Uri proposed another scheme for better detection of wrong keys - we 
> should consider to use this.

His proposal, from http://www.imc.org/ietf-open-pgp/mail-archive/msg02471.html:

   Make the "pseudo-IV" prefix partially non-random - i.e. the last two 
   bytes being checksum for the other 14. No big deal security-wise and
   noticeable help in detecting the right key.

This isn't too bad for 128 bit block ciphers like Twofish or AES, but as
a general principle we would need to apply it to all ciphers, including
64 bit block ciphers.  I don't like taking away 16 of the 64 bits of IV
in that case.  I can't name a specific attack this would cause but it
doesn't feel right to give up that much of the IV.

Also, of course this only works with the pseudo-IV.  As I wrote above, our
use of a pseudo-IV is an oddball quirk that no one else does.  In order to
generate support for the standard we should try to move away from peculiar
features like this and towards the conventional ways of doing things.

> "If a cipher with a blocksize > 64 bits is used, this new packet 
>  format SHOULD be used".

I agree that it would be sensible to encourage the new format when we go
to new block ciphers.  Unfortunately the next version of PGP will have
Twofish support without MDC, since we were not able to come to consensus
here (and it doesn't look like we are coming any closer).

> To clarify thinks for the old encypted data packet (9), we should
> say that the special CFB mode is used with all blocksizes. 

By this, do you mean the special sync operation after reading the pseudo
IV and check bytes?

Hal Finney
Network Associates, Inc.

---

From: Werner Koch <[email-masked]>
Date: Wed, 12 May 1999 09:59:48 +0200

> This is probably a good idea.  If perturbed by an attacker to a later

Yes and the reason for this is simply to extend the range of possible
packet formats (view it as a packet subtype).

> We can deal with that at that time by making sure that V2 and V1 look

And he could also do this by changing the packet type.

> This one worries me.  It allows an attacker to turn a 2 into a 0.  Also,

I see your point.  The reason I suggest this is that there are a lot
of people who prefer to use RIPE-MD160 and this way we have te
opportunity to do just this.  The packet format may also be used for
some very small applications which use a subset of OpenPGP and don't
implement SHA1 at all.  My solution to this is to say in the standard,
that this SHOULD be SHA1 and an implementation SHOULD fail if this 
condition is not met. 

> hash algorithm this ambiguity cannot arise.

I guess we will have new hash algorithms with a larger digest size in the
near future and this way we can more easily extend the specs to make
it possible to use this hash (Frankly, don't see any need in a MDC for 
a larger hash, but if some one wants and has only implemented this
larger hash ...).

> >           From now on CFB encrypted with an IV of all zeroes without

This is fine for automatic parsing of messages to let the parse know
how may bytes he has to hold back. 

> getting our FIPS 140 certification (a standard security certification)

I can't remember that the Internet Standards Process (BCP9) or our
chapter says anything about FIPS certification.  PGPG is a widely
deployed quasi-standard and believed to be really good secure.

If you need some certification it is matter of your company to work 
it out.

> You have not shown whether these are encrypted.  I presume that they are,

Ah sure.  It is what we are currently using.

> same two random ones repeated.  These would all be encrypted.  It's not

But that will be not better than the current practice.  It is okay for
PK encryption but when using a symmetric-only encryption it may not
detect wrong passphrases in all cases.  But okay, we catch this with
the MDC and therefore I think it is good enough.

> 64 bit block ciphers.  I don't like taking away 16 of the 64 bits of IV

So we could always use 128 bits and use only the lower half for 64 bit
blocksize ciphers.  But okay, with the MDC we don't really need it.

> Twofish support without MDC, since we were not able to come to consensus

Ahhh great:  I'm holding back Twofish support for GnuPG for many weeks
now, only to have the chance to use 128 bit block ciphers as a
criteria to decide whether to use MDCed encryption - but NAI has already
decided to make facts and thereby ignoring the discussion at the WG.
But sure, it is your companies decision - tssss.

BTW, how did you solve the ambiguities in the rfc regarding the use of
synced CFB and length of IVs? 

> By this, do you mean the special sync operation after reading the pseudo

Yes.
#define CIPHER_MODE_PHILS_CFB 3

-- 
Werner Koch at guug.de           www.gnupg.org           keyid 621CC013

---

From: uri <[email-masked]>
Date: Wed, 12 May 1999 07:23:19 -0400 (EDT)

[email-masked] says:
> This one worries me.  It allows an attacker to turn a 2 into a 0. 

I would not have "disable MDC" at all.

> Also,
> is there an implication that it can be something other than 2 or 0?

Absolutely - like 3 for HAVAL, 5 for <whatever>...

> If so, this again offers an attacker more opportunities to

True. So it is up to the group to decide if the extra flexibility of
permitting several hash-functions is worth this potential attack...

> at all, you get the MDC, using a fixed hash of SHA-1.

Quite acceptable, if you ask me.

> IV" we have now is hard to explain.

1. A conventional IV is less desirable from security point of view.
2. If you have trouble explaining this approach to others in the
   field - I suggest that those others are in the wrong field.
-- 
Regards,
Uri		[email-masked]
-=-=-=-=-=-=-
<Disclaimer>

---

From: Tom Zerucha <[email-masked]>
Date: Wed, 12 May 1999 17:20:54 -0400

> version, the software will refuse to process the packet.  We need

Actually 5 would be more consistent.  Elsewhere 3 is used for PGP 2.6
level packets, 4 for PGP 5-6.  Anything below 5 for this new packet would
be an error.

> hash algorithm this ambiguity cannot arise.

The receiver would have to check the message on a later version of PGP.
If 6 was a legitimage algorithm ID the hash would work.  The same problem
arises if something shifts between any two valid IDs with the same length 
hash, the second of which would might not be supported.

One note is that if you use my idea of an MDC-ahead prefix packet, and
MDC-result packet bracketing the plaintext, the MDC specification is
encrypted too, making this attack difficult.

(CTB,len=2) 5 2; plaintext; (CTB, len=22) 5 2 <20 byte result>;

Note that this would allow multiple MDCs with different algorithms
(the hash would only be on the plaintext), so you could have

[MDC: rmd160 follows][MDC: SHA1 follows][plaintext][MDC: SHA1 result][MDC:
rmd result].

Or these could be merged, (CTB len = 4) 5 2 3 0;/ (CTB len = 44) 5 2 <20
byte sha1> 3 <20 byte rmd> 0; or something similar.

-----------------------

While we are on the subject, last year at this time there was a suggestion
to drop El Gamal. The objection was mainly that the only other two
alternatives had other problems - RSA was patented, and DSA limited the
hash length to 160 bits, so although you could do larger keys, they added
no security since the hash was the weakest link.  ElGamal allowed for
longer hashes and (if there were no flaws in the implementation) more
functional bits in the public key.

Various suggestions were made including a doublewide DSA or something
similar including coming up with a hash system.

Has anyone followed up on this?