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

[Mandeep Singh Baines]

On Tue, Mar 20, 2012 at 8:11 PM, Mikulas Patocka <mpatocka@xxxxxxxxxx> wrote:
>
>
> 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.
>

But we are hashing fixed-sized blocks so there is no possibility of extension.

However, better safe than sorry. I guess we'll just have to deal with
backward incompatibility. So feel free to add my sign off to the new
patch also.

Signed-off-by: Mandeep Singh Baines <msb@xxxxxxxxxxxx>

Regards,
Mandeep

> 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/