Cryptography-Digest Digest #532, Volume #13 Tue, 23 Jan 01 16:13:01 EST
Contents:
Re: JPEG infidelity for crypto (Kenneth Almquist)
Re: Kooks (was: NSA and Linux Security) ("Douglas A. Gwyn")
Re: using AES finalists in series? ("Douglas A. Gwyn")
Re: Dynamic Transposition Revisited (long) (Terry Ritter)
Re: Dynamic Transposition Revisited (long) (Terry Ritter)
Re: Why Microsoft's Product Activation Stinks ("Joseph Ashwood")
Re: Dynamic Transposition Revisited (long) (Terry Ritter)
Re: Some Enigma Questions ("David C. Barber")
Re: using AES finalists in series? (Terry Ritter)
Re: Cryptographic Windows APIs or OCX? ("Joseph Ashwood")
Re: collisions risks of applying MD5 or SHA1 to a 48-bit input ("Joseph Ashwood")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: JPEG infidelity for crypto
Date: 23 Jan 2001 20:10:47 GMT
[EMAIL PROTECTED] (John Savard) wrote:
> On Sun, 21 Jan 2001 17:03:18 +0800, Dido Sevilla <[EMAIL PROTECTED]>
> wrote, in part:
>
>> What relation does this have to cryptography? Have you missed saying
>> something?
>
> Well, the relation is obvious: simple forms of steganography, which
> depend on preserving things like the LSB of every single pixel, don't
> work with .JPG files.
Steganography is not covered by the sci.crypt FAQ, but my understanding
is that the term refers to hiding data in messages which look like
something else, the point being to disguise the fact that you are
sending encrypted messages. For this purpose, the fact that JPEG is
a lossy compression algorithm is relevant only if the communication
channel applies JPEG compression to all transmitted data. This seems
rather far fetched.
JPEG images would be a good choice for hiding messages precisely because
it is common for multiple compressions of the same scan to appear on the
internet. A typical scheme might work as follows:
1) You and your partner agree on a set of images.
2) When you want to send a message, you select an image and
compression parameters at random. (The compression parameters
should be chosen from a set of "plausible" parameters.)
3) The JPEG image standard specifies that you apply a discrete
cosine transformation, and then round the resulting values
to the nearest integer. (The rounding step makes JPEG lossy.)
Apply the transform, but rather than rounding to the nearest
integer, round up or down based on the next bit of the data to
be hidden. This encodes one bit per pixel.
4) To extract the message, the receiver performs the same discrete
cosine transformation and compares the result with the received
message to determine whether each value was rounded up or down.
If an evesdropper observes multiple copies of the same image being
sent, that might provide a clue that steganography is being used, so
you would want a fairly large number of pictures for this purpose.
The alt.binaries.pictures newsgroups provide a good supply.
> You could complain that we already knew that, and that there are more
> sophisticated (but less efficient) methods of steganography that even
> work with JPEGs; they're mainly used for watermarking.
Watermarking involves modifying an image or other work slightly so
that you can recognize it when you see it again. This is a different
problem than hiding a message. Watermarking systems are designed to
foil deliberate attempts to obscure the watermark by making small
changes to the watermarked copy. The fact that small changes can be
introduced by JPEG compression rather than a deliberate attempt to
obscure the watermark would seem to be irrelevant since protecting
against the latter also protects against the former.
By "small" changes, I mean changes that are not visually obvious. The
example that started this thread was one where the JPEG compression
created visible artifacts. Since these artifacts were not specificly
chosen to obscure a watermark, I suppose the odds are that they would
not affect a typical watermark system.
Note that converting a typical color image to GIF format also loses
information. In a GIF image, each pixel must have a color which
appears in the color map, and the color map is limited to 256 colors.
This typically creates signficant visual artifacts throughout the
image. Of course artificially constructed images (as opposed to
photographic images) can be designed to contain no more than 256
colors. I suspect that a watermark applied to such an image could
be obscured by reducing the watermarked image to 256 colors, and
then fiddling with the low order bits of the color map.
Kenneth Almquist
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Kooks (was: NSA and Linux Security)
Date: Tue, 23 Jan 2001 19:11:01 GMT
Greggy wrote:
> And no inquiry was made of the new four states.
> An oversight on your part, I am certain...
You must mean, on the part of the US Secretary of State.
However, he reasonably assumed that if Virginia *had*
ratified the amendment, they would have done so shortly
after it was sent to the states for ratification, and
was attempting to determine whether they had in fact
done so before 1812 (when Louisiana was admitted to the
union). It is only the kooks, not me nor the Secretary
of State, who claim that ratification occurred in 1819.
This raises the question of how late a ratification can
be performed by a state; are *all* proposed amendments
that were sent to states but not ratified still "open"
for possible ratification? Is a state vote against
ratification final or can it be overridden by a later
vote in favor? Like a lot of our early laws, the
procedures were only loosely specified, with the
expectation that people would be reasonable about such
"fringe" details.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: using AES finalists in series?
Date: Tue, 23 Jan 2001 19:27:06 GMT
David Wagner wrote:
> One can formally prove that chaining is at least as secure as the
> underlying cipher (as long as you use independent keys) -- it's an
> easy exercise for a theory of crypto class -- and the proof is just
> a formalization of Terry Ritter's observation.
The last time we went through the exercise, it wasn't as easy
as it seemed..
My point is that one needs to consider what is actually going
on. Of *course* a composite system using vastly more key bits
than one of its components is likely to be "more secure". The
interesting question is whether a single parameterizable component
(like the AES candidates originally mentioned in this thread)
using the same number of key bits as the composite system could
be "more secure" than the composite system. In another branch
of this thread I gave an argument that says "yes", or at any rate
not "no". Chaining of AES candidates seems to be proposed as a
way to feel better about the uncertainty of their actual strength
against competent cryptanalysis, but if so that is misguided,
since *that* concern has not yet been addressed for chaining.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Tue, 23 Jan 2001 20:13:12 GMT
On Tue, 23 Jan 2001 08:29:16 -0800, in
<[EMAIL PROTECTED]>, in sci.crypt "John A. Malley"
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>[snip]
>
>> >This may be a good place to continue the cryptanalysis of the strength
>> >of the DT cipher. A PRNG with N! states to make every permutation of
>> >the bits in an N bit block can only generate some of the possible
>> >sequences of permutations. There are (N!)! possible sequences of
>> >permutations.
>>
>> There are (N!)**S possible sequences of permutations, of sequence
>> length S.
>
>Please help - where did I go wrong in calculating the total number of
>possible sequences of the N! total possible permutations?
>
>Here's my reasoning -
>
>Given N bits there are N! different, unique ways to permute those bits -
>the N! unique permutations. They make a set P.
>
>I number the permutations in the set from 1 to N!. How many different
>ways can I sequence the members of the set of permutations? Or in other
>words, how many different ways can I write down (list) the elements of
>P? Let the number of elements in P be M, so
>M = N!. The number of unique listing sequences of the M elements is the
>number of permutations of the M elements of P, which is M!. Since M =
>N!, then M = (N!)!.
>
>So that's how I derived the number of ways the individual elements of
>the set of permutations of an N bit block can be listed out as a
>sequence.
OK, I had no idea what you were doing. Of course, I still have no
idea where you are going. Do you have any idea how big (N!)! is?
Even 128! is 3.85620482e+215, and the factorial of that is some number
which is about 2.75610295e+218 bits long. (From
http://www.io.com/~ritter/JAVASCRP/PERMCOMB.HTM#Factorials
).
Surely, there is no reason to imagine that permutations must all occur
before repeating. In fact, that would be a weakness.
The design goal is to allow the very same permutation to occur on the
next block, and then rely on the almost infinitesimal probability of
any particular permutation occurring to be assured that it will almost
never happen. The goal is to make the permutation selection for each
and every block independent, with equal probabilities.
We can see the selected permutation as a "value," in a sequence of
values, exactly the same way we get random values from an RNG, or the
way we think of sequences as some number of symbols, each one chosen
from a set. It is a weakness for a random generator to produce a
value which will not then re-occur until the generator recycles.
>> >AFAIK it's safe to say the PRNG generates N! sequences
>> >(assuming the set of seed values is equal to the set of possible outputs
>> >of the PRNG, both sets are of order N!.) Only N!/ (N!)! of the sequences
>> >can ever be seen.
>>
>> ??
>
>There are M! ways to list the M values from 1 - M.
These are called permutations.
>A PRNG outputs lists
>(sequences) of the values between 1-M.
Some RNG's are like that. Don't do that.
>The PRNG starts from a seed
>value s and makes a list of the M values. Each list is different. The
>PRNG can only make as many unique lists of the M values are there are
>unique seeds s. Let the order of the set S of seed values be K. Then
>the PRNG can only make K out of M! listings (sequences) of the M values
>from 1 - M. So the PRNG only produces a fraction K / M! of the total
>possible sequences of the M values.
Internally, there is some concept of a huge cycle which is shuffled by
an RNG -- the internal state -- but that concept is not necessarily
the output value. Surely, when we have a huge internal state, we do
not imagine that we must take the whole amount of that state as the
RNG result. When we do not, any particular value can re-occur on the
very next RNG step.
The Additive RNG is discussed in Knuth II. And even though those are
tiny, it should be clear that, in an Additive RNG, values can and do
repeat. The intent is to make the probability of that immeasurably
close to independent selection.
>Let the set S be the set of M output values of the PRNG. The order of
>the set M is M. Then the PRNG only produces a fraction M / M! of the
>total possible sequences of the M values.
>
>So let M = N! (the number of possible permutations of N bits). The set
>of seed values S for this PRNG is the set of numbers from 1 through M!
>The PRNG generates a number from 1 through M! to choose the permutation
>to apply to the ith bit block. (This is the most abstract view of the
>PRNG's role in the DTC.)
>
>This PRNG can produce only M = N! possible output sequences of
>permutations. That's why I state the PRNG produces a fraction M! / (M!)!
>of the total possible listings of the M! permutations of the N bits.
>
>Why is this derivation wrong?
Well, it is only wrong if it isn't a step toward your goal. But I
don't see where you are going. It certainly is an upper limit!!!
There is some truth to it, but the implication I get is that once a
particular permutation occurs, it cannot re-occur until the RNG has
cycled, which is false. The sequence of permutations will of course
start to repeat after the RNG has cycled enough to produce the exact
same internal state at the start point of the shuffling process (which
may well take many, many full RNG cycles). But a single RNG cycle
length is, of course, far beyond what could be traversed in practice.
The problem appears to be based on a fundamental misunderstanding of
how RNG's produce output values. Presumably there is a generalization
from simple RNG's to strong ones. It either does not apply, or is
trying to compute something to which I assign little significance.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Tue, 23 Jan 2001 20:14:04 GMT
On Tue, 23 Jan 2001 12:27:59 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>On Tue, 23 Jan 2001 04:24:27 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
>in part:
>
>>I frankly have no idea what (A / B)! could possibly be intended to
>>represent. Perhaps the equation should have been (A/B)**S, where S is
>>the number of blocks, the length of a sequence of permutations.
>
>Well, since you criticized DES because it doesn't provide all (2^64)!
>possible mappings of 64-bit blocks to 64-bit blocks, whereas you claim
>that Dynamic Transposition is, in a sense, complete because it
>provides all n! transpositions of an n-bit block, I am trying to point
>out that you're comparing apples and oranges.
First of all, these two ciphers are so fundamentally different that no
analogy is likely to be very good.
The statement that conventional block ciphers do not implement more
than a tiny fraction of the natural keyspace of the (emulated) huge
substitution is correct. The consequences of this have been described
many times, in many ways, by many people. In essence, just a few
known-plaintext blocks should suffice to identify the actual key out
of all possible keys. The open literature does not show how to do
that, but obviously the possibility of such an attack is inherent in
the use of this conventional block cipher structure.
The idea that Dynamic Transposition does or should produce a
"permutation of permutations," such that no permutation can follow
itself, is just wrong. More to the point, it is not relevant. The
issue is how -- from the outside of the cipher -- anyone could know
what the sequence is, or even what any particular permutation was.
Even though there is a single correct permutation which took the
plaintext to ciphertext, many, many different permutations could have
done that same thing. Since a particular permutation cannot be
identified, probably the most accurate description would be to
accumulate a string of permutation-subsets. These will be huge,
however, so the uncertainty would seem to rise exponentially. And
then where does one go?
These are different types of ciphering.
>For both one transposition such as used in Dynamic Transposition, and
>two rounds of DES, we get:
>
>number of possible blocks < number of mappings provided by cipher <
>number of mappings of the set of blocks to itself
>
>For two rounds of DES, that is:
>
>2^64 < 2^96 < (2^64)!
>
>For arbitrary bit transposition applied to an n-bit balanced block, we
>get
>
>n!/((n/2)!(n/2)!) < n! < (n!/((n/2)!(n/2)!))!
>
>Now, you might react and say that I'm unfairly criticizing Dynamic
>Transposition because it is a _transposition_, but I think it should
>be clear that I am looking at this at the right level of description:
>the cipher is ultimately a mapping from the set of input blocks to the
>set of output blocks.
And that is n!
>And transposition of bits is one kind of
>restricted mapping between those two sets, just as XOR is another
>restricted mapping,
Those are fundamentally different: When we have an additive combiner
(e.g., XOR), and known-plaintext, the confusion value is identified
precisely.
When we have a Dynamic Transposition combiner, and known-plaintext,
the ciphering transposition is *not* identified precisely, but only as
a possibility in a huge set of "false" permutations.
>and substitution on small sub-blocks is a
>restricted mapping.
You mean, that if something is "a restricted mapping," it is, in some
sense, similar to anything else which is "a restricted mapping?" That
doesn't sound very meaningful to me.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Tue, 23 Jan 2001 11:46:07 -0800
Crossposted-To: or.politics,talk.politics.crypto,misc.survivalism
I should have jumped on this sooner, and noticed that Szopa was posting to
several groups for this. For those that are uninformed about the general
concensus about Szopa, please have a look at the newsgroup history
surrounding Szopa in sci.crypt (www.deja.com will be helpful). He is
generally considered very offensive.
However in this case I think he has brought up an important. I don't think
he will benefit from any suit he brings against Microsoft, if for no other
reason than they can afford to hire a legal team that physically crowds him
out of the court room, while he is I assume only monetarily capable of
affording one. Szopa I hope you were smart enough for your lawyer to take
this on speculation, and I hope your lawyer was smart enough to charge you
instead. If he wasn't I'd drop him, he's not smart enough to take on the M$
horde. Best of luck (I may dislike Szopa but if he has a legitimate reason
to believe M$ has performed their typical embrace and devour tactic I
support his cause).
Joe
"Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Richard Heathfield wrote:
> >
> > Anthony Stephen Szopa wrote:
> > >
> > <snip over 200 lines>
> > >
> > > So that's all I have to say for a while.
> >
> > Is that a promise?
>
>
> Here is a guy who spits on the souls of anyone for no damned reason.
>
> I told you that I am the inventor that will save people tens or
> hundreds of billions of dollars in lost revenue and you verbally
> shit on me with your sarcasm.
>
> Did you develope an anti-piracy computer software module that will
> prevent perhaps half at a minimum of the illegal copying of
> computer software in the world? Do you know how important a
> contribution this is?
>
> I can prove that I did this. And if I eventually do prove it
> publicly everyone will know you are a fool. But most importantly
> you will know. I think you probably already know you are a fool.
>
> I am certainly one of a very very few and perhaps the only person in
> the world who can prove that they did it before MS. I am not going
> to divulge my thought processes here or my plans or my actions
> regarding the implications of this situation at this time, as I have
> said. I am actively pursuing my interests.
>
> I think I read that there is about $50 billion dollars worth of
> computer software piracy going on every year.
>
> You must be a real high achiever to top this. Tell your friends
> what a proud soul you are and give them the example you posted here
> and explain to them why you are the one to be so sarcastic. What
> are your qualifications?
>
> I would tell them that you are a high risk gambler and that they
> should stay as far away from you as possible. You just can't
> believe that I did what I say I did, can you? You think you can
> make the jump and take the leap to ridicule me. You have no proof
> that I am lying. Yet you risk your reputation. As I said, you have
> poor judgment although you have calculated that you are on solid
> ground. Quicksand, yes. You are in quicksand and there will be no
> one to come to your aid. Just wait and see.
>
> If and when the proof comes out I hope someone brings it to you
> attention.
>
> I was waiting for a worm to show their slime. You finally showed up.
>
> What is a fool? A fool is a person who plays an Eric Clapton song
> on their own guitar. He plays the song perhaps even as good as Eric
> Clapton. And then he thinks he is as great an artist as Eric
> Clapton.
>
> You are an even greater fool than this because you would play the
> air guitar while listening to Eric Clapton and really believe you
> are as great a musician and artist as Eric Clapton.
>
> Can you feel your heart literally shrinking? You will.
>
> Thanks a lot.
>
> AS
>
>
> Gee, you didn't get any more significant information from me about
> my claim?
>
> Too bad.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Tue, 23 Jan 2001 20:19:18 GMT
On Tue, 23 Jan 2001 19:13:48 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>On Mon, 22 Jan 2001 13:05:04 GMT, [EMAIL PROTECTED]
>(John Savard) wrote, in part:
>
>>And with substitution, unlike Dynamic Transposition, instead of being
>>stuck with one set of n! substitutions, one can use steps of different
>>kinds so that instead of just having, say, all 2^n possible mappings
>>obtained by XORing an n-bit block with an n-bit key, one can explore
>>the space of (2^n)! permutations more deeply - depending on how much
>>key we use, and how complicated a structure we give the cipher.
>
>Well, one can supplement Dynamic Transposition to increase the
>exploration of the mapping space as well. In addition to transposing
>the bits of a balanced block, one could also subject them to
>substitutions that preserve the number of 1 bits: i.e., one could have
>an 8-bit wide S-box that mapped 00000000 to itself, that scrambled the
>8 combinations with a single 1 bit among themselves, that scrambled
>the 28 combinations with two 1 bits among themselves, and so on.
I think you should first plainly describe what you see as the
weakness, before rushing on to try to fix it.
No such operation is needed for strength in Dynamic Transposition.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "David C. Barber" <[EMAIL PROTECTED]>
Subject: Re: Some Enigma Questions
Date: Tue, 23 Jan 2001 13:37:53 -0700
"Jim Gillogly" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "David C. Barber" wrote:
> > Q1: A weakness of the German reflector rotor machines is always given
that
> > no input character could ever map back to itself. I.e. while A->R, you
> > could never have A->A. While it is easy to understand why this happens,
and
> > the advantage it can give in checking a suspected plain text against
> > encrypted text, why doesn't the plug board remove, or at least greatly
> > reduce this vulnerability e.g. A->R->plug board->A?
>
> The letter goes through the plug board both on the way in and on the
> way out. Since the reflector changes a letter into another letter,
> the out path must be different from the in path, resulting in a different
> letter before the plug board. Since each plug swaps two letters, they
> must still be different after the plug board is applied on each end.
The plug board would appear then to be another, fixed rotor -- but one that
could be rewired in the field.
This leads to the interesting question: Would the Enigma have been more
secure if the electrical path had been:
keyboard->r1->r2->r3->reflector->r3->r2->r1->plug board->indicator light
-or-
keyboard->plug board->r1->r2->r3->reflector->r3->r2->r1->indicator light
Of course this might have complicated the operation of the machine by
requiring either an Encode/Decode selector switch, or a more careful wiring
of the plug board connections. A trade-off against the no letter encoding
to itself vulnerability, or have I missed something here?
Of course, the Germans kept thinking the machine was unbreakable because
they couldn't break it themselves. Obviously not the best test of security,
as everyone who has submitted their first cipher as the latest "unbreakable"
code to this group usually finds out.
*David Barber*
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: using AES finalists in series?
Date: Tue, 23 Jan 2001 20:39:52 GMT
On Tue, 23 Jan 2001 19:27:06 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>[...]
>Chaining of AES candidates seems to be proposed as a
>way to feel better about the uncertainty of their actual strength
>against competent cryptanalysis, but if so that is misguided,
>since *that* concern has not yet been addressed for chaining.
I think that issue *has* been plainly addressed, and has been implicit
in most such discussions.
For one thing, a "chain" of ciphers is certainly stronger against
known-plaintext attacks which could function against an individual
cipher. Simply by preventing access to information which is otherwise
considered exposed (plaintext and the related ciphertext for one of
the internal ciphers), whole classes of attacks simply cannot be
mounted.
The other issue is what we do not know. Presumably, your argument is
that if we are willing to assume that a particular cipher can be
broken, we might as well assume that all ciphers can be broken, and
there can be no advantage. So if we can throw a baseball, we should
be able to throw a house. What is wrong with this reasoning?
If we are willing to accept that some ciphers may be weak (of course
we would not knowingly use a weak cipher), it is to our advantage to
use multiple ciphers -- I would say at least three -- including the
best we know of. If that cipher really *is* good, the data are
protected. But if there is some weakness in that cipher -- and if
that weakness can be exploited in the ciphering chain -- then the
other ciphers may act to protect our data in the face of weakness.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Cryptographic Windows APIs or OCX?
Date: Tue, 23 Jan 2001 12:32:03 -0800
My best advice would be to use OpenSSL (www.openssl.org) it is well written,
well documented, and it's free. I believe it supports everything you need.
Joe
"Armando P." <[EMAIL PROTECTED]> wrote in message
news:94k7se$tun$[EMAIL PROTECTED]...
> Hi folks
>
> Ok, I'll make it short and simple: I am a software developer and I
> need to implement SSL (SSLv3/TLS if that helps) into my applications to
> be able to access a specific portal that requires such authentification
> (through x.509 certificates). I am quite new to the field of
> cryptography, but have to learn it in a hurry due to a new mandatory
> governmental law that requires this from our customers (municipalities
> in Austria). I'm in dire need for a good (and well documented)
> Cryptographic API (or Ocx) that I can implement into my existing
> software. I have heard of MS Crypto API, but cant find it
> anywhere...Who can help? As always, I am very grateful for any and all
> advice. Thanks!!!!!
>
> Regards,
> Armando
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: collisions risks of applying MD5 or SHA1 to a 48-bit input
Date: Tue, 23 Jan 2001 12:29:08 -0800
"JL" <[EMAIL PROTECTED]> wrote in message
news:ku8b6.219092$[EMAIL PROTECTED]...
> value itself. Would MD5 or SHA1 be recommended given the input is so
short?
Of course they would be recommended, they are the prime candidates for
pretty much any hash requirement. I would however recommend using at least
an extra secret, like Paul Rubin said an extra 80-bits of random garbage
known only to the administrator would make the search much more difficult.
Now about the odds of collision. You've 2^48 free-range values, and I'm
assuming SHA-1 to be a random oracle (so there will be some minor error
factor, but it shouldn't be significant). The odds of a collision on 1 are
of course 0, because there is nothing to collide. Collision on 2 1/2^160
3 2/(2^160) + value at 2
n n/2^160 + value at n-1
at 2^48 this is 2^49/2^160, or 1/2^111. I'd bet a lot of money that you
won't get a collision. There is a complicating factor though, if an attacker
can generate a pair randomly for collision, you'll get something in the
neighborhood of 2^49/2^80, so the attacker would need 2^30 work to find a
full space collision. However if the input is artificially limited to
48-bits, the likelihood that a collision exists is extremely rare.
Joe
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
