Cryptography-Digest Digest #247, Volume #13 Thu, 30 Nov 00 15:13:01 EST
Contents:
Re: Vulnerability to Attack ("James Dabbs")
Re: keysize for equivalent security for symmetric and asymmetric keys (Roger
Schlafly)
Re: keysize for equivalent security for symmetric and asymmetric keys (DJohn37050)
Re: keysize for equivalent security for symmetric and asymmetric keys (John Savard)
Re: keysize for equivalent security for symmetric and asymmetric keys (John Savard)
Re: keysize for equivalent security for symmetric and asymmetric keys (John Savard)
Re: keysize for equivalent security for symmetric and asymmetric keys ("Trevor L.
Jackson, III")
Re: Trivial Encryption Algorithm (TEA) (Simon Johnson)
Re: Trivial Encryption Algorithm (TEA) (Simon Johnson)
Re: keysize for equivalent security for symmetric and asymmetric keys (Roger
Schlafly)
Re: Public key encryption in Javascript? ([EMAIL PROTECTED])
Re: New cipher idea (Benjamin Goldberg)
----------------------------------------------------------------------------
From: "James Dabbs" <[EMAIL PROTECTED]>
Subject: Re: Vulnerability to Attack
Date: Thu, 30 Nov 2000 12:26:30 -0500
All packets are prepended with a 64-bit random number. It takes the
encrypted result of each 64-bit block and XOR's it with the next 64-bit
block before encrypting it, and so on. It is unclear whether this is
standard practice or a proprietary solution.
The password note is interesting. It would seem to be that this is a clear
weakness of the protocol with a documented history of similar problems. In
this system, passwords are pre-generated by a machine as part of the
manufacturing process of the client box. After the systems are in the
field, the client box can change the password by generating a random string
and passing it to the server under protection of the *current* key from the
*current* password. These boxes are physicsally secure - if they are not,
then there is no need for a culprit to bother to crack the link because he
can probably get what he wants right there. However, it has always bothered
me that if someone cracked the code, he could "follow" all password changes
after that.
Thanks..
James Dabbs
Eric Lee Green <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Thu, 30 Nov 2000 10:28:07 -0500, James Dabbs
<[EMAIL PROTECTED]>
> wrote:
> >a whole packet. The TEA key comes from a hash (proprietary, as far as I
can
> >tell) of the account password string. After a connection, the first PDU
> >contains the account ID string in the clear. Everything else after that
is
> >encrypted. The password itself is not transmitted over the link.
>
> This is succeptible to dictionary attacks. If the hash algorithm can be
> duplicated (a simple case of reverse-engineering a stolen copy of the
> software), a large selection of pre-defined passwords can be hashed with
> the algorithm. Then each resulting hash key can be attempted as a
> decrption key on packets captured off of the network. In one study, this
> approach "cracked" over 80% of the passwords used on a network. This
> approach is also used for most attacks against Microsoft's CHAP
> authentication protocol.
>
> In addition, the protocol may be succeptible to replay attacks, depending
> upon how encryption is handled in the resulting packets (do they have
> a random value pre-pended to them and use a good cipher feedback mode?).
>
> Finally, password storage on the server side is an issue. It may be
> possible for an attacker to gain access to the password store. This
> gives the attacker access to log in as anybody, since all he has
> to do is use the hashes in the password store to encrypt his connections.
>
> All in all, I believe you are quite correct to be worried about the
> security of this scheme. It appears to use techniques which have been
> repeatedly "cracked" in the past. I suggest that you go to
> http://www.counterpane.com and read Bruce Schneir's and Mudge's cracks
> of various versions of Microsoft CHAP, which uses similar techniques
> (though to a different end).
>
> Regarding solutions, SSL is certainly a possibility, and one which has
> received a large amount of cryptoanalysis. I would suggest, however,
> consulting with a competent designer of cryptographic systems because
> SSL is only part of a system, and by no means ensures that the entire
> cryptographic system is secure.
>
> --
> Eric Lee Green http://www.badtux.org
> [EMAIL PROTECTED]
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 30 Nov 2000 09:23:46 -0800
DJohn37050 wrote:
> Regarding the ANSI X9 group,
> not only bankers sit on ANSI X9 workgroups. NIST and NSA representatives sit
> on ANSI X9 committees to ensure the result is reasonably good, security-wise.
> They speak up when it is not. We are talking real money here and bankers want
> it to be protected.
Bankers control the committee. Yes, bankers deal with real money
but that doesn't make them infallible.
> Regarding the keysize chart,
> NIST has a working arrangement with NSA to be able to consult with them on
> these kind of security related matters.
But you don't know whether NIST asked NSA about the chart, nor
what NSA might have said.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 30 Nov 2000 17:46:58 GMT
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Roger,
The bankers and others look to NIST and NSA to speak with authority on matters
of security. NIST and NSA do not speak much, but when they do, the bankers
listen. And so do I.
It was NSA's statement that DES was suitable for its intended purpose that gave
confidence to the bankers that there were no hidden weaknesses. Their
statement turned out to be true, DES thwarted attacks that were not published
until 20 years later and was only obsoleted by the advance of technology.
There was much discussion in ANSI X9 about whether to include ECC composite
binary fields. There were concerns but no known public attack at the time.
Finally NIST spoke out that they would be disallowed in the NIST recommended
curves. The entire group then decided to disallow them. Only later did Nigel
Smart find a specific weakness.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 30 Nov 2000 18:26:13 GMT
On Thu, 30 Nov 2000 09:23:46 -0800, Roger Schlafly
<[EMAIL PROTECTED]> wrote, in part:
>DJohn37050 wrote:
>> Regarding the keysize chart,
>> NIST has a working arrangement with NSA to be able to consult with them on
>> these kind of security related matters.
>But you don't know whether NIST asked NSA about the chart, nor
>what NSA might have said.
My suspicion is they didn't ask. The NSA says, with great difficulty,
only the most limited things in this area.
Saying that none of the 5 AES finalists was crappy probably was enough
public disclosure of that kind (current and technical) to last them a
couple years, even if the agency _is_ now making abundant releases of
historical information.
Based on one particular way of thinking about this, I would be
inclined to say that a 128-bit symmetric key is matched in security by
an RSA modulus having the following properties:
it is 1152 bits long, and the product of two primes, p and q, p>q,
where q is between 512 and 384 bits in length.
But that evaluation is based on Fermat factorization, (have the ratio
between p and q vary over a wide search range) and considerably more
powerful methods are available.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 30 Nov 2000 18:28:41 GMT
On Wed, 29 Nov 2000 21:30:02 GMT, Bob Silverman <[EMAIL PROTECTED]>
wrote, in part:
>In a sense, you are trying to compare the difficulty of flying
>to different galaxies. The greater Magellenic cloud is only 150,000
>light years away, while M31 is 2 million light years away. Is the
> latter "harder to reach"? There is no such thing as
>"twice as impossible with forcastable technology".
Yes, but who says the technology around in 100 years from now is all
going to be forecastable today?
Quantum computing is pretty frightening in itself, and that already is
being played with in the laboratory!
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 30 Nov 2000 18:33:03 GMT
On 29 Nov 2000 23:43:20 GMT, [EMAIL PROTECTED] (David Wagner)
wrote, in part:
>But: I'm not a factoring expert, so I'm wildly guessing here, and
>the above should be treated as a speculative hypothesis. I'd be
>interested to hear opinions on whether you think that this is a
>valid concern.
I think it is very valid, in another way. The 'meet-in-the-middle'
attack is automatically assumed to mean not merely that double-DES is
'broken', but that it isn't even worthwhile, say, to go from
256-bit-key Rijndael to double 256-bit-key Rijndael, you would have to
go all the way to triple 256-bit-key Rijndael to get an improvement.
So people do seem to be behaving as if memory is infinite.
However, when answering the question 'is this cipher secure', it does
make sense to look at it from the pessimistic side, so if memory costs
are harder to quantify than the number of steps an algorithm takes,
this isn't an unreasonable simplification - as long as one doesn't
forget it's a simplification.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Thu, 30 Nov 2000 13:53:15 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Bob Silverman wrote:
> There is no such thing as
>
> "twice as impossible with forcastable technology".
Now this should be enshrined in the literature so that "very impossible"
ranks up there with "very unique".
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: Thu, 30 Nov 2000 18:49:14 GMT
In article <[EMAIL PROTECTED]>,
John Myre <[EMAIL PROTECTED]> wrote:
> James Dabbs wrote:
> >
> > I've seen a brief history of this algorithm. First, it was
invented, then
> > someone broke it, then the author "fixed" it by changing the key
digest.
> <snip>
>
> I think that the "someone" is David Wagner, who actually
> posts here quite often. Also, I think it may be a little
> much to say he "broke" it; it depends on your definitions.
>
> If I understand correctly, the vulnerability of consequence
> is to an attack that requires encryption of 2^32 blocks under
> each of two related keys (i.e., the attacker gets to choose
> how the second key differs from the first). Whether this is
> a real attack depends on your circumstances.
>
> On the other hand, almost anyone would agree that 3DES is
> "safer": not because we know so, but because it has had
> much more analysis without falling.
With this said, there are a few things we can prove which show 3DES is
securish. I.e. The key size is great enough, DES is not a group etc....
Is it possible to show that an algorithm can have a minimum
Differential attack, for example, that requires 2^40 known plain-texts
even if the attack hasn't been found?
> On a third hand: the protocol(s), and other system-level
> implementation issues, are far more likely to be a
> problem than the actual encryption algorithm.
>
> JM
>
yeah, a trojan can recover the key far more effectivly than a known
plain-text actack.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Trivial Encryption Algorithm (TEA)
Date: Thu, 30 Nov 2000 18:45:14 GMT
In article <[EMAIL PROTECTED]>,
John Myre <[EMAIL PROTECTED]> wrote:
> James Dabbs wrote:
> >
> > I've seen a brief history of this algorithm. First, it was
invented, then
> > someone broke it, then the author "fixed" it by changing the key
digest.
> <snip>
>
> I think that the "someone" is David Wagner, who actually
> posts here quite often. Also, I think it may be a little
> much to say he "broke" it; it depends on your definitions.
>
> If I understand correctly, the vulnerability of consequence
> is to an attack that requires encryption of 2^32 blocks under
> each of two related keys (i.e., the attacker gets to choose
> how the second key differs from the first). Whether this is
> a real attack depends on your circumstances.
>
> On the other hand, almost anyone would agree that 3DES is
> "safer": not because we know so, but because it has had
> much more analysis without falling.
With this said, there are a few things we can prove which show 3DES is
securish. I.e. The key size is great enough, DES is not a group etc....
Is it possible to show that an algorithm can have a minimum
Differential attack, for example, that requires 2^40 known plain-texts
even if the attack hasn't been found?
> On a third hand: the protocol(s), and other system-level
> implementation issues, are far more likely to be a
> problem than the actual encryption algorithm.
>
> JM
>
yeah, a trojan can recover the key far more effectivly than a known
plain-text actack.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 30 Nov 2000 11:00:49 -0800
DJohn37050 wrote:
> The bankers and others look to NIST and NSA to speak with authority on matters
> of security. NIST and NSA do not speak much, but when they do, the bankers
> listen. And so do I.
>
> It was NSA's statement that DES was suitable for its intended purpose that gave
> confidence to the bankers that there were no hidden weaknesses. Their
> statement turned out to be true, DES thwarted attacks that were not published
> until 20 years later and was only obsoleted by the advance of technology.
So now the NSA is acknowledging that 1024-bit RSA and 161-bit ECC
are both suitable for their intended purposes? Ok, fine, but that
doesn't mean that they have the same security.
As for the X9 bankers, they are the ones who decided that RSA is
more secure if you use the Bob Silverman pseudo-random prime number
generator. Their crypto wisdom does not impress me.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Public key encryption in Javascript?
Date: Thu, 30 Nov 2000 18:56:31 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Bailey) wrote:
> Have a look at the source code behind:
>
http://www.frontiernet.net/~jmb184/interests/sci.crypt/small_num_expont.
html
> which impliments modular exponentiation in javascript
Ok, so you got my mind spinning with some options... This is what I
came up with. It's perl (cause that's easier for me to tinker with than
Javascript), but I think it might work.
Of course there's many optimizations which I'm sure I missed in the
arbitrary precision binary add, multiply, subtract and modulo
functions, but the scarey thing is that I think it works! I hope I
don't get sued for posting this on usenet... Which, by the way, do you
suppose this violates any patent/copyright laws?
It might be a bit slow, but I think it's linear time.
j
# my attempt at modular exponentiation with
# arbitrary precision binary numbers
# in perl :-)
# consider this (C) 2000 John M Hanna under the GPL
sub badd { # binary add
local($a,$b,$r,$c)=@_;
while($a || $b) {
$c=chop($a) + chop($b) + $c;
if($c & 1) {
$r="1$r";
} else {
$r="0$r";
}
$c>>=1;
}
$r="1$r" if $c;
$r;
}
sub bsub { # binary subtract
local($a,$b,$r,$c)=@_;
while($a || $b) {
$c=chop($a) - chop($b) - $c;
if($c==0) {
$r="0$r";
} elsif($c == 1) {
$r="1$r";
$c=0;
} elsif($c == -1) {
$r="1$r";
$c=1;
} else {
$r="0$r";
$c=1;
}
return '' if !$a && ($b || $c);
}
$r=~s/^0+//;
$r='0' unless $r;
$r;
}
sub bmul { # binary multiply
local($a,$b,$r,$p)=@_;
while($a) {
if(chop($a) eq '1') {
$r=&badd($r,"$b$p");
}
$p.='0';
}
$r;
}
sub bmod { # binary modulo
local($a,$m,$p,$lm,$d)=@_;
$lm=length($m);
while($a) {
return $a if length($a)<$lm;
$p=substr($a,0,$lm); $a=substr($a,$lm);
$d=&bsub($p,$m);
return $p if $d eq '' && $a eq '';
unless(length($d)) {
$p.=substr($a,0,1); $a=substr($a,1);
$d=&bsub($p,$m);
}
$a="$d$a";
$a=~s/^0+//;
}
'0';
}
sub bmodexp { # binary modular exponentiation
local($x,$y,$m,$r)=@_;
$r=1;
while($y) {
if(chop($y) eq '1') {
$r=&bmod(&bmul($r,$x),$m);
}
$x=&bmod(&bmul($x,$x),$m);
}
return $r;
}
sub i2b { # convert integer to binary
local($i,$r)=@_;
while($i) {
if($i & 1) { $r="1$r";} else {$r="0$r";}
$i>>=1;
}
$r || '0';
}
# an example where I know the results
print &bmodexp(&i2b(123),&i2b(17),&i2b(3233)),"=?",&i2b(855),"\n";
print &bmodexp(&i2b(855),&i2b(2753),&i2b(3233)),"=?",&i2b(123),"\n";
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: New cipher idea
Date: Thu, 30 Nov 2000 19:37:18 GMT
Some corrections:
Benjamin Goldberg wrote:
[snip]
> void encrypt( uint8 * txt, uint8 * key ) {
> uint8 buf[32];
> int i, j;
> for( i = 0; i < 16; ++i )
> buff[i] = txt[i] + *key++;
> for( i = 0; i < rounds; ++i ) {
> for( j = 0; j < 16; ++j ) {
> int k, x;
> for( x = buff[j], k = 1; k < 16; ++k )
> x ^= buff[j+k] & mask[k];
> buff[j|16] = x;
> }
> // buff[16..31] now contains the output of 8 order 16
> // LFSRs. Thus, it is a linear transformation of the
> // input.
> for( j = 0; j < 16; ++j )
> buff[j] = sbox[ buff[j|16] ] ^ *key++;
> // Combining the nonlinear step and key addition step
> // makes it a tad faster.
> }
> }
> One possible of this cipher which I can see is that, if just a single
> round is considered, cycling a single byte through all 256 values will
> result in the output of the round cycling through all 256 values, with
> 100% probability.
This actually only applies to the first byte, as it goes into and out of
the linear step. If instead of taking the first 16 outputs of the 8
LFSRs, I took the nth..(n+15)th (with N>1), this wouldn't be true.
However, it would probably look a bit strange, and for large N, would be
a bit too expensive. Perhaps I should try N=2 (the 2nd..17th outputs)?
> However, due how the linear step works, cycling one byte through all
> possible values should result in other bytes in the block changing in
> at least one bit each. The nonlinear step will cause these bit
> changes to affect other bits in each byte. The linear step in the
> *next* round will bring all of these changes back to that byte, in a
> manner that that should be difficult for an attacker to predict.
> Thus, no differential should hold with high probability for more than
> one round.
Well, this is still true, anyway, but it's only a real worry with the
first byte of the data.
> I'll also admit that I don't understand linear cryptanalysis, but if
> the sboxen are good, I think that this cipher will be strong against
> it.
Hmm, can sbox be pluralized like vax and ox? Anyway, this should be
"sbox is," not "sboxen are."
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
