🚀 go-pugleaf

  In reply to me, Vesselin Bontchev writes:
>>          First, you write as if all algorithms have a seed.
>
> My initial thought was that the database of checksums is kept on-line.
> If it isn't (i.e., if it is stored on a write-protected diskette),
> then you don't need any cryptographic checksum, of course. But if it
> is, you cannot just use plain MDx or any other known keyless
> algorithm, because a virus could use the same algorithm to compute the
> new checksum of the infected file and update the database of checksums,
> so that everything will look OK... In these cases, you -must- have
> some kind of key that is kept unknown to the virus.

Since this is essentially the same as what I have written several times,
I guess I can't very well object to it, can I?  :-)

>>                 But what do you mean by "using a different seed for
>> the checksum" in the case of CRC?
>
> Well, a CRC is usually computer like this:
>
> 	crc = INITIAL_VALUE;
>   	while ((c = getc (file)) != EOF)
>		crc = crc_table [(crc & 0x00FF) ^ c] ^ (crc >> 8);
>
> Usually INITIAL_VALUE is 0, but you could set it to anything you would
> like...

Well, I think that comes from using a particular (table-driven) *im-
plementation* of CRC, and is not an essential feature of CRC as it
is defined.  Also, while I agree that in this implementation
INITIAL_VALUE could be considered as a seed, I doubt that varying this
value adds any security, since CRC can be made key-dependent in a
very natural way (by varying the generator) and since, in a certain
sense, it is then provably secure (subject to certain reasonable
assumptions).

>>   More important, in the case of MDx and X9.9, how do you know that
>> varying the seed is enough?
>
>You are right, I don't know whether it is secure enough. But you have
>to do something with the keyless algorithms, if you want to achieve
>different checksums for each user and not allow the virus to guess the
>correct checksum of the modified object...

But why is it necessary to do something with keyless algorithms at
all?  There is an alternative to varying a seed (or artificially
introducing a key) in a keyless algorithm, and that is to use an
algorithm which is key-dependent by its very design (such as the MAA
of ISO 8731-2 or ANSI X9.9, if one wants a cryptographic algorithm).
  I'm not saying that the latter alternative is necessarily better
than the former.  Regardless of which is used, the important criteria
are security and speed, where "security" means mainly the requirement
that, given a file (without knowledge of the key or seed), it be com-
putationally infeasible to create another file with the same checksum
as the given one.

                                     Y. Radai
                                     Hebrew Univ. of Jerusalem, Israel
                                     RADAI@HUJIVMS.BITNET
                                     RADAI@VMS.HUJI.AC.IL