Cryptography-Digest Digest #693, Volume #10 Mon, 6 Dec 99 16:13:01 EST
Contents:
Re: NP-hard Problems (Anton Stiglic)
Re: Random Noise Encryption Buffs (Look Here) (Tim Tyler)
Re: AES cyphers leak information like sieves (Tim Tyler)
Re: High Speed (1GBit/s) 3DES Processor (Helger Lipmaa)
Re: Johnson Device (Scott Nelson)
Re: NSA competitors (JCA)
NSA future role? (SCOTT19U.ZIP_GUY)
Re: Data Encryption in Applet? (Tim Tyler)
Re: Data Encryption in Applet? (Luciano da Silva Coelho)
Re: NSA future role? (Steve K)
Re: NSA should do a cryptoanalysis of AES ("karl malbrain")
----------------------------------------------------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: Mon, 06 Dec 1999 15:02:21 -0500
==============212B898CB9E4A1CA76605E5A
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
>
Your remarks are valid. I was just trying to give a simple intuitive
explanation,
while not completly defining the term. It's simpler to think of problems
that
are not decisional, but complexe, than to think of decisional problems that
are
more complexe than NP-complete.
As for what you are talking about, you could, in the same way, build up a
hierarchy
of different levels of *non-resolvable* classes of problems. But I beleive
that to
understand this one would need some advanced classes in computer complexity.
For what sci.crypt is concerned, I beleive a most intuitive example is what
is
needed.
Anton
> No, there is a much more fundamental difference than that. NP-hard
> problems are not restricted to the class NP, so while most people will
> allow non-decision problems to be called NP-hard, NP-hard problems can
> in fact be *much* harder decision problems than those in the class NP.
>
> For example, take a decision problem A that is complete NTIME(2^n).
> We know by the various time hierarchy results that such an A exists
> and is not in the class NP, so is strictly harder than the problems in
> NP. Furthermore, since NP is a subset of NTIME(2^n), you know that
> everything in NP is reducible to A. Therefore A is NP-hard, but
> cannot possibly be NP-complete, even though it is a decision problem.
>
> So we know that there are (decision) problems that are NP-hard and not
> NP-complete, so there exist provably intractible NP-hard problems.
> However, we don't know if there are any NP-complete problems that
> aren't in P, so there *aren't* any provably intractible NP-complete
> problems (well... there may be "provably" intractible NP-complete
> problems, but we don't know of any such proofs at this time!). So
> there is a *huge* difference between NP-hard and NP-complete, and it's
> definitely not restricted to "the fact that NP-hard problems are not
> limited to decisional problems".
>
> --
> Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
> Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
> University of North Texas | or better,' so I installed Linux."
> Denton, TX 76201 |
--
___________________________________________
Anton Stiglic
Jr. developer & specialist in cryptology.
Zero-Knowledge Systems Inc.
___________________________________________
==============212B898CB9E4A1CA76605E5A
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<blockquote TYPE=CITE> </blockquote>
Your remarks are valid. I was just trying to give a simple
intuitive explanation,
<br>while not completly defining the term. It's simpler to think
of problems that
<br>are not decisional, but complexe, than to think of decisional problems
that are
<br>more complexe than NP-complete.
<br>As for what you are talking about, you could, in the same way, build
up a hierarchy
<br>of different levels of *non-resolvable* classes of problems.
But I beleive that to
<br>understand this one would need some advanced classes in computer complexity.
<br>For what sci.crypt is concerned, I beleive a most intuitive example
is what is
<br>needed.
<p>Anton
<br>
<blockquote TYPE=CITE>No, there is a much more fundamental difference than
that. NP-hard
<br>problems are not restricted to the class NP, so while most people will
<br>allow non-decision problems to be called NP-hard, NP-hard problems
can
<br>in fact be *much* harder decision problems than those in the class
NP.
<p>For example, take a decision problem A that is complete NTIME(2^n).
<br>We know by the various time hierarchy results that such an A exists
<br>and is not in the class NP, so is strictly harder than the problems
in
<br>NP. Furthermore, since NP is a subset of NTIME(2^n), you know
that
<br>everything in NP is reducible to A. Therefore A is NP-hard, but
<br>cannot possibly be NP-complete, even though it is a decision problem.
<p>So we know that there are (decision) problems that are NP-hard and not
<br>NP-complete, so there exist provably intractible NP-hard problems.
<br>However, we don't know if there are any NP-complete problems that
<br>aren't in P, so there *aren't* any provably intractible NP-complete
<br>problems (well... there may be "provably" intractible NP-complete
<br>problems, but we don't know of any such proofs at this time!).
So
<br>there is a *huge* difference between NP-hard and NP-complete, and it's
<br>definitely not restricted to "the fact that NP-hard problems are not
<br>limited to decisional problems".
<p>--
<br>Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
<br>Dept. of Computer Sciences | "The
box said 'Requires Windows 95, NT,
<br>University of North Texas
| or better,' so I installed Linux."
<br>Denton, TX
76201
|</blockquote>
<pre>--
___________________________________________
Anton Stiglic <[EMAIL PROTECTED]>
Jr. developer & specialist in cryptology.
Zero-Knowledge Systems Inc.
___________________________________________</pre>
</html>
==============212B898CB9E4A1CA76605E5A==
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Random Noise Encryption Buffs (Look Here)
Reply-To: [EMAIL PROTECTED]
Date: Mon, 6 Dec 1999 19:54:38 GMT
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
:> : Tim Tyler wrote:
: :> :> Whereas your position appears to be based on faith in the existence of
: :> :> genuine randomness in subatomic behaviour, and in our ability to
: :> :> magnify this up to a macroscopic scale, without distorting it at all.
: Not faith. Fact. We can detect, amplify, and record quantum events. In fact
: there are quantum effects that have macro-scale results such as super fluids.
"Genuine randomness" in quantum events is /not/ fact. It's theory.
I'm well aware that quantum events can be magnified. Schrodinger's cat
springs to mind ;-)
My problem is that there appears to be no practical way to magnify the
supposed randomness to a macroscopic scale in a manner that completely
retains its supposed purity.
*Even* if I were to grant that quantum events were totally random, this
would not help people to build an unbiased RNG based on this source -
since they can't completely remove influences from the environment
on the system they are studying.
: As for distortion-free amplification and recording, such a system might be
: possible, but I see no way to prove that it can be done, nor to prove that any
: given system is perfect in that sense.
Nor do I. On the contrary, I see *every* reason to believe that it can't
be done. In much the same way that a perfect vacuum does not exist, and
in the same sense that nowhere is it perfectly dark, and nowhere is
space-time perfectly flat. You simply can't completely eliminate biasing
influences from the environment on your system.
: Consider that perfection is impossible because whatever instrument we
: use to measure the perfectness will have an asymmetrical error rate.
Yes, a problem.
: Rather than insisting on perfection, it makes sense to look for sources
: whose distortion/bias/predictability is below our ability to detect
: those effects. This leaves us vulnerable to an opponent who can detect
: more subtle effects that we can, but it _quantifies_ the expected degree
: of imperfection. [...]
The ability to detect deviations from randomness is important...
In much the same way the ability to detect weakness in cyphers is
important.
However, I think our ability to build good RNGs should *far* outstrip
our ability to /test/ for randomness.
Get 100 RNGs that pass all our best tests for randomness, and are believed
to be independent of one another and EOR them together.
Similarly, applying a series of multiple encypherments - with different
types of cypher - may be expected to significantly add to the strength of
the resulting system.
There are other related techniques - attempts to build "scalable" RNGs
where some aspects of the randomness increase when the size of the
internal state of the RNG is increased in size is another approach.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Nature always sides with the hidden flaw.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Reply-To: [EMAIL PROTECTED]
Date: Mon, 6 Dec 1999 20:06:51 GMT
Volker Hetzer <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Volker Hetzer <[EMAIL PROTECTED]> wrote:
:> : Tim Tyler wrote:
:> :> Volker Hetzer <[EMAIL PROTECTED]> wrote:
[block size doubling ==> work required for a break doubling?]
:> :> : If [...] the usual attacks (like differential) will require the
:> :> : same number of blocks
:> :>
:> :> Some attacks will require a /much/ larger numbers of blocks, however.
:> :
:> : Such as?
:>
:> Say you're compiling a dictionary of blocks, which matches blocks to
:> corresponding plaintexts. Say you have a target of getting 1/8 of the
:> blocks. This lets you take vague guesses at the contents of the message,
:> pretty much regardless of the block size.
:
: Why should I do this? If I'm able to compile a dictionary with the right
: key I can decrypt the messages anyway.
I'm not saying you have knowledge of /every/ dictionary entry (i.e. block).
You don't need to know the key at all.
My figures were (the extremely high) 1/8 of the blocks as a target.
If your blocks do not affect one another - and you can compile this type
of dictionary from a known portion of the message - then you can use it to
decrypt the rest of the message.
This is a type of known-partial-plaintext attack, which gets harder very
rapidly as the block-size increases.
With a 32-bit block size, it is almost usable on long English text
messages. With a 256-bit block size, it is *far* more than 8 times harder
- as the odds of blocks colliding go through the floor.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
FS: Encyclopaedia Brittanica. Never used. Wife knows all.
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Crossposted-To: comp.dcom.vpn,comp.security.firewalls
Subject: Re: High Speed (1GBit/s) 3DES Processor
Date: Mon, 06 Dec 1999 22:00:48 +0200
Jerry P wrote:
> No market research needed.
>
> 3DES at a 1 Gigabit/sec, like anti-gravity, free desalination,
> non-polluting engines, and ADSL, is obviously a billion-dollar
> winner. NSA can do 3DES at 1 Gigabit/WEEK with Cray computers.
>
> Of course, someone claiming fast 3DES would have to publish
> the source code for peer review before ANYONE it his right
> mind would even consider using it. All other trusted algorithms
> (DES, 3DES, Blowfish, etc.) have been so published.
>
> Almost all the 'proprietary' encryption methodologies have been
> cracked and found to be trivial (cell phones, smart cards,
> DVDs, et al).
My parallel implementation of
IDEA (http://home.cyber.ee/helger/fastidea) runs 300 Mbit/s on 700 MHz
Pentium III. It is software only. And in hardware 3DES is much easier to
implement, and there's also much more companies implementing
DES/3DES than implementing IDEA, since DES/3DES is a standard (the
fastest hardware implementation of IDEA that I know - by Ascom - works
in about the same speed, 300 Mbit/s, as mine software-only
implementation).
I would say 1Gbit/s does not surprise me at all - in particular since
I've known that such chips exist for at
least three years. Or, citing rfc 1851:
Three DES-CBC implementations may be pipelined in series to provide
parallel computation. At the time of writing, at least one hardware
implementation can encrypt or decrypt at about 1 Gbps [Schneier94, p.
231].
And that was in 1994 (probably already in 1993, since it takes some time
to print a book --- I only have the second edition of this book, so
cannot check that information myself). Apply Moore's law (and divide by
three to get 3DES;).
Helger Lipmaa
http://home.cyber.ee/helger
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Johnson Device
Reply-To: [EMAIL PROTECTED]
Date: Mon, 06 Dec 1999 20:21:53 GMT
On Sun, 5 Dec 1999, "Kurt Flei�ig" <[EMAIL PROTECTED]> wrote:
>does anybody use an hadrware device to obtain from the thermodynamic
>Johnsons's effect of the Pc's sound blaster a big bit's chaotic stream for
>one-time-pad encryption?
>
You mean like;
470K ohms
Square Wave ----\/\/\/\/\----+-------- input
|
===== .01 uFarad
|
|
Ground
I've done something similar, though the input was a generic A/D,
not a sound blaster card (I didn't use a PC)
A quick summary of the results;
There's a lot less unguessable noise than you think.
You need to post-process the data.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: NSA competitors
Date: Mon, 06 Dec 1999 12:28:16 -0800
CLSV wrote:
> The NSA is used as some sort of metaphor for high quality
> cryptanalysis. Some claim that the NSA is 5 - 20 years ahead
> of the public cryptographic community. Other sources point to
> failing management, lack of focus in the organization that
> could bring down the technical advantage pretty quick.
>
Past evidence seems to suggest that at least all the way to the
early nineties the NSA was indeed a few years ahead of academia, as
attested by the differential cryptanalysis-resistent DES design, well
before this cryptanalytic technique was published in the specialized
academic literature.
What the status quo is like right now is anybody's guess (and the
NSA's circumspection is legendary) but I personally conjecture that
given that there has been an increased academic interestic in the crypto
disciplines in the last twenty years, the NSA's preeminence may have
been significantly undercut these days. In addition, unless the academic
interest subsides, they might be left behind soon (unless they've got
more and better crypto people than all the academic world.)
> I'm wondering if there is any knowledge about non-US
> government institutes that are specialized in cryptography and
> cryptanalysis? I'm thinking about countries that invest a lot
> in mathematical education like China, Russia, India.
I know that the French and the Brits do have organizations dealing
with this kind of stuff, but they are, if anything, more secretive than
the NSA. I would be very surprised if the Chinese don't do it. But don't
hold your breath till you obtain any info from them.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: alt.politics.org.nsa
Subject: NSA future role?
Date: Mon, 06 Dec 1999 21:25:46 GMT
Since NASA seems to have gone down the shitter with very few real successes
recently. And since the US does not have any real secrets left ( Clinton and
the DNC sold our latest and greatest nukes to China). Why not use a lot of the
wasted money that is spent on the over bloated NSA to revamp a new NASA
where current employes can just change badges. The space program badly
needs good talent. We could even set new goals like a man on Mars by 2010.
After all if Mr BS is correct and the puplic sector encryption methods like
his widely publicezed Two fish is beyond the reach of the NSA why waste
the money. Especially when all the good secrets the NASA was pretending
to protect have already been bought by the chinese.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
Crossposted-To:
comp.lang.java.security,microsoft.public.java.security,comp.lang.java.programmer
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Data Encryption in Applet?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 6 Dec 1999 20:42:22 GMT
In sci.crypt Tim Wood <[EMAIL PROTECTED]> wrote:
: [the original poster] wrote:
:>I am looking for a way to encrypt data through an applet using symmetric
:>(or asymmetric) encryption. I thought of sending an applet containing a
:>symmetric key to a client.
: How? If the symmetric key is not encrypted when you send it, it could be
: intercepted and used to read the, client side encrypted, data.
Solution: use an asymmetric system.
http://java.sun.com/security/ is an interesting resource for Java
folks interested in security.
If you live in the USA, you can download JCE 1.2 from here - which does
public key cryptography.
The searchable archives at http://java.sun.com/security/hypermail/ are
also useful, IMO.
I don't know what non-US folks can do :-(
RSA Data Security has the JSAFE toolkit, which does public key
cryptography - if you have a few hundred dollars spare - but I'm
not even sure if this is available for export.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
... <-- grains of sand. Please take one.
------------------------------
Date: Mon, 06 Dec 1999 18:54:39 -0200
From: Luciano da Silva Coelho <[EMAIL PROTECTED]>
Subject: Re: Data Encryption in Applet?
Crossposted-To:
comp.lang.java.security,microsoft.public.java.security,comp.lang.java.programmer
There're some JCE (Java Security Extension) out of US. For example: Cryptix,
IAIK, DSTC and in a near future (I hope ;-) ) one from my company (e-Sec).
[ ]'s
Luciano Coelho
Sun Certified Programmer for Java2
e-Sec Data Security Technology
[EMAIL PROTECTED]
Tim Tyler wrote:
> In sci.crypt Tim Wood <[EMAIL PROTECTED]> wrote:
> : [the original poster] wrote:
>
> :>I am looking for a way to encrypt data through an applet using symmetric
> :>(or asymmetric) encryption. I thought of sending an applet containing a
> :>symmetric key to a client.
>
> : How? If the symmetric key is not encrypted when you send it, it could be
> : intercepted and used to read the, client side encrypted, data.
>
> Solution: use an asymmetric system.
>
> http://java.sun.com/security/ is an interesting resource for Java
> folks interested in security.
>
> If you live in the USA, you can download JCE 1.2 from here - which does
> public key cryptography.
>
> The searchable archives at http://java.sun.com/security/hypermail/ are
> also useful, IMO.
>
> I don't know what non-US folks can do :-(
>
> RSA Data Security has the JSAFE toolkit, which does public key
> cryptography - if you have a few hundred dollars spare - but I'm
> not even sure if this is available for export.
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> ... <-- grains of sand. Please take one.
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Crossposted-To: alt.politics.org.nsa
Subject: Re: NSA future role?
Date: Mon, 06 Dec 1999 21:03:15 GMT
On Mon, 06 Dec 1999 21:25:46 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:
> Since NASA seems to have gone down the shitter with very few real successes
>recently. And since the US does not have any real secrets left ( Clinton and
>the DNC sold our latest and greatest nukes to China). Why not use a lot of the
>wasted money that is spent on the over bloated NSA to revamp a new NASA
>where current employes can just change badges. The space program badly
>needs good talent. We could even set new goals like a man on Mars by 2010.
>
> After all if Mr BS is correct and the puplic sector encryption methods like
>his widely publicezed Two fish is beyond the reach of the NSA why waste
>the money. Especially when all the good secrets the NASA was pretending
>to protect have already been bought by the chinese.
Looks like the NSA is already shopping for a new role in national
affairs; see:
http://www.prnewswire.com/cgi-bin/stories.pl?ACCT=104&STORY=/www/story/12-05-1999/0001088875&EDATE=
In short, the NSA is publicly talking to the FBI about expanding
"cooperation" between the two agencies. There goes the neighborhood.
Steve K
---Continuing freedom of speech brought to you by---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: NSA should do a cryptoanalysis of AES
Date: Mon, 6 Dec 1999 13:07:54 -0800
Trevor Jackson, III <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> karl malbrain wrote:
>
> > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > karl malbrain wrote:
> > > > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > > > > The infamous "toilet seat" was a limited production of fiberglass
> > > > > moldings for a military transport plane, and would have cost about
> > > > > as much as it did no matter what.
> > > > Pure nonsense. We're talking about how the military specified a
> > > > non-COTS toilet seat in the first place.
> > >
> > > It wasn't a "toilet seat", dammit, it was a *necessarily* custom
> > > molding to fit a specific tight space in a packed aircraft. How
> > > many other aircraft components are COTS consumer items? Proxmire
> > > was grandstanding for political purposes, and shame on you for
> > > falling for it.
> >
> > Your logic reminds me how BART decided to abandon rail-road signaling
> > standards, and specify their VERY own VOLTAGE level between the rails.
> > Nothing but problems ever since. And where did you ever get the idea
that
> > I'm not POLITICAL? Karl M
>
> There's no argument here. pROXMIRE was creating issues out of thin air.
He
> once complained about a $600 coffe pot, conjuring up the image of a 19.95
> Lechmere (RIP) special as the alternative. Like you are going to put a
> table-top coffee pot on a military transport jet, expect it to feed 600
men,
> at altitude (where water boils at lower temperature), and do so safely.
Go
> price a commerical coffee pot as you would for a restaurant. Then price a
> coffee pot used on an airliner.
That's exactly the SAME point. Why don't they use COTS specifications from
the airlines?
> There are also convoluted rules that require the distribution of
> administrative costs over every item listed on an invoice. So an invoice
for
> a jet engine costing ~1e5 and 1 lb of spare titanium 10/32 nuts costing
~1e1
> both share the ~1e3 cost of admin, producing extremely valuable 10/32
nuts.
> Nuts to that.
That's SOCIAL DEMOCRACY in action, trying to reign-in DOUBLE ENTRY
BOOKKEEPING as a NATIONAL SYSTEM of wealth distribution. Karl M
------------------------------
** 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
******************************
