Cryptography-Digest Digest #192
Cryptography-Digest Digest #192, Volume #14 Fri, 20 Apr 01 14:13:00 EDT
Contents:
Re: First cipher (David Wagner)
Re: Basic AES question ("Paul Pires")
Re: Minimal Perfect Hashing (David Wagner)
Re: Distinguisher for RC4 ("Tom St Denis")
Re: Reusing A One Time Pad ("Mark G Wolf")
Good textbooks on information theory (Joe H Acker)
what crypt algo is the smallest to code? ("diediedie")
Re: First cipher ([EMAIL PROTECTED])
Re: what crypt algo is the smallest to code? ("Tom St Denis")
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Douglas A. Gwyn")
Re: First cipher ("Tom St Denis")
Re: First cipher ([EMAIL PROTECTED])
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: First cipher
Date: 20 Apr 2001 17:00:26 GMT
How about something a little more
useful, like pointers on how to cryptanalyze my cipher so I don't bug
the group with the obvious?
Unfortunately, I don't know of any single good book on cryptanalysis,
but Biham and Shamir's _Differential cryptanalysis of the Data Encryption
Standard_ is a pretty darned good starting point. I've heard that this
book may be out of print; if so, the next-best alternative is to go to
Biham's web page and read his papers on differential and linear cryptanalysis.
--
From: "Paul Pires" [EMAIL PROTECTED]
Subject: Re: Basic AES question
Date: Fri, 20 Apr 2001 09:57:41 -0700
Tom St Denis [EMAIL PROTECTED] wrote in message
news:YIZD6.9551$[EMAIL PROTECTED]...
"Paul Pires" [EMAIL PROTECTED] wrote in message
news:UzZD6.16354$[EMAIL PROTECTED]...
Tom St Denis [EMAIL PROTECTED] wrote in message
news:v5ZD6.9193$[EMAIL PROTECTED]...
"Lou Grinzo" [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]...
Thanks to Paul and the others for responding.
As best I can tell from the replies, there doesn't seem to
be a technical reason for limiting keys to those three
sizes. General crypto theory strongly implies that using
other key sizes would have the predictable effect on the
strength of the encryption (longer == stronger), but that
hasn't been tested and proved to be the case. Correct?
No whoever tolds you "longer == stronger" is an idiot. Look at designs
like
LOKI89 and FEAL as compared to DES and come back to the group :-)
If you are going to make comparisons, don't you think they should
be apples to apples? How can you say anything about the effect
of the keysize if you are testing the idea on Algo A versus Algo B??
Because if you followed the argument it was about "does longer keysize
generally mean stronger". I was trying to show (in a futile attempt to use
intelligence) that while LOKI used a longer key than DES (LOKI was suppose
to be a "replacement") it was easier to break...
Anyways LALALALALALALALALALALALALALALA
So glad I took the time to craft a reasoned and thoughtfull question and
supplied my thoughts on the subject (snipped and ignored).
If I just zipped off something snide to trivialize your point you might have
just blown me off.
Paul
Tom
--
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Minimal Perfect Hashing
Date: 20 Apr 2001 17:01:44 GMT
At 48 bits, nothing is truly "one way" - with some weeks of
precomputation, you could use the Hellman time/memory tradeoff to
build a store that would answer any preimage query in milliseconds. If
I'm thinking about this right, it should be especially easy to use
this on a bijective function.
In fact, on a bijective function, it's even easier: the
complexity per query goes down from ~ 2^32 to ~ 2^24.
--
From: "Tom St Denis" [EMAIL PROTECTED]
Subject: Re: Distinguisher for RC4
Date: Fri, 20 Apr 2001 17:03:46 GMT
"David Wagner" [EMAIL PROTECTED] wrote in message
news:9bppjj$9dq$[EMAIL PROTECTED]...
David Formosa (aka ? the Platypus) wrote:
RC4 is a streem cyper/pydorandom number generator, while 3DES is a
block cyper. You can't replace RC4 with 3DES in most situtations.
Nonsense. You can replace RC4 with 3DES-counter mode or 3DES-OFB mode.
I would suggest countermode since at least you're guaranteed a lengthly
period.
Tom
--
From: "Mark G Wolf" [EMAIL PROTECTED]
Subject: Re: Reusing A One Time Pad
Date: Fri, 20 Apr 2001 12:22:59 -0500
Before patenting CryptoSauce, be sure you are not using Dynamic
Substitution.
And what is this dynamic substitution of which you speak?
--
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: Good textbooks on information theory
Date: Fri, 20 Apr 2001 19:26:50 +0200
Hi folks!
I already know a bit about information theory and once r
Cryptography-Digest Digest #192
Cryptography-Digest Digest #192, Volume #13 Mon, 20 Nov 00 16:13:00 EST
Contents:
recurrence ([EMAIL PROTECTED])
Re: simple proof ("William A. McKee")
proof of equation ([EMAIL PROTECTED])
Re: recurrence ([EMAIL PROTECTED])
Re: proof of equation (Francois Grieu)
equation problem ([EMAIL PROTECTED])
how can we show this ([EMAIL PROTECTED])
Re: Total $ spent on voice encryption (John Savard)
Re: Cryptogram Newsletter is off the wall? (Mike Rosing)
Re: How to hash a 50 MB byte file? (Bill Unruh)
Re: Questions about DES ("M.S. Bob")
More about big block ciphers ("Manuel Pancorbo")
Re: A poorman's cipher (Mok-Kong Shen)
Re: proof of equation (Mok-Kong Shen)
Re: [Question] Generation of random keys ("Michael Scott")
Re: Total $ spent on voice encryption (Thomas Kellar)
Re: simple proof (James Felling)
Re: Cryptogram Newsletter is off the wall? (Mok-Kong Shen)
Re: [Question] Generation of random keys (Mok-Kong Shen)
Re: [Question] Generation of random keys ([EMAIL PROTECTED])
Re: Mode of operation to maintain input size with block ciphers?
([EMAIL PROTECTED])
From: [EMAIL PROTECTED]
Subject: recurrence
Date: Mon, 20 Nov 2000 16:04:49 GMT
Consider finding Linear_Search's average cost using an argument like
that used for Binary_Search's average cost. If p is the probability
that X equals any of the n elements of L, then Linear_Search's average
cost is
f(n) = 1(for n =1)
f(n) = 1+(1-p)f(n-1)(for n1)
How can we solve this recurrence
Sent via Deja.com http://www.deja.com/
Before you buy.
--
Reply-To: "William A. McKee" [EMAIL PROTECTED]
From: "William A. McKee" [EMAIL PROTECTED]
Subject: Re: simple proof
Date: Mon, 20 Nov 2000 16:10:36 GMT
Write out the series:
f(n) = 2^0 + 2^1 + 2^2 + ... + 2^(n-2) + 2^(n-1)
you can see the + 2^(n-1) term at the end of the series, so look a the rest
of the series and if you substitute 2^(n-2) for 2^((n-1)-1) you get f(n-1)
next, 2^0 is 1, so you get the + 1 term, now divide the rest by 2 and you
get
f(n) = 1 + 2 (2^0 + 2^1 + ... + 2^(n-2))
look familiar? you get f(n-1) again.
Now prove. f(n) = 2^n - 1 :)
--
William A. McKee
[EMAIL PROTECTED]
http://www.cjkware.com/wamckee/
Asia Communications Quebec Inc.
http://www.cjkware.com/
"We're starfleet: weirdness is part of the job." - Janeway
"I have seen things I cannot deny." - Scully
[EMAIL PROTECTED] wrote in message news:8vbfs5$dqv$[EMAIL PROTECTED]...
Let's say that we have a function, such that
f(n) = Sum{i =0, n-1} 2^i
how can we show these two:
one:
f(n) = f(n-1) +2^(n-1)
second:
f(n) = 2f(n-1) +1
any suggestion for a good start
Sent via Deja.com http://www.deja.com/
Before you buy.
--
From: [EMAIL PROTECTED]
Subject: proof of equation
Date: Mon, 20 Nov 2000 16:32:04 GMT
Let's say that () brackets represent ceiling brackets and {} represents
floor brackets than how can we show that:
(n/2){n/2} = {n^2/4}
ok in the above equation it's not 2/4 instead the term n square is
divided by 4
Sent via Deja.com http://www.deja.com/
Before you buy.
--
From: [EMAIL PROTECTED]
Subject: Re: recurrence
Date: 20 Nov 2000 16:47:11 GMT
[EMAIL PROTECTED] wrote:
Consider finding Linear_Search's average cost using an argument like
that used for Binary_Search's average cost. If p is the probability
that X equals any of the n elements of L, then Linear_Search's average
cost is
f(n) = 1(for n =1)
f(n) = 1+(1-p)f(n-1)(for n1)
How can we solve this recurrence
That's about the 4th obvious homework problem that has been posted
from my-deja.com, most likely the same person posting under different
names for different problems.
Have you ever thought of actually doing your own homework? What
exactly are you in school for? To learn or to muddle through with
others giving you the answers?
--
Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
University of North Texas| or better,' so I installed Linux."
Denton, TX 76201|
--
From: Francois Grieu [EMAIL PROTECTED]
Subject: Re: proof of equation
Date: Mon, 20 Nov 2000 17:57:46 +0100
[EMAIL PROTECTED] wrote:
how can we show that:
ceiling(n/2)*floor(n/2) = floor(n^2/4)
Clearly, this equation can work only for n integer.
Hint: consider separately n even (n = 2*m) and
n odd (n=2*m+1).
Francois Grieu
--
From: [EMAIL PROTECTED]
Subject: equation problem
Date: Mon, 20 Nov 2000 16:54:11 GMT
WE HAVE TO SHOW THAT
(n^2)f(n) = ((n^2)-1)f(n-1)+2(n-1) = f(n) = 2((n+1)/n)*Hn - 4
here Hn is not H muliply by n. instead it's the base n (very small
Cryptography-Digest Digest #192
Cryptography-Digest Digest #192, Volume #12 Mon, 10 Jul 00 10:13:01 EDT
Contents:
Re: Has RSADSI Lost their mind? (Mark Wooding)
Re: Proposal of some processor instructions for cryptographical (Runu Knips)
Re: [Q] Serpent: Gladman Code incomplete ? (Mark Wooding)
Rijndael key schedule question (Dido Sevilla)
Re: [Q] Serpent: Gladman Code incomplete ? (Dido Sevilla)
Re: [Q] Serpent: Gladman Code incomplete ? (Runu Knips)
Re: Proposal of some processor instructions for cryptographical (Konrad Schwarz)
Re: Proposal of some processor instructions for cryptographical (Runu Knips)
Re: Suggestions for crypto for constrained-memory/CPU computers? (Mark Wooding)
Re: Random Numbers (John Savard)
Re: Advanced Cryptography FAQ (John Savard)
Re: Compression Encryption in FISHYLAND (John Savard)
Re: Proposal of some processor instructions for cryptographical applications (Bruce
Hoult)
#sci.crypt irc channel (csybrandy)
key dependent s-boxes (Vladimir Castro Alves)
Re: SecurID crypto (was "one time passwords and RADIUS") ("Trevor L. Jackson, III")
Re: Rijndael key schedule question (Mark Wooding)
tokens and vpns ( was:Re: SecurID crypto (was "one time passwords and RADIUS")
(Padgett 0sirius)
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Has RSADSI Lost their mind?
Date: 10 Jul 2000 09:59:41 GMT
Bill Unruh [EMAIL PROTECTED] wrote:
If you are in the USA, then you fall under US patent law. As such you
have the five choices.
[...]
e) Rewrite OpenSSL to use DH/ElGammel key exchange ( but ov course
then you would not be in compliance with SSL)
Alternatively, use ephemeral Diffie-Hellman with DSA authentication,
which has been in SSL for ages. (And I wish more people would use it:
the forward secrecy properties of Diffie-Hellman are a major benefit.)
-- [mdw]
--
Date: Mon, 10 Jul 2000 12:11:29 +0200
From: Runu Knips [EMAIL PROTECTED]
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Thomas Womack wrote:
"Mok-Kong Shen" [EMAIL PROTECTED] wrote
Transposition is one of the basic operations in cryptography.
Is it, any more? Having a look at the AES candidates, most of them carefully
refrain from calling for bit transpositions simply because they're rather
hard to implement.
Rotations are bit permutations, too, therefore you're simply wrong.
And, well, Serpent contains a really complex initial (and final)
bit permutation, even if I don't understand whats the use for it,
except that the cipher is seriously slowed down in software.
--
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: [Q] Serpent: Gladman Code incomplete ?
Date: 10 Jul 2000 10:18:05 GMT
Runu Knips [EMAIL PROTECTED] wrote:
Last weekend I have studied the Serpent paper, and was surprised how
easy to understand and elegant this cipher is, even if I missed some
of the very basic features of a cipher description in it, meaning test
vectors and at least an idea how to implement the cipher in software.
I also read the Serpent implementation of Brian Gladman
(http://www.btinternet.com/~brian.gladman/cryptography_technology/aes/serpent.c),
but what I don't understand is the fact that Serpent defines an
initial and final bit transformation (called IP and FP in the paper),
which are not implemented in the cipher of Mr. Gladman. So is it true
that Mr. Gladman's implementation is in fact incomplete ?
No. You've misunderstood the description.
There are actually two ways of looking at Serpent. The first one is the
`traditional' approach, where you do the initial permutation, and then
do 32 rounds of key mixing, push each group of four bits through S-boxes
and then do a hairy linear transformation.
In the traditional view, we have four 32-bit words, a, b, c, d. Here's
a diagram, labelling the bits (after the initial permutation).
a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 ... a_{28} a_{29} a_{30} a_{31}
b_0 b_1 b_2 b_3 b_4 b_5 b_6 b_7 ... b_{28} b_{29} b_{30} b_{31}
c_0 c_1 c_2 c_3 c_4 c_5 c_6 c_7 ... c_{28} c_{29} c_{30} c_{31}
d_0 d_1 d_2 d_3 d_4 d_5 d_6 d_7 ... d_{28} d_{29} d_{30} d_{31}
Each block of four bits a_0 a_1 a_2 a_3 gets pushed through an S-box.
That's easy, but deadly slow because that's 32 separate S-box lookups to
do every round. Bleugh.
There's an alternative to doing the initial permutation, though.
Instead of moving all of the bits around, we can leave the bits exactly
where they are and move the rest of the world around instead. What we
have is
a_0 a_4 a_8a_{12} ... d_{16} d_{20} d_{24} d_{28}
a_1 a_5 a_9a_{13} ... d_{17} d_{21} d_{25} d_{29}
a_2 a_6 a_{10} a_{14} ... d_{18} d_{22} d_{26} d_{30}
a_3 a_7 a_{11} a_{15} ... d_{19} d_{23} d_{27} d_{31}
Notice that the four bits going to each S-box, inst
Cryptography-Digest Digest #192
Cryptography-Digest Digest #192, Volume #11 Thu, 24 Feb 00 11:13:01 EST Contents: Wanted : Phd Students (Nigel Smart) Re: Compression in the Real World (John Savard) Re: OAP-L3 Encryption Software - Complete Help Files at web site (Tim Tyler) Re: Passwords secure against dictionary attacks? (Jens Haug) SAC '2000 Call for Papers (Tom Harper) Re: DES algorithm ([EMAIL PROTECTED]) Re: Does the NSA have ALL Possible PGP keys? (Canopy Co Tulsa OK) Re: Passwords secure against dictionary attacks? (John Underwood) Enigma (Yugo Shimada) Re: Enigma (DJohn37050) Re: Passwords secure against dictionary attacks? (Walter Roberson) Re: DES algorithm (Tim Tyler) Re: Implementation of Crypto on DSP (Paul Koning) Re: Transmitting ciphered data (Paul Koning) Re: NSA Linux and the GPL (Paul Koning) From: Nigel Smart [EMAIL PROTECTED] Subject: Wanted : Phd Students Date: Thu, 24 Feb 2000 11:34:06 GMT Hi, The computer science department at Bristol Uni may have a number of studentships available from September for those wishing to take PhD's in Computer Science. In particular there may be a few available for work in Cryptography and Computational Number Theory. Details about Bristol and the Computer Science department can be found at... www.cs.bris.ac.uk and www.bris.ac.uk For those who have no idea where Bristol is, it is about 100 miles west of London, (UK). Yours Nigel -- Nigel Smart, Department of Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol, BS8 1UB, United Kingdom. -- From: [EMAIL PROTECTED] (John Savard) Subject: Re: Compression in the Real World Date: Thu, 24 Feb 2000 11:46:16 GMT On Wed, 23 Feb 2000 19:39:39 GMT, [EMAIL PROTECTED] wrote, in part: Working with large documents, 100-500 pages requires real compressors. he claimed he had a text compression system with a 100:1 compression ratio...and he was an expert in the field.. It is unlikely that a text compression system could do better than 8:1, as Shannon used techniques to estimate the _actual_ entropy of English text which did not require being able to design a compressor to compress that far, and was able to determine that this entropy was in the area of one bit per letter. Compression has led many people into serious errors. A company was taken seriously a few years back when it claimed to have an algorithm that could compress *any* file, even one made up of pure random data, to 1/4 its size. Actually, that is as impossible as building a perpetual-motion machine. I have no doubt that a compressor specialized to compressing text, however, could achieve somewhat better results than current commonly-used compression programs. -- Crossposted-To: talk.politics.crypto,alt.privacy From: Tim Tyler [EMAIL PROTECTED] Subject: Re: OAP-L3 Encryption Software - Complete Help Files at web site Reply-To: [EMAIL PROTECTED] Date: Thu, 24 Feb 2000 12:58:39 GMT In sci.crypt lordcow77 [EMAIL PROTECTED] wrote: : Wagner does not use the word "unbreakable" once in his entire : posting. I don't know where you're getting this stuff from. He : asserted the existence of certain algorithms which were provably : secure *under a specific security model*. The topic stems from Chuck's original statement: ``Many a clever algorithm that was "mathematically proven" by its designer to be unbreakable has quickly fallen when analyzed by the world's leading codebreakers.'' In fact, "unbreakable" /was/ mentioned in Wagner's post: he quoted my use of it, which was made in direct response to Chuck's statement above. The section in question reads: ``Any algorithm that comes with a mathematical proof that it's unbreakable is unlikely to be analysed by the world's leading codebreakers.'' Wagner wrote that my post was "Nonsense" - but then seemd to justify this by mentioning "[c]ryptosystems that are provably secure (under some assumptions)". This can be a very far cry from "unbreakable". He is clearly aware of this, as he continued by saying that some of these cyphers do, in fact, get broken. -- __ |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED] Strip mining helps prevent forest fires. -- From: [EMAIL PROTECTED] (Jens Haug) Crossposted-To: comp.security.misc,alt.security.pgp Subject: Re: Passwords secure against dictionary attacks? Date: 24 Feb 2000 13:42:18 GMT Reply-To: [EMAIL PROTECTED] In article [EMAIL PROTECTED], Tom Holroyd [EMAIL PROTECTED] writes: Say "passphrase" instead of "password" and be free. Assuming your crypt implementation doesn't truncate at 8 characters (many still do -- trash yours if it does). Then set your passphrase to something like &
Cryptography-Digest Digest #192
Cryptography-Digest Digest #192, Volume #10 Tue, 7 Sep 99 02:13:02 EDT
Contents:
Number of k-smooth numbers less than x ([EMAIL PROTECTED])
Re: SQ Announcement (David Wagner)
Re: Quantum computing bit in UK computing magazine. ("rosi")
Re: arguement against randomness ([EMAIL PROTECTED])
Re: Mystery inc. ([EMAIL PROTECTED])
Re: NSA and MS windows (David Wagner)
Re: arguement against randomness ("rosi")
Re: THE NSAKEY (SCOTT19U.ZIP_GUY)
Re: arguement against randomness ("elarson")
Re: SQ Announcement (David Wagner)
From: [EMAIL PROTECTED]
Subject: Number of k-smooth numbers less than x
Date: Tue, 07 Sep 1999 00:11:23 GMT
Would anyone here be able to send me the expression used for the number of
k-smooth numbers less than x (which is denoted \psi(k,x) in the literature I
have read). I have the original journal reference but do not believe I can
gain access to it in paper form.
Many thanks in advance.
=
Dr. John P. Costellahttp://www.ph.unimelb.edu.au/~jpc
[EMAIL PROTECTED] [EMAIL PROTECTED]
Senior Fellow, School of Physics, The University of Melbourne
Faculty of Mathematics, Mentone Grammar, Victoria Australia
=
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
--
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: SQ Announcement
Date: 6 Sep 1999 18:28:34 -0700
In article 7quume$[EMAIL PROTECTED],
Kostadin Bajalcaliev [EMAIL PROTECTED] wrote:
The discussion about SQ1 is starting to look as theory vs. theory. Thanks to
Mr.. Warner I have read the Shannon theory again and I did not find any
conflict between "Information Lose" and "Unconditional Security". They
address the same subject but clearly from two different points of view.
Shannon theory is model what "unconditionally secure" Stream cipher must be.
"Information Lose" theory is "computation security".'
Ahh, good, this helps. I still have questions, but it's an excellent
start. Thanks for taking the time to explain it to me!
Next I'd like to ask whether you think of the "Information Lose" theory
as a design principle or as a theorem. Is it a sufficient condition, a
necessary condition, or an ad-hoc heuristic?
Here's an example which makes me think that the "Information Lose"
principle must be a heuristic design principle and not a provable theorem.
Let my try to restate my understanding of the "Information Lose" approach
and give an example of how to apply you; you can tell me whether I got it
right.
An attempted restatement of the "Information Lose" principle:
Suppose the stream cipher outputs a chunk of n bits at a time.
Then, after each n-bit output is produced, the cipher should
introduce somehow more than n "new bits" into the internal state
before the next chunk of n bits of output is produced.
(The notion of "new bits" is left undefined, and thus this is an informal
heuristic notion.)
Here's an example which shows (if I'm not confused) that a cipher can satisfy
the "Information Lose" principle and yet still be insecure.
Consider a 128-bit LFSR. At each step, one generates one bit of keystream
output by outputting the low bit of the LFSR, and then one clocks the LFSR
10 times. This introduces 10 "new bits" for every bit that is output, and
so it seems as though this should satisfy the "Information Lose" principle.
Nonetheless, it is a simple student exercise to break this cipher.
One may even clock the cipher 1000 times (or more) between each bit of output
if desired, and this still won't make it secure.
Of course, this doesn't mean that the "Information Lose" approach is
useless: heuristic design principles can be extremely useful, even if they
are not proven or not always a guarantee of success. I'm just trying to
understand first what is claimed for the approach.
--
From: "rosi" [EMAIL PROTECTED]
Subject: Re: Quantum computing bit in UK computing magazine.
Date: Mon, 6 Sep 1999 21:15:05 -0400
David Hamilton wrote in message [EMAIL PROTECTED]...
-BEGIN PGP SIGNED MESSAGE-
[snip]
Now, what I know about quantum computing (QC) can be written on a couple of
bits but surely this last sentence is wrong. I thought that public key
encryption would be doomed against 'genuine' QC but that symmetric key (and
I strongly, strongly, and VERY STRONGLY doubt.
I believe I have given a sketchy look into the issue (and just remember
what
multi-state means). Just a couple of days ago I gave some kind of
summarization:
I favor the view that
