Subject: [openpgp] OpenPGP SEIP downgrade attack

From: Jonas Magazinius <[email-masked]>
Date: Mon, 5 Oct 2015 16:07:50 +0200

Hi,

I've recently been analysing the OpenPGP standard and have found that it
is vulnerable to a chosen-ciphertext attack to downgrade an SEIP packet
to a plain SE packet. Due to the properties of CFB mode and OpenPGP’s
predictable message structure, it is possible to switch the SEIP tag to
SE, strip the MDC (and signature), and align and manipulate the
encrypted packet. The implications are, among others, that an encrypted
and signed message can be stripped of its signature and modified
arbitrarily, with certain restrictions, by an attacker without knowing
the key. This attack also resurrects attacks from as early as 2000
[4,5]. Part of the reason SEIP and MDC was introduced ~15 years ago was
to deal with exactly this problem. Looking back at the OpenPGP
mailinglist arhive it seems that the correctness of the integrity
protection has been questioned now and then over the years [1,2], but
it's been maintained that it is secure against this kind of attack [3].
It also seems like thoughts along this line is not new [6], so question
remains why it has not been dealt with before.

Different implementations handle SE packets differently. GPG throws a
warning [3] that the message could have been modified, but other
implementations do not differentiate between SE and SEIP. A quick fix
for this issue would be to throw an error for all SE packets, though I
understand the legacy issues it would bring (as was also suggested [3]).
A large part of the problem here is due to CFB mode, but it seems we're
stuck with that. It would make sense to use a different mode, but again
I understand the legacy issues.

To try it out in practice and to see how hard it would be for someone
else to come to the same conclusion, I created this challenge:
https://0x.nu/
I thought it would be tough to crack, but to my great surprise it was
solved in less than 12 hours. So far only one person has solved it
though. I was going to submit a paper about the attack, but considering
how quickly the challenge was cracked I realised the urgency to report this.

The attack in more detail:

To start out, some important properties of CFB mode. (Sorry for
restating the obvious, it's just for completeness.)

    1) A modification of the length of the ciphertext will cause the
    same effect on the plaintext. Addition of blocks to the ciphertext
    will extend the plaintext equally. Any number of bytes cut off the
    end of the ciphertext will cut the same number of bytes from the
    plaintext.

    2) The decryption of a block depends only on the preceding block,
    regardless of where in the ciphertext it appears. Sequences of
    blocks can be cut, duplicated, or injected amidst two blocks. (When
    injecting the surrounding blocks will fail to decrypt correctly, but
    under the right circumstances that does not matter.)

    3) If part of the plaintext is known, the corresponding part of the
    ciphertext can be modified to produce arbitrary text.

It is important to note that none of these properties depend on the
encryption key, which implies that knowing the key is not required to
abuse them.

Now, turning a SEIP packet into a SE packet, can be done in three steps:

    1) Changing the tag.

    2) Aligning the encrypted blocks to match the resynchronized
    structure of the SE packet.

    3) Ensure correct parsing of the decrypted text into packets.

The first step is obvious. To deal with the second step we can abuse
property 1 and 2, and simply prepend two bytes to the encrypted string.
Because of the resynchronization step in SE packet encryption, these two
bytes will only affect decryption of the last two bytes of the IV. The
rest of the blocks will now be aligned with the SE structure and decrypt
correctly. Because the blocks have been shifted the decrypted text will
however not parse correctly due to the now missplaced checkbytes.

The last step is to make the decrypted text parse as a set of packets.
To parse correctly, the first two bytes of the plaintext must match the
header of a packet such that it allows the rest of the text to parse as
the original packets. This can be achieved by abusing property 2 and 3.
Either, if the first two bytes of plaintext of any block is known, then
that block and the preceeding one can be repurposed to create such a
packet, or if no plaintext is known it can be bruteforced (given a
decryption oracle). Unfortunately OpenPGP packets are very predictable
and there are a number of ways this can be done. In fact, if the message
is signed it is pretty straight forward because of the predictable one
pass signature packet.

This is supposed to convey the idea of the attack, but not be a complete
recipe on how to do it. If more info is needed on the specifics of the
attack in order to fix it, then this can be provided.

Best regards,

Jonas Magazinius
Assured AB, Sweden

[1] Is there any published analysis of OpenPGP's MDC?
https://www.ietf.org/mail-archive/web/openpgp/current/msg00969.html
[2] security fixes (KDF, MDC->MAC)?
https://www.ietf.org/mail-archive/web/openpgp/current/msg02841.html
[3] Re: security fixes (KDF, MDC->MAC)? -
http://www.ietf.org/mail-archive/web/openpgp/current/msg02838.html
[4] A Chosen Ciphertext Attack against Several E-Mail Encryption
Protocols - USENIX'00
[5] Implementation of Chosen-Ciphertext Attacks against PGP and GnuPG -
ISC'02
[6] OpenPGP security analysis -
https://www.ietf.org/mail-archive/web/cfrg/current/msg00059.html

---

From: Watson Ladd <[email-masked]>
Date: Mon, 5 Oct 2015 10:09:56 -0400

On Mon, Oct 5, 2015 at 10:07 AM, Jonas Magazinius
<[email-masked]> wrote:
> Hi,
>
> I've recently been analysing the OpenPGP standard and have found that it is
> vulnerable to a chosen-ciphertext attack to downgrade an SEIP packet to a
> plain SE packet. Due to the properties of CFB mode and OpenPGP’s predictable
> message structure, it is possible to switch the SEIP tag to SE, strip the
> MDC (and signature), and align and manipulate the encrypted packet. The
> implications are, among others, that an encrypted and signed message can be
> stripped of its signature and modified arbitrarily, with certain
> restrictions, by an attacker without knowing the key. This attack also
> resurrects attacks from as early as 2000 [4,5]. Part of the reason SEIP and
> MDC was introduced ~15 years ago was to deal with exactly this problem.
> Looking back at the OpenPGP mailinglist arhive it seems that the correctness
> of the integrity protection has been questioned now and then over the years
> [1,2], but it's been maintained that it is secure against this kind of
> attack [3]. It also seems like thoughts along this line is not new [6], so
> question remains why it has not been dealt with before.
>
> implementations do not differentiate between SE and SEIP. A quick fix for
> this issue would be to throw an error for all SE packets, though I
> understand the legacy issues it would bring (as was also suggested [3]). A
> large part of the problem here is due to CFB mode, but it seems we're stuck
> with that. It would make sense to use a different mode, but again I
> understand the legacy issues.
>
> To try it out in practice and to see how hard it would be for someone else
> to come to the same conclusion, I created this challenge: https://0x.nu/
> I thought it would be tough to crack, but to my great surprise it was solved
> in less than 12 hours. So far only one person has solved it though. I was
> going to submit a paper about the attack, but considering how quickly the
> challenge was cracked I realised the urgency to report this.

I  don't think we need to fix this, so much as completely redesign the
packet format to be correct. If the WG wants to go down this path, I
can definitely do it, but we would need to junk a lot.

> To start out, some important properties of CFB mode. (Sorry for restating
> the obvious, it's just for completeness.)
>
> 1) A modification of the length of the ciphertext will cause the same effect
> on the plaintext. Addition of blocks to the ciphertext will extend the
> plaintext equally. Any number of bytes cut off the end of the ciphertext
> will cut the same number of bytes from the plaintext.
>
> 2) The decryption of a block depends only on the preceding block, regardless
> of where in the ciphertext it appears. Sequences of blocks can be cut,
> duplicated, or injected amidst two blocks. (When injecting the surrounding
> blocks will fail to decrypt correctly, but under the right circumstances
> that does not matter.)
>
> encryption key, which implies that knowing the key is not required to abuse
> them.
>
> 2) Aligning the encrypted blocks to match the resynchronized structure of
> the SE packet.
>
> bytes will only affect decryption of the last two bytes of the IV. The rest
> of the blocks will now be aligned with the SE structure and decrypt
> The last step is to make the decrypted text parse as a set of packets. To
> parse correctly, the first two bytes of the plaintext must match the header
> of a packet such that it allows the rest of the text to parse as the
> original packets. This can be achieved by abusing property 2 and 3. Either,
> if the first two bytes of plaintext of any block is known, then that block
> and the preceeding one can be repurposed to create such a packet, or if no
> plaintext is known it can be bruteforced (given a decryption oracle).
> Unfortunately OpenPGP packets are very predictable and there are a number of
> ways this can be done. In fact, if the message is signed it is pretty
> straight forward because of the predictable one pass signature packet.
>
> [4] A Chosen Ciphertext Attack against Several E-Mail Encryption Protocols -
> USENIX'00
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Neil Hunsperger <[email-masked]>
Date: Mon, 5 Oct 2015 10:39:33 -0700

From: openpgp [mailto:[email-masked]] On Behalf Of Jonas Magazinius
> I've recently been analysing the OpenPGP standard and have found that it is vulnerable to a chosen-ciphertext attack to downgrade an SEIP packet to a plain SE packet.

> I was going to submit a paper about the attack, but considering how quickly the challenge was cracked I realised the urgency to report this.

Assuming SE and SEIP now have equivalent security, does anyone suspect a real-world impact? I.e. is there software that trusts encrypted unsigned data more than it trusts unencrypted unsigned data?

-Neil

---

From: Werner Koch <[email-masked]>
Date: Mon, 05 Oct 2015 20:13:15 +0200

> it's been maintained that it is secure against this kind of attack [3].

Well, I assumed that this is the case (my "Yes") but in the next mail
Trevor explained that this is not true.  More important however is my
remark that we need to get MDC deployed so that we can issue an error
for non MDC packets instead of just a warning.

AFAIK, there are still implementations not supporting MDC and a small
number of folks loudly complaining when I removed PGP-2 support.

> I understand the legacy issues.

One of the goals of 4880bis is:

  - A symmetric encryption mechanism that offers modern message
    integrity protection (AEAD)

Shalom-Salam,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 6 Oct 2015 01:49:40 +0000

Jonas Magazinius <[email-masked]> writes:

>to a plain SE packet. 

Nice work!

>Part of the reason SEIP and MDC was introduced ~15 years ago was to deal 
>with exactly this problem. 

It's always been a quick hack though.  I didn't implement MDC for a long 
time because I was waiting for it to be done properly (encrypt-then-MAC),
but eventually I decided that a hack was better than nothing at all.  It's
really not hard to do properly, just take what CMS / S/MIME did and convert
the bit-bagging to PGP format [0].  Encrypting a non-keyed hash in CFB mode 
of all things is just asking for trouble.

>Different implementations handle SE packets differently.

Is the SEIP -> SE rewrite completely transparent, or are there implementation
quirks/peculiarities that make it work in some cases and not others?  It'd
be interesting to have a sample of a SEIP message with its SE rewrite to look
at.

Peter.

[0] It specifically protects against strip-the-MAC/rewrite-the-message 
    attacks, but if you *can* find an attack I'd be interested in hearing 
    about it.

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 6 Oct 2015 01:51:58 +0000

Werner Koch <[email-masked]> writes:

>More important however is my remark that we need to get MDC deployed so 
>that we can issue an error for non MDC packets instead of just a warning.

We don't need to get it deployed, we need to get it replaced by encrypt-
then-MAC, with the whole handled in a manner where downgrade attacks aren't
possible.

Peter.

---

From: David Leon Gil <[email-masked]>
Date: Tue, 06 Oct 2015 02:19:58 +0000

This is a very nice explanation of the downgrade attack. I suspect that its
discovery predates your work: See
https://github.com/google/end-to-end/issues/161 (scroll down a bit) for a
bug where I note it.

---

From: Werner Koch <[email-masked]>
Date: Tue, 06 Oct 2015 08:55:47 +0200

> then-MAC, with the whole handled in a manner where downgrade attacks aren't

And wait another 15 years until it has been taken up by all
implementations?  What is wrong with the planned AE mode?

Shalom-Salam,

   Werner

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 7 Oct 2015 13:50:52 +0000

Werner Koch <[email-masked]> writes:

>And wait another 15 years until it has been taken up by all implementations?
>What is wrong with the planned AE mode?

Which has just as little support as a planned EtM mode?  

The reason why I prefer EtM is that it can be pretty trivially retrofitted to
existing crypto (just add a SHA-256 MAC somewhere) and is compatible with any
existing cipher, while whatever AEAD mechanism is chosen (I'm guessing AES-
GCM, which seems to be fashionable) is purely for AES, there's no Twofish or
CAST or whatever AEAD mode defined.

Peter.

---

From: Werner Koch <[email-masked]>
Date: Wed, 07 Oct 2015 21:37:45 +0200

> existing crypto (just add a SHA-256 MAC somewhere) and is compatible with any

But raises the same problems as all data format changes.  When taking up
these trouble why got for a slow method whilst faster methods are
available.

> CAST or whatever AEAD mode defined.

OCB works with all 128 bit block length ciphers and is faster than GCM.

Salam-Shalom,

   Werner

---

From: Jon Callas <[email-masked]>
Date: Wed, 7 Oct 2015 15:21:23 -0700

> On Oct 7, 2015, at 12:37 PM, Werner Koch <[email-masked]> wrote:

> OCB works with all 128 bit block length ciphers and is faster than GCM.

So does CCM, and CCM has no intellectual property issues, nor GCM's brittleness.

	Jon

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 8 Oct 2015 14:59:15 +0000

Werner Koch <[email-masked]> writes:

>When taking up these trouble why got for a slow method whilst faster methods
>are available.

AES-GCM is only fast on CPUs with dedicated hardware support for it (PCLMULQDQ
on x86), it's actually quite slow in pure software (on x86 the slowdown is
about an order of magnitude).  The figures are really all over the place
depending on what system it's running on, so it's a bit hard to generalise any
statement about it.

(It's also not clear whether someone encrypting a 10k email message with PGP
is going to notice it being processed at 100MB/s or 150MB/s).

>OCB works with all 128 bit block length ciphers and is faster than GCM.

It's also a lot more patented than GCM.

(I actually really like OCB and don't like GCM much, but the patent situation
makes it pretty problematic).

Peter.

---

From: Werner Koch <[email-masked]>
Date: Thu, 08 Oct 2015 18:18:17 +0200

> is going to notice it being processed at 100MB/s or 150MB/s).

I heard of backups somewhat larger than that.  For mail it is anyway not a
problem - you sign and encrypt and you are done.  Not even a need for an
MDC.

> makes it pretty problematic).

Well, for the majority of uses cases there is a gratis license grant
from Phil Rogaway for his patents.
Further daft-zauner-tls-aes-ocb-03.txt states:

   6.  Intellectual Propery Rights Issues

   Historically OCB Mode has seen difficulty with deployment and
   standardization because of pending patents and intellectual rights
   claims on OCB itself.  In preparation of this document all interested
   parties have declared they will issue IPR statements exempting use of
   OCB Mode in TLS from these claims.  Specifically - OCB Mode as
   described in this document for use in TLS - is based, and strongly
   influenced, by earlier work from Charanjit Jutla on [IAPM].

At IETF-93 this case was mentioned and it was suggested to ask for a
similar licenses exception [1,2] if we consider to use OCB for OpenPGP.

Salam-Shalom,

   Werner

[1] https://datatracker.ietf.org/ipr/2647/
[1] https://datatracker.ietf.org/ipr/2640/

---

From: Watson Ladd <[email-masked]>
Date: Thu, 8 Oct 2015 12:23:52 -0400

> problem - you sign and encrypt and you are done.  Not even a need for an

Does this provide the right agreement semantics for both sender and
recipient? It certainly doesn't solve the security issues with CFB mode.