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 00101010001111010010010001001001000100100......
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 -0000
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 clown and a troll who has been looming around for nearly a
year.
Don't mistake a "regular" (troll) with a knowledgeable person: that self-proclaimed
"security expert" is not even a remailer user. In the past, he proved himself unable
to check a PGP signature, and got ridicule from every single technical topic he wanted
to talk about.
Besides false or inaccurate or misleading technical misinformation, his posts are
about his avowed mental illness, or for bashing remops or real freedom fighters: he
likes to quarrel with every one, and stir shit. Sometimes, it is even pure delirium
(when he misses his pills?)
One of his last actions was to stage a hoax about his own suicide, just to try to grab
some sympathy, after he had been exposed as a troll and technically incompetent.
The worst being his teasing of Script-Kiddie until it triggered a new flood on apas.
Of course, he refuses to apologize.
Actually, the level of contempt he shows for remailer users:
they don't give their names, while he does
that can't do anything against him, without giving their names
is in no way different from what is displayed by Pangborn, Burnore and the like
Ignore him completely, killfile him, respect others' killfiles
KILLFILE:
To put him in your killfile, put "Author: Boschloo"
That will make disappear both him and people who warn about him
If you want to tell him to buzz off, or warn about him,
use a nickname containing "Boschloo" (Boschloo Hater, Boschloo Sucks,...)
to accomodate such killfile for "regulars", and still warn newbies
COURAGE:
Boschloo is getting _no_ answer from apas any more.
He has to crosspost to various newsgroups to try to grab some attention.
In a few months, it will be gone.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Patterns?
Date: 19 Apr 2001 04:15:06 GMT
AY <[EMAIL PROTECTED]> wrote:
> Also, something that everyone should know (but not discussed in HAC!) is
> that the digits of a multiple of 3 always add up to a multiple of 3 (think
> recursion). I just wonder if there's a big list of such curiosities
> somewhere?
I asked on sci.math about this a year ago or so. The consensus was, IIRC,
that trying to generate numbers which didn't satisfy these sorts of
relations was unlikely to be more efficient than sieving over randomly
chosen intervals.
Some number theory books have a discussion of divisibility tests and where
the come from. Ore's _Number Theory and Its History_, for example.
-David
------------------------------
From: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 04:38:45 GMT
You simply don't understand a one time pad. Every word will match at
every position for some bitstring.
--
Samuel S. Paik | [EMAIL PROTECTED]
3D and digital media, architecture and implementation
------------------------------
Date: Thu, 19 Apr 2001 07:54:23 +0300
From: Jyrki Lahtonen <[EMAIL PROTECTED]>
Subject: Re: C code for GF mults
David Eppstein wrote:
>
> In article <SwaD6.29229$I5.122679@stones>,
> "Brian Gladman" <[EMAIL PROTECTED]> wrote:
>
> > There are several ways of doing this but one way for many fileds that are
> > important is to express elements in terms of smaller subfieilds. Hence
> > elements in GF(256) are expressed in the form Ax+B where A and B are in
> > GF(16). We hence exchange one multiplication in GF(256) for what seems like
> > four in GF(16) (and some xors/shifts).
>
> GF(256) (and GF(2^2^k) more generally) also has an interesting
> representation devised by J.H.Conway that I think may not fit into the
> usual polynomials-mod-primitive-polynomial framework:
> see http://www.ics.uci.edu/~eppstein/numth/nim.shar.gz
> for (C++) code.
I'm not familiar with Conway's work, but let's elaborate on
GF(2^(2^k)).
Define elements x_i recursively as follows:
x_0=1, and
for i>0 let x_i be a root of the equation
T^2+x_{i-1}T+1=0 (*)
It is relatively straightforward to see that x_k then generates
(but is not primitive by a long shot) the field GF(2^(2^k)).
If memory serves me right, it even generates a normal base.
Using the bases {1,x_k} over GF(2^(2^(k-1))) it is, indeed,
fairly straightforward to build a fast multiplication algorithm
a la Karacuba.
--
Jyrki Lahtonen, docent
Department of Mathematics,
University of Turku,
FIN-20014 Turku, Finland
http://users.utu.fi/lahtonen
tel: (02) 333 6014
------------------------------
From: "Andre Kim" <[EMAIL PROTECTED]>
Subject: All One Polynomail
Date: Thu, 19 Apr 2001 14:50:32 +0900
Reply-To: "Andre Kim" <[EMAIL PROTECTED]>
I'd like to know the property of all one polynomial for irreducible
polynomial over GF(2^m). If you have any knowledge, book, or article, please
let me know.
Regards!
Andre, Kim.
------------------------------
From: [EMAIL PROTECTED]
Subject: First cipher
Date: Wed, 18 Apr 2001 21:00:38 -0800
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
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...
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 chosen, say b7,b6,...,b0
Two bits, say b1,b0 chose one of four S-boxes. Each S-box
is an 8x8 matrix with 4-bit elements which are chosen
randomly. Three other bits, say b4,b3,b2 , choose the
S-box row, the last three bits choose a S-box column.
The process is repeated on 8 different bits from (c), etc.
e. Left circular shift the output from (d) with the number
of shifts determined by two bits from the subkey.
The output of (e) is the input to the Fiestel network...
Any hints on how to analyze security and efficiency would be
appreciated.
veb3
4/18/01
------------------------------
From: "Robert M Best" <[EMAIL PROTECTED]>
Subject: Re: Crypto question
Date: Wed, 18 Apr 2001 21:11:53 -1000
I'm have not been able to find real-world examples of RSA. Since the
modulus n is the product of two large primes, don't both the public key
(n,e) and private key (n,d) have to be really large numbers like a thousand
bits or so? And how small can the "message" be before RSA becomes
impractical? DES can securely encrypt/decrypt a message of 64 bits with a
key of only 56 bits. Can RSA do that? If RSA encrypted a message of 64
bits, would a typical RSA public key be a thousand bits or so even though
the message is only 64 bits?
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Patterns?
Date: Thu, 19 Apr 2001 09:56:54 +0200
"Wizartar" <[EMAIL PROTECTED]> wrote:
> All numbers ending in 0, 2, 4, 5, 6, 8, once you get above 9 are
> definetly not a prime numbers.
Yes. This test eliminate candidates that evenly divide by 2 or 5.
This result can be generalized to any modulus m: if (x mod m)
and m have a common divisor d>1, then d divides x, so if x>m
then x is not prime.
For example, taking m = 30, we need only consider candidates x>30
such that x mod 30 is one of 1 7 11 13 17 19 23 29.
If we do not need to find all primes in an interval, but only a
random-looking prime (as occurs in RSA key generation), an option
is to pick the value r of (x mod n) at random among the possible
candidates, then test for primality of numbers of the form k*m+r.
Francois Grieu
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Thu, 19 Apr 2001 08:49:20 GMT
Mok-Kong Shen wrote:
>Bryan Olson wrote:
>>
>> Mok-Kong Shen wrote:
>> > Mok-Kong Shen wrote:
>> > > The PRNGs are assumed to be independent (I forgot to
>> > > explictly say that) and uniform.
[Snip...]
>> > Addendum: The scheme of Wichmann and Hill is intended
>> > to get a more uniform stream from a number of not well
>> > uniform streams.
[...]
[Bryan]
> You now say the
> intentions contradict what you just said was assumed.
> 'What' I said contradicts 'what' I assumed?
Yes. The edits above should make that clear.
>> No. You stated a bogus result. What evidence we have
>> indicates that your it's false.
>
>'What' is the bogus result?
"thus rendering the analysis more difficult." There is no
support for this assertion in the note or in the follow-ups.
>'What' is the evidence?
As stated in the strand. The modification throws away
important properties of the scheme. The resulting stream
can come out worse than an individual component stream.
--Bryan
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Thu, 19 Apr 2001 01:51:22 -0700
Mark G Wolf wrote:
> I think a modestly large OTP used in conjunction with other key encryption
> technologies is realistically unbreakable.
So here's where things stand:
OTP:
Shannon proved perfect secrecy
The "reusing" scheme:
Mark G. Wolf thinks it's realistically unbreakable
--Bryan
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Data dependent arcfour via sbox feedback
Date: Thu, 19 Apr 2001 01:58:08 -0700
[EMAIL PROTECTED] wrote:
> I tried to read this thread and related topics, but there are too many
> posts for me. Does Ritter say anywhere whether or not he has tested his
> broad position in court? I don't think his broad interpretation would
> hold. Lets see what he does if a wealthy company like IBM (deep pockets
> in the legal dept.) implements something similar to that described in
> this thread.....
I don't think it's court-tested. The modified cipher is not
likely to be made in usable form, or used or sold. I certainly
wouldn't want to goad anyone into filing lawsuits.
--Bryan
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: Rabin-Miller prime testing
Date: Thu, 19 Apr 2001 09:18:26 GMT
In article Simon Josefsson wrote:
>Bryan Olson <[EMAIL PROTECTED]> writes:
>
>> 2. Do one base-2 Miller-Rabin (or Fermat) test.
>>
>> 3. Do several random-base Miller-Rabin tests, or a Lucas
>> test.
>>
>> In practice, step 2 dominates the run time, since it usually
>> rejects many candidates.
>>
>> Alternately, we can generate provable primes in not much
>> more time, but there's no practical advantage.
>
>Depends on the threat model -- if you're verifying someone else's
>numbers for primeness, you can be deceived if you're only using
>Miller-Rabin or similar methods.
Right, but this was about prime generation. As I noted, prime
testing and prime generation have different requirements.
>Even when generating keys yourself, prime "witnesses" is useful if you
>don't completely trust the application or especially the randomness
>source. IMHO applications should include a prime witness with primes
>they generate, if for no other reason to prove the integrity of the
>application and randomness source.
I don't think so. There are short-certificates for
primality, but the Miller-Rabin "witnesses" testify to
composite-ness, not primality. I don't see what they have
to do with the random source either; given insufficient
entropy, the significant mode of failure is to produce
predictable primes, not non-primes.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypto question
Date: 19 Apr 2001 09:43:09 GMT
Robert M Best <[EMAIL PROTECTED]> wrote:
> If RSA encrypted a message of 64 bits, would a typical RSA public key
> be a thousand bits or so even though the message is only 64 bits?
Yes. 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.
-- [mdw]
------------------------------
From: Lassi =?iso-8859-1?Q?Hippel=E4inen?= <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers Patterns?
Date: Thu, 19 Apr 2001 10:26:32 GMT
Wizartar wrote:
>
> Hi,
>
> Is there any logic to prime numbers, I've been doing a study of them for a
> computer course and still have a long way to good before I get a paper
> together.
>
> For an example of what I mean:
> All numbers ending in 0, 2, 4, 5, 6, 8, once you get above 9 are defiantly
> not a prime numbers. So only numbers ending in 1, 3, 7, 9 need to be
> tested. Are there any other common patterns, once you reach higher numbers?
>
> Any help would be useful,
> Wiz
These are the easy ones. But they are a sort of an artifact, as they
follow from our choice of base 10 = 2*5.
You can develop similar rules for any other base. The more different
factors in the base, the more possibilities. Unfortunately the ones used
in computers, two or its powers, are rather dull.
-- Lassi
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Thu, 19 Apr 2001 10:30:45 GMT
"SCOTT19U.ZIP_GUY" wrote:
> Your example of yes or no was a good one. If I ask someone
> a yes or no type of question and the encrypted OTP answer
> comes out as "QW" I think the responce may have been NO.
> While if "ZXV" was the encrypted response I think the
> anwser was YES. If one sent 1000 characters encrypted with
> a OTP you have no idea if he answersed "YES","NO,"MAYBE",
> SOMETIMES",or he may have asked for further clarification.
Where I come from, we take for granted that the message length
can be determined by the eavesdropper. If nothing else, he can
certainly place an upper bound on it.
Yes/no responses should be a single bit anyway.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Thu, 19 Apr 2001 10:31:21 GMT
Tom St Denis wrote:
> All equal sized messages are equal probable,
No, they're not.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Thu, 19 Apr 2001 10:33:04 GMT
"M.S. Bob" wrote:
> ... I believe some of those spies died.
Everybody dies. Some of the spies were executed.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Thu, 19 Apr 2001 10:47:21 GMT
Mark G Wolf wrote:
> > Ah. It is called "Snake Oil".
> Yeah but can you really make oil from snakes, or is that the joke.
You ought to be able to look it up in a dictionary, but:
There was an era in American history when traveling "medicine shows"
were fairly common. The idea of a medicine show is that there would
be entertainment, and during "commercial breaks" a salesman would
hawk his product, generally an "elixir", as capable of curing a wide
variety of common afflictions, e.g. gout, arthritis, maybe even
blindness. Usually the effectiveness of the elixir would be
demonstrated on a volunteer (who actually was a confederate of the
salesman), effecting a "miracle cure". The ingredients of the
elixir were advertised as being any of a variety of exotic
substances, apparently "snake oil" sometimes being one of these.
In actuality, there was almost always a substantial amount of
ethanol in the elixir, so there were always some happy customers.
In the early era of mail-order catalogues, around the turn of the
century (1900), similar elixirs were advertised for sale, but they
contained the wonder ingredient thorium. I'm not a big fan of
government interference in trade, but in such cases an outfit like
the Food and Drug Administration actually has a valid role to play.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Thu, 19 Apr 2001 10:55:06 GMT
Mok-Kong Shen wrote:
> ... Now please present
> your chi-square results in an easily understandable
> way in conformance with common practice. Please use
> confidence level of 0.95 or higher.
I recommend presenting the inverse-chi-square (e.g. using the
QChiSq function found in my ihat archive). That way the same
result can be directly compared to whatever significance level
the user chooses.
> It is generally preferred to have a larger number of categories
> rather than fewer categories and large number of entries per
> categories,
No. For hypothesis testing, the strongest result (best
discriminating ability) occurs when all the available information
goes into a simple yes/no determination (2 categories).
A rule of thumb is that Pearson's chi-square test often gives
misleading results if there are not at least 5 counts in each
bucket.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Thu, 19 Apr 2001 10:58:33 GMT
newbie wrote:
> You forget the context where the word occur.
No, I'm not forgetting anything.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Thu, 19 Apr 2001 11:02:37 GMT
newbie wrote:
> You have to analyse the context of the plain-text.
> You are not going to find a word "homo erectus " in business letter.
And after I examine the OTP-encrypted ciphertext, my estimate of
the likelihood that "homo erectus" is in the plaintext is exactly
the same as it was before I examined the ciphertext. Therefore I
have obtained no information from my examination of the ciphertext.
That is the operational definition of perfect secrecy.
> Algo to decrypt OTP :
> - look for words used in the context (business, personal, etc...)
> - try to slide the corresponding bit-string on ciphertext until it
> matches.
> - build the disclose little by little.
Doesn't work.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Thu, 19 Apr 2001 11:03:11 GMT
Tom St Denis wrote:
> An OTP is not possible to break since all messages are equally
> probable.
No! No wonder the newbie is so confused.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Thu, 19 Apr 2001 11:06:00 GMT
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.
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.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
