Cryptography-Digest Digest #136, Volume #12 Thu, 29 Jun 00 13:13:01 EDT
Contents:
Re: very large primes (Runu Knips)
Re: MD5 Expansion (Anton Stiglic)
Re: Compression & Encryption in FISHYLAND ("Douglas A. Gwyn")
Re: very large primes ("Douglas A. Gwyn")
Re: very large primes (Roger Schlafly)
Re: Idea or 3DES (Arturo)
Re: Dynamical Cryptography algorithm (Mark Wooding)
Re: Thoughts on "Cracking" of Genetic Code ("Trevor L. Jackson, III")
Re: How Uncertain? ("Douglas A. Gwyn")
Re: Thoughts on "Cracking" of Genetic Code (wtshaw)
Re: Another chaining mode (Mark Wooding)
AES: It's been pretty quiet for some time... (Volker Hetzer)
Re: very large primes (Simon Johnson)
Re: very large primes ([EMAIL PROTECTED])
Re: Surrendering Keys, I think not. (zapzing)
Re: How Uncertain? (Mark Wooding)
sliding window exp.:CLNW vs. VLNW ("Pedro F�lix")
Re: RPK ("Lucas C. Ferreira")
Re: very large primes (Jeffrey Williams)
Re: very large primes ("Douglas A. Gwyn")
Re: Dynamical Cryptography algorithm (Sylvain Martinez)
Re: Remark on practical predictability of sequences (Mark Wooding)
Re: TEA question (Shawn Willden)
----------------------------------------------------------------------------
Date: Thu, 29 Jun 2000 16:04:51 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: very large primes
[EMAIL PROTECTED] wrote:
> is (n!-1) always a prime, and does anyone know of a proof or disproof?
I would be very surprised if there would be some purely arithmetic
forumla which generates nothing but primes (Of course one can find
silly examples such as f(x) := 2).
Many primes are of the form (n**2)-1, but that doesn't mean every
such number is a prime (for example, 4**2-1 = 16-1 = 15 = 5*3 isn't
a prime).
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: MD5 Expansion
Date: Thu, 29 Jun 2000 10:24:13 -0400
In article <[EMAIL PROTECTED]>,
Andrew Bortz <[EMAIL PROTECTED]> wrote:
> In the interest of increasing the size of a MD5 hash, I have been
> thinking of a fairly simple method:
So a provable way of extending the output of a secure hash
function h is to simply split the input m into two equal halves
am and bm (such that m = am || bm, || is concatenation) and output
h(am) || h(bm).
(Like Simon Johnson described).
On way to prove that the extended function is strongly collision
resistant.
You do this by proving that it's as strongly collision resistant as a
single hash.
So now let's say I can find an existential collision with h,
m != m' such that h(m) = h(m'), I can trivially find an existential
collision on the extended scheme: m || n and m' || n, where you
would split m || n into m and n, and split m' || n into m' and n,
will collide in the extended scheme.
So now let's go the other way around, let's say that we can find
a collision with the extended scheme, say that n and n'
are such that h(an) || h(bn) == h(an') || h(bn') (where the splitting
of x gives ax, bx). You can see that an, an' will form a collision
for h, so will bn, bn'. This means that if the extended scheme
is not strongly collision free, the initial hash function h isn't
either.
As simple as that!
Anton
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Compression & Encryption in FISHYLAND
Date: Thu, 29 Jun 2000 14:17:37 GMT
"SCOTT19U.ZIP_GUY" wrote:
> As I have told you many times. With my huffman compression routine
> you can change the last byte to any of its 256 combinations and
> in each case it will decompress to a file that when compressed
> back it will be that same file. THis concept is apparently over
> your head.
I think most of us, including John Savard, understand that perfectly
well. What we don't see is why this would matter in practice. You
have explained it only in terms of testing whether a trial decryption
is possibly valid, but that is relevant only for brute-force key
search, which is already not a viable method of attack for any
cryptosystem we would want to use.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: very large primes
Date: Thu, 29 Jun 2000 14:25:00 GMT
Darren New wrote:
> I think you're thinking of (n!+1)
That doesn't work either. Try n=4.
I vaguely recall that there is some theorem to the effect that
no simple algebraic function of n can generate distinct primes
and only primes for every natural number n.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: very large primes
Date: Thu, 29 Jun 2000 08:00:03 -0700
"Douglas A. Gwyn" wrote:
> I vaguely recall that there is some theorem to the effect that
> no simple algebraic function of n can generate distinct primes
> and only primes for every natural number n.
Maybe not "simple", but there are polynomials whose positive
values are precisely the set of primes.
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: Idea or 3DES
Date: Thu, 29 Jun 2000 14:08:19 GMT
On Thu, 29 Jun 2000 13:42:58 GMT, [EMAIL PROTECTED] wrote:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (JPeschel) wrote:
>> "Trevor L. Jackson, III" [EMAIL PROTECTED] writes:
>>
>> >There is insufficient evidence to distinguish inability from
>> >unwillingness.
>>
>> After writing:
>> "The case would not have been made, and PRZ indicted, if the USG was
>> unwilling. The appropriate explanation for a dropped case is
>inability."
>>
>> just a little semi-paranoid thought,
>
>what if the USG, in fact, did find a weakness that might lead to
>eventual cracking of the ciphers, wouldn't they want people (e.g. the
>drug dealers using pgp,) to continue to use them, and so, intentionally
>dropped the case because of 'inexpediency' of prosecuting it, but after
>leading people to believe that it was secure enough to be a threat that
>warranted USG attention?
>
And what if we accept the fact that not even the USG is all-powerful?
They can�t stop the flow of drugs into the US or prevent a starving-to-death
country like North Korea from becoming a nuclear power, so what makes you think
they could block the Internet out of the US?
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Dynamical Cryptography algorithm
Date: 29 Jun 2000 15:11:19 GMT
Sylvain Martinez <[EMAIL PROTECTED]> wrote:
> > > What I try to say is that:
> >
> > Ahh. You don't want to answer the question.
>
> ??
I asked a question. It was a technical question, expecting a technical
answer. Your reply `What I try to say is that...' was not an answer. I
assumed that, had you wanted to answer the question, you would have done
so. Hence my assertion that you didn't want to answer it. Is my logic
faulty?
> But the way This algorithm has been *designed* is not based on maths
Oh. It's probably not going to be very successul. The problem is that
mathematics is the tool we have for analysing ciphers. Cipher design
without mathematics doesn't work very well.
> Why are you so agressive ?
I'm not.
Your original message came over badly. You made various comments which
were either clearly factually wrong or made little sense, suggesting a
poor grasp of existing techniques and concepts. The report you linked
to is filled with confused terminology and muddled thought; e.g., when
discussing algorithms based on `static formulas', you cite `PGP with
factorial' which makes very little sense (PGP isn't an algorithm, and it
doesn't use factorials); you use a logical AND to do some passphrase
expansion, although this will cause a huge bias towards zero bits in the
result.
> I am an amateur willing to learn ! this is why I have done that
Counterintuitively enough, designing ciphers isn't the right way to
learn cipher design. What you need to do is study other people's
designs, and their analysis. Read the AES entries -- particularly
Twofish and Rijndael -- for hints on presentation and analysis. See
also Schneier's self-study cryptanalysis course.
Try analysing some of the sci.crypt cipher contest entries (homepage at
http://www.wizard.net/~echo/crypto-contest.html). Start with the
`broken' ones and try breaking them yourself (without peeking at the
analysis). Then analyse the unbroken ones and report your results.
You have a chance to show me up: break my entry! ;-)
Then, only then, armed with the knowledge of how to break ciphers,
design your own.
-- [mdw]
------------------------------
Date: Thu, 29 Jun 2000 11:24:31 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Thoughts on "Cracking" of Genetic Code
Steve Roberts wrote:
> [EMAIL PROTECTED] (John Savard) wrote:
>
> >On 27 Jun 2000 13:31:34 EDT, [EMAIL PROTECTED] (Information System)
> >wrote, in part:
> >
> >>As I understand it, what has been accomplished is
> >>the compilation, in crypto terms, of a complete and possibly
> >>accurate transcription of the ciphertext.
> >
> >Well, many years ago, the genetic code was "cracked" in the sense that
> >a code by which three bases (from a set of four) along an RNA or DNA
> >molecule represented an amino acid was determined.
> >
> >The Human Genome Project is indeed not really analogous to
> >codebreaking, and indeed the relationship between the various variant
> >forms of proteins formed by different alleles (the different forms of
> >the same gene) and observed traits in humans has not been completely
> >established - and will not be for quite some time.
> >
>
> The genetic code is a "code" in the sense that it is information
> enCODEd in a particular way, like "ASCII code" for example. But the
> concept of "code" in the public's mind leads to the idea of "breaking
> the code" which leads to more information.
>
> What I predict will occur is that nutters will now start to find
> messages in the genome sequence. It happened to Shakespeare and the
> Bible, why not this?
The presumption is that Shakespeare works and the Bible were of human origin
(inspiration not withstanding), but the genome sequence is not. Thus we
should check the genome carefully for patent, trademark, and copyright
statements.
;-)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How Uncertain?
Date: Thu, 29 Jun 2000 14:51:01 GMT
Mark Wooding wrote:
> Maybe Doug is having a little joke with us about the amount of random
> rubbish which gets posted to Usenet. ;-)
No, I'm serious. One bit per octet is certainly totally entropic
(parity). Another bit is nearly totally entropic, since half the
ASCII range includes almost all characters actually used. So far
we have exceeded BS's estimate without even considering redundancy
in the (English) language. Experiments similar to Shannon's show
that a very large fraction of English discourse is redundant, thus
my estimate of at least 6 bits out of every 8 altogether.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Thoughts on "Cracking" of Genetic Code
Date: Thu, 29 Jun 2000 08:48:33 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
>
> The Human Genome Project is indeed not really analogous to
> codebreaking, and indeed the relationship between the various variant
> forms of proteins formed by different alleles (the different forms of
> the same gene) and observed traits in humans has not been completely
> established - and will not be for quite some time.
>
I disagree that there is no such relationship. The problem is threefold,
to have a good set of the genetic code, the ciphertext, and pair it with
three-dimensional results, protein, etc., and the last part is to fully
understand the exact mechanisms involved in controlling product biological
processes. The challenge to all of this is immense, much greater than
those seeking a quick fix understand.
--
Ralph Nader must not be a politician, he makes sense. Those that
hype confusion about understandable issues are the anarchists.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Another chaining mode
Date: 29 Jun 2000 15:20:47 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> With DES, this gives 2**16, which is probably not enough. For AES,
> this is 2**32, which is (IMHO) borderline. And, yes, as you observed,
> this works best on ciphers with large block size.
This is a concern, but I'm not sure that it's as bad as you've painted
it. Note that even if the input plaintext is random, we'll get
collisions in the output half-block with after 2^{n/4} blocks. But
these tell us nothing at all about the plaintext! I'm not sure that you
can easily pick out a `signal' caused by equal input plaintexts from the
background `noise' of natural collisions.
-- [mdw]
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: AES: It's been pretty quiet for some time...
Date: Thu, 29 Jun 2000 15:22:31 +0000
Hi!
Does anyone know what's going on?
The last announcement was on may, 15.
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
Subject: Re: very large primes
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Thu, 29 Jun 2000 08:29:23 -0700
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>Darren New wrote:
>> I think you're thinking of (n!+1)
>
>That doesn't work either. Try n=4.
>I vaguely recall that there is some theorem to the effect that
>no simple algebraic function of n can generate distinct primes
>and only primes for every natural number n.
Yup, i think it was to show no polynomial can be constructed to
work like this: f(x) = some prime for every x.
I remeber that now, which makes my above posts void.
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: very large primes
Date: Thu, 29 Jun 2000 15:34:26 GMT
In article <[EMAIL PROTECTED]>,
Runu Knips <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > is (n!-1) always a prime, and does anyone know of a proof or
disproof?
>
> I would be very surprised if there would be some purely arithmetic
> forumla which generates nothing but primes (Of course one can find
> silly examples such as f(x) := 2).
>
> Many primes are of the form (n**2)-1, but that doesn't mean every
> such number is a prime (for example, 4**2-1 = 16-1 = 15 = 5*3 isn't
> a prime).
>
thank you for a civil and informative answer .
i did try all the factors thru 7!.
for 8!, 23*1753 was not readily apparent to me.
will try to not annoy this ng with similar queries in the future.
vedaal
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Surrendering Keys, I think not.
Date: Thu, 29 Jun 2000 16:00:30 GMT
In article <[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Okay, i'll propose this again.
>
> We have a document, m. We wish to encrypt this document, such
> that no-one other than the legimitimate person can read it.
>
> Now, to complicate matters, the government wants us to surrender
> our keys if were involved in a criminal investigation. So how do
> we satifiy the police, by providing a key (which is going to be
> fake), and insure are information remains secure?
>
> I figured since the output from any AES candidate should be no
> different from random data, we could prepare a false one time
> pad key, which decrypts to something totally correct (and/or
> legal). The legitimate user of the encrypted file can still
> decrypt it with an AES symetric algorithm, yet they have a back-
> up OTP key incase the secret police come banging on the door,
> demaning keys. They surrender the OTP key -> Or they try and
> break the underlying block-cipher.
>
> Do you see what i mean now?
Yes but I doubt the People Who Seize Stuff (PWSS) will
find your argument convincing, *Because* of the fact
that your "cover story" includes a kind of encryption
that is not particularly useful for personal data.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: How Uncertain?
Date: 29 Jun 2000 16:22:50 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
> > Maybe Doug is having a little joke with us about the amount of random
> > rubbish which gets posted to Usenet. ;-)
>
> No, I'm serious. One bit per octet is certainly totally entropic
> (parity).
I didn't think that most representations of Usenet articles used parity
bits. But don't you mean `redundant', rather than `entropic' here?
> Another bit is nearly totally entropic, since half the ASCII range
> includes almost all characters actually used.
The definition of entropy I'm using is
---
H(X) = - > p_i log p_i
---
i, p_i != 0
[HAC 2.2.1]
A parity check bit would be completely determined by the other bits.
Its entropy is then exactly zero. Is this what you mean by `totally
entropic'? It doesn't make sense to me.
I've measured the distribution of bit 5 of this news article, and it
suggests that it's 1 about twelve times as often as it's 0. I calculate
that the entropy of that bit, according to this simple model, is about
0.39.
> So far we have exceeded BS's estimate without even considering
> redundancy in the (English) language.
I thought Schneier's estimate was about 1.3 bits per byte.
Let's extend your model. Here are probabilities for each bit being 1,
based on an analysis of this news article (so far):
Bit Pr(bit is one)
0 0.432
1 0.367
2 0.456
3 0.355
4 0.316
5 0.926
6 0.683
7 0.000
Assuming that all of these bits are independent, I get a joint entropy
for that lot of 3.10.
Even with this extended model, I think we've a way to go before we get
down to Schneier's estimate. It's a pretty poor model, really.
-- [mdw]
------------------------------
From: "Pedro F�lix" <[EMAIL PROTECTED]>
Subject: sliding window exp.:CLNW vs. VLNW
Date: Thu, 29 Jun 2000 17:20:19 +0100
I apologise if this question is off-topic, but here it goes:
In the context of the sliding window algorithms for exponentiation, there
are (to my knowledge) to basic proposals:
1. constant length non-zero window (CLNW)
2. variable length non-zero window (VLNW)
After reading [1] and [2] I'm still not able to build a concrete example
where the VLNW produces less NW than the CLNW.
Could some one help me?
Thanks
[1] - Cetin Kaya Koc, "High Speed RSA Implementation", RSA Labs.
[2] - Cetin Kaya Koc, "Analysis of sliding window techniques for
exponentiation", ???
------------------------------
From: "Lucas C. Ferreira" <[EMAIL PROTECTED]>
Subject: Re: RPK
Date: Wed, 28 Jun 2000 11:42:54 -0300
If I racall right, Ivisimail uses it. Their site should be
www.invisimail.com, but I'm not sure. The site contains info on the cipher
also, if someone is interested.
Regards,
Lucas
<[EMAIL PROTECTED]> wrote in message news:8j74pn$u68$[EMAIL PROTECTED]...
> This public key cryptographic system seems to fit audio and video
> application very well.
> Does anyone know about "real" applications that use it ?
> Does anyone work on trying to break it ? ( Just to know how robust this
> system is and how reasonnable it is to use it).
> Thank you
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: very large primes
Date: Thu, 29 Jun 2000 11:39:22 -0500
Would you please post an example of such a polynomial?
Jeff
Roger Schlafly wrote:
> "Douglas A. Gwyn" wrote:
> > I vaguely recall that there is some theorem to the effect that
> > no simple algebraic function of n can generate distinct primes
> > and only primes for every natural number n.
>
> Maybe not "simple", but there are polynomials whose positive
> values are precisely the set of primes.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: very large primes
Date: Thu, 29 Jun 2000 16:14:09 GMT
Roger Schlafly wrote:
> Maybe not "simple", but there are polynomials whose positive
> values are precisely the set of primes.
I'd be interested in seeing one.
------------------------------
From: Sylvain Martinez <[EMAIL PROTECTED]>
Subject: Re: Dynamical Cryptography algorithm
Date: Thu, 29 Jun 2000 16:39:24 GMT
> so. Hence my assertion that you didn't want to answer it. Is my
> logic
> faulty?
No, but I didn't see it that way. I was first thinking of "DES" because
I realised it was wrong I said nothing.
[...]
> doesn't use factorials); you use a logical AND to do some passphrase
> expansion, although this will cause a huge bias towards zero bits in
> the result.
I am actually not only doing that :O)
> Counterintuitively enough, designing ciphers isn't the right way to
> learn cipher design. What you need to do is study other people's
> designs, and their analysis. Read the AES entries -- particularly
> Twofish and Rijndael -- for hints on presentation and analysis. See
> also Schneier's self-study cryptanalysis course.
I do not totaly agree with you. It is like learning guitar.
you can take lessons and becoming good at it, or you can learn your
self. This will allow you to understand better some concepts. You would
still need to take proper lessons but if you've done that, let say, for
7 years you will then learn quicker.
In other words it is not a complete waste of time :O)
> Try analysing some of the sci.crypt cipher contest entries (homepage
>at
> http://www.wizard.net/~echo/crypto-contest.html). Start with the
> `broken' ones and try breaking them yourself (without peeking at the
> analysis). Then analyse the unbroken ones and report your results.
> You have a chance to show me up: break my entry! ;-)
Ok, one of my problem is that I am much more interested at creating
something that trying to break an existing algorithm. But you're rigth
I'll try that !
> Then, only then, armed with the knowledge of how to break ciphers,
> design your own.
The I've bee nworking these last few years was :
I desing an algo, you show me it's weak, I work on it, understand why
it's weak and produce a better one, etc ,etc, etc
Cryptography is something that interests me more and more so I will
certainly do as you suggested: look more in depth at th eexisting
algorithm.
Cheers,
Sylvain.
--
---
Unix security administrator
BUGS crypto project: http://www.bcrypt.com
http://www.encryptsolutions.com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Remark on practical predictability of sequences
Date: 29 Jun 2000 16:50:40 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
[Squirt a PRNG output through a block cipher.]
> This is essentially how (for example) Yarrow works.
>
> It feeds a less than perfectly random sequence (in fact it uses a
> counter) through a block cypher (3DES).
Note that some artifacts of the input sequence can slip through due to
the block structure of the cipher.
Consider Yarrow's counter-mode output. We know that no adjacent outputs
of a counter are equal. Since a block cipher with a fixed key is a
permutation, we know that no adjacent ciphertext blocks are equal.
However, in a truly random sequence, we'd expect to find that the
probability of two adjacent n-bit blocks being equal is 2^{-n}, rather
than zero.
Yarrow's frequent rekeying helps here, but while it successfully hides
the low collision frequency of a counter-mode output, it fails to
completely hide the specific case of adjacent equal blocks. While we
need more data to determine whether a given stream is random by looking
at adjacent blocks than by looking for general collisions, I do believe
that this is a (minor) weakness in Yarrow[1]. A possible fix would be
to use a combined OFB/counter mode.
[1] The paper states fairly clearly that the authors' expectation is
that distinguishing Yarrow output from a truly random stream should
require O(2^{160}) effort.
-- [mdw]
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: TEA question
Date: Thu, 29 Jun 2000 11:02:43 -0600
dexMilano wrote:
> Let's make the point.
>
> I don't have unsigned so I have an upper limit of f7777777 (absolute
> value).
No unsigned integers? You must be using Java (I never have figured out why
Gosling did that, BTW. He claims it was a decision to simplify the
language, but it seems to make mine more complex on a regular basis).
There's no problem. Just use a long instead of an int to store this
number. It will be slower, but it can be made to work.
If the magic number is only used in bitwise operations, (no arithemetic),
you can even put it in an int and just allow it to be negative.
Shawn.
------------------------------
** 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
******************************
