Cryptography-Digest Digest #431, Volume #10 Tue, 19 Oct 99 12:13:07 EDT
Contents:
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column ("Roger
Schlafly")
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Mok-Kong
Shen)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Mok-Kong
Shen)
Re: Strengthening passwords against dictionary attacks (Mok-Kong Shen)
Re: detecting backdoor in prime generator (Tom St Denis)
Re: Strengthening passwords against dictionary attacks (Tom St Denis)
Re: SG100 Hardware Random Number Generator (Francois Grieu)
Re: The Quad. in RC6 ([EMAIL PROTECTED])
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks"
Re: detecting backdoor in prime generator (Bob Silverman)
Re: frequency of prime numbers? (Bob Silverman)
----------------------------------------------------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Mon, 18 Oct 1999 21:08:46 -0700
Trevor Jackson, III <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Besides, if Cisco isn't willing to support multiple ciphers, I'll be happy
to
> invest in a second or third tier vendor who is willing to support
multiple
> ciphers because they want to beat Cisco.
What planet do you live on? Cisco is not going out of business
because it only offers AES/Rijndahl and the competition is
supplementing it with one of the AES rejects.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Tue, 19 Oct 1999 09:52:50 +0200
Bruce Schneier wrote:
>
> <[EMAIL PROTECTED]> wrote:
> >
> >O.K. Then in my opinion the main use of AES is in confidentiality.
>
> You will be surprised.
I'll prepare myself for that surprise, maintaining that the use
(more exactly the utility) of an object in an application (of any
nature) is measured by the difference of value of having it or not
having it and that such values are to be summed worldwide across all
kinds of applications.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Tue, 19 Oct 1999 09:52:59 +0200
Roger Schlafly wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote
>
> > On the (presumably reasonable) assumption that the top three
> > candidates in the final round are of approximately the same strength,
> > I don't see any reason against a random choice from the beginning,
> > excepting that other factors like performance can motivate the chooser
> > to investigate the matter in more detail.
>
> You (and the other anti-standard advocates) are living in a dream
> world. Systems in the real world are subject to constraints. You
> can't just pile on random algorithms and choose randomly without
> having substantial costs for doing so.
>
> You probably also don't see any reason GM shouldn't put 2
> engines in each car.
On the other hand, you (and some of the one-standard advocates)
confound the issue. It is not whether one 'can' or 'cannot' use more
than one AES candidates (unless a crypto law forbids that). One just
wants NIST, for whose opinion one has a fair amount of respect, to
testify that besides the AES winner, which is considered the best,
a couple of others are also o.k., so that the question of doubt of
strength of these (in case people want to use them e.g. in multiple
encryption for whatever reason) is greatly reduced in magnitude.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Strengthening passwords against dictionary attacks
Date: Tue, 19 Oct 1999 09:53:04 +0200
Tom St Denis wrote:
>
> Third, why does everybody think storing enciphered text on a local
> machine is so secure. For example in PGP they encrypt the keys but I
> could just as easily make a trojan, distribute it remotely get your key
> when you use it, and send it over the net to my machine. I could for
> example be collecting millions of private keys right as I type this and
> you would never know it.
>
> Basically I don't think you can really protect local machines. You can
> however protect remote communications such as information traffic.
I have not followd this remote/local debate, so I may misunderstand.
I think there are (some) local machines that you or someone you
trust have control (unless you don't exercise control), while you
can't say anathing of the remote ones in most cases. I don't understand
on the other hand your method of collecting private keys. Could
you explain with symbol in a bit detail? Thanks.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: detecting backdoor in prime generator
Date: Tue, 19 Oct 1999 11:22:39 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
>
> > In article <[EMAIL PROTECTED]>,
> > Anton Stiglic <[EMAIL PROTECTED]> wrote:
> > >
> > > Does someone remember the ref to an article talking about
> > > detecting prime generators (or n = pq generators) that have
> > > a backdoor?
> >
> > To the best of my knowledge PGP doesn't have backdoors in their
primes/keys.
> > If you don't trust it, don't use PGP.
> >
>
> This is not at all for PGP.... It's for some theoretical research...
>
What theoretic? You make up a random number and test it for
primailty. If you are suggesting that one scheme may let composites
thru you can always use two algorithms. The chances of both of them
letting it thru is squared (if you maintain an equal probable
proportion between the two algorithms. I.e one scheme may need k runs
to get 2^-k proof and the other 2^-4k ..etc)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Strengthening passwords against dictionary attacks
Date: Tue, 19 Oct 1999 11:24:52 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> >
> >
> > Basically any login system should work like this
> >
> > 1) Server sends R (random bit string, say 32 bits)
> > 2) Remote sends a = HASH(R + password) and R'
> > 3) Server checks a, and sends b = HASH(R' + password)
> > 4) Remote checks b
> >
> > Simple as that.
> >
> > Tom
> >
>
> And where does the server store a? That is the question, a brute
force attack
> can be done on that item.
>
What? a is not the password it is the response to the challenge. You
can toss it when the protocal is done. And if (R, R') are truly random
then you pretty have a 1 in sizeof_hash chance of guessing a or b
correctly.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Francois Grieu)
Subject: Re: SG100 Hardware Random Number Generator
Date: Tue, 19 Oct 1999 14:10:34 +0200
[EMAIL PROTECTED] wrote :
> We have today released the complete source for our SG100
> Hardware Random Number Generator.
Nice move. Let's see. The web site explains the hardware, including
overall block diagram. We have many source files with Swedish comments
such as "Synk med klockan i brus-DLL" and no software
documentation that I could find. Enter reverse engineer mode.
We get that the hardware basically use a noise source to generate
a random state on the data pin of an asynchronous serial port,
which is then read using the OS (Windows NT ?) serial driver.
This probably cause a few portability headaches, because the data
fed to the UART is not properly formatted, but well, eventually
the UART may interpret something as a start bit, sample nonsense,
a stop bit of some kind, and feed a good proportion of this to
the serial driver. OTOH, this is dependant on the UART logic
for at least two things
- what happens for a byte with an incorrect stop bit
or a malformed start bit ?
- when sampling random, does the UART have a bias ?
The designers apparently had a bad surprise in this area, with
a warning on the web site that some UARTs do not work.
The lower level source we have is in DLL_DRV.CPP where
void Read_Raw_Noise( ulong Load_OK, uchar *N_Buff)
reads out Load_OK bytes from the serial port into N_Buff
with carefull timemout checks.
One level above we have
void Execute_Noise_Loop( char *Port, DWORD In_BaudRate)
which we see reading 4 batches of 8000 bytes for a total of
32000 bytes, counting the occurences of each bytes into array
Sum[256], changing this to a frequecy P(x) = Sum[x]/32000,
computing
Inf = -Sigma(P(x)/log(P(x))/log(256)
which clearly is 1 if all bytes are exactly as
likely, and tends to lower when the distribution is skewed.
The machine has better get an FPU with built-in log !
Depending on the range of Inf (stands for Information content)
we see three cases :
- stop with an exception if Inf<0.7
- accept the data if Inf>=0.96
- in between we see an heuristic to compute a number
of times extra data is obtained from the hardware and
remixed with xor/add operating on 32 bit words, like
while ( i < imax) {
input[i] = T_Sum_1 ^= Xtra[i] + input[i]; i++;
input[i] = T_Sum_2 += Xtra[i] + input[i]; i++;
input[i] = T_Sum_1 += Xtra[i] + input[i]; i++;
input[i] = T_Sum_2 ^= Xtra[i] + input[i]; i++;
}
Two minor odditities here:
a) T_Sum_1 and T_Sum_2 are not initialised anywhere, making the
result platform dependant (there is no effort either to make
the result endianness-independant).
b) lower bits are never influenced by any higher rank bits,
and very likely are thus less random; probably there are
also originaly less random, because they follow the start
edge (a known 1 to 0 transition) the UART has locked on.
Comments in the code suggest that when the port is operated at
115200 bps we have Inf like 0.9473 or 0.9491 so the remix probably
occurs, and at 57600 bps Inf like 0.9979 so the remix probably
does not occur; at least this is my guess..
As far as I understand the 32000 bytes of data is passed at the
higher level as data read from a standard IO stream. Clearly this
data is not random enough as is, especially the low order bits
which I bet is very measurably biased at this point at 57600bps
or higher. It seems a little dangerous (and inneficient) that
this medium-random data ever leaves the driver, but clearly the
intend is not to use this data as is : extra layers of software
are here to make sure this data is renewed at regular
time-of-clock intervals (I fail to understand the rationale;
I'd rather renew the data when it's entropy has bee used
for the better part) and postprocessed by extra layers of
cryptographic software.
Problem is : the algorithm is not documented. Here are, verbatim,
the best comments I could extract:
NOTICE! The streamcipher below is intended for the use in the
SG100 applicetion only. Do not use this cipher for secrecy
purposes.
WARNING! Misson critical code. Do not cange the constents,
as they implement aximum length shift registers with a length
of 828 and 804. Remainng tree registers are cyclic.
The construction of this method is based upon that any
large-memory chaotic function will generate some level of true
noise when iterated.
In this application it is suffiicent that the corelations in
the input is destroyed or concealed. Note that the method will
operate only on inputs with 96% information rates or higher.
Actually, it appears the "Maximum length shift registers with a
length of 828 and 804" are of 828*32 and 804*32 bits, and have
companion registers of 1361*32, 1049*32, 971*32 bits.
The implementation use assembly language macros in VC++ to perform
a rotate left by 11 here or by 5 there.
My exploration stop. I probably could further reverse-enginner the
algorithm, but I do not have the motivation.
In summary, it looks like the hardware does give a significant
source of random, if it works on a given UART/serial driver combo.
The low-level software does take reasonable care to detect grossly
malfunctionning hardware. Post-processing use a badly documented
algorithm, using over 16k byte of internal state variables.
Overall the software is too complex for my personal taste and
an easy source code review. The programmer is indeed very cautious
on error checking, but this is not enough to demonstrate the
implementation is correct. Arguably, the code can't be wrong
since it is the current definition of the algorithm !
Francois Grieu
[revised version of a previous post]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Quad. in RC6
Date: Tue, 19 Oct 1999 12:31:58 GMT
In article <7ughig$do6$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <7ufqii$u0n$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>
> > Yeah, that's where I get a little fuzzy. I'm not sure how the
> > multiplication is affected by a transform like that. I'm under the
> > impression that multiplication is affected by the lower bits more
than
> > the higher bits. Therefore, you want to retain as many of the lower
> > bits as possible. With the original 2x, which is equivalent to x <<
> 1,
> > you still retain most of the original bits. By adding 1, you are
> > creating an odd number.
>
> But you never actually lose entropy. It's a bijective function (1 to
> 1) so it can't create or lose any info. You are correct in assuming
> that for high values of a the quality of the diffusion is much less.
> However xcept for the fixed points the value is always going to
change.
>
> I think the last one I had
>
> f(x) = x(ax + b) + c
>
> along with the rest of RC6 would be much better. It would eliminate
> the *known* fixed points, and be a tad harder to attack. The problem
> is it would make the cipher much slower. You would need a fast
> multiplication as well as squaring. In software this might raise it
> from the current ~250 cycles to about 300-320. I wouldn't imagine it
> that detremental.
>
> > Like I said, I'm not sure. Shift's up to and including 8 probably
> won't
> > be too detrimental, if I understand binary multiplication correctly.
> > You're b will probably have to be picked carefully.
>
> Again you are assuming the rest of the cipher plays no role in the
> diffusion of key bits.
I never assumed that. I just think that most of it is determined by the
quad since that is used to rotate the plaintext and is mixed with the
plaintext.
>
> > How about f(x) = x * ((x >>> b) AND 1) where b <= 16? This would
> > probably have good diffusion and ensure an odd number in the second
> part
> > of the multiplication.
>
> You mean OR right? Otherwise this would not be bijective. How about
Ooops, yeah, that's what I meant.
>
> > This function is used to set up the data-dependant rotations, so
your
> > thinking is backwards if I understand it correctly. The goal of the
> > quad is to generate 5 bits to be used for the rotate. The results
of
> > the quad are also mixed in with the data using an XOR, however I
don't
> > believe that plays as significant of a role in the security of the
> > cipher as the data-dependant rotate.
>
> Another solution would be to construct four 8x5 sboxes and just xor
the
> result together. (Similar to blowfish). This way you can create high
> avalanche rotate values which are data dependant.
Interesting idea, but that only affects the rotate. You're forgeting
about the mixing of the quad values with the plaintext. I.e. the values
of the quads are also XOR'd to the plaintext before rotating. If we do
what you say with the S-boxes, where would we get the value that get's
mixed, or do you just use the original plaintext? Maybe rotate the
plaintext? Perhaps something like this:
t = s[b[0]] ^ s[b[1]] ^ s[b[2]] ^ s[b[3]];
u = s[d[0]] ^ s[d[1]] ^ s[d[2]] ^ s[d[3]];
b = b >>> 11;
d = d >>> 13;
a = ((a ^ b) <<< u) + k[i];
c = ((c ^ d) <<< t) + k[i+1];
The values for the set rotates don't have to be those exact values, but
they should probably be fixed.
>
> so we have
>
> f(x) = x(ax + b)
> f(x) = x(ax + b) + c
> f(x) = x(ax + b) >>> c
> f(x) = x(2x + b) + c
> f(x) = x(2x + b) >>> c
>
> The last four remove the *known* fixed point. The last two are faster
> in hardware and software. The fourth is faster in hardware and
> software then the fifth. I think #2 and #4 would be good bets since
> RC6 already has rotates.
Your third and fifth should not be considered because that would screw
up where you get your 5 rotate bits from. The fourth one looks best to
me.
>
> Of course for all 'a' = even, 'b' = odd, 'c' = integer (use lower five
> bits in rotate of course).
>
> Hmm just my two cents.
>
> Tom
Hmmmm, perhaps RSA will pay us for improving their cipher :-)
csybrandy
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks"
Date: 19 Oct 99 13:05:41 GMT
Ross Smith ([EMAIL PROTECTED]) wrote:
: If it has one member, then I fail to see how the
: situation differs from the aim of AES: one standard cipher that everyone
: can reasonably expect their suppliers to implement; any extra ones are a
: matter between suppliers and customers. If it has more than one member,
: then, as Bruce Schneier points out, you're imposing an unreasonable
: burden on implementors.
With one member, there is still the difference that informally many
vendors will include the same A, B, and C in addition.
John Savard
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: detecting backdoor in prime generator
Date: Tue, 19 Oct 1999 14:06:50 GMT
In article <7uhk9o$4em$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> Anton Stiglic <[EMAIL PROTECTED]> wrote:
> > > > Does someone remember the ref to an article talking about
> > > > detecting prime generators (or n = pq generators) that have
> > > > a backdoor?
This entire thread is lacking in rigor. Let us try to add some.
Please start by defining what it means for a prime generator to
have a back door.
Generally speaking, primes themselves don't have backdoors. A
public key can have a backdoor, but the public key has structure
over and above that possessed by a prime.
I suspect that any definition you come up with will be context
dependent, i.e. dependent on the USE of the prime. A backdoor for
RSA is not the same as a backdoor for DSA. I doubt you can define a
general backdoor for a prime generator.
So let me ask for a definition.
> > This is not at all for PGP.... It's for some theoretical
research...
> >
>
> What theoretic? You make up a random number and test it for
> primailty. If you are suggesting that one scheme may let composites
> thru you can always use two algorithms. The chances of both of them
> letting it thru is squared
No. Following a Miller-Rabin test with (say) a Lucas-Lehmer test is
much better than merely squaring the probability of being wrong.
A number must have special structure if it is to get past several
Miller-Rabin tests. That structure is then 'eliminated' by most
Lucas-Lehmer tests.
I suggest that those interested in this subject read Jon Grantham's
article in Math. Comp. in which he discusses the Frobenius test.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Tue, 19 Oct 1999 14:10:21 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Donald Welsh) wrote:
> *Geometry without the parallel axiom. There may be another term for
> it, which eludes me at the moment.
>
Hyperbolic geometry replaces the parallel axiom with:
Given a line and a point not on that line, there are infinitely many
lines that can be drawn through the point that are parallel to the
given line.
Spherical geometry replaces "infinitely many" with "no"
>
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
