Cryptography-Digest Digest #507, Volume #11 Fri, 7 Apr 00 10:13:01 EDT
Contents:
Re: Is AES necessary? ([EMAIL PROTECTED])
Re: Q: Simulation of quantum computing ("J.Wallace")
Re: Is AES necessary? (Tom St Denis)
Re: GSM A5/1 Encryption (Paul Schlyter)
Re: Public|Private key cryptography? (Tom St Denis)
Re: The lighter side of cryptology (Stefek Zaba)
Re: Crypto API for C (Runu Knips)
Re: Processing encrypted data (David A Molnar)
Re: GSM A5/1 Encryption (Matt Linder)
Re: Crypto API for C (David A Molnar)
Re: Is AES necessary? (Mok-Kong Shen)
Re: Schoof's Algorithm (Robert Harley)
Re: GSM A5/1 Encryption (Gerhard Wesp)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is AES necessary?
Date: Fri, 7 Apr 2000 09:18:35 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Mok-Kong Shen wrote:
> Now that we'll soon have an AES, I think it could be interesting
> to take a minute to look back and reflect whether AES is really
> necessary.
>
> I'll start by arguing for one side of the issue:
>
> 3DES is currently yet strong enough. If that's too weak, we could
> use 5DES etc.
it is slooow and 5DES will be sloooooower
and the strength is not only requirement for AES
there are more parameters including speed
> We could employ some trivial variants of DES that enable expansion
> of the effective key space (e.g. permutation of the subkeys or
> the S-boxes).
> M. K. Shen
== <EOF> ==
Disastry http://i.am/disastry/
http://disastry.dhs.org/pgp.htm <-- PGP half-Plugin for Netscape
http://disastry.dhs.org/pegwit <-- Pegwit - simple alternative for PGP
remove .NOSPAM.NET for email reply
=====BEGIN PGP SIGNATURE=====
Version: Netscape PGP half-Plugin 0.14 by Disastry / PGPsdk v1.7.1
Comment: get this Plugin at http://disastry.dhs.org/pgp.htm
iQA/AwUBOO2LxDBaTVEuJQxkEQLqHwCgtc/kOSwmFkn8aJbfgKXHh6SP7QEAn2fW
xP33RdRtX2wPrPIEBiacYTOZ
=dkUy
=====END PGP SIGNATURE=====
------------------------------
From: "J.Wallace" <[EMAIL PROTECTED]>
Subject: Re: Q: Simulation of quantum computing
Date: Fri, 07 Apr 2000 10:55:53 +0100
Mok-Kong Shen wrote:
>
> J.Wallace wrote:
> >
> > No, you could not obtain truly random bits through this type of
> > simulation.
[snip]
> I hope I understand the matter as follows: The simulation is not
> 'exact' (i.e. not an emulation) but only a very good approximation.
> Hence it can't do everything that a real quantum computer can.
> One thing it can't is generation of truly random bits.
Yes, as I understand it, that is correct.
Julia
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Fri, 07 Apr 2000 10:12:41 GMT
Mok-Kong Shen wrote:
>
> Now that we'll soon have an AES, I think it could be interesting
> to take a minute to look back and reflect whether AES is really
> necessary.
>
> I'll start by arguing for one side of the issue:
>
> 3DES is currently yet strong enough. If that's too weak, we could
> use 5DES etc.
>
> We could employ some trivial variants of DES that enable expansion
> of the effective key space (e.g. permutation of the subkeys or
> the S-boxes).
But won't these variants of DES just be in the same vain as AES? BTW I
would tend to believe ciphers like RC6/Twofish/Serpent as way more
securer [i.e harder to attack] then 3DES. So in the long run, you can
still use a 64 bit block cipher like RC5/CAST or SAFER-SK, but if you
want a larger keyspace [why not?] or bigger block size...
Tom
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: GSM A5/1 Encryption
Date: 7 Apr 2000 10:53:44 +0200
In article <8cichn$eaj$[EMAIL PROTECTED]>,
David A. Wagner <[EMAIL PROTECTED]> wrote:
> In article <8ci8mg$hv6$[EMAIL PROTECTED]>,
> Paul Schlyter <[EMAIL PROTECTED]> wrote:
>> Even if the GSM transmission wasn't encrypted at all, it would still
>> be secure against the former, [..]
>
> Right. Digital scanners aren't readily available today.
>
>> [..] since pretty sophisitcated equipment
>> will be required to even distinguish one particular GSM conversation
>> from all the others occurring at the same frequency. No scanner
>> available at Radio Shack will be able to do that.
>
> I think that's optimistic. After all, your already phone does it!
It does -- in a controlled way: you can connect to the GSM network
and make phone calls. But the phone is not designed to eavesdrop on
other phone calls in progress -- it is designed to wait for free
frequency bands, and free time slots within the frequency bands. If it
doesn't find any, it'll tell you the GSM net is too busy.
To modify a GSM phone such that it does eavesdrop on other ongoing
calls is a non-trivial task. It's certainly beyond the capability of
most people who buy scanners at Radio Shack.
> Sure, no scanner available at Radio Shack can do it *today* -- Radio
> Shack doesn't stock digital scanners at the moment -- but as for the
> future, it is hard to say. May I point you to a lovely quote from
> the president of the Cellular Telecomunications Industry Association
> (the US cellphone standards body)? He said
> ``history will likely repeat itself as digital scanners and
> decoders, though expensive now, drop in price in the future.''
Remember one thing though: a scanner where merely the analog
demodulator is replaced by some suitable digital decoder won't help
you that much here. GSM implements time multiplexing as well as
frequency hopping. Thus, if you intercept a GSM phone call with a
digital scanner, you'll get a bunch of calls at once. Yes, you can
store the data on a HD and analyze it later, perhaps succeeding in
extracting the particular phone call you're interested in. However
if that particular call suddenly hops to another frequency, it'll be
gone from whatever you've intercepted.
If/when digital scanners get readily available, I would guess that
the GSM operators counter this by letting the frequencies hop more
often. To successfully intercept a phone call, one scanner wouldn't
be enough -- you'd need a whole array of scanners, each intercepting
one frequency sub-band. The output from each scanner would have to
be stored on a big HD. And then you'd have a lot of fun figuring out
which of all those scans your target call did hop to, and when it did
hop to another frequency.
Yes, this can probably be done -- by a knowledgeable dedicated
individual who have enough resources. But it's certainly beyond
the capabilities of the average guy who buys a scanner at Radio Shack
-- even when digital scanners become available.
IMO the techniques of time multiplexing and frequency hopping is a
more efficient protection against eavesdropping than the A5 encryption.
> All it takes is a small software mod to your GSM cellphone
How do you know the required software mod is small?
> (or maybe even just knowing the right test code) ...
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
Date: Fri, 07 Apr 2000 10:24:43 GMT
Jerry Coffin wrote:
>
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
> [ ... ]
>
> > Actually 56 bits was too small then too. It's not practical to search a
> > 80 bit key space now, or 10 years from now.
>
> "Practical" is obviously open to definition. Right now it appears to
> me that it could be one for a price in the range of 10s of millions
> of dollars. Ten years from now I expect that price will be
> substantially lower. Whether that translates to being practical is
> open to question: the big problem, of course, is that almost every
> way of making money by breaking a cipher is illegal. OTOH, and
> intelligence agency might have a different idea of practicality than
> you do: you don't have to prevent too many terrorist acts (for
> example) to have paid off even a few hundred million dollar machine.
Too search an 80 bit key, in one day you must test 2^63.60 keys a
second. I doubt that could be done with todays hardware even for a
million dollars. That's a clock rate of 13,980,017,795,349,537,628hz,
even assuming each key could take only one clock cycle. To attack an 80
bit key in say a month... you still need 2^58.64 keys/sec ... [this is
at the most, not on avg]
> > Currently RC5des has been
> > going for what 3 years? Let's say they finish tommorow... an 80 bit key
> > with a keyspace 65,536 times larger will take just a bit to solve.
>
> You seem to constantly make the same mistake. You use the speed of a
> collection of general-purpose computers as a comparison point. If
> you're going to do such a thing on a regular basis, that's NOT the
> approach you'd normally take at all. There's no question that a
> machine to search a 64 bit address space could be built right now
> that would do the job in a matter of weeks for a couple of million
> dollars. That's a totally differnet prospect from three+ years, to
> put it mildly.
To find an 64 bit key in a week you need to search [on avg] 2^43.79
keys/sec, that is 15,250,284,452,471 keys a second. Which is not
entirely impossible, but difficult to imagine.
>
> > You are assuming computers [classical] will always
> > get faster, which generally has yet to be proven, even lately, actual
> > improvements in throughput [not just clock rate] are not exponential
> > like we want to think, it's 10% here, 5% there.
>
> Of course it's not proven. Very little about the future is provable.
> Despite this, improvements in computation have been exponential for
> an awful long time, and despite your assertions to the contrary, this
> trend is NOT leveling off at the present time. Intel first announced
> a 500 MHz CPU in March of 1999. The announced a 1GHz CPU in March of
> this year -- a doubling of speed within a matter of days of exactly
> one year. You can argue all you want, but that's as obvious an
> example of exponential growth as you can ask for.
Question is the the 1ghz cpu actually have a throughput of 2x of the
500mhz... that's my point. The bus speed is still what 200mhz right?
So you have a large limiting factor, considering that the matrix
requires a couple TB of memory for even modest numbers now.
> > Well the way Bob Silverman said it, factoring large keys [i.e 1024 bits]
> > will take a whopping amount of ram, more then you can store in a 2^64
> > space. I dunno but I doubt anytime soon computers will have 2^64+ bytes
> > of memory. Assuming that the memory board was made of solely 10^-8 (mm
> > square) transistors,
>
> Depending on your definition of "soon", you're right -- in fact, 2^64
> is almost certainly more than the current annual production of DRAM
> of the entire world (by what looks like 2 to 3 orders of magnitude).
Yeah, but my point was on *ONE* board. You can't use a distributed
computer to solve a matrix, thus solve factoring [using NFS]. So that
one machine needs the 2^64+ bytes of ram....
> The same situation arises, however, with respect to CPU production
> and the ability to tackle a 200-bit ECDL. Even if you could buy
> every CPU Intel produced for the next year, it still wouldn't get the
> job done in a reasonable period of time. Samsung has just announced
> a 1.6 GHz Alpha processor, and if you could get them to produce those
> at the same kind of rates that Intel produces Pentiums, and you could
> buy up all that they produce and all that Intel produce, a 200-bit
> ECDL problem is STILL well out of reach in any reasonable period of
> time.
But that's diff, you can do a distributed model to sieve for
factoring/ecdl. You can't solve the matrix step of the factoring
however since not enough ram exists on one sole machinve todo it.
> IOW, you're right that nobody's going to break RSA with a 2000-bit
> key anytime soon, but if you think they're going to break 200-bit ECC
> much sooner, I think you're badly mistaken.
You are still missing my point. For a random 2000 bit RSA key, *you
can't break it* it simply can't be done with NFS or QS. You would have
to get lucky and guess the factors or something. i.e it's not even a
question which is stronger.
While I still think a 200-bit ECC curve is secure [just think, don't
actually know much about them]...
Tom
------------------------------
From: [EMAIL PROTECTED] (Stefek Zaba)
Subject: Re: The lighter side of cryptology
Date: 7 Apr 2000 12:03:05 GMT
In the UK decryption-order-only or GAK-also debate, the following munging
of the popular (?) Gilbert-and-Sullivan number appeared from under my
fingertips....
When a felon's not engaged in his employment
Or transmitting his felonious little plans,
His capacity for innocent enjoyment
Is just as great as any honest man's.
Our feelings we with difficulty smother
When intercepting duty's to be done.
Chaining one anon remailer to another,
A decryptor's lot is not a happy one.
Ah, when intercepting duty's to be done, to be done,
A decryptor's lot is not a happy one, happy one.
When the enterprising burglar's not a-burgling
When the smuggler's not avoiding VAT
He loves to hear the little brook a-gurgling
And listen to a merry MP3.
When the crack-head's finished jumping on his mother,
He loves to lie a-basking in the sun.
Chaining one anon remailer to another,
A decryptor's lot is not a happy one.
Ah, when intercepting duty's to be done, to be done,
A decryptor's lot is not a happy one, happy one.
------------------------------
Date: Fri, 07 Apr 2000 14:55:01 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Crypto API for C
Tom St Denis schrieb:
> And I don't mind 'good' feedback :-)
Hey okay I'll check it again at home on my little linux pc :)
Just that you're able to sleep ;-)) Btw, many people might
find this address just by using search machines etc, so they
don't know you want feedback in sci.crypt 8-)
P.s.: Hmm no ElGamal yet ... RSA is still patented, isn't it ?
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Processing encrypted data
Date: 7 Apr 2000 12:57:53 GMT
[EMAIL PROTECTED] wrote:
> What are the homomorphic encryption schemes that you know?
Straight RSA is mulitplicatively homomorphic, but you don't want to use
it due to various other problems. You want at least a semantically secure
homomorphic encryption scheme.
Yevgeniy Dodis has pointed out these semantically secure encryption
schemes :
* the semantically secure variant of Elgamal
* Goldwasser and Micali's quadratic residue scheme
* Josh Benaloh's homomorphic encryption scheme
A paper by Naccache and Stern from the 1998 ACM CCS also describes
a semantically secure public key cryptosystem, and mentions some
previous work. It is found at :
http://www.gemplus.fr/smart/r_d/publications/crypto12.htm
I seem to recall that there is also a scheme of this type due to
Pascal Pailler, but I can't find a reference at the moment.
> It's possible to make also LOGIC operations on encrypted data (like
> AND,OR,NOT)?.
I see no reason why not. On the other hand, I don't know of any scheme
which does this off the top of my head.
Thanks,
-David
------------------------------
From: Matt Linder <[EMAIL PROTECTED]>
Subject: Re: GSM A5/1 Encryption
Date: Fri, 07 Apr 2000 13:06:32 GMT
In article <8cg0s0$css$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> Anyway, from the information I've received, it
> looks like the required known plaintext may indeed
> be available to the cryptanalyst. Although it is
> hard to make any definitive statements, as far as
> I can tell, yes, the attacks do seem as though
> they may be workable in real life.
>
> The key is to look at silence frames. I'm told
> that they are often encoded as some constant: every
> frame of silence in the call gets encoded to the
> same thing. I don't personally know whether this
> is correct or not, but if it is, it makes it look
> like required known plaintext may be available.
> The rest of my comments will be predicated on the
> correctness of this assumption.
>
> The other thing one needs to know is that the
> two directions of the call are encoded independently
> (in different frames). Since parties to a
> conversation usually speak one at a time, this
> means we can expect at least half of the frames
> to be silence frames.
>
> If we take the A5/2 attack, this property alone
> is enough to make it work. The cryptanalyst needs
> only to know the xor of some pair of frames, and
> the xor of two silence frames is zero, so the obvious
> thing to do is to try pairs of frames at random
> (hoping that they are both silence frames, and
> knowing that the attack will succeed when this
> is the case) until you succeed. This guessing does
> not increase the complexity of the attack very much,
> since silence frames are common.
>
> I haven't looked at the A5/1 attacks in detail,
> but it also looks as if they can be made to work
> using just this fact about silence frames.
> Certainly if the encoding of a silence frame
> is constant *and known to the attacker*, this
> gives the attacker the necessary known text.
> (Just look for a stretch of silence in the
> conversation, derive some known plaintext, try
> the attack, and if the attack fails, try again;
> once you correctly identify a stretch of
> silence in the conversation, you'll recover
> the correct key.) Even in the case where the
> silence frame encoding is constant but unknown
> to the attacker, I *think* it may also be
> possible to modify the A5/1 attacks to work
> under this model.
>
> This is all very sketchy, because I'm not a
> telephone guy, and I just don't know everything
> that one would need to know to make an assessment.
> This is also all from memory, so I could be
> misremembering some details here and there.
>
> But, if I had to place bets, I'd bet in an
> instant that some of the attacks can be mounted
> in real life, if you just give them a try.
>
Dave,
Im sure I will show how niave I am with this question, but from my
understanding of how A5/1 works, even knowing 2 of the 3 inputs to
the algorithim, (plaintext and frame number) I still dont see how
this helps find the third piece (the 64 bit key) wouldn't you still
have to run through all the 64 bit combinations? Is there a paper on
this subject somewhere?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Crypto API for C
Date: 7 Apr 2000 13:00:53 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
> P.s.: Hmm no ElGamal yet ... RSA is still patented, isn't it ?
September 20, 2000.
-David
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Fri, 07 Apr 2000 15:51:15 +0200
Tom St Denis wrote:
>
> But won't these variants of DES just be in the same vain as AES? BTW I
> would tend to believe ciphers like RC6/Twofish/Serpent as way more
> securer [i.e harder to attack] then 3DES. So in the long run, you can
> still use a 64 bit block cipher like RC5/CAST or SAFER-SK, but if you
> want a larger keyspace [why not?] or bigger block size...
A bigger key space would mean greater strength. I don't mind
which cipher one prefers. I mean that the potential of having
higher strength has not been exhausted. So there is no need to
switch to a entirely new cipher.
M. K. Shen
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: Schoof's Algorithm
Date: 07 Apr 2000 15:46:38 +0200
Mike Rosing <[EMAIL PROTECTED]> writes:
> Would you guys care to write up an explanation of how it all works,
> in "pedestrian" terms? [...]
> Even a basic outline of your method would be nice Robert.
The algorithms involved are fairly complicated so it hardly makes
sense to attempt a summary here! Two colleagues and I have only just
started work on a tech-report describing the method we use, so it will
be quite a while before that is ready. However my implementation is
well advanced and is a lot faster than what has been done before.
Point counting, in characteristic 2, is a solved problem: it's just
that nobody knows it yet. =:-)
Bye,
Rob.
------------------------------
From: [EMAIL PROTECTED] (Gerhard Wesp)
Subject: Re: GSM A5/1 Encryption
Date: 7 Apr 2000 14:09:55 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>,
Paul Koning <[EMAIL PROTECTED]> wrote:
>73 GB worth of disk drive costs only a few thousand dollars, if
actually, you can have it for <= USD 1000.
however, an attack that succeeds within a minute can't use that much
disk space. or it would have to be a _very_ fast disk.
greetings,
-gerhard
--
| ___ Gerhard Wesp
| \_________|_________/ http://www.cosy.sbg.ac.at/~gwesp
| O Ban Dihydrogen Monoxide, the most dangerous
| chemical known to mankind! --- http://www.dhmo.org
------------------------------
** 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
******************************
