Cryptography-Digest Digest #835, Volume #13 Thu, 8 Mar 01 10:13:01 EST
Contents:
Re: How to find a huge prime(1024 bit?) (Paul Crowley)
Re: Any news on the KFB mode? (Paul Crowley)
Re: Encryption software (Paul Crowley)
Re: Super-strong crypto......................(As if). (Paul Crowley)
Re: One-time Pad really unbreakable? (Paul Crowley)
Q: Tempest Systems ("news.singnet.com.sg")
Meaninog of Kasumi (Arturo)
Re: Encryption software ("Tom St Denis")
Re: qrpff-New DVD decryption code (Mach)
Re: Really simple stream cipher ("Henrick Hellström")
Codes and ancryption (was: Re: Super-strong crypto......................(As if).)
(Joe H. Acker)
Re: PKI and Non-repudiation practicalities (Anne & Lynn Wheeler)
Re: Creating serial numbers? (Sundial Services)
----------------------------------------------------------------------------
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 08 Mar 2001 12:00:08 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
> "Dik T. Winter" wrote:
> > That it is not necessarily prime in real life is something completely
> > different. When you start with a false premissa you can prove almost
> > anything, and that is the point, you prove something that is false
> > and there is your contradiction, and what way you go does not matter.
>
> While that is logically unassailable, for most purposes it is
> better to say, "... so it is either prime, or divisible by some
> prime not found in the list", since one already suspects that
> there are other primes and that helps explain in more detail
> how the failure occurs. I.e., it's one thing to see that all
> the steps in a proof work, and another thing to understand why
> the proof as a whole works.
Agreed absolutely. People in general find this proof surprisingly
hard to understand, and often mistakenly conclude that this
construction is guaranteed to produce primes. It's much easier to say
"for any finite list of primes, there are primes not in the list" than
to say "OK, try to imagine yourself in the topsy-turvy world where
there are only finitely many primes..." and then try and show that
such a world is impossibly confusing.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Any news on the KFB mode?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 08 Mar 2001 12:00:08 GMT
[EMAIL PROTECTED] (Terry Ritter) writes:
> There was much mathematical posturing about how such a thing could not
> happen, because if it did, that would amount to factoring N which had
> been mathematically proven to be impossible.
Factoring N has not been "mathematically proven to be impossible", or
even intractable, or even NP-Complete. I'd be surprised if this was
an accurate statement of what was said. The usual statement is
"factoring is believed to be hard".
Also, I'd rather avoid the word "posturing" in a civilised discussion.
> To me, "hoping weakness won't occur" seemed and
> seems an odd form of "cryptographic proof."
Every cipher, apart from the one-time pad, has efficient attacks that
work in a negligible fraction of cases. Consider this attack on
Rijndael: try the 256 keys that start 00112233445566778899AABBCCDDEE.
> The cryptographic "BB&S" argument is that short cycles are very, very
> rare. Thus, short cycles are not a security problem in practice for
> cryptographic "BB&S," because they are hardly ever, ever selected.
> And that is about all we should expect from asymptotic proof.
> A practical ramification is that people often assume that
> "mathematically proven secure" is the same as "cannot fail," which the
> BB&S discussion has shown to be both false and misleading.
No, it means "secure if the underlying problem is hard". Negligibly
effective attacks do not make a cipher insecure.
> That has the dual effect of both depreciating mathematical claims,
> and also encouraging proofs with limited but more interesting
> coverage.
Mathematical claims are as important as ever. However, if the
knowledge that negligibly effective attacks can be ignored motivates
new and interesting designs and proofs then that's certainly a good
thing!
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Encryption software
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 08 Mar 2001 12:00:09 GMT
"Simon Johnson" <[EMAIL PROTECTED]> writes:
> PGP is as good as it gets, its free and open-source (this allows you to
> check that the program does what its meant to). My advice is never buy a
> program to which you don't have the source.
PGP is *not* open source and never has been. The source to the most
recent editions isn't even disclosed, let alone licensed for
independent development.
A genuinely Open Source alternative is GPG, www.gnupg.org, a GPL'd
implementation of the OpenPGP standard.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Super-strong crypto......................(As if).
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 08 Mar 2001 12:00:09 GMT
I think it's probably not worth trying to have a discussion with
someone who doesn't even advertise a valid email address, and I hope
other participants in this newsgroup can be encouraged to ignore such
people until they get a clue.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: One-time Pad really unbreakable?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 08 Mar 2001 12:00:09 GMT
"Mxsmanic" <[EMAIL PROTECTED]> writes:
> Radioactive decay is a source of truly random numbers.
This and other responses miss the point. We have many sources of
random numbers that *seem* to be effective in *practical* terms, but
none of them are *proven* effective the way the one-time-pad is
*proven* effective.
This may seem a trivial point, but sometimes people are hypnotised by
the "proven secrecy" of the OTP and start saying they want to use it
instead of, say, Rijndael. The point of drawing attention to the
failings of that proof in the real world is to break the hypnosis.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: "news.singnet.com.sg" <[EMAIL PROTECTED]>
Subject: Q: Tempest Systems
Date: Thu, 8 Mar 2001 20:52:46 +0800
I've just finished reading the cryptoanalysis thriller Cryptomonicon (hope I
spelled it right) by Neal Stephenson and was intrigued with the last few
chapters where the main character has to sit in his captors' jail cell with
his laptop he is allowed to use.
The captors of course have set up a tempest system to capture signals and
visuals from his notebook computer and the methods he uses to throw them off
track are quite clever.
Any comments on this? Would never happen? Tempest systems aren't that good?
Etc.
Thanks in advance.
------------------------------
From: Arturo <aquiranNO$[EMAIL PROTECTED]>
Subject: Meaninog of Kasumi
Date: Thu, 08 Mar 2001 13:05:22 +0100
KASUMI is the name of the encryption algorithm to be used in
third-generation mobile phones. My question is, what does that workd stand for?
Does it have any meaning? TIA
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Encryption software
Date: Thu, 08 Mar 2001 13:07:10 GMT
"Paul Crowley" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Simon Johnson" <[EMAIL PROTECTED]> writes:
> > PGP is as good as it gets, its free and open-source (this allows you to
> > check that the program does what its meant to). My advice is never buy a
> > program to which you don't have the source.
>
> PGP is *not* open source and never has been. The source to the most
> recent editions isn't even disclosed, let alone licensed for
> independent development.
>
> A genuinely Open Source alternative is GPG, www.gnupg.org, a GPL'd
> implementation of the OpenPGP standard.
Um isn't pgpi opensource?
Tom
------------------------------
Date: 8 Mar 2001 14:01:47 -0000
From: Mach <[EMAIL PROTECTED]>
Crossposted-To: alt.hackers.malicious
Subject: Re: qrpff-New DVD decryption code
=====BEGIN PGP SIGNED MESSAGE=====
> ramalane:
>
> CAMBRIDGE, Mass. -- Descrambling DVDs just got even easier, thanks to a pair
> of MIT programmers.
>
> Using only seven lines of Perl code, Keith Winstein and Marc Horowitz have
> created the shortest-yet method to remove the thin layer of encryption that
> is designed to prevent people -- including Linux users -- from watching DVDs
> without proper authorization.
>
>
> http://www.wired.com/news/culture/0,1284,42259,00.html
>
> The Perl Code:
> http://www.cs.cmu.edu/~dst/DeCSS/Gallery/qrpff-fast.pl
You can also find anotated C source explaining the algorithm at
http://www.cs.cmu.edu/~dst/DeCSS/Gallery
If DVD players already contain decryption code, why do we need
decryption software?
Does an encrypted DVD prevent people from copying it? At a
hardware level, digital information is a series of ones and
zeros, so, what keeps you from copying the ones and zeros of
encrypted data?
_______________________________________________________________________
Mach finger [EMAIL PROTECTED] for public key
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQCVAwUBOqeNMidWgNvgbjuxAQFgBwP+Nej6/gpcsIBqOuBHdC9x0VFW+z9CdRG9
NnPWQdSN+sQUiPGXePSyDUO1UQCXhsmCkXAFTiVUMiGJY7K8Tt44l58a2Dv162u3
N4BXXmFWF7xGNDikMLtLBdeXtVRVkAebIkCwj9HMRZweW4RzA4YpZV11NVXA7VO4
Pqih04wfO0w=
=LQ64
=====END PGP SIGNATURE=====
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Really simple stream cipher
Date: Thu, 8 Mar 2001 15:10:37 +0100
"Scott Fluhrer" <[EMAIL PROTECTED]> skrev i meddelandet
news:98729g$vii$[EMAIL PROTECTED]...
> - The attacker guesses the lsbits of the initial values of V[0], V[1],
K[0],
> K[1]. Note that there are only 16 possible guesses.
>
> - For each of these 16 possible guesses, decrypt the ciphertext and
produce
> the lsbits of the plaintext (looking at the plaintext/ciphertext as a
> sequence of 32 bit values). Note that, because the cipher lacks any
> diffusion whatsoever from the higher order bits to the lower order bits,
he
> can do this ambiguously, using essentially the same algorithm as the
> intended receiver does.
>
> - Examine the 16 possible sequences of plaintext lsbits, and decide which
> one looks most like the lsbits of real plaintext. Note that this is
usually
> possible, in that the lsbits of a plaintext message usually don't look
> particularly random
>
> - Now that you have a good guess at the lsbits of the initial values of
> V[0], V[1], K[0], K[1], start in on the second lsbit.
>
> - Repeat until you have all the bits.
>
> Moral of the story: diffusion is a *really* good idea..
Aaah! The cipher really could be broken, but from my point of view you
failed to explain why: Every other qword of plain text corresponds to a new
random value of K, and your attack does not account for that. Your method
would not be sufficient derive any single one of the values K, V or P given
only a single qword of cipher text (although you would be able to exclude
some of the possibilities).
However, your attack would reduce the number of possible values of K and V
so that some possible values of the first new K would be eliminated. And
then you would possibly be able to end up with unequivocal values of K and V
given a sufficient amount of cipher text. However, the work load of a cipher
text only attack of the kind you describe would be at least O(2**64). A
known plain text attack would have the same work factor. Still, such attacks
are theoretically possible.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: [EMAIL PROTECTED] (Joe H. Acker)
Subject: Codes and ancryption (was: Re: Super-strong crypto......................(As
if).)
Date: Thu, 8 Mar 2001 15:25:56 +0100
Keill_Randor <[EMAIL PROTECTED]> wrote:
> The only way to have a secure encryption system, (and uncrackable), is
> to make sure that the only way to crack an encrypted peice of data -
>(or any other peice of information - (I just concentrate on
computing)), is to run through every peice of data known to a computer -
(Even the NSA won't be able to deal with that).
That reminds me of questions I wanted to ask a long time, although they
aren't directly related to the above statement:
(1) How secure is a book cipher, given the assumption that the book is
not known to the attacker?
Let me specify: If I map words to word positions in the book, will the
resulting numbers in practise have many properties that allow a good
attack without knowing the book that was used? (My first thought is
that there should be plenty of regularities at word and sentence level
to exploit, but I'm not really sure.)
(2) Another question that pops into my mind: If I use a large dictionary
to compress words of the plaintext before encrypting it with a
conventional symmetric cipher, would this code add significant security
in case the dictionary and encoding method is known to the attacker?
Will cryptanalysis be much harder due to the extreme amount of
compression involved? Would mixing the dictionary randomly have any
effect on that? Or is this even less secure, because there are more
regularities at word level than at letter level? (or sentence level vs.
word level, depends somewhat on the point of view) What about digram,
trigram, etc. compression for natural language plaintext?
It seems that ordinary compression is supposed to increase overall
security, but does someone know papers regarding the mixing of more
specialized codes with encryption under the assumption that the code is
public?
I'm eager to hear about your comments, as I'm not very familiar with
practical cryptanalysis.
Greetings,
Erich
------------------------------
Subject: Re: PKI and Non-repudiation practicalities
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Thu, 08 Mar 2001 14:59:11 GMT
"Lyalc" <[EMAIL PROTECTED]> writes:
> >eliminating shared-secrets was the point of the discussion ... and
>
>
> That challenge PKI faces is translates the shared secret risk ( which is one
> to 1) into a shared trust (many to many) situation. Trust in the CA, and
> trust you have the real CA certificate in particular are the low hanging
> fruit on the PKI trust tree there are others in the infrastructure part of
> PKI..
> And all of this is a bigger, more expensive challenge than initially
> thought, by many orders of magnitude.
yep, business processes are almost always significantly more expensive
than technology. in many cases, business processes (and various
associated trusts) have grown up via trial and error over many
(sometimes hundreds of) years. injecting totally unrelated new parties
into such processes (especially in critical paths of trust) is an
enormous undertaking ... in terms of value ... possibly duplicating
the value of the transactional value of the existing processes.
that is one of the reasons after working on:
http://www.garlic.com/~lynn/aadsm5.htm#adsn2
http://www.garlic.com/~lynn/aadsm5.htm#adsn3
http://www.garlic.com/~lynn/aadsm5.htm#adsn4
http://www.garlic.com/~lynn/aadsm5.htm#adsn1
that I decided to start looking at a PKI (public key infrastructure,
AADS model) that used the technology but preserved the existing trust
& business process models.
--
Anne & Lynn Wheeler | [EMAIL PROTECTED] - http://www.garlic.com/~lynn/
------------------------------
Date: Thu, 08 Mar 2001 08:06:02 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Creating serial numbers?
This strategy is a reasonable compromise that may work for Lior, but it
should also be pointed out that - if Eve (the eavesdropper!) is able to
determine the value of the hash-key, she can forge any serial number
without detection.
Additional steps probably should be taken to mask the hash-key so that
it is more difficult than it otherwise would be to determine its true
value.
I've seen serial-number systems that "mix" the number with the
authenticating key; others that store them as two separate but related
values; and still others that obviously append the two parts into one
string. All three seem to work equally well.
As far as "useful relations" go, any particular user is probably in
posession of only one key and has only limited opportunities to
authenticate it.
DEFINITELY make sure that the validated serial-number, once accepted and
installed by whatever (I presume) piece of software, is not stored in
its original form anywhere in the computer. This is why programs ask
for a name and company. The program stores the name, company, and a
hash produced from the validated serial-number, the name, and the
company. Any alteration of any of this renders the program
inoperative.
>Niklas Frykholm wrote:
>
> In article <[EMAIL PROTECTED]>, Paul Rubin wrote:
> >"Lior Messinger" <[EMAIL PROTECTED]> writes:
> >> I need to create a very large set of unique serial numbers (10-100
> >> millions). The requirements:
> >> 1. No one can create but me
> >> 2. Minimum number of digits. In Hex its 7 Digits, I'd like to stick to that
> >
> >7 hex digits = 2**28 = 256 million. If you have 100 million legitimate
> >numbers, then someone picking 7 random hex digits has better than 1/3
> >chance of getting a legitimate number.
> >
> >You need more digits.
>
> Suggestion:
>
> Let ID be a unique ID number in the range (0..100 million). Use a counter.
>
> Let K be a secret key, known only by you (128 bit long).
>
> Generate the serial number as:
>
> ID || H(K || ID)
>
> where H is a hash function.
>
> To verify a serial number, split out the first half (ID), hash it with the
> key and check that the result matches the second half.
>
> Note that you need K to verify a serial number. If you want a serial
> number to be verifiable by someone who doesn't know K, you must probably
> use (slower) assymetric cryptography.
>
> The ID string needs to be 27 bits long to have room for 100 million
> entries. The length of the hash string determines the probability of
> forging a serial number. If you are satisfied with a chance of 1 in
> 500 million, you can use 29 bits, giving you a total serial number
> length of 56 bits or 14 hex digits.
>
> Some people feel uneasy about hashing related values, such as H(K || 1),
> H(K || 2), H(K || 3)... it is possible that there could be an attacked
> based on the fact that there is a simple relation between the hashed
> values. However, I've never heard of a practical attack of this type
> against a strong hash function, such as SHA-1. Also, such an attack would
> probably require the attacker to gather a large ammount of serial numbers.
>
> If you want to preempt attacks of this type, you need to use more bits for the
> ID field and generate the ID numbers (pseudo)randomly to reduce the chance of
> finding useful relations between them.
>
> // Niklas
--
==================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R): "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/products/chimneysweep
------------------------------
** 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
******************************
