Cryptography-Digest Digest #180
Cryptography-Digest Digest #180, Volume #14 Thu, 19 Apr 01 07:13:00 EDT
Contents:
OTP breaking strategy (newbie)
[NEWS] PGP broken (maybe) (Fight Boschloo)
Re: Prime Numbers Patterns? (David A Molnar)
Re: OTP breaking strategy (Samuel Paik)
Re: C code for GF mults (Jyrki Lahtonen)
All One Polynomail ("Andre Kim")
First cipher ([EMAIL PROTECTED])
Re: Crypto question ("Robert M Best")
Re: Prime Numbers Patterns? (Francois Grieu)
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Bryan Olson")
Re: Reusing A One Time Pad (Bryan Olson)
Re: Data dependent arcfour via sbox feedback (Bryan Olson)
Re: Rabin-Miller prime testing ("Bryan Olson")
Re: Crypto question (Mark Wooding)
Re: Prime Numbers Patterns? (Lassi =?iso-8859-1?Q?Hippel=E4inen?=)
Re: Reusing A One Time Pad ("Douglas A. Gwyn")
Re: Reusing A One Time Pad ("Douglas A. Gwyn")
Re: Reusing A One Time Pad ("Douglas A. Gwyn")
Re: Reusing A One Time Pad ("Douglas A. Gwyn")
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Douglas A. Gwyn")
Re: "UNCOBER" = Universal Code Breaker ("Douglas A. Gwyn")
Re: "UNCOBER" = Universal Code Breaker ("Douglas A. Gwyn")
Re: "UNCOBER" = Universal Code Breaker ("Douglas A. Gwyn")
Re: "UNCOBER" = Universal Code Breaker ("Douglas A. Gwyn")
From: newbie [EMAIL PROTECTED]
Subject: OTP breaking strategy
Date: Wed, 18 Apr 2001 18:29:23 -0300
It is hard to break OTP but not impossible.
Let me explain my strategy. You think that I do not know what I'm
talking about.
You have the right to think so.
1. What the crypto is able to know before trying to crack OTP
Hypothesis :
a. The plaintext is correct english or french or any other language.
b. The plaintext is relating to specific domain ( business, bank,
geology, etc...)
c. The cryptanalyst could distinguish between truely random sequence and
non random sequence.
d. The cryptanalyst could know semantic sequence ( noun, verb, etc..)
2. How could he resolve OTP encryption ?
a. Build or use bit-string database specific to a domain related to OTP
encryped message.
If it is business, he can use database of words, sentences specific to
business. Every database is
ordered ( the more occurent to the less occurrent )
b. How decrypting algo will work?
Conditions :
1. ciphertext is 0010101000010010010001001001000100100..
2. length of ciphertext bit-string = n
Algo
First step : (goal : see if output is random or not )
1. pick the more occurent words or sentences
2. slide the bit-string bit by bit ( input ) from the position 1 to [n -
(length of words or sentence )]
3. for every position compute the word or the sentence with ciphertext
using XOR.
Sample
ciphertext = 0 0 1 0 1 0 1 0 0 0 1 1 1
1010010010001001001000100100..
first try (input) 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0
Xor (output) 1 0 0 0 1 1 1 1 .
4. Check if output is random or not.
5. If it is random assign value 1 to the first position of the input
then else 0.
6. Continue sliding the input at the right (positon 2) ...do the same
operation until [n - (length of words or sentence )]
7. When you finish with the first input you input the second using the
same operations.
8. You do that until you finish your database.
At the end of this step you will a large table with :
lines = words and sentences ordered (i)
column = positions from 1 to [n - (lowest length of words or sentences
(j)
x( i,j ) is the value 0 or 1 ( truly random or not )
Second step of selection ( goal - valid position or not)
1. For the first check if its position is unlikely valid or not
Sample : word = credit "
The word credit is unlikely to be the starting - the value is 0, I
change on my table the previous value if it is 1
then else no change
2. the second position I check semantically valid or not etc
3. I repeat until the last position.
4. I repeat the same previous operations for the folowing words and the
sentences on my table.
Third step ( goal - combinig the words and the sentences to form a
sentence that have a sense )
This step is the more difficult because it is not easy to compute it
without looking at the table and choosing
manually witch words and sentences to combine.
I think that this strategy have to be more analysed to allow to insert
in every step appropriate sub-algo.
The deciphering need a work team with linguist, domain expert (
business, bnk, etc..) and statistician.
My strategy have to be improved. I know that.
OTP is not unbreakable.
.
--
Date: 18 Apr 2001 23:45:10 -
From: [EMAIL PROTECTED] (Fight Boschloo)
Subject: [NEWS] PGP broken (maybe)
Crossposted-To: alt.privacy.anon-server,alt.security-pgp
Sure Boschloo will announce that, now, to get some attention
===
HISTORY:
That Boschloo bozo is a
Cryptography-Digest Digest #181
Cryptography-Digest Digest #181, Volume #14 Thu, 19 Apr 01 09:13:00 EDT
Contents:
Re: Prime Numbers Patterns? ("Douglas A. Gwyn")
Re: OTP breaking strategy ("Douglas A. Gwyn")
Re: "UNCOBER" = Universal Code Breaker ("Jack Lindso")
Re: First cipher (Mark Wooding)
Re: Proof of RSA (Mark Wooding)
Re: OTP breaking strategy ("Jack Lindso")
Re: OTP breaking strategy ("Tom St Denis")
Re: First cipher ("Tom St Denis")
Re: Reusing A One Time Pad ("Tom St Denis")
Re: "UNCOBER" = Universal Code Breaker ("Tom St Denis")
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: OTP breaking strategy (John Savard)
Re: "UNCOBER" = Universal Code Breaker (Richard Heathfield)
Re: "UNCOBER" = Universal Code Breaker (John Savard)
Re: OTP breaking strategy (Mok-Kong Shen)
From: "Douglas A. Gwyn" [EMAIL PROTECTED]
Subject: Re: Prime Numbers Patterns?
Date: Thu, 19 Apr 2001 11:12:40 GMT
Wizartar wrote:
Is there any logic to prime numbers, ...
There must be, since any mathematician will agree that they're
rational numbers.
All numbers ending in 0, 2, 4, 5, 6, 8, once you get above 9 are
defiantly not a prime numbers.
You should note a relationship between those digits and the
base (10) you seem to be using to express numbers. Instead
of worrying about primes in general, which is much too hard
a problem, perhaps you should concentrate on explaining this
relationship. That's a more suitable pre-collegiate task.
--
From: "Douglas A. Gwyn" [EMAIL PROTECTED]
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 11:16:29 GMT
newbie wrote:
You think that I do not know what I'm talking about.
You have the right to think so.
Indeed, we have the obligation to think so, based on the ample
evidence you have given us.
--
From: "Jack Lindso" [EMAIL PROTECTED]
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Thu, 19 Apr 2001 14:14:49 +0200
While I actually agree with you, the above line of reasoning seems
to make some assumptions that might not be correct. We know of many
examples in other fields where a general theory has been easier to
find than a specific theory.
It's almost always more difficult to find a general algorithm/theory rather
then a specific one, however it is also much more enlightning finding the
general theory. In any case a general theory should always exist for a
specific problem if that problem is solvable with a specific algorithm.
--
Designing the future is all about envisioning the Infinity.
http://www.atstep.com
=
"Douglas A. Gwyn" [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]...
Jim Gillogly wrote:
since we don't have practical special-purpose attacks on many of the
modern ciphers, it's way premature to talk about a general attack
that solves all of them.
--
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: First cipher
Date: 19 Apr 2001 11:21:14 GMT
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Here's my first attempt at a block cipher. Please critique
and explain WHY as well as where I'm going wrong.
Who said that dinosaurs are dead? This is DES, bigger than ever...
1.) Feistel network, blocklength 64 bits, 128-bit key, 16 rounds
Fair enough.
2.) Key schedule to create 16 64-bit subkeys
a. Split key into two 64-bit subkeys (k1, k2).
b. To generate the next two subkeys, permute
k1, k2 then left circular shift (LCS)
the result of each permutation. The number of
shifts is determined by the value of two bits
(say b1,b0 for example) from the permutation output.
The result of the k1 permutation, LCS(b1,b0) becomes k3.
The result of the k2 permutation, LCS(b1,b0) becomes k4.
c. Repeat (b) until 16 64-bit subkeys are obtained.
Is the LCS(b1,b0) necessary? I wondered if a simple permutation
would be sufficient since the key is assumed to be random and
secret...
This is not a good idea. The problem is that you're using real key bits
in the cipher. If an attack discovers some bits of a round key, it's
actually found some real bits of the key, and therefore bits of other
round keys. The rotations make life a little more difficult but not a
lot. I think you want something with more one-wayness.
Also, there's very little communication between the two halves of your
key. I think that's a bad idea. The DES key schedule is a marvellous
piece of minimalist design, but emulating it is extremely dangerous.
3.) Function (operates on 32-bit half of 64-bit plaintext block)
a. Permute
b. E-box which permutes and expands 32 bits to 64 bits
c. XOR with 64-bit subkey
d. Compression substitution (64 bits to 32 bits)
Eight bits from (c) are
Cryptography-Digest Digest #182
Cryptography-Digest Digest #182, Volume #14 Thu, 19 Apr 01 12:13:01 EDT
Contents:
newbie: cryptanalysis of pseudo-random OTP? ("Osugi Sakae")
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: First cipher ([EMAIL PROTECTED])
Re: Rabin-Miller prime testing (Simon Josefsson)
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: Reusing A One Time Pad ("Tom St Denis")
Re: NSA-Endorsed Schools have a Mediocre Internet Presence (Richard Herring)
Re: NSA-Endorsed Schools have a Mediocre Internet Presence (Richard Herring)
Re: Reusing A One Time Pad (Jerry Coffin)
please help! ("Tom St Denis")
Re: CAST5 Implementation (Mark Wooding)
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: Prime Numbers Patterns? (Kent Briggs)
Re: Reusing A One Time Pad ("Tom St Denis")
Re: NSA-Endorsed Schools have a Mediocre Internet Presence (Richard Herring)
Re: First cipher ("Scott Fluhrer")
Monoalphabetic Substitution Cipher Cracker program ("Robert Reynard")
Re: Crypto question ("Shah Karim")
From: "Osugi Sakae" [EMAIL PROTECTED]
Subject: newbie: cryptanalysis of pseudo-random OTP?
Date: Thu, 19 Apr 2001 22:53:30 +0900
Reply-To: [EMAIL PROTECTED]
forgive me for what is prolly a newbie question, but ...
I understand that a properly impliemented and used OTP is secure, and I
understand that a simple polyalphabetic substitution with a keyword is
not secure, and in fact almost (totally?) worthless if computers are used to
attack it. Several of the intro to crypto books discuss this, right upto
keywords as long as the plaintext. (Forget whose, but one book mentioned
using a Carl Sagan book as the "keyword"). What they don't say is why
this is not secure, just that the language of the keyword rubs off on the
ciphertext. I can understand this, supposing that more of the plaintext
will get enciphered with the letter 'e' than with the letter 'q'. But how
would someone go about cryptoanalyzing this? The kappa test would tell
them that it is a polyalphabetic cipher, but what next? None of the books
I have read (and understood) goes into this.
The books also mention that a OTP is only as secure as the random number,
but again don't mention how someone would break a pseudo-random cipher.
Is it something to do with probabilities of subsequent numbers (for
example, noticing that say 5 tends to follow 8 more often than 10% of the
time? (assuming a cipher that displays as numbers 0-9))
Also, OTP's are hard to impliment, because of the amount of data and the
need for secure exchange and storage. And they work best with a limited
number of people.
So, thinking about these long keywords, OTP, and pseudo-random stuff,
I had an idea that I think i understand. (I am not suggesting this as a real
system, I understand that I am not qualified to declare any system secure
(of course, if I can break it, it is most likely very insecure). This is
just a thought exercise).
1. Take any previously agreed upon text - one from project gutenberg
would be good.
2. Just xor'ing with the text would not be secure, nor I gather would
doing some sort of transformation add all that much security.
3. So, tally the letters' frequencies. Choose the two letters that
account for the closest percentage of the text (4.021% and
4.074% for example).
4. Keep those two and get rid of the others. If it helps security, do
some simple transformation on the letters, either on the full text or on
the modified text consisting of only two letters.
5. Convert the two letters to 1 and 0. You now have a large number of
ones and zeros that can be used as binary input for xor'ing with the
cleartext. (8 digits from the pseudo-random file for each ascii character
in the plaintext).
How secure would it be? How random would the resulting pseudo-
random file be? How does one test this? How would one go
about attacking it? Would it be easiest just to keep a database of
stats for project gutenberg files?
It is a long key but has lost most of the linguistic traits that would
give it away, right? Aside from probable weak keys, would the fact that
such a pseudo-random number is not mathematically generated be an
advantage?
I guess what it comes down to is, would anyone like to comment on the
above and / or recommend some more advanced books or web sites dealing
with cryptanalysis of pseudo-random OTP? Or for that matter a good book
to help me get up to speed on the maths involved?
I've read:
The Code Breakers by Kahn (of course)
Cryptology by Beutelspacher
one or two other introductory books that I cannot recall at the moment
Decrypted Secrets by Bauer
Applied Cryptography by Schneier
Some parts of Schneier's book were hard to follow, but the math in
Bauer's book lost me. The others I think I understood properly.
yoroshiku (japanese for "please be nice to me")
--
Osugi Sakae
"I am not a number, I am a free man."
- the prisoner
== Posted via Newsfeeds.Com, Uncensored
Cryptography-Digest Digest #183
Cryptography-Digest Digest #183, Volume #14 Thu, 19 Apr 01 16:13:00 EDT
Contents:
Basic AES question (Lou Grinzo)
Re: Crypto question ("Mark G Wolf")
Re: Basic AES question ("Tom St Denis")
Re: A practical idea to reinforce passwords (Ichinin)
Re: Crypto question ("Robert M Best")
Re: Crypto question ("Tom St Denis")
Re: C code for GF mults (Mike Rosing)
Re: All One Polynomail (Mike Rosing)
Re: Crypto question (Bill Unruh)
DL blind signature ("Cristiano")
Re: Reusing A One Time Pad ("Joseph Ashwood")
Re: OTP breaking strategy (newbie)
Re: Prime Numbers Patterns? (Bill Unruh)
Re: "UNCOBER" = Universal Code Breaker (newbie)
Good Schools of History and Informatik (Compter Science) (Frank Gerlach)
Re: OTP breaking strategy (newbie)
Re: OTP breaking strategy (newbie)
Re: Crypto question ("Joseph Ashwood")
Re: Reusing A One Time Pad ("Mark G Wolf")
Required Reading (Frank Gerlach)
Re: Any unbroken knapsack cryptosystem? ("JamesBaud")
Re: C Encryption ("JamesBaud")
Re: Reusing A One Time Pad ("Paul Pires")
Re: "UNCOBER" = Universal Code Breaker ("Joseph Ashwood")
Thanks for all replies reg:passphrase salting
(=?iso-8859-1?q?Harald=20Korneliussen?=)
From: [EMAIL PROTECTED] (Lou Grinzo)
Subject: Basic AES question
Date: Thu, 19 Apr 2001 16:17:16 GMT
I'm just starting to learn about AES, and I was wondering:
Why does the AES standard support only the key sizes of
(I think) 128, 192, and 256 bits? Is it purely to keep
the specification and logistical issues simple? Or is there
a technical reason, such as increasing the key size doesn't
make AES any more difficult to attack? (I know that last
one sounds goofy, but in a world where PKI works, almost
anything is possible. g)
Lou
--
From: "Mark G Wolf" [EMAIL PROTECTED]
Subject: Re: Crypto question
Date: Thu, 19 Apr 2001 11:21:47 -0500
So either the private or the public key can be used to decode a a message
encoded with the other. This was something I didn't catch from the RSA
specs.
Just remember to keep one and the same key of your pair always secret.
--
From: "Tom St Denis" [EMAIL PROTECTED]
Subject: Re: Basic AES question
Date: Thu, 19 Apr 2001 16:23:22 GMT
"Lou Grinzo" [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]...
I'm just starting to learn about AES, and I was wondering:
Why does the AES standard support only the key sizes of
(I think) 128, 192, and 256 bits? Is it purely to keep
the specification and logistical issues simple? Or is there
a technical reason, such as increasing the key size doesn't
make AES any more difficult to attack? (I know that last
one sounds goofy, but in a world where PKI works, almost
anything is possible. g)
Those keysizes were chosen as 128-bit = low, 256 = high and 192 = medium.
Although that's a bit naive. 128 bit keys are hardly "low security" by any
forseeable standards... (unlike factoring or DLP brute force is fairly
straight forward...)
Note that Rijndael (i.e AES) supports diff keysizes. Others like RC6
supports virtually any key size including the AES required...
Tom
--
From: Ichinin [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: A practical idea to reinforce passwords
Date: Mon, 16 Apr 2001 16:23:02 +0200
Tom St Denis wrote:
I know too little. But isn't it that UNIX employs a
scheme like that for passwords?
No unix stores a two char SALT which is stored along with your password
afaik.
Unix systems stores the accounts in /etc/passwd,
and the hashes are stored separately in /etc/shadow.
Note: No system (should) use encrypted passwords, if
encryption is used the passwords are wide open to a simple
comparison attack, whereas if you hash(passwd + salt) you
have to break every password. IIRC, even M$ have figured
this out for Win2k, NT4 passwords are not salted, that's
why Lophtcrack have such a good performance.
(OTOH - Passwords storage for Win 95/98 == Joke.)
Regards,
Ichinin
--
From: "Robert M Best" [EMAIL PROTECTED]
Subject: Re: Crypto question
Date: Thu, 19 Apr 2001 07:47:51 -1000
The security of RSA is directly related to the modulus
size. The ciphertexts will be as large as the RSA
modulus. Thus, small plaintexts will have fairly large
ciphertexts. That's life.
Do other public-key cryptosystems besides RSA have that disadvantage? Is
there a PKC where the ciphertext is as small or almost as small as the
plaintext message, even though the private and public keys may be thousands
of bits?
--
From: "Tom St Denis" [EMAIL PROTECTED]
Subject: Re: Crypto question
Date: Thu, 19 Apr 2001 17:54:28 GMT
"Robert M Best" [EMAIL PROTECTED] wrote in message
news:9bn89l$31sm$[EMAIL PROTECTED]...
The security of RSA is directly related to the modulus
size. The
Cryptography-Digest Digest #184
Cryptography-Digest Digest #184, Volume #14 Thu, 19 Apr 01 17:13:01 EDT
Contents:
Minimal Perfect Hashing ("Francois St-Arnaud")
Re: Reusing A One Time Pad ("M.S. Bob")
Re: DL blind signature (Ian Goldberg)
Required Reading For Junior Intelligence Officers (Frank Gerlach)
Re: "UNCOBER" = Universal Code Breaker (newbie)
Re: OTP breaking strategy (Mok-Kong Shen)
Re: Basic AES question (Frank Gerlach)
Re: "UNCOBER" = Universal Code Breaker ("Tom St Denis")
Re: OTP breaking strategy ("Joseph Ashwood")
Re: OTP breaking strategy ("Joseph Ashwood")
Re: I took the $5000 Goldman Challenge ("Tom Gutman")
Re: OTP breaking strategy ([EMAIL PROTECTED])
Re: A practical idea to reinforce passwords (Niklas Frykholm)
Re: newbie: cryptanalysis of pseudo-random OTP? ("M.S. Bob")
Reply-To: "Francois St-Arnaud" [EMAIL PROTECTED]
From: "Francois St-Arnaud" [EMAIL PROTECTED]
Subject: Minimal Perfect Hashing
Date: Thu, 19 Apr 2001 19:47:46 GMT
First, not that I am not at all versed in the math involved in sophisticated
cryptography, so please bear with me...
I have been looking at Minimal Perfect Hashing algorithms
(http://burtleburtle.net/bob/hash/perfect.html in particular) in a attempt
to find an algorithm that fulfills the following requirements. Note that MPH
is probably overkill for what I need to do, but this was my starting point.
The fact that Bob's algorithm above requires a list of all the keys to hash
as a input is not viable for my application.
I'm looking for a simple C algorithm for a function y = f(x) that would take
a 48-bit number x and return another 48-bit number y. f should map x to y in
a one-to-one fashion. f should be one-way, or at least, it should not be
trivial to calculate x knowing y and the algorithm used.
Any thoughts, code snips, links?
Regards,
Francois :)
--
From: "M.S. Bob" [EMAIL PROTECTED]
Subject: Re: Reusing A One Time Pad
Date: Thu, 19 Apr 2001 20:46:41 +0100
Mark G Wolf wrote:
Thanks for the history lesson but my real "question" or curiosity was the
word origins. As best as I can tell "snake oil" came from "snake" for
someone wicked and deceitful, and "oil" from the fact that many "real" cures
of the time relied on varies natural oils and balms, like eucalyptus or
evergreen oil.
Douglas has already answered your question. It comes from the peddling
of snake oil elixirs.
Just as the reference to "kid sister" is not Freudian at all, but a
crypto-slang for security against only the mythical "12 year old kid
sister". Example: monoalphabetic substitution is good only against your
kid sister.
It does not apply if your kid sister works for the NSA or GCHQ.
For other sci.crypt readers interest:
http://groups.google.com/groups?q=mark.wolf%40prodigy.netbtnG=Searchmeta=site%3Dgroups
--
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: DL blind signature
Date: 19 Apr 2001 19:54:48 GMT
[Note: I don't have the particular paper in front of me, so I'm basing
these answers on what usually happens with DL protocols in the subgroup
construction.]
In article 9bnb1s$27$[EMAIL PROTECTED],
Cristiano [EMAIL PROTECTED] wrote:
In many systems (or perhaps in all) for the blind signature based on DL, one
must choose a prime q that divides p-1 (also p is prime) and then a
generator in the moltiplicative group Zq* (cfr Chaum-Pedersen from paper
"Loyalty Program Scheme
for Anonymous Payment Systems" by Arrianto Mukti Wibowo and Kwok Yan Lam).
Careful; g isn't supposed to be a generator for Zq*. g is supposed to
be a generator for the subgroup of Zp* which is of order q.
Doing some trials with small numbers, when I compute the public key y=g^a
mod p (a is my private key) for all ap, the distribution of y may be very
bad; on the contrary, if I compute y=g^a mod q for all aq, the distribution
is as expected: I get all the elements in Zq* (g is a generator!).
Why this "strange" set up?
I think your g may be incorrect. The easiest way to choose g is:
o Let h be a random element of Zp*.
o Let g = h^((p-1)/q) mod p.
o Try again if g=1.
Clearly, g^q mod p = h^(p-1) mod p = 1, so g has order dividing q.
If g is not 1, then since q is prime, g has order exactly q, so g
generates the subgroup of order q of Zp*.
Then if you calculate y=g^a for all aq, you'll get all of the elements
of that subgroup.
My implementation of the algorithm in the above paper at page 13
(Chaum-Pedersen blind signature) doesn't work. The modulo for all the
calculations is not shown. Is it always mod p or mod q?
If you're calculating with group elements, it's mod p. If you're
calculating with exponents, it's mod q.
A last question. At step 3 there is: choose u in Zq* and v in Zq. q is
prime, what is the difference?
Zq* does not include 0.
- Ian
--
From: Frank Gerlach [EMAIL PROTECTED]
Subject: Required Reading For
Cryptography-Digest Digest #185
Cryptography-Digest Digest #185, Volume #14 Thu, 19 Apr 01 18:13:01 EDT
Contents:
Re: First cipher ("M.S. Bob")
Re: A practical idea to reinforce passwords ("Tom St Denis")
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: Reusing A One Time Pad (James Felling)
Re: Current best complexity for factoring? (Terry Boon)
Re: "I do not feel secure using your program any more." (James Felling)
Re: "I do not feel secure using your program any more." ("Tom St Denis")
Re: Basic AES question (SCOTT19U.ZIP_GUY)
Re: Any unbroken knapsack cryptosystem? ("Joseph Ashwood")
Re: OTP breaking strategy (newbie)
Re: "UNCOBER" = Universal Code Breaker (James Felling)
Re: OTP breaking strategy ("Tom St Denis")
Re: OTP breaking strategy ("Tom St Denis")
Re: OTP breaking strategy (Joe H Acker)
Re: Current best complexity for factoring? (SCOTT19U.ZIP_GUY)
From: "M.S. Bob" [EMAIL PROTECTED]
Subject: Re: First cipher
Date: Thu, 19 Apr 2001 21:39:36 +0100
[EMAIL PROTECTED] wrote:
Here's my first attempt at a block cipher. Please critique
and explain WHY as well as where I'm going wrong.
1.) Feistel network, blocklength 64 bits, 128-bit key, 16 rounds
Short (pointers to more) reading list:
Memo to the Amateur Cipher Designer
http://www.counterpane.com/crypto-gram-9810.html#cipherdesign
Self-Study Course in Block Cipher Cryptanalysis
http://www.counterpane.com/self-study.html
Memo to the Amateur Cipher Designer
by Bruce Schneier (October 15, 1998)
Congratulations. You've just invented this great new cipher, and you
want to do something with it. You're new in the field; no one's heard of
you, and you don't have any credentials as a
cryptanalyst. You want to get well-known cryptographers to look at your
work. What can you do?
Unfortunately, you have a tough road ahead of you. I see about two new
cipher designs from amateur cryptographers every week. The odds of any
of these ciphers being secure are slim. The odds
of any of them being both secure and efficient are negligible. The odds
of any of them being worth actual money are virtually non-existent.
Anyone, from the most clueless amateur to the best cryptographer, can
create an algorithm that he himself can't break. It's not even hard.
What is hard is creating an algorithm that no one else
can break, even after years of analysis. And the only way to prove that
is to subject the algorithm to years of analysis by the best
cryptographers around.
"The best cryptographers around" break a lot of ciphers. The academic
literature is littered with the carcasses of ciphers broken by their
analyses. But they're a busy bunch; they don't have time
to break everything. How do they decide what to look at?
Ideally, cryptographers should only look at ciphers that have a
reasonable chance of being secure. And since anyone can create a cipher
that he believes to be secure, this means that
cryptographers should only look at ciphers created by people whose
opinions are worth something. No one is impressed if a random person
creates an cipher he can't break; but if one of the
world's best cryptographers creates an cipher he can't break, now that's
worth looking at.
The real world isn't that tidy. Cryptographers look at algorithms that
are either interesting or are likely to yield publishable results. This
means that they are going to look at algorithms by
respected cryptographers, algorithms fielded in large public systems
(e.g., cellular phones, pay-TV decoders, Microsoft products), and
algorithms that are published in the academic literature.
Algorithms posted to Internet newsgroups by unknowns won't get a second
glance. Neither will patented but unpublished algorithms, or proprietary
algorithms embedded in obscure products.
It's hard to get a cryptographic algorithm published. Most conferences
and workshops won't accept designs from unknowns and without extensive
analysis. This may seem unfair: unknowns
can't get their ciphers published because they are unknowns, and hence
no one will ever see their work. In reality, if the only "work" someone
ever does is in design, then it's probably not worth
publishing. Unknowns can become knowns by publishing cryptanalyses of
existing ciphers; most conferences accept these papers.
When I started writing _Applied Cryptography_, I heard the maxim that
the only good algorithm designers were people who spent years analyzing
existing designs. The maxim made sense, and I
believed it. Over the years, as I spend more time doing design and
analysis, the truth of the maxim has gotten stronger and stronger. My
work on the Twofish design has made me believe this
even more strongly. The cipher's strength is not in its design; anyone
could design something like that. The strength is in its analysis. We
spent over 1000 man-hours analyzing Twofish, breaking
simplified versions and variants, and studying modifications. And we
could not have
Cryptography-Digest Digest #186
Cryptography-Digest Digest #186, Volume #14 Thu, 19 Apr 01 19:13:01 EDT Contents: Re: UNCOBER = Universal Code Breaker (John Savard) Re: Reusing A One Time Pad (Paul Pires) Re: OTP breaking strategy (newbie) Re: Current best complexity for factoring? (Tom St Denis) Re: OTP breaking strategy (Tom St Denis) Re: OTP breaking strategy (SCOTT19U.ZIP_GUY) Re: OTP breaking strategy (newbie) Let's end this OTP argument (Tom St Denis) Re: OTP breaking strategy (Joseph Ashwood) Re: Thanks for all replies reg:passphrase salting (Joseph Ashwood) Rijndael/AES VB Code (Phil Fresle) Re: UNCOBER = Universal Code Breaker (newbie) Re: UNCOBER = Universal Code Breaker (Tom St Denis) Re: OTP breaking strategy (newbie) Re: Crypto question (Robert M Best) Re: OTP breaking strategy (newbie) Re: Crypto question (Shaft) Re: Crypto question (Ivo Brugman) From: [EMAIL PROTECTED] (John Savard) Subject: Re: UNCOBER = Universal Code Breaker Date: Thu, 19 Apr 2001 22:03:52 GMT On Thu, 19 Apr 2001 14:38:17 -0300, newbie [EMAIL PROTECTED] wrote, in part: If the message is 100101010 and the ouput 11 you are quite sure to reject the possible key. The fraction of possible keys that are statistically nonrandom is nearly infinitesimal, and so this is unlikely to eliminate any possible plaintexts. Furthermore, it is generally considered an error when doing an OTP to reject random keys because they don't look random, although using a pad consisting of 000... to encrypt a message would make all but the stoutest hearts quail. (We had an interesting debate on this issue some time ago.) John Savard http://home.ecn.ab.ca/~jsavard/crypto.htm -- From: Paul Pires [EMAIL PROTECTED] Subject: Re: Reusing A One Time Pad Date: Thu, 19 Apr 2001 15:00:33 -0700 And Freud was a mother fu*king as*hole that spawned a small universe of devils, like you perhaps. But that's as bit off topic so I will refrain from commenting any further. Perhaps in a psych group. *PLONK* I find your comments rude, agumentative, childish, biggoted and irresponsible. Luckily, there is a way not to find you at all any more. -- From: newbie [EMAIL PROTECTED] Subject: Re: OTP breaking strategy Date: Thu, 19 Apr 2001 17:58:35 -0300 You are reaching what I had tried to prouve. You could distinguish with extra-information which message is valid. And select the message. Because, the plaintext is deterministic sequence. If you could distinguish truly random output and not random, you have still a way to break it. I know it is very hard. Very very hard. It is like rebuilding the plaintext with very few information. I said OTP could be broken practically. In theory, I KNOW that is unbreakable, but If you combine the context factor and other extra-information you can break it. [EMAIL PROTECTED] wrote: newbie [EMAIL PROTECTED] wrote: : When you introduce the context factor all the messages are not : equiprobable. : That is the way to try to find out the input. : If I analyse any output of 128 bits I will obtain 2^128 messages. I know : that. : But all the messages are not 100% in the context. : And all the output are not 100% random. : I have two ways to select : context factor and degree of randomness. Okay, remember that you don't have access to the pad itself. Now, suppose I have two different pads and I encrypt the following two messages: SELL 750 SHARES BUY 1000 SHARES Since I am not reusing the OTP, I encode each message with a different pad. By some bizarre coincidence, the pads happen to encrypt their messages to exactly the same result: 5e8f128c65a30954371a7e494217ad Now, given that the two messages are reasonably within the same context here, how can you possibly tell which one I actually sent? You might be able to guess which one I sent by analyzing my business and maybe by planting spies in my office, but at that point, you haven't really broken the OTP. In fact, you might figure out that I need to send the BUY 1000 SHARES message, but because I made a mistake, I sent the SELL 750 SHARES message. -- Mark Wutka -- From: Tom St Denis [EMAIL PROTECTED] Subject: Re: Current best complexity for factoring? Date: Thu, 19 Apr 2001 22:07:45 GMT SCOTT19U.ZIP_GUY [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... [EMAIL PROTECTED] (Terry Boon) wrote in [EMAIL PROTECTED]: Given this unless someone finds a factoring algorithm that is easier when the primes come after a long stream of composites, there is no additional risk. This is what I suspect. I would find it curious and surprising to find a factoring algorithm that had this property. You can bet the NSA has devoted a great deal of research into taking advantage of this flaw in the way primes are picked. But I don't think they
