7

Consider the SSH protocol: the SSH packet is like [data, SHA1(data)]. The packet is entirely encrypted by a block cipher. The question is, why do we need a strong hash to protect the packet consistency? IMO, simple XOR of all of the blocks would be as secure as SHA1 checksum. The data and checksum itself are encrypted, and any small change in the encrypted data would change at least one entire block (unpredictably by a possible attacker). Due to encryption mode (CBC) and the fact, the hash is stored at the end of the packet, I suppose even the hash would change unpredictably. So, simple XOR would be same as good as SHA1 and using XOR instead of SHA1 would save some CPU, so why not?

Lets see an example. For simplicity, consider the block of size 4hexa.

And for even more simplicity, consider the open text: 0000 0000 0000 Since all the blocks are same, XOR would be 0000.

So, the packet is: 0000 0000 0000 0000, where the last "0000" is the xor-checksum

Encrypted, it would be: a840 ff70 0030 bbb5

The attacker is unable to decrypt the message, but he want to change it anyhow prevent me from recognise it. How would he do it?

If he change one bit in... hmm... 3rd block:

a840 ff70 0031 bbb5

but what happen when I try to decrypt?

0000 0000 a722 52e3

FAILED!

The only thing I found he can do is, he can drop a block just in case BLOCK_n is equal to BLOCK_0 xor ... xor BLOCK_(n-1) for the each block. If I add the packet length into the header of the packet, then I don't see any security hole there.

  • 1
    "but what happen when I try to decrypt? 0000 0000 a722 52e3" -- This strongly depends on the cipher used. On a (stream) cipher of 8-bit 'blocks', I should be able to change the encrypted text from "840 ff70 0 0 3 0 bbb5" to "840 ff70 0 1 3 1 bbb5" and this would not be detected. – JimmyB Sep 19 '14 at 10:41
  • This is obvious. In my question I mentioned the block cipher and CBC mode. – smrt28 Sep 19 '14 at 10:56
  • 3
    Sure. But this is also about separation of concerns. Ciphers are not designed to ensure integrity, nor are they frequently analyzed for this property, but message digests are; and message digests when used as a MAC and transmitted in addition to the data provide a high degree of trust. In short: Crytographic hashes and (H)MACs are superior to simple XORs or CRCs for security purposes. – JimmyB Sep 19 '14 at 12:30
7

The decision to use SHA1 for message authentication is part of the formal transport design specification (RFC 4253). Furthermore, SHA2 is now recommended as an update to the protocol (RFC6668).

According to this reference the use not only ensures data integrity but also prevents replay attacks. SSH was originally more like what you are suggesting using just CRC checks. The feature you are questioning was added to specifically address weakness in that simpler design.

6

Strictly speaking, it's not about "consistency" but about "integrity", i.e. the data B receives is the same that A sent.

XOR is a simple and reversible operation, with many possible attack vectors even for encrypted data. An attacker may for instance change one bit from 0 to 1 and another one from 1 to 0 in the ciphertext and this may go undetected by XOR.

This attack is more or less applicable to different kinds of cipher, but for stream ciphers it is often trivial to carry out. So if one does not restrict oneself to a certain set of ciphers that are immune to this kind of attack, one will have to ensure integrity by other means: MAC.

Even if an attacker cannot introduce arbitrary data into the encrypted data stream, he should also not be able to destroy information in transit undetected.

5

Just a guess, but XOR isn't a great way at detecting defects in data, and therefore isn't a great way to checksum something. If you XOR each of the blocks and have a bit error in two of the blocks in the same position, the final XOR value would be the same as if there weren't an error. With a hash checksum, any small change would be reflected in the final checksum value, making it a stronger indicator that something in the data is screwed up.

EDIT: zedman9991 has the correct response. I had forgotten that SSH is wrapped up in TCP or UDP, which both provide their own checksums for data integrity, meaning that the hash in the SSH data is meant specifically for both the inregrity AND the prevention of a replay attack.

  • 1
    IMO XOR is ok in this case. Just think what happen if an attacker changed just 1 bite. It would change entire block and all block after that block "randomly" (because CBC and basic strong ciphers property). Also, keep in mind if the attacker change 1st bit in the 1st block and 1st bit in the 2nd block, he would definitely "randomize" the data after decription and so XOR would detect the change same good as SHA. – smrt28 Sep 18 '14 at 15:04
  • @smrt28 XOR is so vulnerable to modifications: Imagine he creates an account on the server with with b in the name instead of c, then he likely needs to change only one bit somewhere else to create the same checksum. This is exponential hard / "impossible" with proper hash functions. – yo' Sep 18 '14 at 18:32
  • @smrt28 I think you're actually correct now that I think about it more. I had forgotten that SSH is wrapped up in UDP or TCP which provide their own checksums. Those can be wrong about 1 in 16 million times, but the chances of that being messed up perfectly and the SSH checksum being messed up perfectly are pretty low. zedman9991 is correct with the replay attack response. – Greg Sep 18 '14 at 18:40
  • pls, see my edited question - the example. Don't think about TCP or UDP layer. SSH was just the way, how to present the problem. (my english is not perfect...) – smrt28 Sep 18 '14 at 20:25
2

Just XORing the plaintext blocks doesn't prevent some types of attack.

For example:

  • If the first or the last block of the message consists entirely of null bytes, you can just delete the IV (so the first encrypted block will be considered the IV) or the last encrypted block and the message will still be judged as valid.

  • In the same fashion, if the first two or last two blocks are identical, you can delete the first two or last two blocks of the transmission.

  • It's not true. If you delete any block it woud, due to CBC enc. mode change entirely the last block and so the XOR checksum – smrt28 Sep 18 '14 at 19:55
  • 1
    @smrt28: The decryption of a block only depends on the block itself and the previous one. – Dennis Sep 18 '14 at 20:02
  • no, it depends on all preceding blocks. – smrt28 Sep 18 '14 at 20:08
  • ...so even the XOR checksum depends on how preceding blocks were decrypted and this is why I think it could be used instead of SHA1, keeping the same security level. – smrt28 Sep 18 '14 at 20:29
  • 2
    The encryption of a block depends on all preceding plaintext blocks, but the decryption of a block depends solely on two. From Wikipedia: Decrypting with the incorrect IV causes the first block of plaintext to be corrupt but subsequent plaintext blocks will be correct. This is because a plaintext block can be recovered from two adjacent blocks of ciphertext. – Dennis Sep 18 '14 at 21:14
1

The protocol is actually like [data, HMAC-SHA1(data)] (or with another hash instead of SHA-1). What is needed here is to authenticate the data, i.e. to guarantee that it comes from a source that knows a particular secret key. A hash allows the recipient to check that the data is equal to something else, but the recipient has nothing to compare to. In contrast, a MAC allows the recipient to verify that it was generated by an entity that knows the secret key.

You're trying to build a MAC on top of a block cipher. This is possible, but you're doing it wrong. Let's assume, as you do, that the data is encrypted with a block cipher in CBC mode.

The data and checksum itself are encrypted, and any small change in the encrypted data would change at least one entire block (unpredictably by a possible attacker).

That's true: one block changes unpredictably. However, this is not good enough: you need to look at the consequences on the other blocks.

Due to encryption mode (CBC) and the fact, the hash is stored at the end of the packet, I suppose even the hash would change unpredictably.

No, the hash would not change unpredictably if the attacker is careful. It is in fact pretty easy to avoid changing the hash you chose, which is the XOR of all the blocks. CBC uses XOR internally, so this shouldn't come up as a complete surprise.

Consider a message consisting of three blocks P₁, P₂, P₃ and the checksum P₊ encrypted with CBC, and let C₁, C₂, C₃, C₊ be the corresponding ciphertext. I'll write E for the block encryption function and D for decryption.

C₁ = E(P₁ ⊕ IV)
C₂ = E(P₂ ⊕ C₁)
C₃ = E(P₃ ⊕ C₂)
C₊ = E(P₊ ⊕ C₃)         where P₊ = P₁ ⊕ P₂ ⊕ P₃

The receiving side decrypts with

P₁ = D(C₁) ⊕ IV
P₂ = D(C₂) ⊕ C₁
P₃ = D(C₃) ⊕ C₂
P₊ = D(C₊) ⊕ C₃

A man-in-the-middle attacker flips C₁ and C₂. Here's what the recipient sees:

P₁' = D(C₂) ⊕ IV
P₂' = D(C₁) ⊕ C₂
P₃' = D(C₃) ⊕ C₁
P₊' = D(C₊) ⊕ C₃

Notice that P₊' = P₊ — perturbing a CBC ciphertext only has an effect up to the next block after the perturbation, the rest remains intact. And

P₁' ⊕ P₂' ⊕ P₃' = D(C₂) ⊕ IV ⊕ D(C₁) ⊕ C₂ ⊕ D(C₃) ⊕ C₁
P₁ ⊕ P₂ ⊕ P₃ = D(C₁) ⊕ IV ⊕ D(C₂) ⊕ C₁ ⊕ D(C₃) ⊕ C₂

Oh, look, these are the same. The checksum on the modified message is correct.

It is possible to design a MAC algorithm based on CBC, but you have to be more careful than this. A naive CBC-MAC allows attacks of the sort you noticed, by playing with the length. There are variants that don't have this problem. However, there's a snag: you must not use the same key for CBC encryption and CBC-MAC! This is because if you use the same key, and the attacker has control over some of the plaintext, then the attacker can cause the sender to calculate a MAC for her. For example, the CBC-MAC of a one-block message is just the result of encrypting that block. So if the attacker wants to send a one-block message, all they have to do is to arrange for the sender to encrypt a message that starts with that block and read the result. It is a general principle that using the same key for two different things is dangerous because it allows protocol confusion errors where the same calculation produces data that must be public for one of the uses of the key and private for the other use.

Xor is not as good as a MAC. In fact, even your initial reading of the authentication tag as [data, SHA1(data)] wouldn't work, because CBC encryption of a hash is not secure (the flaw is more subtle than with xor, but it exists).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.