Cryptography-Digest Digest #3, Volume #12 Sun, 11 Jun 00 09:13:00 EDT
Contents:
Re: randomness tests (Guy Macon)
Re: encoding of passwords ([EMAIL PROTECTED])
Logical attack on RSA ("Michael Brown")
matrix question (Benjamin Goldberg)
Re: Improving DES based MAC ("Tor Rustad")
Re: randomness tests (tomstd)
Re: question of generating random challenges in Java (Tim Tyler)
Re: Extending the size of polyalphabetic substitution tables (Simon Johnson)
Re: Large S-Boxes (Tim Tyler)
Re: Large S-Boxes (Tim Tyler)
Re: Large S-Boxes (Tim Tyler)
Re: Large S-Boxes (tomstd)
Re: randomness tests (Tim Tyler)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: randomness tests
Date: 11 Jun 2000 04:14:45 EDT
tomstd wrote:
>
>Guy Macon wrote:
>>
>>There are people who make software PRNGs and other people who
>>make hardware RNGs which are for sale. Those people don't know
>>what it's for. What would you advise them to do about testing?
>>
>>In particular, the people who make hardware RNGs are shooting
>>for true randomness, and may have acheved this goal. For them
>failing ANY randomness test is unacceptable, so all such tests
>are useful.
>
>For any prng I can devise *at least* one test it would fail.
>(obvious give it the same seed). For example if your prng fails
>the DNA test it may still be perfectly fine for your purposes...
Yet still, someone who sells a PRNG on the open market has no idea
of what the final user's purposes are, and clearly certain PRNGs
are inferior to certain others using just about any randomness test.
You haven't answered my question; what is your advice to the seller
of such a PRNG concerning testing? What is your advice to the seller
of a hardware based RNG concerning testing? Please be specific.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: encoding of passwords
Date: Sun, 11 Jun 2000 08:56:09 GMT
Wouter <[EMAIL PROTECTED]> wrote:
> Thanks for the reaction. It's good to know that not all distributions uses
> the same algorithm. But I know that my system uses DES encryption and I want
> to write a program which does the same (encrypting passwords).
If all you want to do is compute the same hash, use crypt(3). Remember
to link with -lcrypt if you're using the GNU library though. If you
need a faster version, I suggest the one in libdes. It's the fastest
non-assembler version I've seen.
You should bear in mind though, the crypt(3) algorithm is a bit dated,
and has some drawbacks, such as limiting the length of a password to
eight characters. If you need more security than it provides, you
might want to look into another password hashing algorithm.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Logical attack on RSA
Date: Sun, 11 Jun 2000 10:32:41 GMT
Hi there,
I had some spare time recently, and I decided to play around with RSA a
bit, with regard to implementing it in hardware. What I found is that you
can apparantly ram the public key backwards through a multiplier and out
pops the two primes used to generate it. ie:
This set of logical statements multiplies two 2-bit numbers, a and b.
a is made up of a1 and a2, such as if a = 2 then a1=0, a2=1
b is the same, with b1 and b2 making it up
instructions:
c1 = a1 AND b1
c2 = a1 AND b2
c3 = a2 AND b1
c4 = a2 AND b2
d1 = c2 XOR c3
d2 = c2 AND c3
e1 = d2 XOR c4
e2 = d2 AND c4
The resulting number, a * b, is x.
x is broken up into x1, x2, x3, x4 in the same way as a and b
x1 = c1
x2 = d1
x3 = e1
x4 = e2
You can verify these statements if you wish, but trust me, they work.
For example:
a = 2 -> a1 = 0, a2 = 1
b = 3 -> b1 = 1, b2 = 1
c1 = 0 AND 1 = 0
c2 = 0 AND 1 = 0
c3 = 1 AND 1 = 1
c4 = 1 AND 1 = 1
d1 = 0 XOR 1 = 1
d2 = 0 AND 1 = 0
e1 = 0 XOR 1 = 1
e2 = 0 AND 1 = 0
x1 = c1 = 0
x2 = d1 = 1
x3 = e1 = 1
x4 = e2 = 0
x = 0110 = 6 which is 3 * 2
Now, this is the interesting part. This method can also be done in reverse:
c1 = x1 = 0
d1 = x2 = 1
e1 = x3 = 1
e2 = x4 = 0
We know : d2 XOR c4 = 1
Therefore, d2 or c4 must be 1, but not both. ie : d2 = NOT c4
We know : c2 XOR c3 = 1
Therefore, c2 or c3 must be 1, but not both. ie : c2 = NOT c3 (1)
We know d2 = c2 AND c3
= c2 AND (NOT c2)
= 0
Therefore, since d2 = NOT c4, c4 = 1
This means a2 AND b2 = 1, so a2 = b2 = 1
We know : c2 = a1 AND b2, c3 = a2 AND b1
so c2 = a1, c3 = b1, and from (1) we can see a1 = not b1
Substituting in a1 = 1 gives
a1 = 1, a2 = 1, a = 3
b1 = 0, b2 = 1, b = 2
If we had substituted in a1 = 0 then
a1 = 0, a2 = 1, a = 2
b1 = 1, b2 = 1, b = 3
Both of these give the desired result, 6, when multiplied.
Unless I am doing some kind of wierd trial and error here, it seems that I
have factored a number algabraically. Not that there is much point. I've
used far more paper than I would through trial and error :)
I have done this method for a product of 9 (3*3) and it also seems to work.
I am currently working on expanding this method to handle two 3 bit numbers
multiplied together and should have this posted sometime, along with an
example if it works. I'm not going to have a lot of time in the next week
(university exams along with a high school assignment - don't ask, it's
very convuluted) so you can probably do it quicker. E-mail me for a basic
outline. I need to get to bed :)
Regards,
Michael Brown
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: matrix question
Date: Sun, 11 Jun 2000 11:14:18 GMT
I'm trying to test some matrix math things I've written, and I'm
getting results I don't expect... I don't know if it's my code that's
wrong, or what I'm expecting that's wrong.
If I have 4 matrices A, B, C, Ma, Mb, each of which is 4x4, and
Ma is the inverse of Mb, then when I do B = A * Ma, C = B * Mb,
I find C == A, which is what I expect to get.
However, if A, B, C are 1x4 matrices (Ma and Mb the same 4x4 matrices as
before), and I do B = A * Ma, C = B * Mb, I find that C does not equal
A. This seems Wrong. Are my expectations (that A should equal C even
for non-square A,B,C) wrong, or is my code wrong?
------------------------------
From: "Tor Rustad" <[EMAIL PROTECTED]>
Subject: Re: Improving DES based MAC
Date: Sun, 11 Jun 2000 13:29:02 +0200
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > The point is that in hardware devices, NVRAM space can be very
restricted,
> > going from single DES to 2K3DES, double the space requirements already.
If
> > can't hold the key table inside NVRAM, then I need to export/import DES
> > key to external storage, that means extra DES encryption/decryption,
> > which will hurt performance badly...
> Key table? If you are in hardware, then you can do key expansion on the
> fly -- DES was, after all, designed to be implemented easily in hardware.
> And so, we are talking about the relative costs of storing 112 vs. 168
bits.
> (If, by key table, you meant the actual key, my apologies...)
>
> And, if you have 'external storage' available, why are we talking about
> NVRAM? Why do you need RAM that retains it's contents on power-loss if a
> copy of the key is available in "external storage"?
You are giving me a hard time here, the essential point is not NVRAM, but
that you have a Tamper Resistent Security Module (TRSM), which have
internally secure memory locations, where the DES keys are stored in clear
text. Outside these secure memory locations, DES keys are typically
encrypted with a 3DES master key.
Even if DES is implemented in hardware, it takes time to compute extra DES
rounds.
A key table is a place inside the TRSM where cleartext keys can be stored,
this space may be restricted to 800 bytes...
Let say we have a host which uses 100 TRSM, where each TRSM cost $10.000,
hence a total cost of $1.000.000. In such a case, a performance loss will
cost significant amount of money.
> > I did not see the above, nice! So you are stating that the strenght of
> >
> > C = k XOR (DESk( k XOR P ))
> >
> > is 2^64?
> To be precise: at most 2^64. I am not claiming that this is the best
> possible attack...
>
What type of improvement can be used?
> > Is that also the case if one of the XOR operations are removed?
> No. If you remove one of the XORs, it drops to 2^56, as follows (assuming
> the first xor is dropped, the second xor is similar):
>
> C1 = k2 XOR (DESk( P1 ))
> C2 = k2 XOR (DESk( P2 ))
>
> C1 XOR C2 = DESk( P1 ) XOR DESk( P2 )
>
> Iterate through the possible values of k -- there are only 2^56 of them.
I
> will be bold enough to claim that this within a constant factor of the
best
> possible attack, given that DES is treated as a keyed random permuation.
I can't see that dropping the second XOR is similar...
C = DESk( P XOR k1 )
where k is 56 bit, but k1 is 64 bit. I feel really stupid now.... please
tell me.
--
Tor
------------------------------
Subject: Re: randomness tests
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 11 Jun 2000 04:57:15 -0700
In article <8hvhpl$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Guy Macon) wrote:
>
>tomstd wrote:
>>
>>Guy Macon wrote:
>>>
>>>There are people who make software PRNGs and other people who
>>>make hardware RNGs which are for sale. Those people don't
know
>>>what it's for. What would you advise them to do about
testing?
>>>
>>>In particular, the people who make hardware RNGs are shooting
>>>for true randomness, and may have acheved this goal. For them
>>failing ANY randomness test is unacceptable, so all such tests
>>are useful.
>>
>>For any prng I can devise *at least* one test it would fail.
>>(obvious give it the same seed). For example if your prng
fails
>>the DNA test it may still be perfectly fine for your
purposes...
>
>Yet still, someone who sells a PRNG on the open market has no
idea
>of what the final user's purposes are, and clearly certain PRNGs
>are inferior to certain others using just about any randomness
test.
>You haven't answered my question; what is your advice to the
seller
>of such a PRNG concerning testing? What is your advice to the
seller
>of a hardware based RNG concerning testing? Please be
specific.
>
That just it "Please be specific". If I told you my block
cipher pased the DNA randomness test you would say "oh so what
there is a million other things to look at". This is true, a
block cipher has to be secure against other statistical attacks.
So why wouldn't this be true for a prng? Just because your prng
passes DIEHARD doesn't mean it's at all random. It's been shown
time and time again that you can devise means to fool the
statistical might and still not be random.
I would suggest to the developers of prng devices to state
exactly what their tests were and to say what the implications
are.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: question of generating random challenges in Java
Reply-To: [EMAIL PROTECTED]
Date: Sun, 11 Jun 2000 12:13:25 GMT
Jean-Luc <[EMAIL PROTECTED]> wrote:
: For a challenge-response authentication scheme, I need a 16-byte random
: challenge. Below are the details , my question to the group is about the
: scheme's security weaknesses.
: The challenge will be generated in a Java component so the first options in
: mind were the Random and SecureRandom classes. However, the SecureRandom
: appears to be too slow and some threading problems in the Microsoft JVM do
: not recommend it for a multiuser scenario.
*Seeding* secure random can be slow - but it's normally a SHA-1 hash
driven by a counter - which is not *that* slow.
AFAIK, any threading issues would only ever be likely to be connected to
the seeding process - not the class itself.
: According to the JDK documentation, "the Random class uses a 48-bit seed,
: which is modified using a linear congruential formula. (See Donald Knuth,
: <i>The Art of Computer Programming, Volume 2</i>, Section 3.2.1.)". The seed
: would be the current time of the day. I don't have the book so don't know
: how good the randomness is and what's the sequence's length.
2^48 - 1 IIRC.
The randomness sucks. See my "Sun redefines randomness" Java applet at
http://alife.co.uk/nonrandom/ for a visual display of the problem.
This was a bug in the bug parade for a while. Alas, Sun's "fix" was
backwards compatible with their initial version - which is barely suitable
for many simulation applications, which ought to be its intended use.
: My question is whether the strength would be improved or not by generating
: the challenge as an MD5 hash of the Random() number appended to a timestamp.
Hashing the output usually helps with randomness at the expense of speed.
Hashing a LCG is not very much different from hashing a counter, assuming
the hash has no significant flaws.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ This tagline no verb.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Extending the size of polyalphabetic substitution tables
Date: Sun, 11 Jun 2000 12:38:09 GMT
Back to your original question. I've been thinking about your
suggestion; Do you suggest a multidimensional array?
e.g.
(output from s-box)=s(x,y)
It will automatically produces collisions. There will be a minimum of 2
different values for x & y that generate the same output.
Following from this fact, it makes sense that the 2-dimensional array
can be expressed in terms of a 1-dimensional array. If x, y and the
output are of the same size, which i will call m, then the s-box would
be a 2m*m s-box.
Acording to Applied Cryptography V2 (AC2), there is definitly a linear
relationship if, for an m*n s-box, n>=2^m-m. For this construction, we
are a long way above this point.
e.g. If we have an 8*8*8 s-box that can be expressed like 16*8 s-box
then we inequality looks like 8/>= 65520. For this reason i am
confident that such a construction is almost certainly secure against
linear cryptanalysis.
Against differential cryptanalise, i have no real clue, i have a gut
feeling it isn't great. Apon reading p349 of AC2, it said:
"increasing the size of n reduces the effect of differential
cryptanalysis, but greatly increases the effect of linear cryptanalysis"
I would therefore reason that the inverse is also true, increasing the
size of M increases the effect of differential cryptanalysis, but
reduces (as i have just proven) the effect of linear cryptanalysis.
I hope i have answered your question.
Simon Johnson
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Reply-To: [EMAIL PROTECTED]
Date: Sun, 11 Jun 2000 12:22:08 GMT
zapzing <[EMAIL PROTECTED]> wrote:
: I agree that 8X8 sboxes ared too small to design
: randomly. One should never use any sboxes smaller
: than 16X16 if they are designed randomly. I await
: your tests with 16X16 random sboxes.
16x16 s-boxes??
Goodness - let's hope you don't need more than one of them.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Destroy Microsoft.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Reply-To: [EMAIL PROTECTED]
Date: Sun, 11 Jun 2000 12:35:21 GMT
tomstd <[EMAIL PROTECTED]> wrote:
:Terry Ritter wrote:
:>In a sense, computer caching is a hostile environment for
:>cryptography, in that it encourages constructions which re-use
:>internal data and discourages constructions which benefit less
:>from cache.
: You should know better.
: CAST sboxes are perfect 32x32 sboxes that only take 4kb of
: memory. I have no clue how they made them, but Obviously the
: same idea could be applied to make 16x16 sboxes that only take
: 1kb of ram (using two 8x16 sboxes).
CAST s-boxes are normally described as being 8x32 s-boxes, not 32x32
s-boxes - because that's what they are.
The end result is a 64-bit s-box (the cypher itself) - but I don't think
anybody would claim that this is "perfect".
A 16x16 s-box takes up 128Kb RAM - not 1Kb.
An 8x16 s-box - a bit like the ones used in CAST - would take up 2Kb.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Reply-To: [EMAIL PROTECTED]
Date: Sun, 11 Jun 2000 12:38:41 GMT
zapzing <[EMAIL PROTECTED]> wrote:
: Well it depends on whether: 1-you might need less rounds
: if you use a larger sbox. 2-you might have an optimizing
: compiler that can do something else with the time while
: it waits, 3-maybe this is a hardware implementation that
: works in a totally different way.
A big LUT is generally slow in hardware as well as in software,
and it takes up more area.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
Subject: Re: Large S-Boxes
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 11 Jun 2000 06:01:14 -0700
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]>
wrote:
>zapzing <[EMAIL PROTECTED]> wrote:
>
>: I agree that 8X8 sboxes ared too small to design
>: randomly. One should never use any sboxes smaller
>: than 16X16 if they are designed randomly. I await
>: your tests with 16X16 random sboxes.
>
>16x16 s-boxes??
>
>Goodness - let's hope you don't need more than one of them.
I don't think he got the point of my test. That's ok, let them
do as they wish.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: randomness tests
Reply-To: [EMAIL PROTECTED]
Date: Sun, 11 Jun 2000 12:48:41 GMT
tomstd <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>[EMAIL PROTECTED] wrote:
:>: in order to check randomness of my random number(bit) generator
:>: i use
:>: 1. ent package
:>: 2. diehard package [...]
:>
:>: can anyone suggest me any tests?
:>
:>pLab have a C++ test-suite for download: (at the bottom of)
:> http://random.mat.sbg.ac.at/tests/
: Again, total garbage. The original poster never said what he is
: using the prng for so how can you be sure that these tests are
: good for what he needs?
He asked for tests. I gave him a big C++ test suite.
I don't see how this qualifies as total garbage.
Personally, I find randomness tests very useful for cryptographic purposes
- by weeding out garbage. It's not terribly important what the
application requiring randomness is - if it fails the sorts of simple
tests in randomness test suites, the chances of it resisting the dedicated
attention of an analyst seem to be pretty low.
: Would people stop clinging to Diehard/ent/etc as the ONLY way to
: test a prng!
Who ever said that!???
: IF you don't know what it's for, how can you tell if it's good or not?
If they're asking for a random number generator, it's pretty safe to
assume that something that outputs 0,0,0,0,0,0,57,0,0,0,0,0,0 will *not*
qualify as being "good". This is the sort of thing that a randomness test
will easily pick up on.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ This tagline no verb.
------------------------------
** 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
******************************
