Cryptography-Digest Digest #410, Volume #11 Fri, 24 Mar 00 08:13:01 EST
Contents:
Re: Hashing Algorithms. (basic newbie question) (Runu Knips)
Re: multiple encryption ([EMAIL PROTECTED])
Re: Hashes! (newbie question) (Mark Wooding)
Re: Prime numbers? (newbie alert -- again) ("Tom St Denis")
Re: Prime numbers? (newbie alert) ("Tom St Denis")
Re: what is a 2048 bit cipher? ("Tom St Denis")
Re: OAP-L3: Answer me these? ("Tom St Denis")
Re: Concerning UK publishes "impossible" decryption law (Geoff Dyer)
Re: Concerning UK publishes "impossible" decryption law ("ÐRëÐÐ")
Fastest DES implementation on Intel PIII ? (Pascal JUNOD)
multiple encryption (Vlad)
Re: implementing rot13 ("Peter L. Montgomery")
Re: Concerning UK publishes "impossible" decryption law ("ÐRëÐÐ")
----------------------------------------------------------------------------
Date: Fri, 24 Mar 2000 12:27:41 +0100
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Hashing Algorithms. (basic newbie question)
Yen-Choon Ching schrieb:
> BTW, are there any different with these terms:
> - one-way function
> - hash function
> - collision free hash function
No, a "hash function" is just a function which maps one
bitstream into another bitstream, where the input stream
is typically of any size and the output stream is
typically of a fixed size. Note that identity is also
a hash function, for example.
A "one way hash function" is a hash function which is
useable in cryptography.
* You cannot tell from the output what the input was,
i.e. you cannot construct an input which creates an
given output with anything better but brute force.
* You cannot construct a second input which creates
the same output like a given first input with anything
better but brute force.
* You cannot find two inputs which create the same
output with anything better but brute force.
Brute force means, for a fixed output of n bits, you
have to test (2^n/2) tests (on average) to find an
input for a given output, or a second input for a
given output, and you need (2^(n/2)/2) tests to find
a pair of inputs which result in the same output.
This means, if you use SHA-1 or RIPE MD160 (both 160
bit outputs), you have to check (2^160/2) for the
first two cases, and (2^80/2) for the third.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: multiple encryption
Date: Fri, 24 Mar 2000 11:18:18 GMT
In article <8bdf2g$rp$[EMAIL PROTECTED]>,
Vlad <[EMAIL PROTECTED]> wrote:
> Hello.
> If I encrypt my data using short keys (40, 56) more then one time,
> ( 1 file is encrypting 40 times with 56 bit key ) how it can increase
> the encryption level ?
Since you have to assume that the algorithm(s) are known to the attacker,
encrypting 40 times in the best case will require breaking the cipher 40
times instead of one. So if one can break your one time encryption in 1
day, he'll have to wait 40 days or buy a 40 times faster machine.
But wait! I guess this is far too optimistic. If you can break the first
encrypted cyphertext and are able to obtain the key, you will be able to
just decrypt the next 39 cyphertexts using your key or the key schedule
of your algorithm. So it's not much more secure than encrypting 1 time.
Still multiple encryption can make sense. For example, if you use
different algorithms, this can significantly improve security while it
does not necessarily make cryptanalysis harder. Seems like a strange
claim, but not if you assume that you do not trust each algorithm or
implementation in full. Even if one algorithm is weak, the other might
hold and vice versa.
A silly and oversimplified example would be that you assume that each
algorithm developed by cryptographers of one country has been weakened by
agencies of the respective country in a way that they can break it but
other agencies can not (very improbable, like I said, a silly
example...). If you use multiple encryption with algorithms developed in
different countries, no agency will be able to break your encryption even
though each has introduced their own weakness. Same applies for using
mutliple 3rd party encryption libraries, each of it you don't fully
trust.
Best regards,
Erich Steinmann
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Hashes! (newbie question)
Date: 24 Mar 2000 11:34:07 GMT
Jerry Coffin <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
>
> > Indeed. Both can provide at most 80-bits-worth of security against an
> > adversary attempting to find collisions.
>
> Yes and no. If you're using it in a situation where a birthday
> attack can be used at all, you're right. Hashes are often used in
> situations where a birthday attack simply won't work.
[snip uses of second preimage resistant hashes and why collision finding
isn't always useful in practice.]
I did specifically mention collision resistance. I think the excuses
you've been making (while fairly reasonable) show that we have come to
expect rather less from our hash functions than (say) our symmetric
ciphers. And I think that's a bit odd.
AES, for example, wants a block cipher, over 128-bit blocks, which
offers up to 256-bits-worth of security even against fairly impractical
things such as related-key attacks, whereas our favourite collision
resistant functions seem to offer only 80 bits of collision resistance.
Thinking a bit more clearly now, though, the situation isn't quite as
grim as I might have made it appear. I think what you should have said,
rather than making excuses about other uses of hashes, is something
like:
If an adversary wants to forge your signature on a document by fiddling
with the hash (for some nefarious reason), he has to find a collision
/now/, i.e., before you sign the collided hash. After you've signed,
he'd has to find a second preimage, which (as you point out) is much
harder. So we can safely stop using the hash when its collision
resistance starts to look insufficient, and old signatures will still
remain good for a while afterwards.
Block ciphers do have some similar properties, though. `Online'
attacks, such as chosen plaintext or related-key attacks, need to be
made against a system in active use. Once a cipher looks weak against
these sorts of things, we can replace it with something better, the main
risk being that it's possible an adversary captured an old ciphertext,
and is able to perform `offline' attacks against that forever. (Yes,
I'm aware that a lot of work needs to be done to change the cipher
protecting, say, archive material.)
So, yes, my gloomy picture from my last message was over-pessimistic.
However, I still think that security expectations for collision
resistant functions are disproportionately low, and I'd very much like
to see strong hashes with larger outputs, to bring them back in line.
No, I don't have any answers: I'm just standing on the sidelines
whinging, which I know isn't completely helpful. However, my
concern is genuine and, I believe, not completely ill-educated.
In a vaguely similar vein, has anyone any actual results against
RIPEMD-320 (i.e., the RIPEMD-160 variant which doesn't split recombine
the chaining variables between the two parallel streams of rounds)? I'm
aware that the authors don't suggest that this variant offers any
security advantages over RIPEMD-160 itself, and I'm not actually
intending to use it, but I'd be interested to know nonetheless.
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Prime numbers? (newbie alert -- again)
Date: Fri, 24 Mar 2000 11:56:04 GMT
proton <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Mainly what I was interested in was wether prime numbers vs. non-
> prime numbers provided any benefit in `PRNG's as you call it
> (didnt actually see that acronym until yesterday).
Depends on the PRNG you are using.
> I was wondering why `(de-1) mod (p-1)(q-1) = 0' created this
> numeric magic. The numbers involved were too big for me to
> see any relation right away (but it feels like Im starting to
> get a clue).
>
> Your terminology is unfortunatly pure greek to me.
'd' is the the inverse exponent of 'e'. Think of something like e = 5, d =
1/5. Now try
C = P^e
P = C^d
It's the exact same idea. Except now the inverse exponent is the modular
inverse of the encryption exponent [modulo the order of the group].
So you get
C = P^e
P = C^d
Which works because....
P = (P^e)^d
P = P^ed
P = P^1
P = P
> > Therefore the first thing you need to do is improve your math
> > skills. Start with any good book on elementary number theory.
>
> The last few years ive learned most by `consuming' a bit at a
> time. And its alot more fun than learning just theory and not
> having anything to apply it to. It also gives me a better
> understanding of the whole thing when I can directly point to
> a problem, say `I need to learn the maths to solve this' and
> then actually go out and find the answers.
>
> Most of yous probably disagree with this method since you have
> to put up with my silly questions when Im trying to learn about
> crypto. But atleast Im not forcing you to answer my questions.
Actually I am a HS student, and I learn a bit at a time. May I suggest you
get a program like maple or MuPAD to work out these types of problems?
>
> > How did you 'verify' that RSA is correct using bc?
> > The best one could do is verify some examples. But this is not
> > the same as verifying the math.
>
> I verified an example. I dont know enought number theory to start
> whacking away at verifying the theory itself. `bc' because my
> calculator only handles ~11 figures, which is probably only enough
> to verify p=5,q=7 or something to that effect.
>
> Im no good at theory, Im just trying to learn a bit of it so that
> I can use when Im programming. In some of my projects (both in-head
> and in-bits) there would be need for crypto or crypto would provide
> nice benefits. So I figured that I could assimilate bits and peices
> of information about small helpfull items here.
>
> Was I wrong?
Well please don't market your software until you know what you are doing.
And of course feel free to ask questions here, this is of course a
newsgroup.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Prime numbers? (newbie alert)
Date: Fri, 24 Mar 2000 11:57:43 GMT
proton <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > Jerry Coffin <[EMAIL PROTECTED]> wrote
> > > > I've also understood how the RSA algorithm works
> > > > as its explained in the crypto faq. But I still dont
> > > > understand *why* it works, and if prime numbers are
> > > > required for it to work...
> > >
> > > It's _possible_ to encrypt and decrypt correctly using a pair of
> > > composite numbers, but composites that will work this way are quite
> > > rare; primes are much more common.
> >
> > Actually if you know the factorization of the composite (p, q) [either
one]
> > then you can still calc phi(pq) and get rsa to work. For example if q
were
> > prime, and p = 2r, where r is prime, then the order of the group is just
> > (q - 1)(2 - 1)(r - 1)...
>
> One question that comes to mind: Can there be more than one public key
> (e) ?
Of course, as long as 'e' is relatively prime to the order of the group (p -
1)(q - 1) [if p/q are primes] you can always find an inverse exponent.
Normally however each user gets their own primes and exponent. Normally
aswell 'e' is fixed to something like 65537 or 17, since those are fast
exponents to encrypt with.
>
> > > > And to those who immediately thinks I should go buy
> > > > a book: I cant afford books at the the moment..
> > >
> > > You might want to look at the "Handbook of Applied Cryptography",
> > > which is available freely online. I'm sorry, but I don't have the
> > > URL handy right now; you should be able to find it fairly easily.
>
> > The URL is http://cacr.math.uwaterloo.ca/hac/
>
> Downloading it right now =)
It's a good thing to read.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: what is a 2048 bit cipher?
Date: Fri, 24 Mar 2000 11:58:50 GMT
Gareth Howell <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <7rBC4.65644$[EMAIL PROTECTED]>, "Tom St
Denis" <[EMAIL PROTECTED]> wrote:
>
> > So how do ciphers and algorithms fall? Cryptanalysis. Essentially not
> > abrute force search.
>
> Hi !
>
> More often than not its because someone left their password lying around,
or even because they chose a bad password.
>
> Who needs to search through 2048 bits , or whatever, if they only have a 5
character password ?
Good point. I was simply trying to relay some facts to the newbie-crypto
people about required keysize and the importance of scrutiny :)
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Answer me these?
Date: Fri, 24 Mar 2000 12:00:58 GMT
Right after quantum computers come out you can use a million bit key :)
Until then it's a waste of resources. Of course if you are using an AES
cipher why not just go with a 256-bit key. My main point was relating to
these million-bit ciphers people are making.
[foot in mouth situtation on] In my library CB I actually use the largest
possible key for all the symmetric ciphers it includes. For RC5 for example
I use 256 bit keys, 20 rounds, etc...[foot in mouth off]
Cheers,
Tom
Joseph Ashwood <[EMAIL PROTECTED]> wrote in message
news:e#aujAVl$GA.215@cpmsnbbsa02...
> I think we have to part company a bit on this. I am not
> comfortable saying that quantum computers won't become a
> reality in my lifetime. With a quantum computer 160-bit
> encryption becomes equivalent to an 80-bit cipher on a
> standard computer. I'm not comfortable trusting long term
> security to only 80 effective bits.
> Joe
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:_LBC4.65775$[EMAIL PROTECTED]...
> >
> > <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > How is it a waste of resources when it can be broken by
> someone? Are
> > > you saying that 160 is unbreakable?
> >
> > Searching 2^160 keys in any cipher is not feasible. You
> would have to find
> > a faster way to break the cipher.
> >
> > See my post on 'what is a 2048 bit cipher'.
> >
> > Tom
> >
> >
>
>
------------------------------
From: [EMAIL PROTECTED] (Geoff Dyer)
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,alt.security.scramdisk,alt.privacy
Subject: Re: Concerning UK publishes "impossible" decryption law
Date: Fri, 24 Mar 2000 12:13:49 GMT
On Wed, 22 Mar 2000 09:35:12 +1100, "ÐRëÐÐ" <[EMAIL PROTECTED]>
wrote:
>i would definately like to see this url
The stuff mentioned came from a paper "Secure Deletion of Data from
Magnetic and Solid-State Memory" by Peter Gutmann, of the Department
of Computer Science at the University of Auckland, in New Zealand.
<http://www.cs.auckland.ac.nz/~pgut001/pubs/secure_del.html>
The paper is included in the help file for Eraser, by Sami Tolvanen,
and may also be somewhere on the Eraser site. That is at
<http://www.tolvanen.com/eraser/>
--
Geoff
(to e-mail me, remove any instances of "-nospam" from my address)
------------------------------
Reply-To: "ÐRëÐÐ" <[EMAIL PROTECTED]>
From: "ÐRëÐÐ" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,alt.security.scramdisk,alt.privacy
Subject: Re: Concerning UK publishes "impossible" decryption law
Date: Fri, 24 Mar 2000 19:59:33 +1100
oh, i know there is no law in australia saying we cant use any kind of
encryption, we can have whatever we like, but most countries that have the
unbreakable encryption, (read 128 bit from america) cant export it to us. if
we can get it, we can use it.
------------------------------
Date: Fri, 24 Mar 2000 12:18:15 +0000
From: Pascal JUNOD <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Fastest DES implementation on Intel PIII ?
Hi, I'm seeking the fastest DES implementation on the Intel platform.
Any suggestion ?
A+
Pascal
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod, [EMAIL PROTECTED] *
* Laboratoire de Sécurité et de Cryptographie (LASEC) *
* ++ 41 (0) 21 693 7617, INR 313, EPFL, CH-1015 Lausanne *
* Route d'Yverdon 25, CH-1028 Préverenges, Switzerland *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
From: Vlad <[EMAIL PROTECTED]>
Subject: multiple encryption
Date: Fri, 24 Mar 2000 12:30:28 GMT
Hello.
Thanks for your replies on this subject. I am sorry that I've made
repeating postings - it was my mistake while I was working with Deja.
As I understood from recent discussions I should make analysis to
determine whether the generated keys form a group or not. Is there
any particular method (software library ) for that ? Is it possible
to determine the encryption strength of group of keys( does this
task has decision at all)?
Can anyone suggest references to materials for further reading on
this topic (especially in Internet).
Thanks.
Vladislav
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Subject: Re: implementing rot13
Date: Fri, 24 Mar 2000 12:34:17 GMT
In article <[EMAIL PROTECTED]>
Terje Mathisen <[EMAIL PROTECTED]> writes:
>[EMAIL PROTECTED] wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>> Dan Day wrote:
>> > >Why not instead:
>> > >for ( char *s=string; *s; s++)
>> > > *s += isalpha(*s) ? (toupper(*s)<('A'+13))*26-13 : 0;
>> > Cute.
>> > Okay, the gauntlet has been thrown -- who can do it in even
>> > fewer (non-whitespace) characters?
>> replace 'A'+13 with 'N'
>replace 'N' with 78
If we assume ASCII representation, we can avoid toupper,
testing for example
(*s & 31) < 14 ? 13 : -13
or
(*s + 2) & 16 ? -13 : 13
or
13 - ((*s + 2) & 16)*5/3
instead of (toupper(*s)>78)*26-13.
[Experts on C precedence rules may be able to eliminate some parentheses.]
--
E = m c^2. Einstein = Man of the Century. Why the squaring?
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
Reply-To: "ÐRëÐÐ" <[EMAIL PROTECTED]>
From: "ÐRëÐÐ" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.pgp.discuss,alt.security.scramdisk,alt.privacy
Subject: Re: Concerning UK publishes "impossible" decryption law
Date: Fri, 24 Mar 2000 23:55:18 +1100
cool thanks, i will look into it!
--
"Oh GOD, Please save me from your followers"
more of my ramblings can be found at http://oakgrove.mainpage.net
"Man is a part of nature, not apart from nature"
anti spam, remove 'nospam' to mail me
ICQ:16544782
"Geoff Dyer" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Wed, 22 Mar 2000 09:35:12 +1100, "ÐRëÐÐ" <[EMAIL PROTECTED]>
> wrote:
>
> >i would definately like to see this url
>
> The stuff mentioned came from a paper "Secure Deletion of Data from
> Magnetic and Solid-State Memory" by Peter Gutmann, of the Department
> of Computer Science at the University of Auckland, in New Zealand.
>
> <http://www.cs.auckland.ac.nz/~pgut001/pubs/secure_del.html>
>
> The paper is included in the help file for Eraser, by Sami Tolvanen,
> and may also be somewhere on the Eraser site. That is at
> <http://www.tolvanen.com/eraser/>
>
> --
> Geoff
> (to e-mail me, remove any instances of "-nospam" from my address)
------------------------------
** 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
******************************
