Re: [dm-devel] [PATCH] dm: remake of the verity target

From: Mikulas Patocka
Date: Tue Mar 20 2012 - 23:11:34 EST




On Tue, 20 Mar 2012, Mikulas Patocka wrote:

> > Changes:
> >
> > * Salt is hashed before the block (it used to be hased after). The reason
> > is that if random salt is hashed before the block, it makes the process
> > resilient to hash function collisions - so you can safely use md5, even if
> > there's a collision attach for it.
>
> I am not aware of any additional benefit to prepending the salt versus
> appending. Could you please provide such a reference.
>
> I would like to avoid breaking backward compatibility unless there is
> a real benefit.
>
> Regards,
> Mandeep
>

This is some deeper explanation why I do it this way. The reason is to
protect agains collision attacks (such as a known attack on MD5 or
possible future attacks against other hash functions).

"Preimage attack" means that you are given a hash value and you create a
message that hashes to that hash value. There is no known preimage attack
for currently used hash functions.

"Collision attack" means that you are able to create two messages that
hash into the same hash value. There is currently collision attack known
for MD5.


Suppose that I publish some software, calculate MD5 digest of it and sign
that digest. This is safe (despite the existing collision attack on MD5)
beacuse there is no preimage attack --- no one is able to create another
file with the same MD5 hash.

However, it is still possible to break security with collision attack, but
the attacker must be able to submit some of his data into the software
signed with MD5.


Suppose for example that software developer publishes "real_program" and
signs it with MD5. The attacker inserts some security backdoor into the
program and gets "insecure_program". The attacker takes two MD5 states ---
the state as it was after hashing "real_program" and the state as it was
after hashing "insecure_program" --- and with collision attack, he is able
to create two messages "m1" and "m2" such that they result in MD5
collision.

The result is that
MD5("real_program"+"m1") and MD5("insecure_program"+"m2") hash to the same
value.

Now, to make the attack successful, the attacker must trick the software
developer somehow into inserting "m1" into his program.

It is not trivial, but possible to trick the software developer into
inserting attacker-controlled data into the program. For example, the
attacker can send him a file containing the string "m1" and claim that it
is Chinese localization of the program --- if the software developer has
no knowledge of Chinese writing system, he can't diferentiate a real
Chinese text from a string of random characters --- so he inserts the file
containing "m1" into his program and publishes it.

Now the attack is finished, the software developer published and signed
"real_program"+"m1" and there exists another file "insecure_program"+"m2"
that hashes into the same MD5 value. So the attacker can misrepresent
"insecure_program"+"m2" as being real.


You can protect from this situation either by using a hash function
without collision attack or by prepending some random data before the
program to be hashed. If the developer signs "random_data"+"real_program"
with MD5 in the above example, there is no way how the attacker can create
a collision --- the attacker can still create "m1" and "m2" and trick the
developer into including "m1" in the program --- but the developer uses
different "random_data" next time he publishes a next version of the
software, so there will be no MD5 collision.


This is a reason why I changed dm-verity hashing system. The salt is
random-generated when creating the hashes. When we hash a data block, we
prepend the salt to the data. Consequently, the attacker can't exploit the
collision attack as described above. If we append the hash (as it used to
be before), it would be possible to exploit the collision attack.

Mikulas
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/