Cryptography-Digest Digest #955, Volume #12 Wed, 18 Oct 00 21:13:01 EDT
Contents:
Re: Is it trivial for NSA to crack these ciphers? ("Stephen M. Gardner")
Re: Is it trivial for NSA to crack these ciphers? ("Stephen M. Gardner")
Re: x509 (Bryan Olson)
Re: Is it trivial for NSA to crack these ciphers? ("Stephen M. Gardner")
Re: Is it trivial for NSA to crack these ciphers? ("Stephen M. Gardner")
Re: Is it trivial for NSA to crack these ciphers? ("Stephen M. Gardner")
Preliminaries on A. Plotnikov's P=NP paper (Stas Busygin)
Re: Why trust root CAs ? (Anne & Lynn Wheeler)
Re: ---- As I study Rinjdael... (Greggy)
Re: ---- As I study Rinjdael... (Greggy)
Re: DNA encoding (glen herrmannsfeldt)
Re: x509 (Roger)
----------------------------------------------------------------------------
From: "Stephen M. Gardner" <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
Date: Wed, 18 Oct 2000 17:07:06 -0500
John Savard wrote:
> Hence, it is quite possible it knows of ways to attack DES or Rijndael
> that are beyond anything known to the public.
I find it extremely hard to believe that there are better academic attacks let
alone practical attacks against these codes that have somehow remained secret. How
many cryptographers do you think the NSA committed to the study of Rijndael? Do
you seriously think it was many more than were going for glory by attacking it when
it was an AES finalist? And now that it is the selection the prize is instant fame
and a phone ringing off the hook with press and job offers.
> Whether what it knows is sufficient to effectively break these
> algorithms is quite another matter, and there are sound reasons to
> suspect that it might not. However, nothing is stopping people from
> taking additional precautions.
Like I said, I doubt they are light years ahead in academic attacks let alone
practical attacks against well managed crypto policy using any of the AES
finalists.
--
Take a walk on the wild side: http://www.metronet.com/~gardner/
There is a road, no simple highway, between the dawn and the
dark of night. And if you go no one may follow. That path is
for your steps alone.
The Grateful Dead ("Ripple")
------------------------------
From: "Stephen M. Gardner" <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
Date: Wed, 18 Oct 2000 17:17:35 -0500
lcs Mixmaster Remailer wrote:
> Aren't you forgetting the obvious fact that these "alphabet soup agencies" don't use
>any of these ciphers to conceal data that is important to them?
Nope. NIH isn't just the acronym for the Nationa Institute of Health. ;-)
> And overall, the U.S. government seems to have loosened up crypto restrictions.
>Call this FUD if you want, but I find it hard to believe these controls were relaxed
>because either:
> A) The genie was already out of the bottle
> B) American software companies were finally successful in convincing the government
>that they were loosing business to overseas companies.
> C) The original policy was just plain stupid, and the government changed to to look
>smart(er).
Those reasons are precisely why it was done.
> I suppose one could assert the "not invented here" philosophy as the primary reason
>the government uses secret ciphers to contain secret data.
Yup. Besides, as many have pointed out, obscurity may not be a good bulwark but it
is another barrier.
> But no one disputes that there are genuine cryptography experts at Ft. Meade that
>believe their ciphers are the best and most secure in the world.
But are they so good that the open community can't even guess at the security of
the major AES contenders? I don't think so. Some folks here are pretty paranoid and
put alot of
faith in the government to be smarter than anyone else.
--
Take a walk on the wild side: http://www.metronet.com/~gardner/
There is a road, no simple highway, between the dawn and the
dark of night. And if you go no one may follow. That path is
for your steps alone.
The Grateful Dead ("Ripple")
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: x509
Date: Wed, 18 Oct 2000 22:13:19 GMT
David Wagner wrote:
> Bryan Olson wrote:
> >[That is, why does the identifier of the signing algorithm
> >appear both inside and outside the data under the
> >signature?]
> >
> >I've wondered about that. If anyone knows of some attack
> >defeated by identifying the signing algorithm inside the
> >signed message, please tell.
> >
> >For now my theory is that whether the identifier is inside
> >or outside the signed data does not matter.
>
> If I understand correctly, you're asking whether there is an
> attack if the algorithm-identifier is not mentioned in the
> signed part? The answer is Yes, there are attacks.
>
> For instance, MD4 is almost broken. Suppose someone extends
> Dobbertin's techniques just a bit, enough to find pre-images
> for MD4. Now you're smart: you stopped using MD4 ages ago,
> and all your signatures take the form <m, "MD5", Sign(MD5(m))>.
>
> Under the above scenario, there is an attack. Let y = MD5(m). I use
> my inversion algorithm to find a preimage m' of y under MD4. Now note
> that <m', "MD4", Sign(MD5(m))> is a valid signature on m', which any
> receiver will accept. But the original signer never intended for m'
> to be signed! Therefore, the message integrity property is violated;
> QED.
But the algorithm ID protected under the signature does not
prevent this attack.
> More generally, it is not sufficient that MD5 be collision-free; it is
> required that the mapping (h,m) |-> h(m) be collision-free, where the
> domain of this mapping is the Cartesian product of the set of
recognized
> hash functions with the set of possible messages. In other words,
> we must also assume that there is no efficient algorithm to find m,m'
> such that MD5(m) = SHA(m'), and this property is not guaranteed by the
> collision-freeness of MD5 and SHA.
>
> Did I misunderstand your question?
Maybe. Your answer implies that we should put into a
certificate a statement of what signature algorithm(s)
(including hash) may be used with the subject public key.
But that is _not_ the meaning of the algorithm ID in X.509
certificates. The algorithm field only identifies the
algorithm used to sign this one certificate.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Stephen M. Gardner" <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
Date: Wed, 18 Oct 2000 17:21:52 -0500
CiPHER wrote:
> I have no doubts in my mind that every (applicable) cipher out there
> has already been easily broken by the top intelligence agencies.
This statement may have more to do with your ability than theirs. ;-)
> You see, otherwise, they'd really be shitting it and export laws would
> be tougher than you could possible imagine...
The genie is already outof the bottle. What good do export controls
do when non-residents of the US know as much as residents do? This is
just plain silly.
> ...and everyone acts suprised when flaws are found in the 'best'
> systems.
Do you know any *practical* flaws in ANY of the AES constestants?
--
Take a walk on the wild side: http://www.metronet.com/~gardner/
There is a road, no simple highway, between the dawn and the
dark of night. And if you go no one may follow. That path is
for your steps alone.
The Grateful Dead ("Ripple")
------------------------------
From: "Stephen M. Gardner" <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
Date: Wed, 18 Oct 2000 17:31:49 -0500
Bob Silverman wrote:
> (1) What people outside the NSA think is irrelevant. They can not
> possibly have information about the NSA's true capabilities. Given
> this, any "opinion" is worthless, because it is totally unfounded.
Sure. But as you point out there is nothing to make anyone think that
the NSA has magical powers. Speculating that the NSA has no godlike powers
is speculation too but it is fairly safe speculation. ;-)
> (4) We *know* how much arithmetic is required to break a 128-bit
> cipher. We know how much storage is needed to conduct a linear or
> differential attack. Why then do we keep getting speculation that the
> NSA can somehow magically break ciphers that the outside world can not?
Because "the truth is out there". ;-) Seriously, I think psychology is
more at play here than knowledge of crypto. Some people get a kick out of
believing that the NSA is all-powerful just like others get a kick out of
believing in alien autopsies in New Mexico.
> I am curious about the psychology of people who ask these kinds of
> questions -- questions for which it is clear that noone can answer
> in a meaningful way. What is the point?
To say that no one can reasonably speculate about NSA capabilities just
because NSA doesn't reveal them neglects the fact that the laws of physics
are the same in Ft Mead as they are in Moscow. As you point out it is
possible to reasonably conclude that they are not wizardlike in their
capabilities compared to the outside world. Is that speculation? Do you
anyone have hard facts? Well, not really but you do have house odds and I'm
always damned glad when I can bet with house odds. ;=)
--
Take a walk on the wild side: http://www.metronet.com/~gardner/
There is a road, no simple highway, between the dawn and the
dark of night. And if you go no one may follow. That path is
for your steps alone.
The Grateful Dead ("Ripple")
------------------------------
From: "Stephen M. Gardner" <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
Date: Wed, 18 Oct 2000 17:13:44 -0500
Mok-Kong Shen wrote:
> Wise people never 'demonstrate'
> their strength (or depth of knowledge) unless absolutely
> necessary.
Sure. The NSA doesn't give its secrets up willingly but being asked to believe
that they have, by virtue of their
history and past glories, some magic wizardry that isn't even considered by mere
mortals has a strong X-files odor to
it. This is not 1950. There is a lot of crypto research in the open now and the
people engaged in it are very bright
and don't have to take a lie detector test periodically or suffer the indignity of
being questioned about the most
personal aspects of their lives. The security bullshit tends to discourage the best
and brightest from applying for a
job there when they can more easily obtain a fulfilling job in industry or academia.
> In allday life physical sizes of persons rarely
> correspond to their relative 'strength'.
But that has nothing to do with whether one demonstrates one's strength.
> Recently a newspaper
> photo showed that a young Japanese school boy succeeded to
> put Mr. Putin onto the ground with Judo.
Being head of Russia doesn't necessarily endow one with superior strength and
agility. I'm not sure why this is so
suprising given the nature of judo.
--
Take a walk on the wild side: http://www.metronet.com/~gardner/
There is a road, no simple highway, between the dawn and the
dark of night. And if you go no one may follow. That path is
for your steps alone.
The Grateful Dead ("Ripple")
------------------------------
From: Stas Busygin <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Preliminaries on A. Plotnikov's P=NP paper
Date: Thu, 19 Oct 2000 02:08:35 +0300
Dear All!
I've just sent my preliminary conclusions concerning the paper to
theory-edge list. If you are interested in this investigation,
please find them:
http://www.egroups.com/message/theory-edge/1498
BTW, the paper has been patched several times recently. If you read
its version dated before 10/17, please download the patched text:
http://www.geocities.com/st_busygin/clipat.html
Best wishes,
Stas Busygin
email: [EMAIL PROTECTED]
WWW: http://www.busygin.dp.ua
------------------------------
Subject: Re: Why trust root CAs ?
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
From: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
Date: Wed, 18 Oct 2000 23:49:41 GMT
Greggy <[EMAIL PROTECTED]> writes:
> If you were a bank and you had these choices before you and your
> marketing people were telling you that you can either:
>
> A) use this totally insecure CA strategy and provide your customer base
> with a very simple to use web site that would save you money in teller
> payrolls
>
> or
>
> B) use a real strategy for security that makes your customers work
> harder, which in turn would drive your customers away from your new web
> sites (and you lose the payroll savings as well)
>
> which would you choose?
there have been other situations making such claim regarding
things like CAs & certificates in financial infrastructures.
the frequent fallicy is ignoring the fact that customer support is
required and that requires things like answering questions about
pieces and components (i.e. a 1-800 number in the case something
doesn't work ... who does the customer call).
in order for the call center to effectively answer calls ... they need
access to the related components ... which leads a financial
institution to registering the components in databases accessable by
the call centers.
the per screen lay-out costs at the call center and the registration
process in support of the call center frequently dominate all the
costs associated with any such activity (regardless of the
implementation).
of course the above only applies to real-live roll-outs and can be
bypassed/ignored in the case of toy pilots, in which case other
trade-off decisions can be made regarding the degree of investment in
toy pilots (i.e. like punting on the issue of providing customer
support).
One of the issues for toy pilots can be assumption that the early
adapter participation in toy pilots will self-select ... i.e.
everything goes right and the individual participates or it doesn't go
right and they don't participate.
getting out a technology "with-it" press release on a toy pilot, it is
possible to cut all sort of corners, possibly leaving worrying about
the real implementation later after testing the water.
Furthermore, CA/certificates as being easy for customers and
non-CA/certificates as being hard for customers is not a proven
generalization (improved integrity doesn't have to be unnecessarily
intrusive).
Skirting the requirement of expense for full customer support in
association with toy pilots is probably a much better understood
generalization.
--
Anne & Lynn Wheeler | [EMAIL PROTECTED]
http://www.garlic.com/~lynn/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: ---- As I study Rinjdael...
Date: Thu, 19 Oct 2000 00:02:42 GMT
In article <[EMAIL PROTECTED]>,
Cornelius Sybrandy <[EMAIL PROTECTED]> wrote:
> > But Rijndael was chosen primarily for its speed, so there is also
the
> > option of choosing one of the available ciphers from among the other
> > finalists, such as Twofish, SERPENT, or, now, MARS as well.
> >
>
> Just so I'm not confused, but MARS is now free to use? The last I
heard
> there were no definates on that subject.
>From www.ibm.com, search on Mars:
The MARS cipher - IBM submission to
AES MARS is now available worldwide
under a royalty-free license from Tivoli.
Read the press release or contact Ron
Silletti at 914-765-4373 for more details.
May 1
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: ---- As I study Rinjdael...
Date: Thu, 19 Oct 2000 00:05:14 GMT
News Releases
========================================================================
========
E-commerce Encryption Algorithm Now Available from Tivoli®, Royalty-Free
FOR MORE INFORMATION
About Tivoli Security Business Unit
SAN JOSE, Calif. – January 18, 2000 – (RSA Conference) – IBM today
announced the immediate availability of its MARS encryption algorithm
under a royalty-free license, worldwide from Tivoli Systems Inc. The
MARS algorithm is designed to protect e-commerce transactions and
mission critical data, creating a secure environment for businesses and
their customers in the Internet economy. Tivoli is focused on
delivering security management and control applications to help enable
e-business and e-commerce.
MARS is one of five finalists being considered for the Advanced
Encryption Standard, the follow-on to the Data Encryption Standard
(DES), developed by IBM® more than 20 years ago. The MARS encryption
algorithm is four times faster than DES and is the only finalist that
features two separate security mechanisms instead of one, providing a
powerful defensive tool.
The computer industry's exponential growth has necessitated a change in
the Data Encryption Standard. The National Institute of Standards and
Technology (NIST) is in the process of selecting the new standard. MARS
satisfies all NIST requirements, including a minimal 128-bit key. The
MARS encryption algorithm can be implemented in both hardware and
software. NIST is expected to complete its selection process and
announce a winner by third quarter 2000. The technical specifications
for MARS may be accessed at: http://www.tivoli.com/security.
About Tivoli Systems Inc.
Tivoli Systems Inc. provides the industry's leading open, highly
scalable and cross-platform technology management solutions that span
networks, systems, applications and business-to-business e-commerce.
Leading companies around the world use Tivoli software and Tivoli
Ready™ products to reduce the cost and complexity of managing networks,
systems, databases and applications. Headquartered in Austin, Texas,
Tivoli is an IBM company (NYSE: IBM). Tivoli distributes its products
worldwide through a network of global sales offices, systems
integrators, resellers and IBM sales channels. For more information,
visit www.tivoli.com.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (glen herrmannsfeldt)
Subject: Re: DNA encoding
Date: 19 Oct 2000 00:50:57 GMT
[EMAIL PROTECTED] writes:
(snip)
>I'd assume in the first round that the message is there in
>isolation and not attached to other DNA. So I would sequence
>a good number of the vectors and try to identify the source
>of the DNA mixed in with the message - for example, it might
>be human DNA. (For economic reasons it would be prohibitive
>to synthesise enough different random strands of DNA as background,
>it would make more sense to use a biological source). I'd
>do hybridisation with what appeared to be the background DNA
>to remove as many vectors from consideration as possible and
>have a look at the reduced population.
PCR will find it with only a few copies. If you put enough other
DNA in place, it will be really hard to find mechanically.
DNA is easy to splice together, so it could be spliced into
a 100MB piece of some ordinary DNA. If the ordinary DNA was
from a large number of different samples (say different people)
there would be enough natural variation that you would never
find it. Say I take 10**5 copies of DNA from 1000 people.
That is 10**8 human genomes. Splice the message into a chromosome
and make 100 copies of it. Now you have to sequence 10**8 human
genomes worth to find the sequence.
-- glen
>Another approach (once everyone goes to the effort of inserting
>their message into pieces of the DNA they will be using for
>background - this won't affect PCR in the slightest) is based
>on the fact that you can't afford to put just one copy of the
>message in (in fact, it's not physically possible -
>you're dealing with stochastic effects at such low dilutions).
>By doing some hybridisation of vectors against each other, you
>should quickly get an idea of how much of the DNA is single-
>copy (it can be safely ignored) and how much is in multiple
>copies and how many classes there are. The person could
>have mixed their message with DNA that only belonged to one
>class (for example a purified vector) but that would make it
>very easy to identify the minority of vectors that contain DNA
>different from all the rest. Clearly there is a trade-off in
>creating a background mixture of DNA that makes it harder to
>find the message.
>If I knew the substitution code used for the message, I'd
>check each vectors' profile on a microarray (DNA chip). The message
>might not be pinpointed but as long as it reduced the number of
>vectors I had to sequence, it would help. Microarrays are still
>somewhat expensive technology but I doubt they will be long.
>And in the end, brute force sequencing of all vectors would be
>more effective than brute force PCR for all primers. There'd be
>about 4^40 primer pairs to test and it's unlikely I'd need to
>sequence that many vectors before I found a copy of the message.
>And even with the brute force PCR, I'd still have to do a lot
>of sequencing because many of the other primer pairs would also
>amplify something. The brute force PCR approach strikes me as
>about the dumbest way to find the message.
>Ingrid
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: Roger <[EMAIL PROTECTED]>
Subject: Re: x509
Date: Wed, 18 Oct 2000 17:58:22 -0700
Bryan Olson wrote:
> Maybe. Your answer implies that we should put into a
> certificate a statement of what signature algorithm(s)
> (including hash) may be used with the subject public key.
> But that is _not_ the meaning of the algorithm ID in X.509
> certificates. The algorithm field only identifies the
> algorithm used to sign this one certificate.
I agree with that implication. I never understood why anyone
would want a cert for a signature algorithm and key without
the hash function. The signature function is useless without
the hash function.
I suppose someone might think that a cert for a public key
without a hash function might be of some use, because you
could switch to another hash function in case the hash function
is broken. But that scenario is dangerous, because then others
might be using that cert to forge messages with the broken
hash function. So I think it would be better to revoke the
cert anyway if it was being used with a broken hash function.
So can anyone tell me? Why aren't signature public keys
always linked to a specific hash function in a cert?
------------------------------
** 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
******************************
