Cryptography-Digest Digest #983, Volume #11 Fri, 9 Jun 00 06:13:00 EDT
Contents:
Re: Some dumb questions (William Rowden)
Re: Some dumb questions (Jim Gillogly)
Re: Question about recommended keysizes (768 bit RSA) (Jerry Coffin)
Re: XTR independent benchmarks (Roger Schlafly)
Re: Cryptographic voting (Greg)
Re: Cryptographic voting (Greg)
Re: Cryptographic voting (Mike Oliver)
Re: equation involving xor and mod 2^32 operations ("Clive Tooth")
Re: Observer 4/6/2000: "Your privacy ends here" (Brian {Hamilton Kelly})
ANSI X.917 PRBG (jkauffman)
Re: Some dumb questions (John Savard)
Re: My lastest paper on Block Ciphers (Runu Knips)
Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher)) (Runu Knips)
Re: My lastest paper on Block Ciphers ("Sam Simpson")
Re: Some dumb questions (Volker Hetzer)
Re: Thoughts on an encryption protocol? (Volker Hetzer)
Re: PSS and PSSR patent status (was Re: XTR) (Bodo Moeller)
----------------------------------------------------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Fri, 09 Jun 2000 05:20:36 GMT
In article <8hpg22$v9e$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (William Rowden) wrote:
> How does one decipher plaintext enciphered with a generator that is
> biased?
Now that I see more of this thread, I think Volker Hetzer's post
provides one answer to this question.
--
-William
SPAM filtered; damages claimed for UCE according to RCW19.86
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Fri, 09 Jun 2000 05:38:14 +0000
William Rowden wrote:
> I was trying to characterize the problem of deciphering the
> result of XORing exactly two ciphertexts, without dragging probable
> n-grams across it. The XOR of the ciphertexts is equivalent to the
> XOR of the plaintexts in this context. I was imagining one of the
> plaintexts arbitrarily as the message, and the other as a
> (pseudorandom) key. This relates to question number 1 at the
> beginning of the thread (the OTP reuse being question 2). How does
> one decipher plaintext enciphered with a generator that is biased?
If it really reduces to a biased generator with no other structure
possible, then you would presumably be hosed in terms of recovering
plaintext -- you would be reduced to using the results to take advantage
of the information in less direct ways: confirming that a particular
ciphertext message matches some expected or captured plaintext, and so
on.
However, much of this thread is talking about a two-step process:
a simple transposition or substitution followed by the two-time-pad
operation. In this case you do have a good chance at cryptanalysis,
trying to break both parts of the cipher simultaneously.
If the substitution is messy enough, c/a probably won't get anywhere.
For example, if it's DES-CBC, then the combination will be much harder
than DES-CBC alone, even with an average PRNG for the 2TP. If it's
DES-ECB underneath, there's a good chance that the overlap will be
spotted due to code book collisions, given enough ciphertext and
consistent enough plaintext... but presumably recovering the pt will
still be hard. But if you're doing DES anyway, why not use something
even faster and stronger, and skip all the 2TP bumf?
If there's any chance that you will be falling away from the True Path,
it's better to fall in a well-analyzed direction... I suggest using 3DES
alone instead of trying to cobble together a strong cipher from some
primitive ones.
--
Jim Gillogly
20 Forelithe S.R. 2000, 05:25
12.19.7.5.0, 13 Ahau 3 Zotz, First Lord of Night
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy.anon-server,alt.security.pgp
Subject: Re: Question about recommended keysizes (768 bit RSA)
Date: Thu, 8 Jun 2000 23:54:39 -0600
In article <8hp29n$jlg$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> I am curious as to why people think that 1024 bits RSA is not
> vulnerable... according to Stahling's book....p 181.. 1000 bit integer
> can be factored with 10**7 MIP-Year. Current Cray T3's run at over one
> terraflops...well thats pretty near factoring a 1000 bit key...
The problem with factoring a number this size is NOT the number of
CPU operations -- it's the number of memory operations and (most
particularly) the _amount_ of memory needed. You basically need a
single computer with a truly _tremendous_ amount of memory to even
contemplate factoring a number this size. To do a job this size, you
need a LOT more RAM in the computer than even most large networks
have in hard-drive space.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Thu, 08 Jun 2000 23:53:22 -0700
"Paulo S. L. M. Barreto" wrote:
> I can't see any fundamental difference between working in (subgroups of)
> GF(p^6) and GF(2^m), where the size of p^6 is roughly equal to that of
> 2^m. Please correct me if I am wrong: the best attack known against DL
> in GF(2^m) has the same complexity as the best attack against DL in
> GF(r) where r ~ p^6 except for the constant factor in the exponent.
Yes, but who's talking about GF(2^m)?
> This doesn't seem to be possible: isn't the complexity of DL in GF(p^6)
> bound by the complexity of DL in the largest subgroup due to
> Pohlig-Hellman attacks?
Yes, but that attack may not be best. Pohlig-Hellman depends
on the size of the largest subgroup. GNFS is another attack,
and it depends on p^6. Depending on the subgroup sizes, GNFS
might be faster.
> As for Don Johnson, his comments are obvious: he certainly has far too
> many patents on EC to be happy about any competing cryptosystem :-)
> However, his argument involving NIST's curves -- as if selection by NIST
> was any irrevocable proof of security -- is clearly sophistry (remember
> SHA-0? it was flawed).
NIST also supplied curves in a range of sizes. How these size
match up with real-world security needs is a matter of some
debate.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Fri, 09 Jun 2000 07:05:55 GMT
> Scary, isn't it? that's why I say the heck
> with voting, let's just have a Monarchy!
> That protocol is quite secure!
What do you think of this government structure:
A senate composed of one senator for every ten million people. That
would be like a senate of 26 senators today and the elections would
have nothing to do with states or state boundaries.
Everyone votes for their top five candidates from a national pool of
any number of candidates for the senate and the 26 with the greatest
number of votes go to the senate on Jan 1 the following year until Dec
31 that same year - a one year term. After one runs for office, win or
lose, they are forever barred from running again. That solves a lot of
problems with career politicians and special interests trying to get
them to make good on deals. They are barred from such future paybacks.
The senate has only one purpose for existance - to vote on which of
them will become the next president for a single term up to 10 years
AND to exercise the power if necessary of immediately removing the
president for any reason they feel warrants his removal - any at all.
Popular opinion can lead them to do so even if the guy is legal.
And once the president has been removed or completed his full term, he
is barred from running for any federal office as well.
Since the president is where the power rests, he can do anything other
than violate the CONSTITUTION. That is, he cannot strip a person of
their rights that are spelled out in the constitution. However,
because he has no need to negotiate with anyone regarding budgets,
policies, etc., everyone knows where the buck stops ON EVERYTHING.
There is NO BLAMING THE CONGRESS or the other party for this or that!
Talk about accountability! No more of these shell games with who did
what and why we can't work together, etc.
Personally, I would like to give this a 20 year shot to see what
problems it might pose for a republic.
--
Tyranny is kept at bay by guns and will. Our government
knows we have the guns, but they don't know if we have
the will. Nor do we.
The only lawful gun law on the books- the second amendment.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Fri, 09 Jun 2000 07:12:39 GMT
> >Tyranny is kept at bay by guns and will. Our government
> >knows we have the guns, but they don't know if we have
> >the will. Nor do we.
> >The only lawful gun law on the books- the second amendment.
>
> Every modern tyranny is enforced by guns and will.
I dear say that the couple of hundred thousand guns in the hands of the
federal government are kept at bay by the guns of the couple of hundred
million guns in the hands of the populace.
> Whether the possession of guns suppports freedom or
> tyranny depends on the will of the gunners.
okay...
> Since the will of the gunners in this country is to force
> their views on a disagreeing majority, they are supporting
> tyranny.
Who are the gunners in your statement? The populace that is armed or
the government?
>
> Their leader seems to have given up the role of Moses to take up the
> role of Julius Caesar.
If the gunners are the government, then I would think that a better
description is that their leader seems to have given up the role of
Washington for Hitler or Stalin.
--
Tyranny is kept at bay by guns and will. Our government
knows we have the guns, but they don't know if we have
the will. Nor do we.
The only lawful gun law on the books- the second amendment.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Fri, 09 Jun 2000 00:30:02 -0700
Greg wrote:
>
> > 1) Is the voting to be secre or public
>
> SECRET!
>
> > 2) If it is to be secret, should the voter have a
> > way of checking that his vote has been counted
> > correctly.
>
> ABSOLUTELY. THIS IS A HARD REQUIREMENT.
These requirements seem somewhat at odds, unless you can
come up with a scheme whereby a voter can satisfy himself
as to how his vote has been counted, but cannot prove it
to anyone else. Otherwise, the party wishing to pressure
him to vote in a certain way could demand that he prove
he *had* so voted.
------------------------------
From: "Clive Tooth" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: equation involving xor and mod 2^32 operations
Date: Fri, 9 Jun 2000 08:45:48 +0100
Anton Stiglic wrote in message <[EMAIL PROTECTED]>...
>Clive Tooth wrote:
>>
>> Interesting.
>>
>> Let a, b and x be n-bit numbers and let + be the add mod 2^n operator.
>> Fix a and b. Let x range through all n-bit numbers.
>> It appears that the maximum number of distinct values that (a+x)xor(b+x)
can
>> assume (depending on the choice of a and b) is F_(n+1), the (n+1)'th
>> Fibonacci number.
>>
>> I have no proof of this.
>
>Interesting, how did you derive this conjecture?
By my usual method: trying to dispel my ignorance by the application of
brute force.
I wrote a program and looked at the results.
Any sequence with ..., 34, 55, 89, ... in it can only be one thing.
--
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
End of document
------------------------------
From: [EMAIL PROTECTED] (Brian {Hamilton Kelly})
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,alt.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Fri, 09 Jun 2000 00:33:01 GMT
In article <[EMAIL PROTECTED]>
DHowe@get_email_from_sig "Dave Howe" writes:
> Q: Why should you be allowed to open any email you like?
> A: Because we have always opened any Post Mail we wanted, and want to
> keep that power
> Q: You do? why do you have permission for that? where is the law that
> gives you the right to do so?
> A: There isn't a law to stop us!
Which US Secretary of State was it who said "Gentlemen don't open other
peoples' mails"?
[snip]
> Q: And you expect us to believe this?
> A: No, but it doesn't matter, since we cleared the House of Lords of
> most of those who would object due to some moral imperative, and
> replaced them with good loyal Party Members. muhahahaha!
Nice one. Hope the editor of the FT is noting this.
--
Brian {Hamilton Kelly} [EMAIL PROTECTED]
"We have gone from a world of concentrated knowledge and wisdom to one of
distributed ignorance. And we know and understand less while being incr-
easingly capable." Prof. Peter Cochrane, BT Labs
------------------------------
From: jkauffman <[EMAIL PROTECTED]>
Subject: ANSI X.917 PRBG
Date: Fri, 09 Jun 2000 01:08:04 -0700
Does anyone have any idea how many bits it is safe to
generate from an X.917 generator before it becomes
computationally easier to break the generator than to
brute force attack the 192 bits of input randomness?
* Sent from AltaVista http://www.altavista.com Where you can also find related Web
Pages, Images, Audios, Videos, News, and Shopping. Smart is Beautiful
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Some dumb questions
Date: Fri, 09 Jun 2000 08:31:14 GMT
On Tue, 06 Jun 2000 11:04:19 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>But to proceed from that knowledge to get the plaintext in ASCII
>is a long way that is not apparent at all.
If there is a small bias, but there is still no correlation, so that
while there are, say, 51% ones and 49% zeroes, the keystream is
otherwise perfectly random, then, you are correct that it is still
difficult to proceed to the plaintext.
>Yes, you get the xor of two messages. But how to go further from
>that point (there is no known plaintext whatever)?
Well, if it is a misused one-time-pad, one does not assume any other
encipherment. If there were not even any compression applied to the
messages, then certain things would stand out.
In ASCII: control characters start with 000, spaces and most
punctuation start with 001, uppercase letters start with 010,
lowercase letters start with 011.
Thus, most bytes of the XOR of two ASCII messages will start with 000.
Such bytes will most likely be the XOR of two lowercase letters, and
which two can be narrowed down by frequency charts (excluding
low-frequency letters will be more important than looking for
high-frequency ones). But an all-zero byte could be the XOR of two
spaces instead of, say, two "e"s.
Bytes starting with 010 will probably be the XOR of a space with a
lowercase letter, so we will have several highly probable letters,
without knowing which message they come from. But if there are two
bytes starting with 010 in a row, the first one would perhaps be the
XOR of a period or comma with a lowercase letter.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
Date: Fri, 09 Jun 2000 10:28:31 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: My lastest paper on Block Ciphers
tomstd wrote:
> I have just finished the Draft of my latest paper. It's called
>
> "On Cryptographically Strong F Functions"
>
> And is available (sorry) only in Word97 format at
>
> http://tomstdenis.com/ffunctions.zip
>
> There are probably tons of little mistakes, I have yet to have
> anyone proofread it...
>
> I am open to critiques :)
Tom, I have no time to really read your paper right now, only
for a short look at it (content looks good), but if you would
know how ugly the special characters of a candadian winword
document look in a german winword you would have thought twice
before using that format. I have the impression that these
should be greek characters in the formulas but they aren't.
They are really strange figures such as an inverted color <-
or a small figure looking a little bit like @ etc. It's simply
unreadeable, sorry.
------------------------------
Date: Fri, 09 Jun 2000 10:34:49 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher))
tomstd wrote:
> Look at IDEA for hints on making ciphers like that.
Well, thats maybe the best advice. Study others
ciphers and attacks first. If one has understand
what weaknesses a cipher can have, designing one
is far more fruitful.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: My lastest paper on Block Ciphers
Date: Fri, 9 Jun 2000 09:42:34 +0100
The "Starmath" font you use for mathematical symbols is not a
standard font supplied with Windows/Office - perhaps you could either
embed the font or use a portable document format (ps / pdf?).
Apart from that, the paper is an interesting and generally well
written piece.
Regards,
--
Sam Simpson
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
tomstd <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I have just finished the Draft of my latest paper. It's called
>
> "On Cryptographically Strong F Functions"
>
> And is available (sorry) only in Word97 format at
>
> http://tomstdenis.com/ffunctions.zip
>
> There are probably tons of little mistakes, I have yet to have
> anyone proofread it...
>
> I am open to critiques :)
>
> Tom
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion
Network *
> The fastest and easiest way to search and participate in Usenet -
Free!
>
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Fri, 09 Jun 2000 09:25:33 +0000
Mok-Kong Shen wrote:
> Of course your point of 'relativity' of my word 'fairly' is justified. An
> encryption scheme may be crackable in one environment though not
> in another because of resources. If I understand correctly, you would
> write a program to try to break the xor of an arbitrary pair and, if
> you can break it, then you have identified that the originals belong the
> same segment of OTP. Is that right?
yes
> (But then you have succeded in fact to read the messages.)
Yes
> Now could you give some sketch of ideas that underly such a program?
You are not gonna like this, but no, I'm not giving you code or algorithms.
Your email address is a pretty generic one and I don't know whether you are
some high school or university student looking for an easy way out of an
assignment.
In particular, your insistence on a rather exotic set of side conditions (like
knowing only the character distribution of a language, but not its n-grams)
makes it unlikely to me that you are working on a real world problem.
IMHO the explanations you've got so far (from others and (hopefully) me)
should get you started thinking about an approach.
If it helps you, I never learned about breaking book ciphers. What I wrote
was simply the best I could come up with after a few hours of thinking.
I'm sure you could do the same. Stop treating this as a programming
problem but view it from the statistical angle.
Nevertheless, have fun!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Thoughts on an encryption protocol?
Date: Fri, 09 Jun 2000 09:31:45 +0000
Bryan Olson wrote:
> So let's outline a solution to the synchronization problem.
> It does not require exactly-once semantics, or even a
> sliding window of keys. Each side starts with the same key,
> and keeps a counter that increments on each roll-forward.
> Each message includes the current counter. If one side gets
> a message with a count higher than his own current counter
> value, he can roll-forward to the given counter and key.
Now he only has to make sure that
- creating one key from the previus one can not be broken
from the messages (without analyzing the device)
- even a successfully analysed device does not enable the attacker
to find out about past keys.
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: [EMAIL PROTECTED] (Bodo Moeller)
Subject: Re: PSS and PSSR patent status (was Re: XTR)
Date: 9 Jun 2000 09:22:07 GMT
> David Hopwood <[EMAIL PROTECTED]>:
>> The patent pending on PSS is by the University of California; in a letter
>> to the IEEE archived at http://grouper.ieee.org/groups/1363/letters/UC.txt
> That page doesn�t exist.
Try <URL: http://grouper.ieee.org/groups/1363/P1363/letters/UC.html>.
------------------------------
** 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
******************************
