Cryptography-Digest Digest #321, Volume #11 Mon, 13 Mar 00 10:13:01 EST
Contents:
MD5 collisions (Larry)
Re: MD5 collisions (Terje Mathisen)
US export status of RC4? (Impervious)
Re: Best language for encryption?? ("Gary Watson")
sci.crypt.applied ("Gary Watson")
Re: MD5 collisions (Casper H.S. Dik - Network Security Engineer)
Re: Concerning UK publishes "impossible" decryption law (Vg'f whfg Ybxv ntnva.)
Re: If we spent as much time.. (John Savard)
Re: MD5 collisions ("Tom St Denis")
Re: MD5 collisions (SCOTT19U.ZIP_GUY)
any free-lance cryptanalysts out there? ([EMAIL PROTECTED])
Re: Random permutations (Herman Rubin)
Re: US export status of RC4? (Kent Briggs)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Larry)
Subject: MD5 collisions
Date: 13 Mar 2000 05:23:23 -0500
I apologize if this is foolish and/or a FAQ - I'm not able to find
this discussed:
For some value of X, has anyone proven that there are no MD5
collisions for ASCII strings of up to X characters?
(I can do small values of X myself - I was wondering if anyone had
definitively demonstrated this for some higher arbitrary figure, ie
256, 1024, etc...)
I want to hash lots of small strings (probaby 3-200 chars, only ASCII
printable). I realize that the odds are phenomenally small of a
collision in that data set. I'm trying to convince some relatively
non-techies to use this architecture- as opposed to saying "it's
unlikely", I'd rather say "It's been looked at and there are none."
(if that's true).
Thanks.
--L
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: MD5 collisions
Date: Mon, 13 Mar 2000 11:53:27 +0100
Larry wrote:
>
> I apologize if this is foolish and/or a FAQ - I'm not able to find
> this discussed:
>
> For some value of X, has anyone proven that there are no MD5
> collisions for ASCII strings of up to X characters?
>
> (I can do small values of X myself - I was wondering if anyone had
> definitively demonstrated this for some higher arbitrary figure, ie
> 256, 1024, etc...)
>
> I want to hash lots of small strings (probaby 3-200 chars, only ASCII
> printable). I realize that the odds are phenomenally small of a
> collision in that data set. I'm trying to convince some relatively
> non-techies to use this architecture- as opposed to saying "it's
> unlikely", I'd rather say "It's been looked at and there are none."
> (if that's true).
As soon as you go beyond 16 bytes of input (i.e. 128 bits), you are
guaranteed that there will be collisions in the MD5 hashes.
This is of course obvious, there is no way to stuff more than 128 bits
into a 128-bit container.
OTOH, if you are only going to use this for siginificantly less than
2^64 (sqrt(2^128)) different messages, then the likelyhood of a single
collision will be very low as well.
It all depends on what you mean by 'lots' of small strings.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: [EMAIL PROTECTED] (Impervious)
Subject: US export status of RC4?
Date: Mon, 13 Mar 2000 10:50:01 GMT
Hello all,
Does anyone know the current US export regulations for RC4? I have a
freeware utility I want to release based on an RC4 Implementation with
a 256-bit key and SHA hashing, but I don't want to get in any
trouble!! :)
If anyone can help or point me to a URL with info I'd be sincerely
grateful.
Manuel
------------------------------
From: "Gary Watson" <[EMAIL PROTECTED]>
Subject: Re: Best language for encryption??
Date: Mon, 13 Mar 2000 11:09:37 -0000
By far the best language for encryption is VHDL. ;-)
--
Gary Watson
[EMAIL PROTECTED] (Change dot sex to dot com to reply!!!)
Nexsan Technologies Ltd.
Derby DE21 7BF ENGLAND
http://www.nexsan.com
Paul Schlyter <[EMAIL PROTECTED]> wrote in message
news:89gidn$1la$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>
> > wtshaw wrote:
> >> It all depends on your purpose. C appears useful, but tends to be
> >> more cryptic than BASIC, which is a higher level language than C.
> >> C and C++ are powerful, but for demonstration purposes BASIC is much
> >> more apparent in source, and tends not to rely on brand x classes or
> >> header files as training wheels to get the most out of it, as it
> >> already works at a sopistocated level.
[condensed]
------------------------------
From: "Gary Watson" <[EMAIL PROTECTED]>
Subject: sci.crypt.applied
Date: Mon, 13 Mar 2000 11:36:54 -0000
I haven't seen a great deal of discussion of applied cryptography in this
ng, that is, the nuts-n-bolts techniques used to implement a cipher in such
a way that the final product is secure. I'm not proposing a new
sci.crypt.applied newsgroup, but if it existed, perhaps the charter would
propose discussions of:
GENERAL SECURITY
* Physical security
* Emissions security (Tempest)
* Communications security
KEYING
* Key generation
* Key distribution
* Keynets
* Memorable (nmemonic) versus random keys
* Rejection of weak keys
* Key fill devices
* Steganographic keying
* Blind keying
* Key escrow (boo! hiss!)
* Biometrics
HARDWARE
* Available components
* Design of ASICs and FPGAs including VHDL samples
* Reverse-engineering countermeasures
* Anti-tamper / tamper detection
* Authentication
* Smart cards
SOFTWARE
* Code to implement algorithms
* Efficiency
* User interface including non-interceptable key input
* Anti-cracker
* Anti-spoofer
* Anti-any other type of hacking
* Scrubbing media including RAM ("secure delete")
* Identifying and destroying all temporary files and buffers
* Better integration with Winblows environment
* Discussion of weaknesses in commercial packages
I'm sure most of you could come up with addtional categories. My thinking
is that these discussions are not really about the science of
"cryptography", rather, they are implementation detals relevant only to
today's hardware and software environment. I looked through 3000 ng message
headers in sci.crypt across the last couple of days, and the above topics
didn't seem to get enough attention. Their importance is obvious, and
though I notice some purists in the ng who argue that the only important
thing is having the best cipher in the universe, but with poor (or even
"average") implementation, it's like hanging a bank vault door on a house
made of balsa wood.
Any thoughts or flames?
--
Gary Watson
[EMAIL PROTECTED] (Change dot sex to dot com to reply!!!)
Nexsan Technologies Ltd.
Derby DE21 7BF ENGLAND
http://www.nexsan.com
------------------------------
From: [EMAIL PROTECTED] (Casper H.S. Dik - Network Security Engineer)
Subject: Re: MD5 collisions
Date: 13 Mar 2000 11:34:56 GMT
[[ PLEASE DON'T SEND ME EMAIL COPIES OF POSTINGS ]]
[EMAIL PROTECTED] (Larry) writes:
>For some value of X, has anyone proven that there are no MD5
>collisions for ASCII strings of up to X characters?
Never heard of something like that.
>(I can do small values of X myself - I was wondering if anyone had
>definitively demonstrated this for some higher arbitrary figure, ie
>256, 1024, etc...)
It's easy to compute the upperbound of X; an md5 hash is 128 bits.
If we suppose that each ascii character takes 7 bits (somewhat
less, but more than 6), collisions muct occur when X > 128/7; i.e.,
after 18 or so characters.
The birthday paradox suggests that there's a high likelyhood
of collisions occuring with smaller strings (as soon as you have 2^64
hashes, there's a +/- 50% chance of a collision)
>I want to hash lots of small strings (probaby 3-200 chars, only ASCII
>printable). I realize that the odds are phenomenally small of a
>collision in that data set. I'm trying to convince some relatively
>non-techies to use this architecture- as opposed to saying "it's
>unlikely", I'd rather say "It's been looked at and there are none."
>(if that's true).
As shown above, "it's been looked at and there are some", but the odds
are tiny indeed.
Hashing is typically done with worse apgorithms (shorter output values);
your algorithm shouldn't depend on "no collisions"; typically, you heap
all values with the same hash in a "bucket"; with the hash function
you find the proper bucket and then search it for a proper match.
How are you going to use the 128 bit MD5 key to index a hashtable?
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
------------------------------
From: Vg'f whfg Ybxv ntnva. <Yb*[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,alt.security.scramdisk,alt.privacy
Subject: Re: Concerning UK publishes "impossible" decryption law
Reply-To: [EMAIL PROTECTED]
Date: Mon, 13 Mar 2000 12:54:59 GMT
On Mon, 13 Mar 2000 09:05:46 +0100, Terje Mathisen
<[EMAIL PROTECTED]> wrote:
>:JimD wrote:
>:>
>:> On Sun, 12 Mar 2000 07:06:56 -0600, Chuck <[EMAIL PROTECTED]> wrote:
>:>
>:> >On Sun, 12 Mar 2000 00:34:25 +1100, "�R���" <[EMAIL PROTECTED]> wrote:
>:> >
>:> >>i have been trying to work out a way of using the windows login to booby
>:> >>trap the hd, say if they ask you what your logon is, and you tell em its
>:> >>your name and ph number, when its not, and they use it, poof, a batch file
>:> >>wipes all sensitive data and does a pgp free space wipe as it boots up, i
>:> >>can figure out how to write the batch file, but not where to put it, perhaps
>:> >>in the new user run once registry line? any ideas?
>:> >
>:> >Doesn't work. The first thing they do is turn everything off. The
>:> >second thing they do is plug your hard drive into a system that boots
>:> >from their own hard drive, and create an exact image of every sector
>:> >(including freespace) for later analysis. There's no need to boot from
>:> >your hard drive or to run any of your programs from it. If they need
>:> >to run one of your programs, they copy the image to an identical test
>:> >drive and do it there. Self-destruct code only wipes the test drive
>:> >and provides a neon sign pointing to the stuff you want to keep
>:> >secret.
>:>
>:> You seem to know a lot about it, or appear to. Are you one of THEM?
>:
>:Probably not.
>:
>:What Chuck writes is simply common sense.
There is a method behind the madness though. Although "THEM" is kind
of a vague boogey-man entity that hide under beds of people wearing
foil hats (shiny side out). I was a cop until I retired a couple of
years ago, and that is how our computer-crime lab worked it. The
answer is surprisingly simple - the 'best evidence' rule and
liability.
"Best Evidence' is always the original in an undamaged and unaltered
state. In the case of a HD, the investigators will have to testify
that the drive has been unaltered between the time of seizure and the
time of entry into trial. Since fooling around with the HD always
will alter it, a carbon copy is used to recover and gather data.
Second, there is always the chance that the drive will not contain any
information of evidentiary value and will have to be returned to the
owner in an unaltered state. Let's say for example that the police
seize my HD in the belief that it contains records pertaining to (pick
a crime) but in fact contains only records pertaining to my legitimate
business, and those records are damaged while in police custody. I
can hold the police department and the city liable for that damage.
Then, of course, the common sense factor. It is always best to work
from a copy and not the original - as every one of us who had to
laboriously copy a 26-floppy program onto other floppies before
installing it well knows. If for any reason one of our backup disks
was corrupted, we always had the original to fall back upon to make
another copy. It wasn't that long ago that going to CompUSA and
buying a new program and a box of blank floppies at the same time was
a common action.
>:Terje
Vg'f whfg Ybxv ntnva.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: If we spent as much time..
Date: Mon, 13 Mar 2000 12:42:08 GMT
On Sat, 11 Mar 2000 10:16:46 -0800, "Steve A. Wagner Jr."
<[EMAIL PROTECTED]> wrote, in part:
>If we spent as much time studying crytography and trying to crack and
>improve the most respected and current crypto algorithms, we'd have much
>more secure alternatives for the future. Instead, everyone wants to
>sport a unique cipher with their name on it. Could the large population
>of cipherpunks channel their efforts toward real crypto....
That sounds too much like work.
>And if you lack the math background for this, as I do, there's nothing
>wrong with designing software and hardware that use known and proven
>security protocols.
Indeed, one must consider that possibility; otherwise, it sounds too
much like "why don't all those people who waste time watching Star
Trek do cutting-edge scientific research instead"?
Actually, a lot of the people who are writing encryption programs and
utilities for people's use are using well-known ciphers.
But, for people, even within their own limitations, to want to
exercise creativity and make a modest contribution, is only to be
expected, and I do not find it harmful, as long as they keep a sense
of perspective. As long as they are realistic in acknowledging the
limitations their designs may have.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: MD5 collisions
Date: Mon, 13 Mar 2000 13:19:01 GMT
Larry <[EMAIL PROTECTED]> wrote in message news:8aifir$qf2$[EMAIL PROTECTED]...
>
> I apologize if this is foolish and/or a FAQ - I'm not able to find
> this discussed:
>
> For some value of X, has anyone proven that there are no MD5
> collisions for ASCII strings of up to X characters?
>
> (I can do small values of X myself - I was wondering if anyone had
> definitively demonstrated this for some higher arbitrary figure, ie
> 256, 1024, etc...)
>
> I want to hash lots of small strings (probaby 3-200 chars, only ASCII
> printable). I realize that the odds are phenomenally small of a
> collision in that data set. I'm trying to convince some relatively
> non-techies to use this architecture- as opposed to saying "it's
> unlikely", I'd rather say "It's been looked at and there are none."
> (if that's true).
>
> Thanks.
A hash is not strong because there are no collisions. A hash is strong
because two inputs that do collide are entirely uncorrelated and difficult
[impossible] to predict. For example if you hash 256 bit strings you are
guaranteed to have at least 2^128 collisions. Finding which 256 bit strings
collide to the same value is a diffcult task though.
Tom
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: MD5 collisions
Date: Mon, 13 Mar 2000 15:48:09 GMT
In article <9V5z4.14381$[EMAIL PROTECTED]>, "Tom St Denis"
<[EMAIL PROTECTED]> wrote:
>
>Larry <[EMAIL PROTECTED]> wrote in message news:8aifir$qf2$[EMAIL PROTECTED]...
>>
>> I apologize if this is foolish and/or a FAQ - I'm not able to find
>> this discussed:
>>
>> For some value of X, has anyone proven that there are no MD5
>> collisions for ASCII strings of up to X characters?
>>
>> (I can do small values of X myself - I was wondering if anyone had
>> definitively demonstrated this for some higher arbitrary figure, ie
>> 256, 1024, etc...)
>>
>> I want to hash lots of small strings (probaby 3-200 chars, only ASCII
>> printable). I realize that the odds are phenomenally small of a
>> collision in that data set. I'm trying to convince some relatively
>> non-techies to use this architecture- as opposed to saying "it's
>> unlikely", I'd rather say "It's been looked at and there are none."
>> (if that's true).
>>
>> Thanks.
>
>A hash is not strong because there are no collisions. A hash is strong
>because two inputs that do collide are entirely uncorrelated and difficult
>[impossible] to predict. For example if you hash 256 bit strings you are
>guaranteed to have at least 2^128 collisions. Finding which 256 bit strings
>collide to the same value is a diffcult task though.
>
>Tom
>
>
One of the measures of a hash would be the fact that there are few
collisions for short strings. Why this is important seems to allude TOM
but assuming you have a good hash that hashes to 128 bits. Then as
Tom stated if the strings you are hashing are 256 bits then there will be
many possilbe collisions. One way to reduce the collsions would be to
use a conditional compressor like you find at my site. No wasted bits
you just compress to a smaller string based on the subset of characters
used in the 256 bit string.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction of the
truth."
------------------------------
From: [EMAIL PROTECTED]
Subject: any free-lance cryptanalysts out there?
Date: Mon, 13 Mar 2000 14:54:30 GMT
I'm a newby here and I'm looking for someone who will help me decipher
some text. It's a long story, but briefly I have discovered a piece of
text which contains two pieces of encoded text. I have not been able to
decipher it and I need some help - actually I need someone to do it for
me. Can anyone recommend an expert? Preferably I need someone who
lives in the UK, since that is where I am and that is where the text is.
The solution to this will be published in a book - if the solution is
worthwhile, and I have the strongest reasons for believeing that it will
be. Who ever decides to join me in this enterprise will share the
authorship of the book if they want. You can contact me direct if you
think you can help, but please - only those who really are good at this
should apply.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Random permutations
Date: 13 Mar 2000 09:57:58 -0500
In article <[EMAIL PROTECTED]>,
Samuel Paik <[EMAIL PROTECTED]> wrote:
>Mok-Kong Shen wrote:
>> The common method of generating a random permutation is that
>> due to Durstenfeld (see Knuth), utilising uniformly distributed
>> real-valued random numbers in (0, 1] to swap pair of elements.
>> Since such random numbers are most often derived from integer-
>> valued random numbers through division operations, an alternative
>> method suggests itself, basing on the idea underlying the
>> well-known procedure in classical cryptography of selecting the
>> columns of a polyalphabetic substitution table with the aid of a
>> given key.
The cost of the random numbers probably exceeds the
division, if they are any good. If division is needed,
it is typically the fast floating division, not the
slow integer division.
That is, one attaches to the elements to be permuted
>> a field which is filled with the integer-valued random numbers
>> (one for each element). Subsequently one sorts such records
>> according to the said field. I guess that this method of doing
>> random permutations (which evidently has nothing new in it) is
>> equivalent (in quality) to that of Durstenfeld. Any comments?
>Supplying n random numbers to do n swaps is O(n) in time with
>a very small constant factor and uses essentially no storage.
One can even do better, if it is a bit sequence which
is produced. There is no way of getting around O(n log n)
BITS, and this number with an additional factor, and less
than 2n comparisons, can be achieved. This will certainly
beat sorting. There are methods which use fewer bits, even
the minimum number for making the decisions one at a time,
which get below the information plus 2n bits on the average,
but they will need O(n log n) comparisons.
The low comparison method, together with the swap, is
as follows; the code can be tweaked for greater
efficiency. We denote by q(k) the smallest integer
j such that k <= 2^j. The array is a[k], 0 <= k < n.
for(m=n; m>1; m--){
until(k < m) k = binary number with q(m) random bits;
swap(a[k], a[m-1);
}
The bit managing can be done fairly efficiently, and
the computation of q(m) can be moved to the modified
for loop.
This will reduce the number of comparisons far below
that for any kind of sort, and the number of bits
used to at most a small factor over the minimum.
>Supplying n random numbers than using comparison sorting
>is O(n log n). With interpolation sort, you get back to
>O(n) but the constant factor is greater than with the usual
>algorithm, and you need additional memory.
>Divisions may be expensive enough to compensate for the
>extra work, but I have doubts.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: US export status of RC4?
Date: Mon, 13 Mar 2000 15:03:41 GMT
Impervious wrote:
> Hello all,
>
> Does anyone know the current US export regulations for RC4? I have a
> freeware utility I want to release based on an RC4 Implementation with
> a 256-bit key and SHA hashing, but I don't want to get in any
> trouble!! :)
>
> If anyone can help or point me to a URL with info I'd be sincerely
> grateful.
>
> Manuel
BXA encryption export controls page:
http://www.bxa.doc.gov/Encryption/Default.htm
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
