Cryptography-Digest Digest #145, Volume #12 Sat, 1 Jul 00 12:13:01 EDT
Contents:
Re: Is this a HOAX or RSA is REALLY broken?!? (Shawn Willden)
Re: Observer 4/6/2000: "Your privacy ends here" (Simon Elliott)
Re: Newbie question about factoring (Nick Maclaren)
Re: Compression and known plaintext in brute force analysis (restatements caused by
the missing info .... thread) (Tim Tyler)
Re: Newbie question about factoring (Simon Johnson)
Re: unable to use HIGH ENCRYPTION on IIS 5.0 (1024 bit key) (Withheld)
Re: Is this a HOAX or RSA is REALLY broken?!? ([EMAIL PROTECTED])
Re: Newbie question about factoring (Bob Silverman)
Re: CRC-64 and 128 - Generator Polynomials? (Roger Fleming)
Re: Is this a HOAX or RSA is REALLY broken?!? (Daniel James)
Re: Newbie question about factoring (Daniel A. Jimenez)
Re: Newbie question about factoring ("Scott Fluhrer")
Re: Encryption and IBM's 12 teraflop MPC...... (jungle)
Re: Surrendering Keys, I think not. (zapzing)
Re: Remark on practical predictability of sequences ("Rick Braddam")
----------------------------------------------------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: 01 Jul 2000 02:15:48 -0600
Greg <[EMAIL PROTECTED]> writes:
> In article <[EMAIL PROTECTED]>,
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> > Greg wrote:
> > > Give all of this, it would appear to be an intel op against
> > > European banks by possibly Isreali intelligence using the news
> > > paper as a pawn.
> >
> > One doesn't need to assume a conspiracy when plain ignorance would
> > explain it just as well.
>
> One need not excuse the possibilities when a simple explanation is
> available either.
On balance, I think Occam's razor would favor Douglas' explanation.
To put it another way:
"Never attribute to malice that which is adequately explained by
stupidity",
-- Unknown (to me)
Shawn.
------------------------------
From: Simon Elliott <[EMAIL PROTECTED]>
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.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Sat, 1 Jul 2000 09:20:03 +0100
Reply-To: Simon Elliott <[EMAIL PROTECTED]>
JimD <[EMAIL PROTECTED]> writes
>>>>>Absolutely. There was that woman from Shrewsbury they had
>>>>>murdered.
>>>>
>>>>Hilda Murrell ?
>>>
>>>None other.
>>
>>What was that all about? I don't remember reading about this in the
>>papers.
>
>It was a long time ago, during the Thatcher r�gime I think.
>
>This Hilda Murrell, had a nephew(?) who knew what happened to
>the log of the submarine that sunk the Belgrano. You'll recall
>the log mysteriously went missing when enquiries were being made
>about this incident.
>
>She was also active in some peace movement or other - that and
>the matter of the log was just a bit too much of a risk for
>the odious Thatcher woman to take, so she had her eliminated.
>Or so the story goes. The local police, unsurprisingly, got
>nowhere with the murder enquiry.
I always wondered what happened to the log of HMS Conqueror. For a while
in 1982 this was a hot subject in the news, then suddenly the people who
knew about the log couldn't be found or wouldn't talk to the press. I
thought at the time that this seemed a bit suspicious, especially when
suddenly the whole issue was dropped by the media.
I assumed at the time that the people involved had been made an offer
they couldn't refuse. I didn't realise there was ever a murder enquiry.
This could suddenly become an issue again, now that the Belgrano
incident is being put to ECHR.
--
Simon Elliott phone : +44 (0)1444 413799
Software Consultant fax : +44 (0)870 0557822
Courtlands Technical Services email : <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Nick Maclaren)
Crossposted-To: comp.theory
Subject: Re: Newbie question about factoring
Date: 1 Jul 2000 08:45:16 GMT
In article <8jj7u8$o3$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>
>In RSA's FAQ it also states that Shor's
>(quantum) algorithm for factorization could do
>factoring in polynomial time if properly
>implemented. Additionally, it was proven that
>Shor's algorithm cannot be generalized for
>*all* NP problems. Does this imply that
>factoring *cannot* be NP-complete, or what
>does it mean?
A "quantum computer" can be regarded as a Turing machine in which
certain operations that take exponential time in the latter can
be done in polynomial or even constant time. When people talk
about complexities, it is important to realise that they are always
relative to a particular computational model.
This arises regularly with arguments about whether multiplication
is O(N) or O(N log N) or whether various sorting algorithms are
O(N), O(N log N) or O(N log N log log N). The unusual aspect of
quantum computing is that the model makes a large difference, not
a small one.
However, some people believe that building a quantum computer is
an exponentially complex problem, which makes Shor's algorithm
of theoretical interest only. Time will tell.
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: [EMAIL PROTECTED]
Tel.: +44 1223 334761 Fax: +44 1223 334679
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression and known plaintext in brute force analysis (restatements
caused by the missing info .... thread)
Reply-To: [EMAIL PROTECTED]
Date: Sat, 1 Jul 2000 09:24:43 GMT
zapzing <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> zapzing <[EMAIL PROTECTED]> wrote:
:> : And another problem: suppose a random (or already encrypted)
:> : file is encrypted. Then an amount of predictable
:> : information will be added to a file that was previously
:> : perfectly unpredicatble.
:>
:> Since most people agree that in practice, this is often true, a
:> simple solution should be employed:
:>
:> *Don't* feed plaintext with statistically random characteristics
:> straight into your compressor, if you can avoid doing so.
:>
:> Random plaintexts are typically expanded only to a small degree
:> (compared to the extent to which a patterend file is compressed)[.]
: All of this is agreed. But If you make compression a
: *decision* that a *user* (luser) has to make [problems arise]
If your user doesn't want the choice, there's no need to shove it
in their face.
: And if you make it *automatic* then you also run afoul of
: Murphy's law since there is then the risk that luser will
: run through a bunch of data that cannot be compressed.
"Automatic" need not mean that the compression is /always/ applied.
It is possible (for example) for the compressor to analyse
the text and choose between two different compression algorithms,
(one of which is the identity transformation) depending on what it's
being fed.
The result would not be a 1-1 compressor - since it wastes one bit
describing which algorithm is in use.
Such a compressor would expand the most incompressible plaintexts by at
most one bit - and many plaintexts would be compressed significantly.
The added bit might knock a single bit off the keyspace of the encryption
algorithm, but - assuming you're aware of this - this is unlikely to be
a major source of practical difficulties.
This sort of solution is available to those worried about the issue
of having random files significantly bulked up by compression.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: Newbie question about factoring
Date: Sat, 01 Jul 2000 11:30:28 GMT
In article <8jivkc$qd9$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In the FAQs for sci.crypt and rsasecurity.com
> it is stated that the security of RSA depends
> (partially) on the assumption that factoring is
> hard. Does this mean the assumption that
> factoring is NP-hard and, if not, then how
> hard?
NP-Hard = NP-Complete, which fatoring probably isn't.
>Also, can factoring be described as a
> decision problem?
If you mean it can be solved trivally by making alot of 'guesses' in
parrell, i.e. Be easily solved on a non-determinstic Turing Machine then
yes your correct. Is this the definition of an NP problem?
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
--
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: Withheld <[EMAIL PROTECTED]>
Subject: Re: unable to use HIGH ENCRYPTION on IIS 5.0 (1024 bit key)
Date: Sat, 1 Jul 2000 12:56:40 +0100
Reply-To: Withheld <[EMAIL PROTECTED]>
This may not be much help, but if you're using the UK version check to
mae sure all the bits of the key are secret.
I vaguely recall using the UK version of IIS which claimed to be using a
128-bit key, but only 40 of the bits were secret.
In article <[EMAIL PROTECTED]>, Phil <[EMAIL PROTECTED]>
writes
>I'm unable to install a 1024 bit server-key on my win2000 server.
>Trying to process the pending request in IIS 5.0 (IIS Certificate Wizard) I
>always get the error msg:
>The pending certificate request ... was not found.
>
>It works perfectly with a 512 bit key, but 1024 doesn't work.
>
>I've got a Win2000 Adv.Server, English Version (from the International MSDN
>Subscription),
>I've recently installed the High Encryption Pack (English Version) and have
>even checked the schannel.dll to make sure it is the US & Canada Version.
>
>Any help is very welcome !
>
>Thanks in advance,
>
>Phil
>
>
--
Withheld
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: 1 Jul 2000 12:20:55 GMT
Make the assumption that it's going to happen in 5 years. How do you
maximise the benefits? Archive all available ciphertext, if that is not
feasible, target criminals, politicians, multinationals etc. (Insert your
own preferences here)
After 5 years plus suitable analysis, jail the criminals, disgrace the
politicians, split up the multinationals - whatever suits your agenda. But
remember that the effort will be limited by resources, money and human
stupidity.
Keith
http://www.cix.co.uk/~klockstone
------------------------
'Unwise a grave for Arthur'
-- The Black Book of Carmarthen
In article <8jhg0m$m1l$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Greg)
wrote:
> Give all of this, it would appear to be an intel op against European
> banks by possibly Isreali intelligence using the news paper as a pawn.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: Newbie question about factoring
Date: Sat, 01 Jul 2000 13:07:08 GMT
In article <[EMAIL PROTECTED]>,
Dido Sevilla <[EMAIL PROTECTED]> wrote:
> Factoring is not NP-hard (at least, not if P!=NP). Just very, very
> difficult. All known algorithms for factoring take time proportional
to
> the size of the number being factored.
BZZT. FALSE.
Thank you for playing.
If what you said WERE true, then factoring would be P-Time.
Please do us a favor and study the subject a little bit before
making further pronouncements.
No one has been able to find an
> algorithm for factoring that takes time proportional to a polynomial
in
> the number of digits of the number to be factored
Damn it! Read what you wrote above. I quote:
"All known algorithms for factoring take time proportional to
the size of the number being factored. "
The size of a number IS its number of digits.
You contradict yourself.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Roger Fleming)
Subject: Re: CRC-64 and 128 - Generator Polynomials?
Date: Sat, 01 Jul 2000 13:13:15 GMT
"Ken Christensen" <[EMAIL PROTECTED]> wrote:
>Are there "standard" generator polynomials for 64 and 128-bit CRC?
CRC-32 already has only a 1 in 4 billion chance of missing a random error, and
no CRC has any chance of stopping a deliberate attack. Consequently there is
no point in standardising longer CRCs.
>I want
>to study how CRC128 compares to MD5 in terms of 1) computation cost in s/w,
>2) gate count in h/w, and 3) probability of collisions (duplicate hashes)
>for hashing of Web URLs. Using remainder methods for computing CRC in s/w
>seems to me would require less CPU cycles than MD5???
CRCs are enormously faster and more compact than MD5. I see no reason why this
should be different for a CRC-64 or -128. The collision probability for
_random_ collisions is purely a function of hash length: if it's n bits long,
there is a 1 in 2^^n chance of another, randomly selected value giving the
same hash, while in a set of 2^^(n/2) values there is a roughly 50:50 chance
that there will be one pair of values with a matching hash. Thus CRC-32 will
let you collect about 65,000 hashes before it is likely you will get 1
duplicate; your hypothetical CRC-64 would let you collect about 4 billion
before it is likely you would have 1 duplicate.
However with CRC it is trivial to _calculate_ another value that will give the
same hash, whereas a cryptographic hash like MD5 is supposed to offer no
calculation better than random chance. If you need the speed of CRC but want
some attack resistance, and can afford a little setup time, there is a way to
make a MAC (keyed hash) out of CRC: generate an n-bit primitive polynomial at
random (uniformly distributed selection is achieved by generating random
n-bit numbers and testing for primitivity), generate the CRC, and xor with an
n-bit mask. The generator polynomial and the mask form the key, with a
strength of about 3/2n.
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: Sat, 01 Jul 2000 15:48:34 +0100
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Shawn Willden wrote:
> > One need not excuse the possibilities when a simple explanation is
> > available either.
>
> On balance, I think Occam's razor would favor Douglas' explanation.
> To put it another way:
>
> "Never attribute to malice that which is adequately explained by
> stupidity",
>
> -- Unknown (to me)
>
The malice and stupidity thing is sometimes called 'Hanlon's Razor', and is
attributed to Robert A. Heinlein.
See: http://www.netmeg.net/jargon/terms/h/Hanlon_s_Razor.html
Cheers,
Daniel
------------------------------
From: [EMAIL PROTECTED] (Daniel A. Jimenez)
Crossposted-To: comp.theory
Subject: Re: Newbie question about factoring
Date: 1 Jul 2000 10:05:26 -0500
In article <8jkkok$tm9$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
>In article <8jivkc$qd9$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>> In the FAQs for sci.crypt and rsasecurity.com
>> it is stated that the security of RSA depends
>> (partially) on the assumption that factoring is
>> hard. Does this mean the assumption that
>> factoring is NP-hard and, if not, then how
>> hard?
>
>NP-Hard = NP-Complete, which fatoring probably isn't.
NP-hard != NP-complete. NP-complete is a strict subset of NP-hard.
For instance, the Halting Problem is NP-hard, but not NP-complete.
Finding the optimal tour for the Travelling Salesman Problem is NP-hard,
but not NP-complete.
>>Also, can factoring be described as a
>> decision problem?
>
>If you mean it can be solved trivally by making alot of 'guesses' in
>parrell, i.e. Be easily solved on a non-determinstic Turing Machine then
>yes your correct. Is this the definition of an NP problem?
No, it's not and that isn't what he meant. See my and others' previous
posts on the matter. Basically, a decision problem is one with a "yes" or
"no" answer. You can cast factoring into a decision problem that solves a
piece of the factoring problem, then solve many instance of the decision
problem and put all the pieces together. Problems in NP and NP-complete
problems can only be decision problems. However, NP-hard can be applied
to both decision problems and function problems.
--
Daniel Jimenez [EMAIL PROTECTED]
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: Newbie question about factoring
Date: Sat, 1 Jul 2000 08:08:26 -0700
Daniel A. Jimenez <[EMAIL PROTECTED]> wrote in message
news:8jl1bm$gm0$[EMAIL PROTECTED]...
[snip]
> Finding the optimal tour for the Travelling Salesman Problem is NP-hard,
> but not NP-complete.
Huh? You appear to have some sort of clue, so maybe you know something I
don't. I was under the impression that the Travelling Salesman Problem was
NP-complete, and while "Finding the optimal tour for the Travelling Salesman
Problem" is not a decision problem, you can easily use a Travelling Salesman
Problem oracle to find the optimal tour in polynomial time. Or, am I
missing something?
--
poncho
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: Sat, 01 Jul 2000 11:01:30 -0400
Bill Unruh wrote:
> That is a Massivly Parallel Computer, which means it acts like a whole
> bunch of individual machines. Parts of the factoring are much faster on
> such a machine, parts apparently are not. However if you just use the
> raw assymptotic formula for say NFS, then 2046 bits would take 10^22
> sec. 1024 would take 10^13 sec. Ie, just take Schneier's times and
> divide by the ratio in speeds of the computers.
about 3 x 10^14 years ...
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Surrendering Keys, I think not.
Date: Sat, 01 Jul 2000 15:32:07 GMT
I think Usnet should be renamed "Re-Usenet".
In article <[EMAIL PROTECTED]>,
jkauffman <[EMAIL PROTECTED]> wrote:
> Consider the following scheme:
>
> I want to send message M to someone. I design a piece of
> crypto software which operates as follows:
>
> First it generates a OTP. It encrypts M with the OTP O to
> produce ciphertext C. It then asks the user to supply an
> innocuous message M' and generates a fake OTP O' such that
> O'(C) = M'. O and O' are concatenated in some format and
> encrypted with standard PKC, the resulting ciphertext C'
> being sent along with C. At the receiving end the software
> recovers C, O and O' and the user stores C in their machine
> and O and O' somewhere else physically secure (e.g. floppy
> disk). C' is then destroyed completely (this is very
> important).
> Now when the police demand the key, you can give them O' and
> they have no way of knowing that it isn't O. Not only this
> but you can produce the encryption software to prove that
> this is the mechanism that you always use for encryption.
> The obvious flaw in the plan is that if the police get hold
> of C' then they can demand your private key and break the
> whole system. However, if everyone did this then there is no
> way that the police can keep a record of every C' sent
> across the net. They would therefore have to specifically
> target comms between two parties, having prior knowledge
> that these two parties are engaged in criminal activities.
> This kind of solves two problems at once. On the one hand it
> means that if they put their minds to it the police can
> intercept and decrypt criminal messages, which is a good
> thing. On the other hand if you're not a criminal they can't
> just turn up at your house and demand the keys to your
> encrypted messages.
>
> * Sent from AltaVista http://www.altavista.com Where you can also find
related Web Pages, Images, Audios, Videos, News, and Shopping. Smart is
Beautiful
>
--
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: "Rick Braddam" <[EMAIL PROTECTED]>
Subject: Re: Remark on practical predictability of sequences
Date: Sat, 1 Jul 2000 10:22:01 -0500
Reply-To: "Rick Braddam" <[EMAIL PROTECTED]>
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Rick Braddam wrote:
>
> [snip]
>
> > I hope this helps those not familiar with Yarrow. I just checked at
> > Counterpane's site at
> > http://www.counterpane.com/yarrow.html and found that version 0.8.71
is
> > the one currently
> > available for download. The paper available describes one which uses
both
> > SHA1 and 3DES,
> > but the paper does not present any algorithms, and two figures which
might
>
> [snip]
>
> The wording of the paper concerning the input sequence seems to
> suggest that it should come from hardware. My point is that a software
> source, typically a common PRNG, should be o.k., if a good block
> cipher is used for post-processing.
To quote from yarrow-full.pdf:
"To update the key the PRNG needs to collect inputs that are truly random,
or at least not known, predictable or controllable by the attacker. Often
used examples include the exact timing of key strokes or the detailed
movements of the mouse. Typically, there are a fairly large number of
these inputs over time, and each of the input values is fairly small. We
call these inputs the samples."
In the previous version, 0.8.71, the collected data was just hashed with
SHA1. Frequent reseeding was done, as well as having a "slow pool" and a
"fast pool". There were also three user pools, and user-provided input
with entropy estimate could be hashed into any of them as well as the
default pool. Note that the user pools can be filled with input obtained
by the user (program) from a hardware random bit generator. I don't recall
there being any code within Yarrow for directly receiving input from one,
though. Unless you want to count timing of keystrokes etc as hardware
inputs.
The full version adds a block cipher keyed by the hash of the compressed
"samples", encrypting a counter. The 0.8.71 version appears to me to
pretty well mix things up, but the full version should satisfy *almost*
anyone's level of paranoia.
Well, it isn't based on an LFSR or similiar, but being software based I
think it still fits in the set of "common PRNG"s.
I'm sure one of the Counterpane team will correct any misconceptions I may
have written. The way the paper reads to me, the full version is an
extention of the earlier one. It could be totally unrelated, though.
Rick
------------------------------
** 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
******************************
