Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am examining a protocol that uses CRC32 as a MAC (see note 1) the weaknesses of this method but I would nevertheless like to see if it is just weak or actually relatively easily to break.

The examined protocol has the format more or less of:

Plaintext = Headers (6 bytes) || CRC (4 bytes) || Data
Ciphertext = 3DES-CBC(Plaintext)

This is used for a Server to send a Client a message and the Client will authenticate the message by decrypting it and checking the CRC. An attacker cannot ask the Server or the Client to encrypt a message, they could predict though the plaintext from a ciphertext.

Searching about it I can see that there is an attack on SSH 1.5 that is similar. To perform the attack the format of the data is put into this format for SSH:

Plaintext = Padding (8 bytes) || Data || CRC (4 bytes)
Ciphertext = 3DES-CBC(Plaintext)

The attack is performed partially by taking advantage of the CBC encryption by changing the first block which is the 8 byte padding in order to manipulate the second 8 byte block. If I was to perform the same attack though on the examined protocol since the 4 byte CRC is split between the first and second protocol it wouldn't work.

Note that the question is not if the protocol is weaker compared to a protocol where a proper MAC like HMAC had been used but if there is any attack that could relatively easily break the authentication.

NOTES

  1. From fgrieu: The terminology is not quite right: CRC32 can't be used as (a weak substitute for) a MAC, for it is a keyless transformation of the message. Rather, here, it is used as (a weak substitute for) a hash in a hash-then-encrypt scheme
share|improve this question
    
CRC is not a MAC at all, it provides no authentication –  Richie Frame Jul 21 at 5:24
1  
The terminology is not quite right: CRC32 can't be used as (a weak substitute for) a MAC, for it is a keyless transformation of the message. Rather, here, it is used as (a weak substitute for) a hash in a hash-then-encrypt scheme, something which itself does not generally insure message integrity. $\;$ If the IV for the 3DES-CBC encryption is 8 random bytes prepended to the cryptogram, and the length of Data variable, and the adversary able to mount a chosen-ciphertext attacks, then such generic attacks on hash-then-CBC-encrypt work here. –  fgrieu Jul 21 at 5:47
    
@fgrieu : $\:$ Is there such an attack when the hash goes before the plaintext? $\;\;\;\;$ –  Ricky Demer Jul 21 at 5:56
3  
@RickyDemer: Yes. Adapted to the present context (with CRC instead of Hash, but that works for a hash just the same): one decides the desired Forgery, computes its CRC, builds 6zeroes||Headers||CRC||Forgery, submits that as (chosen) Data for authentication and encryption; and from the resulting cryptogram removes the first 16 bytes (including 8 bytes IV). What remains will pass verification (the first 8 bytes will be the IV). –  fgrieu Jul 21 at 6:12
    
In my first comment, read "the adversary able to mount a chosen-PLAINTEXT attack". –  fgrieu Jul 21 at 7:03

1 Answer 1

Well, 32 bits is somewhat short, so one could just try ciphertexts.
However, there is a much better attack.

Choose M0 arbitrarily, let P be the CBC padding for Headers || CRC || M0,
and choose M1 so that CRC( M0 || P || M1 ) = CRC(M0).
Submit M0 || P || M1 to be encrypted, truncate the ciphertext to the length of
encryptions of M0, and then output the result. $\:$ That will be a valid encryption of M0.


Even without chosen plaintext, one should be able to change the headers.

Let H be the headers and let CL be the first 16 bits of CRC and let L be the (bit-)length of Data.
Choose 48 bits X which are not all zero so that the CRC of [X combined with L zero bits
however the protocol does that] ends with the same 16 bits as the CRC of 48+L zero bits.
Xor the IV with [X concatenated with [the xor of the first 16 bits of the two just-mentioned CRCs.
By the affineness of CRC, the result will be a valid ciphertext
with the same Data and header H xor X.

share|improve this answer
    
I should have added that the protocol doesn't support asking for a specific plaintext to be encrypted. So basically the server will send a message to the client and the client will authenticate it using this protocol. The plaintext could be predicted though. –  Antikithira Jul 22 at 1:53
    
How long is the message? $\;$ –  Ricky Demer Jul 22 at 2:18
    
Th message could be as small as 16 bytes and as big probably to a couple of hundrend bytes –  Antikithira Jul 23 at 2:32
    
What padding do they use? $\:$ How many possible plaintexts are there? $\;\;\;\;$ –  Ricky Demer Jul 23 at 4:14
    
@Antikithira : $\:$ Also, is the CRC computers over Headers too or just Data? $\hspace{1.62 in}$ –  Ricky Demer Jul 23 at 17:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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