Cryptography-Digest Digest #555, Volume #9 Sun, 16 May 99 21:13:07 EDT
Contents:
Re: Fast random number generator -- Need C code for simulation
Re: Fast random number generator -- Need C code for simulation
Re: Keyed bit permutation (Christopher)
Re: Keyed bit permutation (Christopher)
Re: On Contextual Strength ("Douglas A. Gwyn")
Re: Security ("Douglas A. Gwyn")
Re: Scramdisk/Norton query ("N")
Mandlebrot transform (DGoncz)
Re: Hello I am paper, please read me. ("Vedat Hallac")
Re: On Contextual Strength ("R H Braddam")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Fast random number generator -- Need C code for simulation
Date: 16 May 99 19:15:45 GMT
catfish ([EMAIL PROTECTED]) wrote:
: I've been following this interesting thread and wonder if there's some
: fast C code for a long-period RNG.
Well, here's the code you are looking for, except the generator may not
be quite as fast as you'ld like. First, the actual routine you call:
int nrand( void )
{ int ir ;
ir = ( rbyte(0) << 7 ) | ( rbyte(0) >> 1 ) ;
return ir ;
}
which just calls the routine that does the actual work, generating random
bytes.
rbyte(0) is the call to obtain a random number.
rbyte(n), for n a number from 1 to 19682, initializes the random number
generator.
The code assumes that a variable declared long is at least a 32-bit signed
number.
The number of possible sequences is limited, since this is only a random
number generator. That could be remedied by allowing individual elements
in the seed array to be modified, and perhaps requiring a call with -1 as
a parameter to fill the table.
int rbyte( int arg )
{ static int btable[ 729 ] ;
static long a[ 6 ] ;
static long b[ 6 ] ;
long w[ 6 ] ;
long ii ;
int i, j, val, ptr ;
if ( arg != 0 )
{ ii = arg ;
/* Ensure that ii is a number in the range 0 to 19682. */
if ( ii < 1 )
{ ii = 1 - ii ;
}
if ( ii > 19682 )
{ ii = ii % 19683 ;
}
/* Initialize both seeds. */
for ( i=0 ; i<=5 ; i++ )
{ a[i] = ii ;
b[i] = ii ;
}
/* Initialize the table for a MacLaren-Marsaglia generator. */
for ( i=0 ; i<729 ; i++ )
{ for ( j=5 ; j>=0 ; j-- )
{ w[j] = a[j] * 21721 ;
}
for ( j=5 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
for ( j=4 ; j>=0 ; j-- )
{ w[j] = w[j] + a[j+1] * 12468 ;
}
for ( j=4 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
for ( j=3 ; j>=0 ; j-- )
{ w[j] = w[j] + a[j+2] * 20651 ;
}
for ( j=3 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
for ( j=2 ; j>=0 ; j-- )
{ w[j] = w[j] + a[j+3] * 30054 ;
}
for ( j=2 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
for ( j=1 ; j>=0 ; j-- )
{ w[j] = w[j] + a[j+4] * 12159 ;
}
ii = w[1] >> 15 ;
w[1] = w[1] - ( ii << 15 ) ;
w[0] = w[0] + ii ;
w[0] = w[0] & 32767 ;
w[0] = w[0] + a[5] * 10711 ;
w[0] = w[0] & 32767 ;
for ( j=0 ; j<= 5 ; j++ )
{ a[j] = w[j] ;
}
btable[ i ] = w[0] >> 7 ;
}
return 0 ;
}
else
{ for ( j=5 ; j>=0 ; j-- )
{ w[j] = a[j] * 21721 ;
}
for ( j=5 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
for ( j=4 ; j>=0 ; j-- )
{ w[j] = w[j] + a[j+1] * 12468 ;
}
for ( j=4 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
for ( j=3 ; j>=0 ; j-- )
{ w[j] = w[j] + a[j+2] * 20651 ;
}
for ( j=3 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
for ( j=2 ; j>=0 ; j-- )
{ w[j] = w[j] + a[j+3] * 30054 ;
}
for ( j=2 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
for ( j=1 ; j>=0 ; j-- )
{ w[j] = w[j] + a[j+4] * 12159 ;
}
ii = w[1] >> 15 ;
w[1] = w[1] - ( ii << 15 ) ;
w[0] = w[0] + ii ;
w[0] = w[0] & 32767 ;
w[0] = w[0] + a[5] * 10711 ;
w[0] = w[0] & 32767 ;
for ( j=0 ; j<= 5 ; j++ )
{ a[j] = w[j] ;
}
val = w[0] >> 7 ;
for ( j=5 ; j>=0 ; j-- )
{ w[j] = b[j] * 11206 ;
}
for ( j=5 ; j>=1 ; j-- )
{ ii = w[j] / 19683 ;
w[j] = w[j] - ii * 19683 ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] % 19683 ;
for ( j=4 ; j>=0 ; j-- )
{ w[j] = w[j] + b[j+1] * 8592 ;
}
for ( j=4 ; j>=1 ; j-- )
{ ii = w[j] / 19683 ;
w[j] = w[j] - ii * 19683 ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] % 19683 ;
for ( j=3 ; j>=0 ; j-- )
{ w[j] = w[j] + b[j+2] * 10267 ;
}
for ( j=3 ; j>=1 ; j-- )
{ ii = w[j] / 19683 ;
w[j] = w[j] - ii * 19683 ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] % 19683 ;
for ( j=2 ; j>=0 ; j-- )
{ w[j] = w[j] + b[j+3] * 5517 ;
}
for ( j=2 ; j>=1 ; j-- )
{ ii = w[j] / 19683 ;
w[j] = w[j] - ii * 19683 ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] % 19683 ;
for ( j=1 ; j>=0 ; j-- )
{ w[j] = w[j] + b[j+4] * 9632 ;
}
ii = w[1] / 19683 ;
w[1] = w[1] - ii * 19683 ;
w[0] = w[0] + ii ;
w[0] = w[0] % 19683 ;
w[0] = w[0] + b[5] * 11721 ;
w[0] = w[0] % 19683 ;
ptr = w[0] / 27 ;
ii = btable[ ptr ] ;
btable[ ptr ] = val ;
return ii ;
}
}
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Fast random number generator -- Need C code for simulation
Date: 16 May 99 19:40:58 GMT
Oops. Since this is intended to be with two linear congruential
generators, not multiplicative congruential, I left out some code.
After each of the two occurrences of:
: ii = w[1] >> 15 ;
: w[1] = w[1] - ( ii << 15 ) ;
: w[0] = w[0] + ii ;
: w[0] = w[0] & 32767 ;
: w[0] = w[0] + a[5] * 10711 ;
: w[0] = w[0] & 32767 ;
insert
w[5] = w[5] + 10981 ;
w[4] = w[4] + 23248 ;
w[3] = w[3] + 16125 ;
w[2] = w[2] + 9418 ;
w[1] = w[1] + 10404 ;
w[0] = w[0] + 30331 ;
for ( j=5 ; j>=1 ; j-- )
{ ii = w[j] >> 15 ;
w[j] = w[j] - ( ii << 15 ) ;
w[j-1] = w[j-1] + ii ;
}
w[0] = w[0] & 32767 ;
and after
: ii = w[1] / 19683 ;
: w[1] = w[1] - ii * 19683 ;
: w[0] = w[0] + ii ;
: w[0] = w[0] % 19683 ;
: w[0] = w[0] + b[5] * 11721 ;
: w[0] = w[0] % 19683 ;
insert
w[5] = w[5] + 11035 ;
w[4] = w[4] + 8727 ;
w[3] = w[3] + 10501 ;
w[2] = w[2] + 9713 ;
w[1] = w[1] + 17361 ;
w[0] = w[0] + 5568 ;
for ( i=5; i>=1; i-- )
{ ii = w[i] / 19683 ;
w[i] = w[i] - ii * 19683 ;
w[i-1] = w[i-1] + ii ;
}
w[0] = w[0] % 19683 ;
for ( i=0; i<=5; i++ )
{ b[i] = w[i] ;
}
and once you have done that, the routine will be complete and ready for
use.
John Savard
------------------------------
From: [EMAIL PROTECTED] (Christopher)
Subject: Re: Keyed bit permutation
Date: Sun, 16 May 1999 17:44:48 -0400
Well, the keyed-permutation is efficient in hardware, eight NANDs per
subkey bit, three levels deep (including the inversion of the subkey
bit). And the final (fixed) permutation costs nothing in hardware.
The input to each S-boxe (ignoring the subkey-permute and other
subkey-XOR) is one of the four bytes of the 32bit word after
right-shifting the entire word. The choice of S-boxes depends on the two
bits bordering each of those bytes, so the diffusion rate should be
similar to DES. After two rounds I suspect any of the primes may have
been used on any of the bytes. Also, after two rounds each output bit
seems to depend on 4 key bits and 4 other plaintext bits, without taking
the S-box function into account.
Choosing the fixed permutation so that after four rounds each plaintext
bit is used as a row selector to one of the S-boxes would seem like a
reasonable design criteria. Taking into account the keyed permutation it
should still be possible to guarantee that after 5 rounds, so I would
think a differential attack after 5 rounds would require 2^48 chosen
plaintexts, revealing 16 key bits. There may be a way to get 12 bits of
key after 4 rounds and 2^32 chosen plaintexts, but it doesn't seem to
follow that that can be used as a general attack against the 8 round
variant.
I don't know how many if the input bits effect each output bit of the
S-box functions, intuitively I would think 7, but used all 8 above. Also,
this is my first, cursory attempt at this, comments and corrections are of
course welcome.
--
Keep away from people who try to belittle your ambitions. Small people
always do that, but the really great make you feel that you, too, can
become great. -Mark Twain
In article <7hmgm4$md5$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
|:| I was just looking at ICE, and I was wondering if the keyed-permutation
|:| (bit swap) is strong. From what I can see it's non-linear, but can
|:| suffer from differential attacks.
|:|
|:| What are the design criterias for such swaps anyways? Also are they
|:| efficient in hardware? I would imagine so.
|:|
|:| Tom
|:| --
|:| PGP public keys. SPARE key is for daily work, WORK key is for
|:| published work. The spare is at
|:| 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
|:| 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
|:|
|:|
|:| --== Sent via Deja.com http://www.deja.com/ ==--
|:| ---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (Christopher)
Subject: Re: Keyed bit permutation
Date: Sun, 16 May 1999 18:16:12 -0400
Oops, that should be seven NANDs per subkey bit, including the subkey bit
inversion used twice.
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Christopher) wrote:
|:| Well, the keyed-permutation is efficient in hardware, eight NANDs per
|:| subkey bit, three levels deep (including the inversion of the subkey
|:| bit). And the final (fixed) permutation costs nothing in hardware.
|:|
--
It's easier to judge a book by its cover knowing nothing of its contents.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: On Contextual Strength
Date: Sun, 16 May 1999 22:50:32 GMT
"D. J. Bernstein" wrote:
> In short, if the generator isn't secure, then there's verifiable
> evidence that it isn't secure. The only problem is _finding_ the
> evidence. No method is known that's guaranteed to do this quickly---
> there are far too many algorithms to try---but people have
> nevertheless succeeded in many cases. In cases where many people have
> failed, the reason might be that the generator is secure after all.
What I was arguing was that there is an essential difference between
an existence proof and a constructive proof; the mere knowledge that
an effective algorithm "exists in principle" doesn't really help the
cryptanalyst, who still doesn't know how to find such an algorithm
with the available resources.
Perhaps this is pointed up well by your last sentence -- failure to
find an effective way to crack a system really provides very little
evidence of the system's theoretical security. My concern is that
several participants in these discussions sound like they believe
the exact opposite.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Security
Date: Sun, 16 May 1999 22:52:46 GMT
[EMAIL PROTECTED] wrote:
> Well if a brute force search of a 256 bit key is the only way ...
Of course, that would need to be proved. Such proofs are quite rare.
------------------------------
From: "N" <[EMAIL PROTECTED]>
Subject: Re: Scramdisk/Norton query
Date: Sun, 16 May 1999 22:57:40 GMT
Hey!
I thought my original thread had died!
I seem to have three SVL files appearing randomly -
00007337.svl (19.0K)
00000011.svl (1Mb)
00000055.svl (200Mb)
and try as I might, I just can't rid myself of them! They are all deleted
by "(unknown)" and all had
C:\Recycled\Nprotect as their original location.
I don't think it's Norton at fault, but it is peculiar that Norton seems to
deem the phantom files as having resided in the protected recycle bin
*prior* to deletion! Strange, eh?!
If anyone can give me back my 201.02Mb of lost space, or at least explain
these goings-on, please do!
N
Joshua Falkin wrote in message
<[EMAIL PROTECTED]>...
>I Stumbled across this same problem. There's got to be a bug in the
>Scram disk program....Why is there a hidden svl container on my hard
>drive that I did not create???
>I found it by sending the contents of what appeared to be an empty
>Recycled bin to WinZip. there it was, 200mb of who knows what?
>
>
>
>On Fri, 23 Apr 1999 23:44:45 GMT, "N" <[EMAIL PROTECTED]> wrote:
>
>>Can anyone tell me why deleted files with an SVL extension keep appearing
in
>>my Norton protected recycle bin, even though no container files have been
>>loaded or deleted and the Scramdisk utility program has not been running?
>>
>>When I remove them from the bin, they always reappear, often within
minutes!
>>They normally have a name such as 00000011.svl or 00007337.svl, for
example,
>>and range in size from 20K to 200Mb! I have tried excluding this file
>>extension from Norton Protection, but to no avail. Norton cannot identify
>>which program deleted them, but since the Scramdisk utility program isn't
>>running presumably it must be work of the driver SD.VXD?
>>
>>It does seem to be a gross waste of space for spurious files as large as
>>200Mb to be taking up this kind of space continually!
>>
>>Thanks
>>N
>>
>>
>>
>>
>>
>>
>
------------------------------
From: [EMAIL PROTECTED] (DGoncz)
Subject: Mandlebrot transform
Date: 16 May 1999 23:13:14 GMT
The Mandelbrot transform transforms a complex number a + bi into
c= (a+bi)^2 + (d+ei)
The number of iterations repeated when c is transformed by the same procedure
without having the tranformed point "leave the room" is the height of the
fractal at the point a + bi.
Is there an encryption technique here? It's all floating point math.
An integer version can be imagined by assigning one complex number to each
point in a computer bitmap screen, or more generally a two dimensional array of
ordered positive and negative integers, and then rounding off the complex
result to one of the points in the array.
Might such an integer transform have a crytographic use, possibly in encoding a
picture or a fax?
Yours,
Doug Goncz
Replikon Research, PO Box 4094, Seven Corners, VA 22044-0094
Please DO copy your reply to me via e-mail.
http://users.aol.com/DGoncz or /ReplikonVA
Please poll my fax at 7 oh three five 36 five 469 for a photo of my drill
press.
------------------------------
From: "Vedat Hallac" <[EMAIL PROTECTED]>
Subject: Re: Hello I am paper, please read me.
Date: Mon, 17 May 1999 09:36:03 +1000
>About TwoDeck, the security lies within not being able to find the
>output of A in B(A(x)), if you don't know A you can't find B.
The problem with using only B(A(i)) is that, given any two decks, A and B,
if you swap A(i) and A(j), and swap B(A(i)) and B(A(j)) you end up with an
equivalent transformation B(A(i)) for all i.
Once you can swap elements of A without modifying the result, you can sort
A, and reduce the transformation to a "canonical form" where A'(i) is i, and
B'(A'(i))==B'(i)==B(A(i)). This will be an equivalent deck configuration,
which can be discovered using N known plain-cipher texts.
Another property is that shuffling A at k, and then sorting it is equivalent
to shuffling B at k (I did not prove this, but it seems to be the case).
Thus, you can completely remove deck A from your algorithm, by converting
all shuffle(A, i) statements to shuffle(B, i), because you start from a
completely sorted A.
With the current implementation, 5*N known plaintexts will allow you to
discover the first 32 bit output of the rand() function, and with at most
2^32 steps you can discover the seed value.
If you use all bits of the key for the seeding of the RNG, after each
shuffle, there will only be 256 possible deck configurations, and you can
discover which one is true with a little knowledge about the plaintext (e.g.
the plaintext is ASCII characters only), or a one byte of known plaintext
from each block.
I still do not see a simple way of inverting the shuffles to get the key
bytes from the discovered deck B configuration.
------------------------------
From: "R H Braddam" <[EMAIL PROTECTED]>
Subject: Re: On Contextual Strength
Date: Sun, 16 May 1999 17:11:26 -0500
Please excuse me for asking questions at this point, but I've been trying to
follow this thread, and sometimes it gets a little confusing.
Bryan Olson wrote in message <[EMAIL PROTECTED]>...
{
{Obviously, multiple encryption increases the fudge factor.
{Whether it's a good way to increase the fudge factor is
{debatable, but that's for another thread.
By multiple encryption do you mean:
a. triple DES with 3 keys, (for example) or
b. encrypt a message with DES, then with Idea (then... etc) or
c. something else?
If something else, what?
{My argument is that the many-cipher system is _worse_ for us
{and better for the attacker. I think it's much more likely
{to expose 10% of the data than is a single cipher system, and
{unless we intelligently partition the data among the ciphers,
{exposing 10% is probably 90% as bad as exposing everything.
Here's one of the places I got lost this time. One many-cipher combination I
can think of off the top of my head is just triple-DES with three keys. It
just so happens that all three ciphers are DES. From what I've read in
sci.crypt, it is considered much stronger than single DES. Is it more likely
to expose data than single DES? What if the second pass is made with
Blowfish instead of DES? Is the DES-Blowfish-DES combination more likely to
expose information? If not, it would appear to me that the reliability of
the ciphers used is more important than the combination or how many times it
is used. Processing time is increased, but is security also increased? If
so, is it increased porportionally to the increase in processing time?
How do you mean "partition the data"? I thought Terry was proposing a or b
above with selectable ciphers. I remember reading where he suggested
encrypting different messages with different ciphers selected from a
collection, but I thought he expanded on that to say encrypt different
messages with multiple ciphers selected from the collection. Sort of like
triple DES but with a different cipher and key on each pass through a block
or message.
Would Terry's idea have more merit if the collection of ciphers was limited
to those which had received extensive analysis? We'd still have several to
choose from, as in Wei Dai's Crypto++ 3.1 library.
{I don't see any justification for the idea that we're
{fracturing the adversaries effort so he won't be able to break
{any significant portion of the traffic. It seems that we'd
{have to assume that the our adversary's attacks are applicable
{only to individual ciphers, and that's not the way most attacks
{we know about work. We'd have to assume he can't easily tell
{whether his attacks apply to a cipher, which seems absurd.
This is especially confusing. It seems like you are saying that most attacks
analysts know about apply to individual ciphers and to multi-cipher stacks
(cascaded ciphers). Do you mean apply to them equally? And that an analyst
can easily tell whether his attacks apply to a cipher or a cascaded cipher.
Is there an implied "or not" here? Is that why some ciphers are described as
secure because no attack better than brute-force keysearch has been found?
{Assumptions about how may adversary attacks ciphers seem worse
{than assumptions about what is possible. At least there's a
{good chance that academic cryptanalysis is pretty good. It
{really is science, and it really can make progress. My attacker
{may be better at it, but we're looking for the same thing.
{There's nothing fundamental stopping me from knowing what he
{knows.
Of course nothing stops you from knowing what your adversary knows. I think
he may have some advantages which help him (and his coworkers) stay ahead of
the rest of the world, though, such as:
the "company" he works for _may_ have a _practically_ _unlimited_ budget,
he may have access to and use the best state-of-the-art computers and
equipment that a practically unlimited budget can buy _or build_,
he may do cryptoanalysis and cryptosystems design as a full time job,
he may have no outside (commercial, etc) interests to distract him from his
job,
and he may be highly motivated to the point of obsession with secrecy and
security.
Of course, all those things are just maybes. Maybe.
Government crypto types are really weird. Paranoid, too. At least the ones
I've met. A long time ago.
{No research is going to tell me the capabilities of my enemies.
{If you disagree with me about the generality of the adversaries
{attacks, how can one of us convince the other? Neither position
{is either provable or falsifiable. It's not science; we can't
{make progress.
I remember reading somewhere that the difficulty of breaking a cascaded
cipher is not less than the difficulty of breaking the strongest cipher in
the cascade. Is that true? If it is, does it imply that there is nothing to
loose, security-wise, by using cascaded ciphers? On the other hand, is it
possible to use the second and third ciphers in a 3 cipher cascade to hide
the first from analysis? What constraints and/or conditions would apply?
I don't need Ultimate Security, at least not right now. I would like to know
that if I decided I did need it that it was available, at least as nearly as
possible. I hope that you and all the others in sci.crypt will continue to
explore every avenue to find ways to improve cryptography. There may come a
day when the best we can get is barely good enough. I hope not, and I don't
look forward to it, but it is possible.
Murphy's Law is the only sure thing in the Universe.
Rick
------------------------------
** 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
******************************
