Cryptography-Digest Digest #291, Volume #9 Sat, 27 Mar 99 08:13:03 EST
Contents:
Re: GOOD PRIME GENERATOR (GPG) (Ray Girvan)
Re: Message Digest ("karl malbrain")
Re: Is TEA Algorithm safe???? (Mark Carroll)
Re: Newbie, what a stupid term... ([EMAIL PROTECTED])
Re: paper (Sandy Harris)
Re: a little math please (David Brownridge)
Re: Live from the Second AES Conference ("Brian Gladman")
Re: compare RSA and D-Hellman (Doug Stell)
Re: a little math please (Peter L. Montgomery)
Re: RNG quality in browsers? ("Sassa")
Re: Crytpo Gurus - Please comment on this sceneario ("Sassa")
TEA and RC6 hybrid algorithm ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Ray Girvan <[EMAIL PROTECTED]>
Subject: Re: GOOD PRIME GENERATOR (GPG)
Date: Sat, 27 Mar 1999 01:59:11 +0100
Mike L. Griebel <[EMAIL PROTECTED]> writes:
> I have not found any better way to find such primes than by
> my algorithm. Maybe you know of one? I would be very interested.
I would check the literature; there's stuff on the Web too. For
instance, the field of finding consecutive primes in arithmetic
progression is quite lively; there's some very sharp pre-analysis
that gives upper and lower bounds. See Paul Zimmermann's "Ten
Consecutive Primes in Arithmetic Progression" (mathPAD, 8/1, March
1998) which has a number of references including RK Guy's "Unsolved
problems in number theory", 2nd edition, Springer-Verlag, 1994. But
this is getting into sci.math territory...
Ray
--
[EMAIL PROTECTED] +++ Technical Author +++ Topsham, Devon, UK
http://www.users.zetnet.co.uk/rgirvan/ +++ The Apothecary's Drawer
------------------------------
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Message Digest
Date: Fri, 26 Mar 1999 16:08:16 -0800
wtshaw <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <fYvK2.248$[EMAIL PROTECTED]>, "karl malbrain"
> <[EMAIL PROTECTED]> wrote:
> >
> > So, practically, the answer to your question is EXPECT a value of 1
digested
> > value for 1 message. Karl M
>
> If a fixed length Message Digest is considered too brief, consider that
> any strong algorithm can produce a respectable signature simply by
> processing with a specified key on plaintext, or ciphertext, provided that
> the encryption key for the ciphertext was different.
I'm sorry that you've chosen to <<snip>> the pertenent section of my
reply -- hence the redundancy (factored from the VULGAR)
No, the 128 bit length of the Message Digest is MORE than enough length to
GIVE each message ever created by a person its own (expected to be unique)
MD value. Let's see, 2^32 ~ number of persons alive, that leaves ~
2^(128-32) messages each!!! Gee, that's more than the number of nucleons in
the known universe!
(... sections snipped under the rubrick that I'm still ~45 quarter units shy
of my BSEE from CAL...)
> Ethnic clensing does not appear to be a response to a high moral calling.
My, how this was never an issue under the PROTECTIVE CUSTODY of the
CONSTITUTED RED army!! Karl M
------------------------------
From: [EMAIL PROTECTED] (Mark Carroll)
Subject: Re: Is TEA Algorithm safe????
Date: 23 Mar 1999 11:02:21 +0000 (GMT)
In article <7d62uk$1kb$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
>
>> Or, am I hopelessly mistaken and you gain no extra security at all no
>> matter how you chain blocks together? If so, expect many followups to
>> correct me. (-: I'm just thinking out loud here...
>
>If you chain (CBC or PCBC) you increase the difficulting of analyzing the data
>without the key. If you simply use ECB similar blocks can be analysed.
Right - thanks.
>BTW, I thought the weakness (according to the paper) involves 2 related keys
>and 2^32 plaintexts?
You're probably right: ISTR an attack of this sort; this is one of the
attacks that didn't really worry me for most applications. (Thought there
was another attack since, but I may be mistaken and it sure wasn't much
more frightening.)
>BTWx2, are there any 16-bit versions of TEA? Using 16-bit registers?
I've not heard of any, but it's certainly a very interesting question
- TEA may not be terribly hard to adapt to different block sizes.
-- Mark
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Newbie, what a stupid term...
Date: Sun, 21 Mar 1999 12:24:48 GMT
> I would like to know the best place to start to learn
> cryptography. To learn the the vocab and the math skills. Also
> where to learn the concept of Unix password encryption. I do not
> understand if there are random characters introduced, how does it
> come out the same when the server compares the resulting hash? I
> know two of the same passwords will not look the same. Well a
> simple as possible answer would be nice. Please use sinple
> terms too.
Get the sci.crypt faq, you can learn alot of starting material from it (I
did), then pick up some papers on encryption, try Dr. Rivests papers first,
they are easy to understand. If you want try implementing the algorithms in
a programming language.
If you are really keen, try to get Applied Cryptography (I am trying to get
it for my b-day). From what I hear (and if you look at the TOC) it covers
all the rudimentary algorithms, and basic maths.
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Sandy Harris)
Subject: Re: paper
Date: Sat, 27 Mar 1999 05:58:52 GMT
Marcin Kontak <[EMAIL PROTECTED]> writes:
>Could anybody help me ?
>Where can I get papers:
>
> * K. Nyberg - "Perfect Nonlinear S-boxes"
> * O. S. Rothaus - "On 'Bent' Functions"
> * S. Mister - "Notes on Maiorana Functions and S-Box Design"
None of the ones you mention, but several S-box related papers are
on the SAC conference site:
http://adonis.ee.queensu.ca:8000/sac
95 or 96 has one by Mister & Adams which discusses Maiorana functions.
------------------------------
From: David Brownridge <[EMAIL PROTECTED]>
Subject: Re: a little math please
Date: Sat, 27 Mar 1999 17:53:24 +1100
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote
(<news:[EMAIL PROTECTED]> in <news:sci.crypt>):
> What I would like to know, given a grid of 16x16, filled with an even number
> of 0 and 1 bits, how many combinations are there?
>
> Not 2^256, because remember that they have to be even.
C(256,128) = 256!/(128!)^2
You get to choose 128 of the 256 cells to have value 1. The rest must
be 0.
--
rgds
DVD
(David Brownridge) <mailto:[EMAIL PROTECTED]>
[posted & mailed]
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Live from the Second AES Conference
Date: Wed, 24 Mar 1999 09:15:22 -0000
<[EMAIL PROTECTED]> wrote in message
news:7d6q7j$mvs$[EMAIL PROTECTED]...
>
>
> Here is my report on the first day of the AES2 in Rome. Lots of
> participants, 180+ people from (according to NIST) 23 countries.
> About half the speakers today were not native English speakers, so
> this is indeed an international process. 28 papers were submitted
> (all are at NIST's site: aes.nist.gov) and 21 will be presented
> here.
Many thanks for a helpful and informative summary of the AES2 conference. As
a contributor who could not attend I much appreciate this feedback.
[snip]
> Then came Bruce Schneier's presentation about speed. Again Bruce's
> exposition was interesting and clear. He made a good point that
> only assembly code speeds should be compared because otherwise you
> measure a particular compiler's efficiency rather than the
> cipher's. This is true...
No its not! A number of factors are involved in ***all*** comparisons:
1. algorithm efficiency
2. the efficiency of the tools used to convert the code into machine format
3. the quality of the implementation.
and others as well. It is quite wrong to suggest that comparisons in high
level languages test only item 2 and, if Bruce really did say this, then he
clearly does not understand the issues involved. It is true that assembler
comparisons will reduce the uncertainties caused by item 2 but they often do
so at the expense of introducing far worse uncertainties as a result of item
3. In Bruce's own assembler comparisons, for example, the 'quality'
(non-existence!) of assembler implementations of some AES candidates
produced results in earlier versions of his report that were quite wrong. I
personally spent quite a bit of time communicating with Bruce and his team
seeking corrections of quite large magnitude in some of his comparisons.
In practice it is important to compare AES candidate performance in
assembler and in higher level languages. Other things being equal, an
algorithm that can be coded efficiently in both assembler and high level
languages is better than one that is inefficient unless it is coded in
assembler. If an algorithm is efficient in high level languages we can have
both efficiency AND portability and these are both valuable properties.
Fortunately there are several AES candidates that meet this requirement.
[snip]
> Bruce Schneier made a case against the idea of choosing not one
> but several "approved" AES algorithms.
It is worth reading Don Johnson's paper here. I too have suggested that it
would be wrong to select a single AES algorithm (in comments to the NIST AES
forum). It is simply not good security practice to 'put all our eggs in one
basket' in this way.
But I do not support choosing algorithms for good performance in different
domains. If we choose a good 'smartcard algorithm', a good 'PC algorithm',
.... we will not get the algorithm redundancy that we need in each domain.
Hence if we do go for (say) three AES winners, it will be important to
select algorithms that are all good across a broad range of application
domains, not the best algorithms in each individual application domain. So
we do need to take Don's ideas on board and consider carefully whether we
want to take the risks involved in selecting a single winner.
> One wonders what is so wrong in declaring several good algorithms
> for specialized environments. Actually, after today's presentation
> about attacks against smart cards, somebody mentioned that a smart
> card is a sufficiently different environment to justify a specialized
cipher.
While I support the selection of more than one AES winner, I don't like the
idea of selection on the basis of the best performers in each application
domain since this will undermine the very algorithm redundancy that we are
seeking.
> So who will make it to the second round? No idea.
We need much more on security rather than performance here. And we don't
yet understand implementation assurance differences between the AES
candidates. Here, we are only just starting to see (with smartcards) some
of the many issues involved and we have very little information for other
processor families in this respect. In AES time scales it will be attacks on
implementation weaknesses that will almost certainly offer the easiest 'way
in' and we are really only just starting to look at these issues.
Brian Gladman
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: compare RSA and D-Hellman
Date: Wed, 24 Mar 1999 15:08:34 GMT
>i wonder, if there was ever found any weakness in Diffie-Hellman's algorithm
>(yes, that old-old algorithm :).
It is still believed that the conjecture that D-H is a difficult to
break as it is to do a discrete log is true. Therefore, the algorithm
has no known weaknesses, but it is possible to pick a weak prime
modulus.
>i know it as SKIP algorithm, but i am not sure if it is a common name for
>it. ( you know, shared_secret = a^(p*q) mod n )
SKIP is one of many protocols that use the D-H key agreement protocol.
SKIP's use, however, is extremely limited.
>>i suppose, there was found some weakness, or why should they have to develop
>>RSA?
There are hundreds of public key algorithms, if you count all the
varients. So, you could ask the same about any of them.
D-H is a key agreement algorithm and the basis of a lot of other
algorithms. It did not provide a reversible encryption or signature
capability. That's what prompted the development of RSA and ElGamal.
RSA and D-H simply serve very different purposes.
>>i did not use any software, endrypting with RSA, so i'd like to know, how
>>fast it enciphers.
In general, the time required is roughlyt proportional to the number
of bits in the exponent plus the number of those bits that are 1's.
Since most implementations use a small public exponent, the public
operation is very fast, while the private operation is slow.
D-H uses the same math function, modular exponentiation. However, the
first half of the calculation is often done with a small base, which
makes that calculation a little faster.
>The only weakness in public key systems are imposters. For example in DH,
>person A wants to talk to person B, but must go thru person C. Person C could
>pretend to be the other person.. i.e
>
>ideal:
>A --> C --> B
>A <-- C <-- B
>
>man-in middle attack: When A tries to send to B, C pretends he is B. But
>still relays the info to B. When C sends to B he pretends he is A. etc...
>
>You can do the same with RSA.
This is addressed by the use of certificates or any other means by
which you know for sure who's public key you are using. You simply
need to use an authenticated public key.
BTW, this is not the only known weakness systems can have. You can do
lots of things wrong or fail to so some things right and have a
weakness. If you do the right things and avoid the wrong things,
public key schemes are very secure.
------------------------------
From: [EMAIL PROTECTED] (Peter L. Montgomery)
Subject: Re: a little math please
Date: Sat, 27 Mar 1999 08:43:10 GMT
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>[EMAIL PROTECTED] wrote
>(<news:[EMAIL PROTECTED]> in <news:sci.crypt>):
>> What I would like to know, given a grid of 16x16, filled with an even number
>> of 0 and 1 bits, how many combinations are there?
>C(256,128) = 256!/(128!)^2
>You get to choose 128 of the 256 cells to have value 1. The rest must
>be 0.
The question's wording is ambiguous. If `an even number of' means
`equally many', then C(256, 128) is correct. If `an even number of' means
`counts divisible by 2', then 2^255, as posted by others, is correct.
--
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: "Sassa" <[EMAIL PROTECTED]>
Crossposted-To: comp.infosystems.www.browsers.misc
Subject: Re: RNG quality in browsers?
Date: Sat, 27 Mar 1999 13:36:19 +0200
Reply-To: [EMAIL PROTECTED]
hi
26-Mar-99 07:46 you wrote:
> Sassa wrote:
>> well... if one RNG alone, then indeed, you need 4 bytes to determine initial
>> random seed. but what if you choose one of, say, 4 32-bit RNGs using fifth
>> 32-bit RNG? i suppose, it will become (32/2)*4 byte sequence?
> I am not sure I understand what you mean. It does not matter if many
> algorithms are used, if you use 4 algorithms each with a 8-bit seed, the
> total amount of initial randomness is 32 bits. A pseudo-RNG cannot add
> any randomness to the seed.
every step you need a random number. if you use one 32-bit RNG, then 4 bytes
of random sequence define initial random seed.
now, if you use 5 RNGs (say, save current state of the RNG, and load the
state for the other RNG: i have 5*4=20 bytes random seed; so first 4 bytes
is the state for RNG0, following 4 bytes is the state for RNG1....), every
random number can be evaluated this way: pick pseudo-random value from RNG0,
and according to it you choose one of four RNGs, which results random
number.
now if you have a sequence of random bytes, you will need more, than 4 bytes
to determine each and every of 4 initial random seeds for RNGs, for you can
not tell which of 4 RNGs generated a certain byte:
you've got a random sequence `abcdef'.
say, `a' was generated with RNG1.
was `b' generated by RNG1? or by RNG2? or by RNG3? or... ?
then was `c' generated by RNG1 or RNG2 or RNG3 or...?
so you cannot tell whether RNG1 generated `abcd' or `acde' or `adef' or...
thus you'll need a longer sequence, than 4 bytes. and at least 16 bytes.
initial value for 32-bit RNG0 can be determined by 32/2=16 2-bit numbers
(2-bit number picks one of 4 RNGs).
say, RNG0 can produce such a sequence, that you may have 15 times 0, and
only on 16 time you have 1. so you'll have 15 bytes belonging to RNG1 and 1
byte to RNG2 and not a byte determining RNG3 and RNG4. so in the worst case
you'll need even more, than (32/2)*4 bytes to determine all 4 RNGs.
note, that you'll also need 2^32 tries to determine RNG0 initial value.
in some cases you'll need a shorter sequence, but still you'll need to spend
some time to determine RNG0.
> For browsers, we can assume that the RNG algorithm itself is not secret.
> If a 32-bit seed is used, it is easy enough for an attacker to generate
> a dictionary of all the 128-bit keys that the browser can create, by
> going through all the 2^32 seeds.
if browser uses the only RNG, then yes.
but if it uses a "battery" of RNGs - then hardly yes...
> Mika Niemi
--
Sassa
Apiary Inc.
______
@()(_)
/\\
[EMAIL PROTECTED]
------------------------------
From: "Sassa" <[EMAIL PROTECTED]>
Subject: Re: Crytpo Gurus - Please comment on this sceneario
Date: Sat, 27 Mar 1999 12:40:44 +0200
Reply-To: [EMAIL PROTECTED]
hi
>> coefficients. after ~20 steps it guessed humans answer at... mmm.... 60 or
>> 70 percent? probability (i do not remember, it was a little article on
>> reocgnition). but i am afraid to give you false information.
>> anyway, human's answers were _pretty_ predictable.
> I would say 60-70% are pretty unpredictable. It is more on the
> random guessing side (50%) than on the prediction side.
it was a talk, that human, _knowing_ that he _should_ give _random_ numbers,
actually gives numbers that are not quite random. i cannot remember at what
a probability computer guessed human's randoms ok, but it was significantly
over 50%.
a man just sets his conscioussness to give randoms, so he thinks 'aha, i
gave 0 last time. let's give 1 this time. oh, no, computer will easily
_guess_ this number. i'll give 0 this time to fraud it :)'. and the
algorithm with which human decides to give numbers is pseudo random.
if one throwed a coin and input 0 or 1 according to it, the computer failed
to give answers with probability significantly different of 50%.
anyway, 60-70% is better, than 50% :)
> Mahlzeit
--
Sassa
Apiary Inc.
______
@()(_)
/\\
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: TEA and RC6 hybrid algorithm
Date: Sat, 27 Mar 1999 11:25:39 GMT
Hi, first off let me say "Yes I am not an expert". However I am using what I
have learned.
I looked at RC6 and TEA and tried to combine them. My algorithm features ease
of use, with strength. Basically I use data dependant rotations (rc6) with
non-linear algebra (tea).
My algorithm enciphers a 128-bit block with a 128-bit key. All of the bits
in my key are active (unlike TEA which has the top bits as weak). I have
found after 8 rounds that the diffusion is almost 100%, meaning with one
wrong bit in the key, almost all of the output is wrong (well pretty much all
of it).
I would really like to analyse this one. I think because I used well known
techniques that it shouldn't be to hard. If someone could help (???) point me
in the right direction?
The code is at
http://members.tripod.com/~tomstdenis/tc1.c
Which includes a lengthly comment (includes pseudo-code).
Thanks,
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
