Cryptography-Digest Digest #948, Volume #10 Fri, 21 Jan 00 14:13:01 EST
Contents:
Re: Forward secrecy for public key encryption: MYH (David Wagner)
Re: Combination of stream and block encryption techniques (wtshaw)
Re: Mispronounce words. (OT ) (wtshaw)
Re: LSFR (Mike Rosing)
Re: MIRDEK: more fun with playing cards. ("r.e.s.")
Is Cramer-Shoup 98 with 5020 bits secure? (Oliver Moeller)
Re: UK Government challenge? (Angus Walker)
Re: ECC vs RSA - A.J.Menezes responds to Schneier (Mike Rosing)
Re: MIRDEK: more fun with playing cards. ("r.e.s.")
Re: Intel 810 chipset Random Number Generator (Paul Koning)
Re: NIST, AES at RSA conference (Paul Koning)
Re: simplistic oneway hash (Paul Koning)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Forward secrecy for public key encryption: MYH
Date: 21 Jan 2000 10:19:43 -0800
In article <[EMAIL PROTECTED]>,
David Hopwood <[EMAIL PROTECTED]> wrote:
> I think that answers your question :-)
Yup, thanks. :-)
Ok, I see you are way ahead of me.
By the way, thanks for the explanations
of why these attacks don't work.
-- David
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Combination of stream and block encryption techniques
Date: Fri, 21 Jan 2000 12:32:29 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> In most cases there *is* a clear difference between a "stream" cipher
> and a "block" cipher; it's essentially the same as the difference
> between a continuous-flow chemical process and a batch process.
OK, welcome to truths of production analagous to crypto processes, fine
with me. It clearly makes my favorite invented algorithm one of the batch
variety, but with a short-term need for continuous-flow type
mechanization.
The problem with continuous flow is that sooner or later something breaks,
gets used up, or starts to malfunction. This could be a few minutes to a
few months, with the workaround for failure called preventive maintenance,
which means you periodically stop, clean up, and restart everything.
On an electronic processing level, we do the same things, expecially if
something like windows, more a batch system, as compared to Mac, which is
more a stream system which generally takes care of certain headache
problems seen in windows automatically.
As for cryptosystems, if the generator runs out, recycles, your stream
turns out to be a long batch. If you select a stream method that restarts
and resets itself, even inductively, it is a batch in some ways. It seems
that much of this is your choice, with little absolute differences between
potential stream and block ciphers.
--
To prevent the comprimise of with the most common configuration
of computers is something like preventing a sculptor from being too original. If a
computer design is corruptable, it will be.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Mispronounce words. (OT )
Date: Fri, 21 Jan 2000 12:41:02 -0600
> My question was the echo of my question as a child for whom spelling
> was not logical, but thanks to all who explained the etymology.
>
> > I was told by a foreign friend that the normal rule for English is
> > that the emphasis is on the third syllable of the word. Hence the..
The best universal rule in such things in English is that there is no
universal rule. Of course, you can pick French, which THEY say is always
right, German, which is better ronounced with a beer under your belt,
Russian, which is best pronounced while mad, or Italian, which sounds best
in an argument.
--
To prevent the comprimise of with the most common configuration
of computers is something like preventing a sculptor from being too original. If a
computer design is corruptable, it will be.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: LSFR
Date: Fri, 21 Jan 2000 12:23:24 -0600
r.e.s. wrote:
>
> "David Wagner" <[EMAIL PROTECTED]> wrote ...
> [re 10-register base-10 LFSR]
> : I think you need to look at the feedback polynomial
> : mod 2 and mod 5. If both of those are primitive, I'd expect the
> : period to be either (2^10 - 1) * (5^10 - 1), 2^10 - 1, 5^10 - 1, or 1.
> :
> : For example, if I initialize the register with all zeros, it stays all
> : zeros. If I initialize the register with values that are all even,
> : it stays this way. If I initialize the register with values that are
> : all divisible by 5, this too stays the same. So (at best) there will
> : be four cycles, one of each of the lengths mentioned above.
I think you are correct that the coefficients should be modulo a prime
to create a field. But I'm not sure about getting maximal length for
an LFSR. There should be some primitive polynomial even mod 10 that
would give (10^n-1) elements. You'd have to start with an odd number
tho.
> OK. In that case, since I'm interested mainly in the n-register LFSR
> with x(i) = x(i-n) + x(i-n+1) (mod 10), where there are n initial values,
> I have two main questions -- sorry to be so pedestrian about this:
>
> 1) Is the polynomial x^n + x^(n-1) + 1 primitive as required?
Maybe. You might have to hunt for an n such that it is primitive.
> 2) If so, is the proportion of possible initial-value vectors that
> produce the maximum cycle length just (2^n - 1)(5^n - 1)/10^n?
I don't know, that's a really good question. But I'd guess it's less,
something like 1 - [(2^n-1)(5^n-1) + (2^n-1) + (5^n-1) + 1]/10^n.
> And third, a more practical question, being optimistic about the first two:
>
> 3) Wouldn't non-linear post-processing effectively destroy vulnerability
> to Berlekamp-Massey? (For example, collect a few rows of output digits,
> n digits per row, then read them out by columnar transposition.)
>
> Although these methods were used in the "VIC" cipher (with n=10) to key
> a double transposition, couldn't they be used with larger n to get
> something adequate as a stream cipher, still workable by hand?
>
> (n registers would yield ~n/0.3 bits of entropy; also, if the above
> questions have optimistic answers, it looks like there's only a 1/2^n
> chance of missing the maximum cycle-length.)
I'm not sure I understand what you mean by post-processing. But I
suppose
if the output is munged more after the lfsr, it will help hide the lfsr.
It should be interesting to code up and play with. See if there's an n
in the range of 5 to 8. And don't stick with 1 for coefficients, try
them
all.
The only other question I have would be how to evaluate the lfsr: do we
need to take x^i for the i'th tap? In binary it's 1 or 0, there's no
question. But for mod B, I'm not so sure.
Patience, persistence, truth,
Dr. mike
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Fri, 21 Jan 2000 10:38:03 -0800
It's simple to use a 4x13 card layout to implement the *exact* ARC4
logic with state-vector length 52 (and modular addition combiner.)
The only card-movement is the swap, which takes about 1 second, and
the pointer(coin)-movement takes about 10 seconds for both pointers
total. I can easily run off 14-15 letters per minute this way, so
I think this version of "52 card ARC4" is faster than any other
secure card cipher.
Also, as I already posted, you can shuffle the deck to initialize
the state vector if you want randomization. My suggestion was to
not specify the initialization method as necessarily being ARC4's,
but to instead leave it up to the user. (But ARC4's keying method
could easily be adapted for using passphrases with "52-card ARC4.)
Concerning the alleged bias in ARC4, imo it's so small as to be
negligible in the context of hand ciphers.
--
r.e.s.
[EMAIL PROTECTED]
"Paul Crowley" <[EMAIL PROTECTED]> wrote ...
[...]
: I'm not
: surprised to learn that it's fast, but finding enough table space to
: lay out all the cards is a pain, and when you do the arithmetic as you
: suggest you're looking at a very different cipher than RC4 - possibly
: one far more biased. If you ever code it up, though, please let us
: know and I'll do some statistics on the output.
[...]
: I also think that only randomised ciphers are practical proposals,
: since you can't keep exchanging keyphrases! So I'd be interested to
: hear ideas about how to make a randomised cipher out of ARC-13-4.
[...]
------------------------------
From: Oliver Moeller <[EMAIL PROTECTED]>
Subject: Is Cramer-Shoup 98 with 5020 bits secure?
Date: 21 Jan 2000 19:31:35 +0100
Hi everyone,
Maybe it is not custom to place a 'bet' in this newsgroup, but I nevertheless
will (see http://www.brics.dk/~omoeller/sub/challenge.html ).
In Crypto'98, Cramer and Shoup presented a public key crypto system, that is
not compromised by 'lunchtime attacks' (ie. if an eavesdropper can use your
terminal during lunch to decrypt some chosen messages, it does not help him
later on to decrypt a (unseen) message.)
I was wondering how tedious it would be to implement it and whether it would
be very slow - to my surprise, it is not too bad in both respects. But I had
to diverge from original suggestions. I am wondering, if they compromise
security, like:
When generating the key, generators of the prime modulus p have to be
found; my way to do that is to chose p in a way, that all prime factors
(q_1...q_n) of p-1 are known. Then by Fermat, for g in {2,...,p-1}
g is a generator of p iff (for all i) g^((p-1)/q_i) =/= 1 (mod p)
Then generators can be generated by picking random numbers and checking for
that property.
(This is a generalisation of the method suggested in [CS98], 5.1)
Key generation seems to be very tedious. It took about 3 weeks on a 130MHz PC
to generate a key with a 5020bit prime modulus. In this case, it takes about
120 minutes [heavily dependent on architecture] to en/decrypt with a Java
implementation, so it is not of 'industrial interest', but feasible, if small
amounts of data are to be sent sparsely. Moreover, you can do it with a web
browser without installing any software.
The largest key I was able to generate is a 5020 bit prime modulus p
(where p+1 has one very large prime factor). I did not carefully estimate what
kind of (standard) machinery it would take to break this with known discrete
log algorithms, but it should be beyond hopes with brute force algorithms.
Is there a leak that compromises security?
In fact, the used key has a _special_ property that might be the
known-ciphertext attack easier: In, p-1 one of the small prime factors occurs
twice. Possibly, this could be exploited.
But my bet is, that this does not help.
In fact, I'm offering a prize of 1000,- Danish Kroner (admittedly not a
fortune, about 140 US-$) for the one, who would manage to retrieve the
original message text, given the cypher text and my public key:
http://www.brics.dk/~omoeller/sub/challenge.html
I strongly believe, that this cannot be done in practice - but if I am proven
wrong here, I think it's worth the money.
Cheers,
- oli
Ref.:
[CS98] Ronald Cramer and Victor Shoup: A practical public key crypto system
provably secure against adaptive chosen ciphertext attack. in proceedings of
Crypto 1998, LNCS 1462,p.13ff
+-----------------------------------------------------------------+
| M. Oliver M"oller |\ _,,,---,,_ |
| Department of Computer Science /,`.-'`' -. ;-;;,_ |
| Ny Munkegade, building 540 - B3.14 |,4- ) )-,_..;\ ( `'-' |
| DK-8000 Aarhus C, Denmark '---''(_/--' `-'\_) |
| Email: [EMAIL PROTECTED] Phone: (+45) 8942 3274 |
| URL: http://www.brics.dk/~omoeller Fax : (+45) 8942 3255 |
+-----------------------------------------------------------------+
------------------------------
From: Angus Walker <[EMAIL PROTECTED]>
Subject: Re: UK Government challenge?
Date: Thu, 20 Jan 2000 08:57:00 +0000
>We couldn't be bothered to look for the 5th,
>since just the four made the message clear, and we can guess the other
>one.
Couldn't be bothered or couldn't find it? I'm up to four now too
(thanks to being told the fourth one!) Is it the one that probably says
ONE!N that you have left?
--
Angus Walker
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: ECC vs RSA - A.J.Menezes responds to Schneier
Date: Fri, 21 Jan 2000 12:40:47 -0600
Bob Silverman wrote:
> You need a DEDICATED, tightly coupled parallel processor with enough
> memory. (it will need to have 64-bit processors). And this means
> someone has to PAY for such a machine.
Correct, I was assuming direct connections. Just off the shelf
hardware.
> Also please note that I have seen it suggested that in some cases,
> one might want to use keys as big as 3000 bits (or so). The matrix
> for such a key can't even be addressed on a 64 bit machine. I don't
> see 128 bit processors coming any time soon. [and 10^22 bytes of memory
> is going to be expensive!]
Actually many game machines today are 128 bit processors. They
are just vector processors tho, not useful for this application.
But I agree that the total ram would slow down even the NSA :-)
> We will not see any improvement in algorithms. The block-Lanczos
> algorithm is about as close to the theoretically best possible as
> any algorithm in existence. (Theoretical best possible is
> Omega(N^(2 + epsilon)) for any epsilon > 0 (maybe depending on N).
> B-L achieves O(N^2 d)
> where d is avg. density per row. Even in practice now, epsilon is
> small (.25 or so)
So we're back to hardware: can we build a dedicated processor that
solves this problem quickly. Sure, but it'll cost a lot of millions
of any currency you want to mention!
> But Lenstra's paper argues that space is not an issue and says 1024
> bit keys are safe only for a couple more years. Further, his paper
> uses the very model of computation I discussed above: free idle time.
> And that just won't work.
>
> Yet many have latched onto his paper as if it were gospel.
It's conservative. From a practical stand point it may well be
silly, but academics don't care about practicality. Since it's
_possible_ to build a device that can crack 1024 bits, it doesn't
matter that it's impractical.
I'll keep my 1024 bit PGP key. It still works ok on a 40 MHz 68040 :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Fri, 21 Jan 2000 10:56:26 -0800
"Paul Crowley" <[EMAIL PROTECTED]> wrote ...
: "r.e.s." <[EMAIL PROTECTED]> writes:
: > For ARC4 using 54 cards in the way I described, it's certainly 52!,
: > because the jokers are used strictly as pointers.
:
: The position of the pointers is part of the state of both pure ARC4
: and ARC4-52, thus 52! * 52 * 52.
I disagree. Your two extra factors of 52 have no counterpart in any
free selection of values. The pointers are required to be initialized
as x=y=0, and are thereafter completely determined by the algorithm's
way of managing the evolution of the 52-element state-vector.
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Crossposted-To: sci.physics
Subject: Re: Intel 810 chipset Random Number Generator
Date: Fri, 21 Jan 2000 13:39:35 -0500
Michael Kagalenko wrote:
>
> Paul Koning ([EMAIL PROTECTED]) wrote
> ]Of course they do. But their signal to noise ratio is high.
> ]If you're after noise, then you want a source that has a low
> ](preferably negative) signal to noise ratio. Crystals fail
> ]that criterion by a very large margin, which is why no competent
> ]designer uses them for this purpose.
>
> That's fair comment, however note, that quartz crystals are a very common
> component of digital equipment, and atomic time standard is available
> via internet. You can produce thermally random
> data by measuring the clock drift against more precise clock (first
> you'd have to find out the crystal frequency, of course). To elaborate
> a bit, if t is precise time, and t' is the time measured by quartz
> oscillator (reclaibrated by using t to avoid systematic drift),
> then
> <t-t'> = 0 (1)
>
> (<> stands for math. expectation), however, that does not
> mean that there is no drift, but that drift in both directions is equiprobable
> (the recalibration I mentioned above consists in making sure that (1)
> holds)
>
> If the drift can be assumed to be brownian random walk,
> the average square drift < (t-t')^2 > grows linearly with time
>
> < (t-t')^2 > = constant * t
I'm not sure what you mean by "thermally random data". It seems
that you're making a pile of assumptions that may or may not
be valid.
The error of a crystal oscillator comes from a number of components.
First of all there's the manufacturing tolerance of the crystal,
typically 0.01%. Note that in practice this means the error is
close to -0.01% or +0.01%, a bimodal distribution. It's a bad
mistake to think of crystal frequencies as normally distributed!
Then there's drift, caused by temperature variations of the
crystal, and also by parameter changes in other components of
the oscillator (which might include things like power supply
voltage). Since you mention "thermally random" it sounds like
you're assuming temperature-induced drift is a random function.
I'd challenge that. In a typical temperature-controlled environment
(e.g., a building) it will have a significant periodic component
because the temperature control system is a servo system.
There probably is a random component in the frequency variation.
If you're hard up for a challenge I suppose you could try to
extract that from underneath all the other components. But for
goodness sake, WHY? It would be vastly harder, and the bit rate
vastly slower, than sensible solutions such as a regular noise
source.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Fri, 21 Jan 2000 13:41:31 -0500
Mok-Kong Shen wrote:
>
> Serge Vaudenay wrote:
> >
>
> > Actually, if an expert do not have any personal interest about AES, he
> > should better wait
> > for the final standard before doing some substantial work. In the
> > meanwhile he can work
> > for other standards.
>
> Very probably I misunderstood. But my (superficial) interpretation
> of your sentence means that the AES winner would not have got much
> study by the majority of the experts at the time point the winner
> is declared to be a standard by NIST for use by people of the
> whole world. That's pretty bad, isn't it?
Yes, but is it true? Admittedly I'm only an interested amateur,
but it sure looks like a significant number of the big names
of (non-classified) cryptography are involved.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: simplistic oneway hash
Date: Fri, 21 Jan 2000 13:49:56 -0500
[EMAIL PROTECTED] wrote:
>
> I have what is probably a rather unusual request. I need a very simple
> to code and understand one-way hash. I don't care a great deal as to
> whether it is truly secure at all, as long as it can be implemented
> in no more than a couple dozen lines of code in Fortran 90.
> ...
> 1) It must be simple to code (no more than a couple dozen lines)
> 2) It must be collision free
> 3) It must be relatively one-way (such that they won't be tempted to
> take a short-cut. we'll still look to make sure they really wrote
> they code, which is the most important part).
Well, CRC is a nice example of a hash function that isn't secure.
Would that do? It's trivial to implement. Then again, if you know
enough algebra it fails requirement (3).
paul
------------------------------
** 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
******************************
