Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The RUB in Germany reports that XML encryption is broken. This is essentially the W3C standard for protecting XML documents from prying eyes.
Does this mean that an attacker can only see a single message, or that they can actually infer the encryption key for all messages?
Is this a new vulnerability in CBC?
How is this relate to pre-existing applications that use CBC?
This question came from our site for information security professionals.
After reading the paper How to Break XML Encryption (thanks to Krzysztof for the link), here are my two cents.
This attack relies on the fact that a CBC-ciphertext C = (IV, C1, ... Cd) can be decomposed into pairs of (IV, C1), (C1, C2), (C2, C3), ... (C(d-1), Cd), each of which is also a valid CBC ciphertext for the same key, relating to the corresponding pieces of plaintext (ignoring padding).
Having such a pair C' = (IV, C1) (for example), we can modify its corresponding plaintext arbitrarily by modifying the initialization vector part.
Now we take an validation oracle - a function to which we can send a pair, and which tells us some information about the plain text. In this attack on XML encryption, the oracle tells us if (a) the plaintext is correctly padded, and (b) does not result in invalid XML (like characters not allowed in XML, or unmatched & or <). Such an oracle can be constructed from the error messages of the attacked web services.
Repeated querying of this oracle with slightly different values of of the initialization vector now allows us to reconstruct the individual bytes of the plaintext.
Some more analysis of the paper is in this blog post Attack of the week: XML Encryption by Matthew Green.
Does this mean that an attacker can only see a single message, or that they can actually infer the encryption key for all messages?
The attack is an attack on the mode of operation - it works for any block cipher in CBC-mode if such a validation oracle can be effectively constructed and used. It does not give back the key, since it actually circumvents the block cipher instead of attacking it.
It needs a number of oracle queries for each broken plaintext byte (the exact number will on the type of oracle), but can be applied to any intercepted ciphertext message. It also allows constructing ciphertexts with arbitrary plaintext (using more such oracle queries).
Is this a new vulnerability in CBC?
From the introduction, it seems that similar attacks on other protocols using CBC-mode (attacking the padding scheme instead of the encoding like here) were already known before (as early as 2002). The fact that CBC-messages can be decomposed as shown above is certainly not a new insight.
But this specific way of breaking seems new (it was discovered in February 2011, they just waited a bit with writing and publishing the paper).
How is this relate to pre-existing applications that use CBC?
Protocols like TLS, SSH and IPSec combine the encryption with a message authentication code for integrity/authentication (or even use a combined "authenticated encryption" scheme). A chosen-ciphertext attacker (like here) has usually no way of constructing a valid MAC tag, and if the application rejects messages with a wrong MAC instead of trying to parse the plaintext (and giving a suitable error message), there should be no problem.
XML Encryption also provides for a MAC, but it is optional - in a way that allows an attacker to strip off the MAC and still get a valid encrypted message.
For file or email encryption (like PGP), there is usually a key per message, and no easy way of using an validation oracle.
Neither. It means that an attacker can decrypt all messages that have been encrypted using this standard.
The attack is a padding oracle attack. That means that, if the attacker has a ciphertext they want to decrypt, they can send several variations of the ciphertext to the server. By analyzing the server's responses (e.g., error messages returned), it is possible for the attacker to deduce the corresponding decrypted cleartext. The attacker never learns the encryption/decryption key. However, the attacker can repeat this as many times as desired to decrypt every ciphertext they have captured. The workload to decrypt N ciphertexts is proportional to N. In particular, the paper reports that their attack performs 14 queries to the server per byte decrypted.
The padding oracle attack is possible because the XML standard didn't use an encryption algorithm that is secure against chosen-ciphertext attacks. Or, put another way, they used encryption without authentication.
This is another instance of the classic crypto design error: Don't use encryption without authentication. One way to avoid this error is to use authenticated encryption and other misuse-resistant algorithms.
Your third question asked how this attack relates to pre-existing applications of CBC. Before being used to break XML encryption, it was used on certain protocols run over TLS/SSL. See my answer here. For other protocols like IPSEC, WTLS, and SSH, the original paper proposing the attack has a good discussion of its applicability (in Section 5).
