Cryptography-Digest Digest #654, Volume #13 Wed, 7 Feb 01 23:13:00 EST
Contents:
Re: On combining permutations and substitutions in encryption ("Matt Timmermans")
Re: Encrypting Predictable Files [now on AONTs] ([EMAIL PROTECTED])
Re: Bleichenbacher finds bug in DSA RNG (Paul Rubin)
Re: Encrypting Predictable Files ("Matt Timmermans")
Re: Encrypting Predictable Files ("Matt Timmermans")
Re: Some basic questions ("Douglas A. Gwyn")
Re: Phillo's alg is faster than index calculus ("Douglas A. Gwyn")
Re: On combining permutations and substitutions in encryption ("Douglas A. Gwyn")
Re: Mod function (Nemo psj)
Re: On combining permutations and substitutions in encryption ("Matt Timmermans")
Re: On combining permutations and substitutions in encryption ([EMAIL PROTECTED])
Re: Encrypting Predictable Files ([EMAIL PROTECTED])
break RSA? ("Pahenty")
Re: CipherText: modification // correction ("Prichard, Chuck")
Re: relative key strength private vs public key (Dido Sevilla)
----------------------------------------------------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Thu, 08 Feb 2001 01:44:08 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Wow. So if it can be proved that P=NP, then ALL ciphers which run in
> polynomial time lose most of their security against known plaintext.
> What a horrifying possibility.
Most likely. It might turn out that some have pretty high polynomial bounds
(i.e., n^lots), which could make them pretty secure with the key sizes they
use, but we surely wouldn't be able to say "you can't break this before the
sun explodes" anymore.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encrypting Predictable Files [now on AONTs]
Date: Thu, 08 Feb 2001 02:01:25 GMT
In article <uQfPzuVkAHA.341@cpmsnbbsa09>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> I know I said I wouldn't respond however the topic has changed
substantially
> enough that I think something more can be said, and should be said by
> someone.
>
> <[EMAIL PROTECTED]> wrote in message
news:95sdqg$5jr$[EMAIL PROTECTED]...
> > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> [both talked about AONT in more detail then I went into]
>
> I think both definitions are perfectly acceptable for defining an AONT
> because the name by itself is under specified. There are
Deterministic AONT
> algorithms, this would be things like DSs concept of F(F'(F(x)))=F(x)
> regardless of how many times it is run. And there is also non-
deterministic
> AONT algorithms, OAEP is a very good example of this. Each has it's
uses,
> just as Deterministic and Non-deterministic encryption algorithms
each have
> their place. In general Non-deterministic algorithms will be more
secure if
> for no other reason than there is more entropy in the design. It is
also
> worth noting that any deterministic AONT can be made into a
> Non-Deterministic AONT by padding the pre transform data with random
bits.
> Arguments over which is "the" AONT is a worthless argument, maybe it
would
> be more helpful for everyone involved if we were to refer to them as
DAONT
> or NDAONT, where you could refer to the entire category as AONT. I
think
> this solution would allow the various degrees of specificity that
everyone
> is discussing.
> Joe
>
>
I must have missed something this almost sounds correct.
And the Joe who write previously in this thread got mad and
said he was not going to write anymore. But I think there is
more to it than just AONT and NDAONT. I think many methods
leave signatures in the result output. What I mean by this
is that if someone studies enough of your messages why let
them know what method your using for encryption. By using
methods that limit the possible set of ciphertext files
or by useing methods that limit the number of possible keys
that could have been used can't help the people in the long
run. Here I am talking about combination of compression
followed by encryption which even in Mr BS's book he claimed
it was a great idea. But why add weknesses in when it is not
necessiary.
Joe I know you can't read my stuff but try Matt's he is a
modern program using modern methods. I stll like machine
code and no rules.
Dave
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Bleichenbacher finds bug in DSA RNG
Date: 07 Feb 2001 18:14:56 -0800
Wei Dai <[EMAIL PROTECTED]> writes:
>
> Still, everyone who implements ECDSA or any other ElGamal-type
> signature scheme should double-check that the per-signature secret
> exponent k is uniformly selected between 0 and q.
Does it matter? How much entropy is really lost? Suppose half the
values between 0 and q are selected equally often, and the other half
are *never* selected. That is equivalent to reducing the group size
by one bit, right?
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files
Date: Thu, 08 Feb 2001 02:19:42 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Matt Timmermans wrote:
> > If you have ciphertext, but _no_ knowledge of the plaintext, then attack
is
> > impossible if the transformation from PT to CT is bijective. All
possible
> > plaintexts are plausible, and so you have no way to check any guess at
the
> > key.
>
> Well, that's a good tack to take, but "bijective" is misleading.
I suppose I believe you. I can't see how it's misleading, but a number of
people have said that it is.
> If the key has M bits and the ciphertext and plaintext have N > M
> bits, as is normally the case, then not all 2^N plaintexts are
> possible; only 2^M of them are possible. Thus knowledge of the
> general system itself contributes useful information about the
> plaintext.
I was very careful to "ciphertext-only attacks against the key". The
ciphertext certainly does provide some information about the plaintext, but
none about the key.
To say "bijective" and have it mean something precise, you need to specify
the domain and codomain (which I neglected to do ;-). In this case, the
domain is the set of all possible plaintexts, the range is the set of all
possible outputs from the cryptosystem (over all plaintexts and keys), and
the functions that must be bijective are the PT-CT transforms (from the
domain into the codomain) with each possible key.
In short, for any viable ciphertext, and any chosen key, there is a
corresponding plaintext. That's the surjection. The injection isn't really
necessary for this kind of security, but we usually get it for free. (So,
yes, I misspoke when I said "necessary and sufficient" in my earlier post.
Surjection is necessary and sufficient.)
Alternatively, you could say that, for every key, the crypto system must
have the same domain and codomain, but I find that much less helpful that
saying "bijective" or "surjective" -- when you design such a system, you
have no knowledge of any key, and so the definitions of the domain and
codomain fit.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Encrypting Predictable Files
Date: Thu, 08 Feb 2001 02:28:13 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> If you're going to introduce AONT into your system, you need almost
> nothing else. Simply XORing your key with the AONT'd text is enough,
> even for a fairly short key (provided that key's long enough to avoid
> being brute forced).
Hmmm. XORing with the AONT output leaves you open to known plaintext
attacks against the key, if I know the content of an entire message. XORing
with the plaintext, of course, does't prevent the AONT from being inverted.
Perhaps if you XORed your key into both? Seems like an interesting question
for someone who's actually good at determining the security of such things.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Some basic questions
Date: Thu, 8 Feb 2001 01:41:12 GMT
Geoff Blair wrote:
> 1. Can anyone point me to some source material about the very basics of
> cryptography?
Start with the sci.crypt FAQ and references therein.
I'm particularly fond of David Kahn's book "The Codebreakers"
(unabridged hardcover edition only, should be available in
many public libraries) for history, development up to WWII,
and a basic presentation of enough technical principles to
get you properly oriented. Bauer's "Decrypted Secrets" is
also good, and more modern.
> 2. I have been programing using several languages for years now and I
> was wondering about a code word I keep hearing about but have never see
> explained. What is XOR and what does it do?
XOR is short for "exclusive-or", which is a logical (Boolean)
operation with the following truth table:
A B A xor B
t t f
t f t
f t t
f f f
As you can see, "A xor B" means "either A or B, but not both".
It has the useful property that A xor B xor B reproduces A,
so if A is a plaintext (message) bit and B is a key bit,
then A xor B can be used as a ciphertext bit, and the possessor
of the key can recover the original message from the ciphertext
by performing *the same operation* (xor-with-B) as was used to
encipher the message. Of course you should do this independently
for each bit of the message. Such a system, *if* the key bits
are truly random and are used for only one encryption before
being discarded, is an instance of a "one-time pad" and is the
standard example of an encryption method where it can be
*proved* that, apart from the message length, no information
that he didn't already have is provided about the plaintext to
anyone who intercepts the ciphertext, no matter how clever he
is at cryptanalysis. The reason we don't use this in practice
is that providing a suitable amount of key bits is a big problem.
> 3. What is the average key length for the best security systems online
> right now?
I don't know what you mean by "security systems on line".
Web browsers usually use a 128-bit key these days for things
like SSL (used for so-called "secure Web sites"). It is
generally considered that the common "RSA" public-key system
used with a key length of 1024 or more is secure insofar as
the underlying encryption algorithm goes, although any given
implementation of a system could have other flaws.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Phillo's alg is faster than index calculus
Date: Thu, 8 Feb 2001 01:46:02 GMT
Tom St Denis wrote:
> Don't advertise a method you're not willing to back up with proof. That's
> like me saying "there's no god" and I will let the theologians work out the
> details.
Hm, that analogy could work in a different way --
i.e., it's their problem, so why shouldn't they be the ones
to work on it?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Thu, 8 Feb 2001 02:04:16 GMT
Matt Timmermans wrote:
> ... but we surely wouldn't be able to say "you can't break this before the
> sun explodes" anymore.
In which case that was never true, was it?
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 08 Feb 2001 02:48:43 GMT
Subject: Re: Mod function
MOD is a math function.. i seriously doubht anyone is going to sue over it.. i
mean come on its a clock function.. what bassis could someone have for
ownership?
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: On combining permutations and substitutions in encryption
Date: Thu, 08 Feb 2001 02:58:55 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Matt Timmermans wrote:
> > ... but we surely wouldn't be able to say "you can't break this before
the
> > sun explodes" anymore.
>
> In which case that was never true, was it?
Quite ;-)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: On combining permutations and substitutions in encryption
Date: Thu, 08 Feb 2001 02:54:32 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> Matt Timmermans wrote:
> >
> > "Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > What do you mean the size of the input?
> > >
> > > Or, to put it another way, suppose you have AES with a 192 bit
key.
> > > Write the relationship between the key bits, the plaintext bits,
and
> > > the ciphertext bits as a 3SAT problem. Does this conversion take
> > > polynomial in terms of 192, or superpolynomial in terms of 192?
(I
> > > think you've said the conversion takes polynomial time in terms of
> > > 192, but I'm not sure.) If it takes polynomial time to convert,
> > > then there cannot be more than polynomial terms in the 3SAT
problem.
> > > If it takes superpolynomial time to convert, then there may [or
may
> > > not] be a superpolynomial number of terms.
> >
> > Strictly speaking (though not as strictly as Bryan does, which is
why
> > I'm posting yet another response ;-), the reduction takes time
> > polynomial in worst-case run time of the algorithm (AES, in this
> > instance) for inputs of the given size. So (assuming key size
> > unbounded), if the worst-case running time of AES(K,M) is polynomial
> > in length(K)+length(M), then the question "AES(K,M)==C?" can be
> > converted to 3-SAT in time polynomial in length(K)+length(M).
>
> Wow. So if it can be proved that P=NP, then ALL ciphers which run in
> polynomial time lose most of their security against known plaintext.
> What a horrifying possibility.
I guess that is why the NSA and the crypto gods keep trying to
get people to use short key systems. This thread is making me feel
better about scott19u and its million+ bit key all the time. Since
You can't break it with short messages. Since even if you have a
plain text cipher text pair. You really have no information about
what the correct 19 bit s-table is. Many soultions will not have
any of the S table values correct. So it is potentailly more secure
from this kind of future attack.
David
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encrypting Predictable Files
Date: Thu, 08 Feb 2001 03:13:32 GMT
In article <1vng6.72440$[EMAIL PROTECTED]>,
"Matt Timmermans" <[EMAIL PROTECTED]> wrote:
>
> "Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > If you're going to introduce AONT into your system, you need almost
> > nothing else. Simply XORing your key with the AONT'd text is
enough,
> > even for a fairly short key (provided that key's long enough to
avoid
> > being brute forced).
>
> Hmmm. XORing with the AONT output leaves you open to known plaintext
> attacks against the key, if I know the content of an entire message.
XORing
> with the plaintext, of course, does't prevent the AONT from being
inverted.
> Perhaps if you XORed your key into both? Seems like an interesting
question
> for someone who's actually good at determining the security of such
things.
>
>
This is a good question I hope you can find someone to anwser it.
Since this is sort of what SCOTT19u does. IT uses the start of the
plain text to find a spot in the S-table where entries are XORed
against the plaint text. Then you could say it does the AONT transform
and then takes the current cipher text 19 bits to find another spot
in the S-tables and starts XOR form there. So its very similar to
what your saying. In fact if the first plaintext 19 bits matches the
first 19 bits of cipher text it would exactly be your situation.
such a case would occur once every 2^38 times. The question is
can one get any of the S-table values from such plaintext cipher
text pairs. Paul Onions where are you.
David Scott
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Pahenty" <[EMAIL PROTECTED]>
Subject: break RSA?
Date: Thu, 8 Feb 2001 09:43:31 +0600
http://www.mb.com.ph/INFO/2001-02/IT020601.asp
Pinoy who discovered new faster way of decoding RSA encryption explains
claim
Mathematics enthusiast Leo de Velez who claims to have discovered a faster
way of decoding RSA encryption believes that his findings are solid since
nobody is still using his formula of 2^X = 1 mod N where N is given as the
public key, find X.
RSA is an Internet encryption and authentication system that uses an
algorithm developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman.
"To do this, one approach that I claim as also mine is to multiple N with a
number Y. Such that N * Y will give a binary product with all bit one," De
Velez said.
Example: N = 55, its binary representation is 110111 If we multiply N by Y =
19065, the product will be equal to 11111111111111111111 (20 digits).
To find Y = 19065, we just add 110111 to itself many times but shifting the
binary number to the left so that we always add 1 to the zero to make it 1.
For instance,
110111
+ 110111
-------
111101111
+110111
------------
10101011111
and so on until the sum is all 1. De Velez said the shifting to the left
represents the number Y = 19065 = 100101001111001. The first digit on the
right = 1 representing the top most number in the addition above.
Then, it was shifted 3 position to the left, the first two position, since
there was no addition represents 0, the third represent 1. You can compare
it to the binary digit of Y above.
Going back, the number of 1's in the final sum is 20 and that is X. This
means X = 20. This will now be used to calculate the private keys.
De Velez said that RSA has sent him an e-mail to say that the other keys
that he discovered can actually decipher 100 percent of the codes. "This
means the private key is not unique which a layman like me believe is
unique."
Ron Rivest of RSA has informed De Velez: "In response to my inquiry, which
was: Maybe you could explain how it works on the following example?
n = 55
e = 3
ciphertext = 2
"You (De Velez) said: Using the extended Euclidian algorithm twice with some
empirical formula, you can get a private key of 7 which can decipher about
80 percent of the codes. Using again the extended Euclidian algorithm, you
can calculate 27, 47 as some of the other private keys that can decipher the
code."
"You may or not be aware that any decryption exponent d that satisfies e * d
= 1 (mod lambda(n)) where lambda(n) = lcm(p-1,q-1) will work perfectly as an
RSA decryption exponent, since every element of the multiplicative group
modulo n (where n = pq) will have order dividing lambda(n).
Note that lambda(n) divides phi(n) always. In the example with n = 55, we
have phi(n) = (p-1)(q-1) = 40 and lambda(n) = 20.
Since 7 is a multiplicative inverse of 3, modulo 20, then 7 is a perfectly
good decoding exponent for 3. It doesn't just decrypt 80% of the values; it
decrypts them all. Since 3*27=81=1 (mod 20) and 3*47=141=1 (mod 20), the
decoding exponents 27 and 47 are also perfect decoders corresponding to the
exponent 3.
Rivest noted that any technique that can find a multiplicative inverse of e
modulo lambda(n) can be used to factor n. "So if your approach finds such
exponents somehow, then you also have a factoring algorithm, not just an
algorithm to break RSA," Rivest said. (Edu H. Lopez)
------------------------------
From: "Prichard, Chuck" <[EMAIL PROTECTED]>
Subject: Re: CipherText: modification // correction
Date: Thu, 08 Feb 2001 03:41:43 GMT
Actually this line is intended,,
$self->{S_KEY} .= chr($self->{MASK}[ord($key) - 31] + 31);
There is alot of work that can be done to improve the algorithm at this
line.
To effect greater randomness and cipher strength in a most efficient
manner.
"Real progress is often measured in the smallest units around." -C.
Prichard
(That is the only important amount remaining of the work to be done
improving a struggle for perfection.)
This addition will be a significant improvement to the implementation.
A new JavaScript version is in progress.
C. Prichard
http://greentv.crosswalkcentral.com
http://members.nbci.com/chuck_prichard/
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: relative key strength private vs public key
Date: Thu, 08 Feb 2001 11:58:12 +0800
There appears to be a section on this in the Snake Oil FAQ, although I
have no idea how they came up with the numbers in the table there:
Table 2: Key Lengths With Similar
Resistance to Brute-Force Attacks
Symmetric Key Length Public Key Length
56 bits 384 bits
64 bits 512 bits
80 bits 768 bits
112 bits 1792 bits
128 bits 2304 bits
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
** 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
******************************
