Cryptography-Digest Digest #600, Volume #12 Sat, 2 Sep 00 23:13:00 EDT
Contents:
Re: Serpent S-boxes (again) (Mok-Kong Shen)
Re: Capability of memorizing passwords (Guy Macon)
Re: Capability of memorizing passwords (Guy Macon)
Re: Patent, Patent is a nightmare, all software patent shuld not be (Mok-Kong Shen)
Re: Extending RC4 to 16 bits (Guy Macon)
Re: one-time pad question (Guy Macon)
Re: QKD and The Space Shuttle (Guy Macon)
Re: Steganography vs. Security through Obscurity (Guy Macon)
Re: RSA public exponent (Eric Young)
Re: QKD and The Space Shuttle (-m-)
Re: QKD and The Space Shuttle (-m-)
Re: QKD and The Space Shuttle (-m-)
Re: QKD and The Space Shuttle (-m-)
Re: QKD and The Space Shuttle (-m-)
Elkies extention to Schoof's algorithm ([EMAIL PROTECTED])
Re: PRNG Test Theory (Benjamin Goldberg)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Serpent S-boxes (again)
Date: Sun, 03 Sep 2000 01:35:32 +0200
Mack wrote:
>
> The number of s-boxes satisfying these criteria were
> 30720 with no equation of order 2
> 36864 with one equation of order 2
>
> Only 2672 equations made up all of the
> s-boxes.
>
> The total number of s-boxes satisfying the
> criteria is 67584*24=1622016
Is there a typo? How does the figure 1622016 stand
in relation to 30720 and 36864? Are there 1622016
S-boxes that SATISFY all the criteria that you
have given? How many S-boxes really satisfy ALL
the criteria? Thanks.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Capability of memorizing passwords
Date: 02 Sep 2000 23:30:41 GMT
Mok-Kong Shen wrote:
>
>It is often said that it is difficult for people to
>memorize random passwords (commonly 8 characters). I am
>very surprised to read in a magazine that the record of
>memorizing a bit sequence, given a time of 30 minutes, is
>2745 bits! So brain's capability of processing random
>stuffs doesn't seem to be too bad after all.
>
>M. K. Shen
As I have worked on various secret projects for various companies,
again and again I have been asked to memorize some 8 to 16 character
password consisting of random letters and numbers. Every time I
get a new one I add it to the front end of a long memorized passphrase
that I use for my own encryption. The passphrase is now really long
and would be quite impossible to memorize if I started today, but I
can type it in correctly every time. Odd how the mind works.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Capability of memorizing passwords
Date: 02 Sep 2000 23:50:30 GMT
Paul Rubin wrote:
>
>
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>> Goofy. Use a large dictionary of 6-letter words (and below) to translate
a
>>> 128-bit sequence into a 10-word passphrase, easily memorizable. That's
what I
>>> did. Works easily.
>>
>>I suppose not everyone knows your technique. Could you
>>give an example that works, i.e. automatically translates
>>back to the arbitrarily given 128 bit?
>
>I think the idea is to make sure the passphrase has 128 bits of entropy,
>not to be able to recover the initial passphrase. But anyway, say there's
>8192 (= 2**13) words in the dictionary. Just choose 10 of them at random
>and use that as a passphrase, and there's your 128 bits.
Better than choosing 10 at random is choosing 12 and adding connecting
words and changing the order, tenses, and prurality so as to make a
recognizable english sentence that is nonsense, like "the blue thermion
qaucked into a puddle of feminist leafs, then seven polycarbonate
resistors squiggled against the violent doghouse". This is much easier
to remember than "blue violent resistor feminist quack puddle leaf
thermion polycarbonate seven squiggle doghouse" or even "violent resistor
feminist quack puddle thermion polycarbonate seven squiggle doghouse",
and is still quite impossible for an attacker to guess, even with software
that restricts guessing to recognizable english sentences.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be
Date: Sun, 03 Sep 2000 02:06:03 +0200
Paul Pires wrote:
>
> Not a dumb question. No it probably is not the patent. I don't
> know because I went to the IBM site I reccomended to you
> and downloaded the REAL patent. Ah!, maybe your talking
> about the page that comes up on the IBM site? No that's not it
> either. Look at the upper left hand buttons. One says
> "View images" This will show you the patent or you can pay
> $2.00 and download a PDF version to print.
>
> http://www.patents.ibm.com/details?&pn=US06061448__
>
> If you are interested in I.P. Always go to the source. Don't let
> people point you to a precis or a summary or a "laymans version".
> You can look at these but the patent is the patent.
>
> Bad news is that after reading it critically with my sparce knowledge,
> it still seemed practically void :-) Fell free to E-mail me direct if you
> need any pointers. I probably don't know the answer but I am cheerful.
Thanks. I had a look of the 11 pages on the web but the
(printing) quality of what I could view on the screen is
too poor for me to examine in full detail conveniently.
(Maybe my monitor is not good engough, I don't know.)
>From what I could see, it seems that the description is
indeed very 'general' (hence the patentability is questionable),
i.e. conforming to what you said above.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Extending RC4 to 16 bits
Date: 02 Sep 2000 23:55:10 GMT
Scott Fluhrer wrote:
>- Ignoring that, the idea of generalizing RC4 to include other bit sizes has
>already appeared in the literature. It may be a bit too late to try to try
>to place it under the quite restrictive Gnu copyright...
Did said literature conclude anything about the effect on cryptographic
strength?
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: one-time pad question
Date: 02 Sep 2000 23:58:57 GMT
Jim wrote:
>
>Mr. Ian E. Yolk wrote:
>
>>be done. The main reason that pure randomness is stressed in the
>>description of a one time pad is that the mathematical proof that the
>>method is secure depends on that provision, among other things. A
>>technically non-random pad might still be secure, but you won't be able to
>>prove it.
>
>So it must follow that, because the perfectly random key does not
>exist, that any and all OTP can be broken?
Perfectly random keys do exist, and we not knowing whether or not
an OTP with a nonrandom key can be broken is not the same as knowing
that it can be broken.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: 03 Sep 2000 00:03:06 GMT
Mary Shafer wrote:
>
>
>Markus Mehring <[EMAIL PROTECTED]> writes:
>
>> Sometimes, apart from that it's mostly nautical miles, the sensible
>> rest of the world uses kilometers instead. :)
>
>Even otherwise completely metric countries use knots for airspeed,
>nautical miles for distance, and feet for altitude in aviation. I
>suspect that referring to satellite altitude in miles is a
>continuation of this practice.
And you can still buy a Pint of beer in England and a Half Liter of
Cola in the US...
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Steganography vs. Security through Obscurity
Date: 03 Sep 2000 00:07:38 GMT
Mok-Kong Shen wrote:
>
>
>
>
>zapzing wrote:
>>
>
>> Don't you think it will look somewhat suspicious,
>> all this random data being sent around ?
>
>One of the best way, I suppose, is to publish some
>commonly useful data, e.g. some daily or weekly
>collected physical measurments, on a web page and embed
>the message data in them. That way it's difficult to
>trace out the recipients who access these to get the
>messages.
Usenet articles are better than web pages for this. An attacker can
monitor everyone who reads a web page, but it would be much harder to
monitor everyone who reads a newsgroup post.
------------------------------
From: Eric Young <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: Sun, 03 Sep 2000 00:24:47 GMT
Paul Schlyter wrote:
....
> >There is no reason one cannot use a large 'e' but that makes the RSA
> >public operation rather slow.
> >Normally with an 'e' of 2^16+1, the public operation will be 10-16
> >times faster than the private operation. If 'e' is the same size as d,
> >it will take about the same amount of time to do a public operation as
> >a private one (or probably slower since CRT could not be used).
> >Now while this may be nice for security, people would prefer to
> >trade irrationally long keys for performance.
>
> Is this really an issue nowadays? Aren't today's CPU's fast enough
> to do a full-length 1024-bit RSA operation, without CRT, in a fraction
> of a second anyway?
Yes but my server that does 500 web pages a second suddenly grinds down
to 60 per second once a single RSA private operation becomes involved.
SET is much much worse and I'm sure there are plenty of applications
that involve lots of signing and/or verification on the server, so the
nature of the algorithm and application becomes important.
For client, user interaction based application (PGP) RSA private operations
are now fast enough (except for some low power embedded devices);
for server farms, it needs all the help it can get.
While I'm on this track, I should also mention that ciphers that need 128k
of data (as mentioned recently in the RC4 variant) will also be rather ugly
for servers. If we have 100 concurrent connections, each of which will
have 256k of random access memory associated
(two directional channel), the OS
cannot swap the data out (it will be in the working set) and will not be
reused as a data buffer that is first MACed and then encrypted and then
copied into kernel space will be, so the cache will also be thrashing.
So we need an extra 128meg AND we get the bonus of cache thrashing;
perhaps 3DES is not so bad :-). I will not go even mention
multi-cpu boxes :-).
The problem now days in the connected world there are only two classes of
services (outside of intranets), those that take a hit every hour/day or so
and those that are being thrashed and can never be fast enough.
It is this second class that performance and the nature of the algorithm
matters :-).
And just for the record, the best general CPU in terms of
1024bit RSA private key operations per mhz that I am aware of is
433 1024bit RSA private (2 prime, using CRT) on a 466mhz Alpha 264.
And while this is plenty fast, if we were serving 500 pages a second,
we would probably drop down to at most 200 pages if an RSA private
is involved in each transaction. And yes, hardware can be used,
but this costs money, (and lets not even get into the issue of key
security, most applications don't :-).
eric (trying to relate performance to $ :-)
------------------------------
From: -m- <[EMAIL PROTECTED]>
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Sat, 02 Sep 2000 21:15:07 -0400
David A Molnar wrote:
>
> In sci.crypt Ron B. <[EMAIL PROTECTED]> wrote:
>
> > Good questions. _But_ how is ths relevant to sci.cript and
> > talk.politics.crypto ?
>
> "Give me a random beacon and I shall secure the world..." - some greek
You already have a random beacon. YOU have not found it. Actually you
have many, many truly random sources of information. The trick is not
to find a random source of data but to agree upon one....
It is odd to me that the worlds best math guru's can be so blind.
But then I am an insane idiot and thus you folks may discount me as much
as is convienent.
------------------------------
From: -m- <[EMAIL PROTECTED]>
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Sat, 02 Sep 2000 21:20:02 -0400
Mok-Kong Shen wrote:
>
> David A Molnar wrote:
> >
> [snip]
> > The problem with all of these protocols is that if an adversary can
> > replace the random beacon with his own source, all bets are off.
> > So some people would *like* to see a satellite in the sky broadcasting
> > random bits to the world. There will still be issues with ground-side
> > jamming and with authentication of the satellite, though, which are
> > not yet fully ironed out (at least not that I've seen).
>
> Isn't the trouble in principle the same with certification
> where one needs some trust/belief on a third party,
NO.
> in
> other words there is some non-objectivity that can NEVER
> be entirely disposed of?
NO.
>
> M. K. Shen
That occurs when a third party is involved. There are situations when
only two parties are involved. Thus the process of authentication is a
recursive process which must start with a (2) TWO party exchance of
authentication and not a (3) three party authentication.... mutually
trusted partners are a vulnerability which simply can not be tolerated
in an authentication system. Perhaps that is what you said, in the
first place?
------------------------------
From: -m- <[EMAIL PROTECTED]>
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Sat, 02 Sep 2000 21:28:35 -0400
David A Molnar wrote:
>
> In sci.crypt Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > Isn't the trouble in principle the same with certification
> > where one needs some trust/belief on a third party, in
> > other words there is some non-objectivity that can NEVER
> > be entirely disposed of?
>
> There is a trusted third party in both cases, yes.
1) There is NO trusted third party.... Tenet ONE.
> The kind of trust we need seems slightly different.
> In the CA case, we need to trust that the CA properly identifies
> people and keeps its private signing key secure. Plus the usual
> computational assumptions if something like RSA is used.
>
> In the random beacon case, we need to trust that the beacon
> really "is random."
WE DO NOT NEED A RANDOM BEACON. DAMN, and DOUBLE DAMN!!!!! And all
shouting aside. We NEED to AGREE on a random beacon... Security in an
encryption function is dependent upon the length of the DATA stream as
well as the randomness of the key stream... Is there anyone,
listening? Get past the ego trip of trying to figure out a way to
generate truly random data and realize that it has already been done.
>
> Your non-objective call which you think is a stronger set of assumptions.
>
> Personally the random beacon seems weaker (building a hardware RNG seems
Actually it seems to be a waste of time...
> like something which can be more precisely engineered than a PKI),
It does not need to be engineered...
> assuming that we can tell if we're talking to the correct random beacon.
Never mind, I have to assume that you believe there are NO secrets.
> *That* I'm not sure how to satisfactorily solve.
That, you will solve when you decide that people actually are able to
share secrets...
>
> -David
------------------------------
From: -m- <[EMAIL PROTECTED]>
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Sat, 02 Sep 2000 21:31:37 -0400
Richard Bembridge wrote:
>
> "Jeffrey Williams" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Additionally, what does QKD stand for?
>
> Quantum Key Distribution.
>
> Public key cryptosystems are 'asymmetric' - the key used to encode the
> message is different to that used to decode the message.
>
> Symmetric cryptosystems uses one key to do both jobs.
>
> A good example of a symmetric system is the Vernam cipher, AKA 'the one-time
> pad'.
> This system is provably 100% secure (given that the key used is
> *random* - I don' want to start a debate on random numbers! Sorry.)
Not an issue, random numbers are available.
>
> So, if a satellite can beam keys all over the world, then we can all use
> 100% secure cryptosystems. Because public key systems are not 100% secure.
> They are *virtually* 100% secure, but not totally 100% secure.
>
> If the (and again I am being hypothetical here - I don't want to start a
> debate just yet!) mooted Quantum Computer ever takes off and gets a register
> big enough, then it will exhibit *massive parallelism* - in other words it
> can work on millions (say) of problems at once.
>
> Hence the argument is that Quantum Computers may spell the end of public key
> cryptography as we know them, but...
> Quantum Key Distribution may pave the way for guaranteed security.
>
> The NSA in the US and the RIP Bill in the UK can go kiss my hairy behind.
:)
>
> This leads on to all kinds of philosophical questions. And I'm tired now. I
> must get back to my dissertation: Quantum Cryptography - Is Quantum Key
> Distribution Technologically and Socially Viable?
Quantum Key distribution is not necessary...
>
> RMB
------------------------------
From: -m- <[EMAIL PROTECTED]>
Crossposted-To: sci.space.shuttle,talk.politics.crypto
Subject: Re: QKD and The Space Shuttle
Date: Sat, 02 Sep 2000 21:33:03 -0400
Hello John...
Your writings seem to be everywhere.
-Oz
John Savard wrote:
>
> On Wed, 30 Aug 2000 20:53:22 +0100, "Richard Bembridge"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >What kind of payloads can the Shuttle handle?
>
> The Space Telescope represented the upper limit.
>
> >What is the typical altitude of the Shuttle when in Low Earth Orbit (LEO)?
>
> About 250 miles.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Elkies extention to Schoof's algorithm
Date: Sun, 03 Sep 2000 01:33:10 GMT
The well-known Elkies extention to Schoof's point counting algorithm
for eliptic curves defined over GF(p) supplies candidates for certain
values of #E mod q, a small prime. How can this information be best
used to speed up the final stage of a hybrid algorithm that combines
the information gathered from Atkins primes via the Chinese Remainder
Theorem and then uses this value of #E mod n (the product of the small
primes) to speed up a final stage search using Pollard's algorithm?
One possible idea that I contemplated involves enumerating all of the
possible values for #E mod n. This introduces a combinatorial bloom
that quickly overwhelms the benefits for using Elkies prime information
in the first place. Do most point counting implementation discard this
information with using it?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: PRNG Test Theory
Date: Sun, 03 Sep 2000 02:18:06 GMT
Trevor L. Jackson, III wrote:
>
> Benjamin Goldberg wrote:
>
> > Trevor L. Jackson, III wrote:
> > >
> > > Paul Pires wrote:
> > >
> > > > Yes but there is an interesting question here. Can rejecting
> > > > Non-random (determined by any means) ever result in random? My
> > > > Knee jerk reaction is no but I never thought of it that way
> > > > before.
> > >
> > > The answer is clearly no for finite rejection tests. Consider
> > > that a set of tests that deals only with the most recent N bits of
> > > output must enter a cycle with length < 2^N.
> > >
> > > For rejection systems that deal with all of the output (finite in
> > > each instance, but ever-increasing), but have a description of
> > > "random" of finite size must also enter a cycle (*) because a
> > > finite description of "random" permits only a finite criteria for
> > > choosing the next bit. The N-bit definition of "random" provides
> > > only 2^N fitness values. So as the output sequence grows the
> > > collisions among the fitness results will increase in frequency
> > > until they dominate the generator.
> > >
> > > I have not spent the time to prove that the increasing collision
> > > frequency actually forces a cycle, but I believe this can be
> > > shown.
> > >
> > > (*) this assumes that when the fitness of the prefix+'0' sequence
> > > is identical to the fitness of the prefix+'1' sequence a
> > > deterministic selection is made; say alternation.
> >
> > What if, when prefix+'0' and prefix+'1' are equally fit, the
> > generator then selects from among prefix+'00', prefix+'01',
> > prefix+'10', prefix+'11'. If there is no clear best suffix, or no
> > best first bit for the suffix, look at length 3 suffixes, etc.
>
> There seems to be no particular point to extending the analysis. In
> principle if the prefix+0 and the prefix+1 fitnesses are equal then
> the "randomness" of the two sequences are equal. So there is no
> reason to care.
Untrue. Please remember that our 'randomness' uses an entire string as
input. It's entirely possible for prefix+1 and prefix+0 to the same
'randomness' value but for prefix+00, prefix+01, prefix+10, and
prefix+11 to all have different 'randomness' values.
> It may help to apply your extension thoroughly and see what happens.
> In theory a perfect randomness criteria would accept any sequence as
> random because a truly random source is just as likely to produce it
> as it is likely to produce any other sequence. So there is no
> criteria that can be used to distinguish between equally likely
> sequences.
>
> Note that this indifference cannot be eliminated. It derives from the
> fact that randomness is not a property of a sequence, but of a source
> (generator).
>
> If you look into the generation of the classical randomness tables
> (e.g., Rand) you'll find that the data was heavily edited to remove
> artifacts that looked orderly. Of course such editing produces an
> unlikely distribution, so the result is clearly distinguishable from
> typical (as opposed to truly) random output.
I must admit that this is indeed a problem with this generator: If you
have bits 0..x of the stream, you can, with 100% certanty and with no
more work than it took to generate in the first place, predict the x+1st
bit of the stream. Hidden state is a Good Idea in a PRNG, and this one
doesn't have any.
> It is interesting to note that if you encode some of this
> meta-analysis into the criteria for generating output you form a level
> crossing self reference. Which brings up the issue of decidability.
Umm, what's "level crossing self reference?"
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
** 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
******************************
