Cryptography-Digest Digest #1, Volume #12 Sun, 11 Jun 00 01:13:01 EDT
Contents:
Re: randomness tests (Guy Macon)
Re: randomness tests (tomstd)
Secret Spliting - Theshold shemes. (Simon Johnson)
Digits of pi in Twofish ("David S. Hansen")
Re: question of generating random challenges in Java (Dido Sevilla)
Re: Large S-Boxes (David A Molnar)
Re: Digits of pi in Twofish (tomstd)
Re: Updated: Evidence Eliminator Dis-Information Center (Includes info on false SPAM
accusations) (The Bearded One)
Re: How does DES work? (Sundial Services)
Re: Large S-Boxes ("Trevor L. Jackson, III")
Re: Digits of pi in Twofish (Jim Gillogly)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: randomness tests
Date: 10 Jun 2000 21:56:09 EDT
tomstd wrote:
>
>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?
>
>Would people stop clinging to Diehard/ent/etc as the ONLY way to
>test a prng!!!! IF you don't know what it's for, how can you
>tell if it's good or not?
>
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
ANT randomness test is unacceptav=ble, so all such tests are useful.
------------------------------
Subject: Re: randomness tests
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 19:32:30 -0700
In article <8hurjp$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Guy Macon) wrote:
>tomstd wrote:
>>
>>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?
>>
>>Would people stop clinging to Diehard/ent/etc as the ONLY way
to
>>test a prng!!!! IF you don't know what it's for, how can you
>>tell if it's good or not?
>>
>
>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
>ANT randomness test is unacceptav=ble, 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...
The tests are very suggestive and not quantiative.
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: Simon Johnson <[EMAIL PROTECTED]>
Subject: Secret Spliting - Theshold shemes.
Date: Sun, 11 Jun 2000 02:33:35 GMT
Just to insure you know what i'm talking about, i'll include the
description of the threshold sheme i am refering to:
To split message C, amoung x users such that n shadows can recover the
message do the following:
1.) Choose a number greater than C (a prime would be optimal) for the
mod, p.
2.) Choose random coeffients for the following equation
t = ax^n-1 + bx^n-2 ......... + c mod p
3.) increment X and calculate t to generate the shadows.
Now my question is this: Is there a quick way to recreate the equation
using a the correct number of shadows?
My method use simple sequence finding techiques:
e.g.
Consider
f(x) = X^2 + (3)x + 23 mod 29
i.e. f(x) = ax^2 + bx + c mod 29
Shadow 1: 1+3+23 mod 29 = 27 mod 29 (0 mod reductions)
Shadow 2: 4+6+23 mod 29 = 4 mod 29 (1 mod reductions)
Shadow 3: 9 + 9 + 23 = 12 mod 29 (1 mod reductions)
To reconstruct 23 and coeffients:
Sequence = 27, 4+29=33, 12+29=41
First diff: 6,8
2nd diff: 2
a=2/2 = 1
Table:
Shadow ax^2 Diff 2nd diff.
27 1 26 3
33 4 29
41 9 32 3
b = 3
27 = 1^2 + 3 + c
C= 27-4 = 23 - which recovers the secret.
The question: There has to be a faster method than this? Plus the
shadows, to be processed, have to be in n'th shadow order for this
method to work.
Any suggestions?
Simon Johnson
PS. If there are any grave errors, or i am writing jibirish, forgive me
its 3:37 AM and i am really very tired :).
--
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: "David S. Hansen" <[EMAIL PROTECTED]>
Subject: Digits of pi in Twofish
Date: Sun, 11 Jun 2000 03:10:58 GMT
Hello, new here. I was looking over the original source for the twofish
algorithm and noticed that the sboxes are originally initialized with the
digits of pi - any particular reason for this, in terms of cryptographic
strength ?
*** David S. Hansen
*** [EMAIL PROTECTED]
*** http://www.haploid.com
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: question of generating random challenges in Java
Date: Sun, 11 Jun 2000 11:01:17 +0800
Jean-Luc wrote:
>
> 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.
>
For cryptographic purposes, linear congruential generators are
worthless. It is a fairly simple matter to attempt to get the seed, as
the generator's properties are very well known. Then, from the point of
view of your attacker, your "random seed" is no longer very random. By
applying the same transformations he or she would be able to get every
number in your sequence with very little effort. You should write your
own cryptographically-secure PRNG and use that instead of the built-in
one. See Chapter 5 ("Pseudorandom Bits and Sequences") in the "Handbook
of Applied Cryptography" (http://www.cacr.math.uwaterloo.ca/hac/).
Since Java provides bit-twiddling operators like C does, implementing
such a PRNG shouldn't be too difficult.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
Mobile Robotics Laboratory +63 (917) 4458925
University of the Philippines Diliman
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: 11 Jun 2000 03:01:19 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
> My original 'dumbies guide' post was prehaps the wrong words to use,
> rather i require a wedge to break into the art of analysing math-made
> ciphers.
> Basically, i'm looking for a medium-paced introduction to math based
> cryptanyalisis. Any offers?
May be worth looking for Stern & Joux _Lattice Basis Reduction : A Toolbox
for the Cryptanalyst_. It is a different technique than the differential
and linear and other cryptanalysis likely to be mentioned in this thread,
but worth knowing about..
------------------------------
Subject: Re: Digits of pi in Twofish
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 20:35:12 -0700
it's blowfish not twofish that uses pi, and there is absolutely
no cryptographic reason to the best of my limited knowledge
* 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: The Bearded One <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Updated: Evidence Eliminator Dis-Information Center (Includes info on
false SPAM accusations)
Date: Sat, 10 Jun 2000 23:53:46 -0700
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
>
>
>On Fri, 09 Jun 2000 18:01:22 -0500, EE Detractor <[EMAIL PROTECTED]>
>wrote:
>
>>On Fri, 09 Jun 2000 20:45:50 +0100, EE Support
>><[EMAIL PROTECTED]> wrote:
>>
>>>It has become commonly said by posters
>>>to these newsgroups that the ones posting the "anti-Evidence
>>>Eliminator" messages in all their disguises, are wearing badges and
>>>intend to compromise your privacy and security, by stopping you
>>>downloading a free Evidence Eliminator.
>>
>>Mostly it's been said by you, as a way to evade hard questions and
>>concerns that have been raised by the regulars about the product and
>>the company.
>>
>It has been said by a number of us.
>
>>Care to explain why Evidence Eliminator is coming under this kind of
>>"attack" and not, say, PGP or Scramdisk or the thousands of other
>>high-level security products on the web????
>>
>Because cops can force the passwords to these things out of you, or
>your ass goes to jail for contempt of court. They even have ways of
>finding evidence scattered around on the main, unhidden, drive. The
>average person simply doesn't begin to know enough about the
>architecture of Windows to find all of the nooks and crannies where
>passwords, damning evidence, etc., could be hiding, just waiting for
>Encase to find it.
>
>The difference between these "other" security measures and EE is that
>EE DESTROYS the evidence in such a fashion that it can NEVER be
>recovered again -- IF you heed EE's instructions.
>
>That's why you and the rest of the "cop" brigade fear it.
>
>Let me remind you of one thing about cops. Do you know who it was who
>turned over all the Jewish children in France to the Nazis for
>extermination? The gendarmes. In each country the cops helped scoop
>up the innocent women and children for the death camps. Why? "Because
>if we didn't do it, someone else would have to. No matter what, there
>has to be the order of law during these difficult times."
>
>Screw cops! They'd do the same thing here in America. Cops are cops,
>whether they speak English, French, German or Swahili.
>
>- The Thistle -
>
Godwin's law invoked.
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOUHZIpGBLKZYRHrPAQG+ZwgA2CZwT6SE8yUzgfXBJQSelPnM7jS9RRgX
NYyiO+cIyiZthEtuBfKECQWEmUYJJlcfASy/N0Wp/LFbdN5pBPe7jn4+91ZSNJTN
1yv03JESs0MIfvYGjkyLNUc297B0jRgXKsqU8RH6Qsr3DYdXk/3lKrChMrBk6o0F
wst6DrrNya6+hpQa2x5Vv0xVtDbqYm2+wIbxz3s7BlFAoVf8e64mDPK2ba08qWhb
DlV1GcI+wkF/TodXDLAHRf6T3kYd/5euSUXxbUZqeyZuUUY3ojqd/U5fZ7J6HQ3x
EEjeZ6/BYqMgaW9bNvRFvq7JpwSoN3LYZ1fxRcowcbJ0jh10Eb45eg==
=4/AM
=====END PGP SIGNATURE=====
------------------------------
Date: Sat, 10 Jun 2000 21:39:55 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: How does DES work?
While your analogy of DES as "56 instructions" is certainly an
intriguing look at this cipher, it implies -- erroneously -- both that a
single bit of the key only influences the cipher one time, and that
these influences are independent of one another.
In fact, the cipher is like a house of cards. Influencing a single bit
of the key or of the data produces an "avalanche" of cascading effects
on the final output. One of the non-obvious reasons for this is those
S-boxes: those tables of inputs and outputs which, as it turns out, are
-not- chosen by chance. As other replies have suggested, if you do have
a model of the cipher at work, it's remarkable to observe "what happens
when I push -this- button ..."
>Michael Brown wrote:
>
> I was reading about DES's insecurities and wondering a bit about how it
> works. I read somewhere else that it "folds" up the string of bits or
> something, and was wondering if it is something like this: each bit
> specifies a command, for example 0=swap each bit with its neighbour to the
> right, 1=swap each bit with its neighbour to the left, so a 56 bit key
> would have 56 "instructions". Is is instruction based, or something
> completely different. If it's different, are there any other encryption
> things that use this method (there seems to be a <lot> of different ones
> mentioned...) or a similar one (eg:16 instructions)?
>
> Any pointers to DES info also appreciated.
>
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
Date: Sun, 11 Jun 2000 00:50:09 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
zapzing wrote:
> In article <8htu11$qkn$[EMAIL PROTECTED]>,
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
> >
> > Simon Johnson <[EMAIL PROTECTED]> wrote in message
> > news:8hstkt$dik$[EMAIL PROTECTED]...
> > > In article <8hsknh$bov$[EMAIL PROTECTED]>,
> > > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
> > > >
> > > > Simon Johnson <[EMAIL PROTECTED]> wrote in message
> > > > news:8hrtja$nte$[EMAIL PROTECTED]...
> > > > >
> > > > >
> > > > > I think i'm flogging a dead-horse here, but i'm after evidence
> in 'a
> > > > > dummies guide to' style to the pro's and con's of randomly
> > > generated S-
> > > > > boxes.
> > > > >
> > > > > I'm thinking 16x16 for a block-cipher i'm devolping (don't hold
> u're
> > > > > breath, i don't have 1/2 a clue what i'm doing :), i just having
> > > fun.)
> > > >
> > > > So, you're think about an sbox that will take 128k of memory?
> Well,
> > > that'll
> > > > work in the sense that (with high probability) there won't be any
> > > > troublesome characteristics, however, an sbox that big won't fit
> in a
> > > > conventional L1 cache. Assuming you're running it on any modern
> CPU,
> > > any
> > > > sbox reference will take several cycles while the CPU waits for
> the
> > > memory
> > > > (or more likely, the L2 cache) to retrieve it. Since this will
> > > happen to
> > > > almost every sbox reference, you're performance is likely to be
> > > dreadful,
> > > > and as has been pointed out, a secure block cipher is actually
> pretty
> > > easy
> > > > to design if you are willing to settle for dreadful performance...
> > >
> > > I never even considered that. I suppose the real question is two
> block
> > > thru an 8x8 faster than one block thru a 16x16? Another important,
> and
> > > linked, question is how long does it take to retreive from the L1
> cache?
> > > Moreover, won't the operating system be using this cache?
> > I think you don't quite understand what L1 cache is. In modern CPUs
> (it was
> > different in the past, and it may very well be different in the
> future), you
> > have CPUs that can do a single operation in 2-5 nsec, and you have
> main
> > memory (the memory that is cheap enough to have multiple megabytes
> lying
> > around) that might be able to do a single access in 50nsec. So that
> the CPU
> > isn't spending all its time waiting for the memory, CPU designers
> insert a
> > 'cache' between the two. This cache is designed so that the CPU can
> access
> > it in one 2-5nsec cycle (so the CPU doesn't slow down accessing it),
> and
> > usually the CPU can access multiple locations in the cache at once.
> This
> > cache is usually situated on the CPU chip, and is typically
> 4k-32kbytes
> > large. This cache (actually, any cache, this is the definition of
> "cache")
> > works by storing the contents of recently accessed portions of the
> main
> > memory, in hopes that the program will access them again. So, if you
> access
> > a location once, the CPU stalls for the 50 nsec waiting for that
> location
> > again. But, if you access the location again, the CPU can read that
> > location immediately. However, if the cache was full (every location
> [1]
> > was already holding a memory location), the L1 cache picks something
> already
> > in the cache and throws it out.
> >
> > And, because the L1 cache isn't big enough, computer designers insert
> a
> > second 'L2' cache between the L1 cache and the main memory. This
> cache is
> > larger (128k-1Megabyte), and slower (10-20nsec, IIRC).
> >
> > Now, suppose you have a 128k sbox, and a 32k L1 cache [2]. That means
> that
> > at most 1/4 of the sbox is currently in the L1 cache, even if your
> > encryption routine makes no other data accesses, and has been running
> long
> > enough to read the sbox into the cache. Sbox accesses are essentially
> > random, and so any sbox reference that your program makes has at least
> a 3/4
> > probability of missing the L1 cache, causing (at least) several cycles
> of
> > stall while the sbox contents are read from the L2 cache.
> >
> > And so, yes, 2 8x8 sbox accesses (two distinct 8x8 sboxes easily fits
> in the
> > L1 cache) are usually considerably faster than a single 16x16 sbox
> access.
> >
> > And, as for whether the OS is using the cache -- I think you are
> confusing
> > that with 'disk cache', which is the same caching concept applied to
> disk
> > accesses. The L1 cache is a feature of the CPU, and every program
> running
> > on the computer, including the OS, does use it. Practically speaking,
> only
> > the program currently running on the CPU has its data in the cache.
> >
> > >
> > > These points considered, it looks like the signs point to an
> optimized
> > > s-box. The problem with this approach is i don't even know where to
> > > start.
> > A better approach might be to do an initial design (using either
> random
> > sboxes, or no sboxes), and see if you can break it. If you can't,
> simplify
> > the design. Breaking ciphers teaches you much more than just
> designing
> > them.
> >
> > [1] Actually, L1 caches usually can't hold any memory location in any
> cache
> > element -- there are usually constraints. That can be ignored for
> this
> > overview
> >
> > [2] L1 caches are often split up between 'instruction' and 'data', so
> a 32k
> > L1 cache can usually hold only 16k worth of sbox data. I will ignore
> this.
>
> It would depend on your algorithm design, in conjunction
> with your hardware, wouldn't it? I mean you caould have
> an algorithm that sends out some data to be run through
> an sbox, does some other neet stuff, then the data that
> was sent out comes beck from the sbox device, all nice
> and sboxed up, just in time to be processed further.
The current generation of processors already has a solution for the CPU/memory
speed gap. 80786 processors support a set of prefetch instructions that load
cache lines from main memory into cache prior to the memory access that
references the data. The Intel version is fairly crude, but AMD has a nice
set of prefetch instructions.
Unfortunately modern compilers are not yet smart enough to utilize the
prefetch instructions effectively. As the CPU/memory gap increases the
motivation for improved cache management we can expect software to fill the
gap.
Anyone who has worked in micro assembler is familiar with the special
requirements of memory reference instructions. One often has to load the
memory address buffers/latches several cycles prior to reading or writing the
actual data values. In that environment pipelining is a lot like basket
weaving. It can be done manually, but the complexity screams for an automated
solution.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Digits of pi in Twofish
Date: Sun, 11 Jun 2000 04:51:16 +0000
tomstd wrote:
>
> it's blowfish not twofish that uses pi, and there is absolutely
> no cryptographic reason to the best of my limited knowledge
'Transparency' is a good cryptographic reason. "See, we're using
a pile of bits in here, but there's no back door -- honest. You
can verify for yourself that it's the most obvious pile of bits in
all of mathematics."
--
Jim Gillogly
Hevensday, 22 Forelithe S.R. 2000, 04:48
12.19.7.5.2, 2 Ik 5 Zotz, Third Lord of Night
------------------------------
** 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
******************************
