From: jhmeyers@miu.edu (John H Meyers)
Newsgroups: comp.sys.hp48
Subject: Re: A checksum collision (cheksum)
Date: 10 Apr 1998 10:31:15 GMT
Organization: MIU Computer Services,  Fairfield, IA 52557.  Not Approved.
Lines: 86
Message-ID: <6gksdj$8rn$1@news.iastate.edu>
References: <6gd093$snm$1@nnrp1.dejanews.com>,<6gfb9r$ejl$3@news.iastate.edu>
Reply-To: jhmeyers@miu.edu
NNTP-Posting-Host: vax1.mum.edu
Xref: republic.btigate.com comp.sys.hp48:9133

Alex (3912@bigfoot.com) was looking for different objects
having identical checksums.

It is not hard to find some, using the "Birthday Paradox"
(See "Re: Birthday Question" posted 1996/03/02 in sci.math)

For example, I generated 999 random 5-character uppercase strings,
then took the checksum of each object, sorted the results and
scanned for duplicates (all via HP48 list processing, of course),
obtaining the following string object pairs which have identical
checksums; if you change both strings of each pair to lower case
(or just change some of the letters in corresponding positions),
the pair of checksums will also remain identical:

  BEILK and MIGUA (assume quoted strings; I'll just type the letters)
  CYTOZ and LUZVP
  AOBVP and XJDSR
  ZLTFV and FNUIT
  QZWIE and WLGPB
  SSJPJ and KNMQX
  BHFTM and ITGJI
  QYAPU and BCPHV
  UDYOG and RJYZQ (you can also replace each "Y" with any other character)
  RDCDU and RNMJA (ditto for the "R"s, or you can just drop both "R"s)

Since the HP48 16-bit checksum (also used in Kermit packet checking)
has 2^16 = 65536 different possible values, the probability of any
two particular randomly-chosen objects having identical checksums
is only 1/65536; however, in a collection of 999 objects, there are
about 500,000 different ways to pick any one pair from them, which
gives us an immediate sense of the likelihood (but not certainty)
that several pairs having duplicated checksums may exist within
the whole collection, although we don't know in advance which
pairs this may be.

If this seems paradoxical, consider the fact that although your
particular chance of winning a lottery having odds of 1 in
10 million is negligible, if 50 million tickets are sold,
then the odds that *someone* is a winner are pretty good,
even though each individual person's chances are very small.

If a 32-bit checksum were used, then there would be 4,294,967,296
different possible checksums, and the calculator couldn't store
enough objects to make it likely to find any duplicates at all.

With a 128-bit checksum (or "hash"), as is commonly used for
"authenticating" or "signing" electronic documents, it is unlikely
that any two documents in the world would have identical hash values;
if the "hash function" is also very difficult to "work backwards"
(to figure out what input might produce its output), then it is also
very difficult to alter a document without detection, whereas it is
a trifling matter to produce objects having any given 16-bit CRC
(or almost any common "error-detection" CRC of any number of bits).

Here is the program which found the above list of string pairs having
identical CRC; however, since the results depend upon the initial
random number seed, they will vary with each execution of the program:

%%HP: T(3)A(D)F(.); @ Find duplicate checksums using Birthday Paradox
\<<

  @ Set random seed randomly (better than 0 RDZ)
  DATE EXP TIME EXP * RDZ

  @ Create list of desired number of random strings:
  \<< "" 1 5 START RAND 26 * 64.5 + CHR + NEXT \>> @ 5-characters each
  'n' 1 999 1 SEQ @ E.g. 999 strings
  @ 300 strings should usually be enough to find some duplicate(s).

  DUP 1 \<< BYTES DROP \>> DOSUBS SORT @ List all checksums
  2 \<< DUP2 SAME { DROP } { DROP2 } IFTE \>> DOSUBS @ Duplicates?

  @ If no duplicates, the HP48 will error below,
  @ because DOSUBS will not return/accept an empty result/argument list.

  @ Remove from strings list all whose checksum isn't in duplicates list:
  \-> x \<< 1 \<< DUP BYTES DROP x SWAP POS NOT { DROP } IFT \>> DOSUBS \>>

  @ Make final list of checksums and strings:
  1 \<< DUP BYTES DROP SWAP 2 \->LIST \>> DOSUBS SORT
  @ Press EVAL and then use Interactive Stack to view results.

\>>

-----------------------------------------------------------
With best wishes from:   John H Meyers   <jhmeyers@mum.edu>