Cryptography-Digest Digest #447
Cryptography-Digest Digest #447, Volume #14 Sat, 26 May 01 11:13:01 EDT Contents: Re: Best, Strongest Algorithm (Tim Tyler) Re: Best, Strongest Algorithm (Tim Tyler) Re: survey (Tom St Denis) Re: A generic feistel cipher with hash and gf(257) mixers (Tom St Denis) Re: Crypto NEWBIE, wants to create the 100% SAFE FRACTAL encoding... Am (Mok-Kong Shen) Help with 'P' in PKCS1V2.1 RSAES-OAEP (Sam) Newbie question about algo (Martin Kiewitz) Re: Newbie question about algo (Tom St Denis) Essay on The need for a look at real life crypto (Tom St Denis) Re: Differential cryptanalysis. ([EMAIL PROTECTED]) Re: 1st CipherText Application prototyped (Prichard, Chuck) Re: Crypto NEWBIE, wants to create the 100% SAFE FRACTAL encoding... Am I a fool ? (Al) Re: Small (not fast) RIPEMD-160 (Mark Wooding) Re: 1st CipherText Application prototyped (Tom St Denis) Re: A generic feistel cipher with hash and gf(257) mixers (Jim Steuert) Re: A generic feistel cipher with hash and gf(257) mixers (Tom St Denis) Re: A generic feistel cipher with hash and gf(257) mixers (Jim Steuert) Re: Crypto NEWBIE, wants to create the 100% SAFE FRACTAL encoding... Am I a fool ? (John Savard) Re: Good crypto or just good enough? (Harris Georgiou) Re: Getting back to the self-study Analysis (Harris Georgiou) From: Tim Tyler [EMAIL PROTECTED] Subject: Re: Best, Strongest Algorithm Reply-To: [EMAIL PROTECTED] Date: Sat, 26 May 2001 09:09:56 GMT Mark Wooding [EMAIL PROTECTED] wrote: : Tim Tyler [EMAIL PROTECTED] wrote: : It certainly has some different properties - here is some of the upside: : : * Use of the same key on different messages is much better with BICOM, due : to the whitening. : * Bitflipping produces a huge error extension in BICOM - but none in : counter mode. : Useless. If you want to detect tampering, use a MAC. If you don't, you : probably want minimal error extension. The advantage of this boils down to the fact that information in the plaintext if diffused in the cyphertext. Imagine you have an attack that allows you to go from some known plaintext to a key. With CTR mode this attack will produce immediate results, since the inputs to the cypher (i.e. the counter) is not normally considered to be part of the secret key. However with something with good diffusion properties this attack would be likely to fail - unless the *entire* plaintext of the message is already known. Of course, it is not realistic to assume the existence of a known plaintext attack - but it should illustrate how diffusing plaintext information in the cyphertext can be desirable in the case where one is not 100% certain of the security of the block cypher used. : * BICOM compresses - files should be smaller, so there's less cyphertext : for the attacker to look at and messages are brought closer to the : unicity distance, so the likelihood of multiple correct-looking decrypts : is increased. : So do gzip, bzip2 and so on. Using a cipher with a compression : algorithm is common practice. Yes, that's exactly what BICOM is. Are we now changing the subject to comparing BICOM with CTR mode plus some unspecified compression algorithm? : Your problem is that you're actually using a really strange attack : model. You're assuming that the best attack against the cipher is : actually brute-force search of the keyspace, with unknown plaintext. : This smells unreasonably optimistic to me. I'm not assuming that. I was asked to explain how BICOM could be more secure than CTR mode. I gave an example of one attack against which it /is/ more secure. That attack happens to be the best attack publicly known against the cypher in question. There may well be other attacks against Rijndael that I don't know about, However, the chances of these affecting BICOM and /not/ affecting CTR mode appear to be practically nil. : No proof for CTR mode either. : What? You must have been dreaming. There's a proof that attacking CTR : under the real-or-random model is only `a bit' harder than : distinguishing the block cipher from a random function (where `a bit' is : carefully quantified). Ah, that's not what I was talking about. I should perhaps have specified more clearly that I meant there was no proof of security for *Rijndael* in CTR mode. There's no proof of security for Rijndael in any other mode either. There's no proof of security for Rijndael full stop. Rijndael will probably be broken, in the fullness of time. -- __ |im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/ -- From: Tim Tyler [EMAIL PROTECTED] Subject: Re: Best, Strongest Algorithm Reply-To: [EMAIL PROTECTED] Date: Sat, 26 May 2001 09:14:57 GMT Joseph Ashwood [EMAIL PROTECTED] wrote: : Tim Tyler [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... [snip two proposed modes of operation
Cryptography-Digest Digest #447
Cryptography-Digest Digest #447, Volume #13 Tue, 9 Jan 01 21:13:00 EST
Contents:
Re: xor'd text file ("Paul Pires")
Re: SOFTWARE BETA TESTERS URGENTLY REQUIRED (Nemo psj)
Re: Crypto book with mathematical explanations? ("M.S. Bob")
Twofish for dummies ("Robert Larsen")
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) ("Paul Pires")
Re: secure DOS files ("Thomas J. Boschloo")
Re: Password security for file transfer w/o speed loss? (Thomas Wu)
Re: Comparison of ECDLP vs. DLP (D. J. Bernstein)
Re: NIST hmac fips (David Hopwood)
Re: Comparison of ECDLP vs. DLP (Gregory G Rose)
Re: secure RNG (Tom St Denis)
Re: Need of very simple algorithms? (AllanW)
From: "Paul Pires" [EMAIL PROTECTED]
Subject: Re: xor'd text file
Date: Tue, 9 Jan 2001 13:06:40 -0800
Forrest Johnson [EMAIL PROTECTED] wrote in message
news:93dfq9$[EMAIL PROTECTED]...
[EMAIL PROTECTED] (Joshua Cryer) wrote in
SmO56.16021$[EMAIL PROTECTED]:
I dont quite understand what you mean by 'seed'. The number 65535 is
16bits
in binary. Do you mean the number which is = 65535 has been XOR'd
with
every
16 bits in the text file? If that was the case then frequency analysis
would
still work pretty well on the file. Look at how many times each byte
occurs
in the text file. The highest frequencied items will most likely be
plaintext
space or E. From there you can figure out what number would transfer
the ciphertext letter into space or E. Apply this to the whole file
and see
what
happens.
What I mean is this. The file is XOR'd to a pseudo-random number
generator which is limited to 65535 possible seeds (yeah, 16 bits). I
actually know many words, and even complete sentences that were used in
the original text file. I just don't know how I could begin to reverse
engineer since I know for certian that it was XOR'd at least twice
(maybe more) with two different seeds. Someone told me that this is very
crackable. Well. How?
You mentioned in your original post that the enciphered file is very large.
Is it larger than 65535 bits? If so, you should be able to take advantage
of the fact that a PRNG has a period that is very commonly equal to the
size of the seed space. Thus, the cipher stream from the PRNG will start
repeating after 65535 bits.
Another chance to learn :-) I think there are problems with the above
statement, correct me if I am wrong. It's the "very commonly" part.
He said the seeds were 65535 bits and that he did not know the PRNG
used, so I assume he doesn't know the size of the internal state, what I
assume you are refferring to as the "seed space". The cipher must repeat
when it's output exceeds it's internal state (It cannot exibit more complexity
than it contains) but when it acually does this is drivin by the actual PRNG
and the particular seed used unless it is a very bad PRNG indeed. If the
internal
state was 2048 bits like RC-4, then you are in for a fair job of hunting. Kind
of a birthday paradox. Figure out how big the population of a room needs to
be to have two states be identical whith a certain probability when there are
2^2048th different ones. This should tell you how often it is likely to occur.
The required population is the expected cycle at that probability. Finding the
lucky couple in order to exploit the effect sounds challenging.
Paul
Even if the text was enciphered several times, using the same PRNG with
different keys would still produce this cyclic pattern. The XOR function
is commutative, so it doesn't matter what the order of application is -- A
XOR B XOR C is equal to A XOR C XOR B. In addition, the operation of A XOR
B XOR C is equivalent to A XOR Z where Z is equal to B XOR C. In other
words, repeatedly XORing the plaintext file with a succession of values is
the equivalent of XORing it with some other single value.
Given this property and the cyclic nature of the PRNG, an XOR of the first
enciphered bit with the 65536th bit will produce a a result equal to the
two plaintext bits (1 and 65536) XORed together (providing the cycle is
65535). If you know the plaintext value of bit 1, you could then extract
the plaintext value of bit 65536.
You said that you knew some plaintext already. If you know the position of
this plaintext in the file, you could test what I've suggested:
1) Take a string of enciphered text equal to the length of the known
plaintext from the same position as the known plaintext.
2) XOR this string with another string equal in length and positioned one
cycle away. The result should be two plaintext strings XORed together.
3) Finally, take your known plaintext and XOR it with the result of step 2.
This should produce the second plaintext string. If you get gibberish, it
mean
Cryptography-Digest Digest #447
Cryptography-Digest Digest #447, Volume #11 Thu, 30 Mar 00 07:13:01 EST
Contents:
Re: The lighter side of cryptology ([EMAIL PROTECTED])
Re: The lighter side of cryptology ([EMAIL PROTECTED])
Re: A newby question: "3DES" is 57.5 bits, and not 168 bits? (John Savard)
Re: Opinions? ([EMAIL PROTECTED])
The NSA's little NCSC bots ([EMAIL PROTECTED])
Coderpunks Query on Teledyne Crypto (John Savard)
Re: Key exchange using Secret Key Encryption (NFN NMI L.)
Re: Does the NSA have ALL Possible PGP keys? ([EMAIL PROTECTED])
Re: Newbie, Where should I start, ([EMAIL PROTECTED])
Re: Basic info on cryptography (Slip Gun)
Re: prime solution ([EMAIL PROTECTED])
Re: Q: Differencing time series (Mok-Kong Shen)
Re: Coderpunks Query on Teledyne Crypto (Mok-Kong Shen)
Re: Key exchange using Secret Key Encryption ([EMAIL PROTECTED])
Re: Coderpunks Query on Teledyne Crypto (John Savard)
Re: prime solution (John Savard)
From: [EMAIL PROTECTED]
Subject: Re: The lighter side of cryptology
Date: Thu, 30 Mar 2000 06:36:14 GMT
In article
nAvE4.2979$[EMAIL PROTECTED]
m,
"Leo Sgouros" [EMAIL PROTECTED]
wrote:
those that care know everything they need to :-)
This is one cryptic message that I cannot
decipher. What does it mean?
Sent via Deja.com http://www.deja.com/
Before you buy.
--
From: [EMAIL PROTECTED]
Subject: Re: The lighter side of cryptology
Date: Thu, 30 Mar 2000 06:45:09 GMT
In article
8bu51l$mj2$[EMAIL PROTECTED],
[EMAIL PROTECTED] (Xcott Craver) wrote:
IMHO, this constitutes a great achievement.
Perhaps you have a latent part- time destiny
as the Benny Hill or Howard Stern of crypto !-)
But not every bra has a cryptographic function. Most are used for ASCII
armor or for compression. Some are even designed to make the plaintext
stand out and more enjoyable to read.
Touche, but I believe what we have here is a clear case of steganography.
Yikes. I think that we should hammer down some definitions before
this whole thing gets out of hand.
Cryptography:
Building a difficult-to-unhook bra.
Steganography:
Building a flesh-colored bra, or one whose unhook mechanism is
hidden somewhere unexpected (Man: "How the Hell...?" Woman:
"It unhooks in front." Man: "Damn those steganographers.")
Public-Key Cryptography:
Building a bra that anyone can put on, but that only Alice can
remove.
Watermarking:
Building a bra that stays on even after smoothing, compression,
and rotation. Also, Bob should not be able to put his own bra
on over Alice's and claim ownership of her body.
Fingerprinting:
Um, I'm probably already in trouble for the last one, so I'll
just skip this.
Signatures:
Building a bra with a nametag ("Property of Alice, machine wash
warm...") such that bras with Alice's name only fit Alice's body.
Bob could in theory remove Alice's bra and replace it with his
own, but there's no real reason for him to do so.
Zero-Knowledge Proofs:
Alice transforms her bra into a duffle bag, and either (a) shows
Bob how to open it, or (b) shows Bob how she made it into a duffle
bag. Alice repeats the procedure until Bob is satisfied (perverted
freak).
One-time Pad:
Kleenex.
NSA: An organization that wants women to go back to wearing corsets and
chastity belts. Oh, and Bill Clinton gets to keep all the keys.
Sent via Deja.com http://www.deja.com/
Before you buy.
--
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: A newby question: "3DES" is 57.5 bits, and not 168 bits?
Date: Thu, 30 Mar 2000 06:52:15 GMT
On Tue, 28 Mar 2000 19:34:19 GMT, [EMAIL PROTECTED] (Steven C. Den
Beste) wrote, in part:
I thought that one of the strengths -- and weaknesses -- of DES was that if
you did the decipher properly, then the engine told you that you had
succeeded even if you didn't know what the plaintext was.
There might be a way to write a routine to encipher, or decipher, DES,
so that it would tell you if you wrote it without bugs. Usually,
though, test vectors are used for that purpose.
(Something to the
effect that if it was done properly then the shift register contained all
zeros after the process. If it contained any 1's, then it was the wrong
key.)
But, as others have noted, that is definitely not true. Because DES is
a block cipher that takes 64-bit plaintext inputs to 64-bit cipher
outputs, the cipher output has no extra information in it. You can
decipher any 64-bit block with all 2^56 different keys, and you will
get 2^56 results. They won't necessarily all be different, but the
only thing that makes one result more likely to be correct than
another is if it looks, to you, more like the kind of plaintext you
were expecting the other fellow to have enciphered.
Now, one might encipher using DES in a chaining mode, and
Cryptography-Digest Digest #447
Cryptography-Digest Digest #447, Volume #10 Mon, 25 Oct 99 10:13:03 EDT
Contents:
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Mok-Kong
Shen)
Re: Note on Feistel Ciphers (Mok-Kong Shen)
Re: some information theory (very long plus 72K attchmt) ("Mattias")
Re: Some humble thoughts on block chaining (Mok-Kong Shen)
Re: Character Frequencies Tables for languages other than English (Eric Hambuch)
How to use CBC w/ RC4? (Tom)
Re: Some humble thoughts on block chaining (Bo Dömstedt)
RC 4: security law ([EMAIL PROTECTED])
Re: How to use CBC w/ RC4? (Tom St Denis)
Re: compression and encryption (Tom St Denis)
Re: OAP-L3: How Do You Spell S-H-A-R-E-W-A-R-E (Tom St Denis)
Re: Posting Anonymously (Steve K)
Re: NAI version of PGP no secure? ("Sergey Kuznetsov")
From: Mok-Kong Shen [EMAIL PROTECTED]
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Mon, 25 Oct 1999 10:06:22 +0200
[EMAIL PROTECTED] wrote:
Now if the attacker *does* know which cipher has been used for each
ciphertext block, then he can attack the ciphertext encrypted by the
weakest cipher. Consider this: even though we in the public don't know
the lower bound of security of the individual ciphers we must assume
that a powerful attacker does know. We also can assume that these lower
bounds vary a lot - it would be strange indeed if different ciphers
were very similar in their lower bound of security. So in a pool of
four ciphers it is quite probable that one (the "lemon") is orders of
magnitude weaker than the others and that the attacker knows this. Let
us assume the lemon falls to a known plaintext attack that requires a
small number of known plaintexts. It is true that the attacker will now
have to collect four times more data for the lemon, but this quantity
will be a trifle compared to the plaintext that must be known for
attacking any of the other three ciphers. Therefore the attacker will
easily break 25% of the communications recovering almost all
intelligence. Instead of using this method, we would be better off
choosing one cipher by chance sticking to it.
A tiny remark: Using variable keys as proposed by me in another
thread, such attacks presumably have to be considered in a different
perspective.
M. K. Shen
--
From: Mok-Kong Shen [EMAIL PROTECTED]
Subject: Re: Note on Feistel Ciphers
Date: Mon, 25 Oct 1999 10:06:11 +0200
[EMAIL PROTECTED] wrote:
Mok-Kong Shen wrote:
[EMAIL PROTECTED] wrote:
[...]
The Feistel structure is already powerful enough to
induce any bit permutation. The point is not that we
might actually want to implement a permutation as
Feistel rounds, but that the separation of the left
and right halves that one might intuitively suspect in
the Feistel structure does not in fact exist.
Whether one can realize an arbitrary permutation with Feistel
construct is not my concern. My point was that adding in a
permutation step could render analyisis schemes that somehow exploit
the seperation unworkable.
My point is that your concern, attacks that exploit
a separation between the halves in Feistel ciphers,
is of no concern at all. The separation is only in
the process of computation; it is known not to limit
the resulting dependencies. What does the
realization of arbitrary bit-permutations within the
Feistel construct prove? That any weakness that can
be repaired by adding bit-permutations is not
characteristic of Feistel ciphers.
Adding permutations certainly contribute some complexity.
In the sense that adding most anything key-dependent
contributes some complexity to most any secret-key
cipher. The relevant point to a "Note on Feistel
Ciphers" is that Feistel ciphers already cover
bit-permutations.
I guess that probably you wanted to use the last sentence above in an
other than normal sense. Anyway, I am afraid that this sentence
together with your previous sentence
The Feistel structure is already powerful enough to
induce any bit permutation
can generate something very misleading for the reader. Using the
context of mine, which considers the input and output of two
rounds taken together, did you mean that there exists a key, such
that the output bit sequence (whole block) is any prescribed
permutation of a given input? I am not sure that it is simple (or
even generally possible) to show that there are two subkeys (since
two rounds are involved here) that do that for a given Feistel
design. In the mathematical argument given in your previous post:
L ^= R K
R ^= L K
L ^= R K
you used the SAME symbol K in the three equations. That means that
the round functions operated on (the always current) L and R under
three
