Cryptography-Digest Digest #927, Volume #13 Sat, 17 Mar 01 15:13:00 EST
Contents:
Re: How to eliminate redondancy? ("Trevor L. Jackson, III")
Re: One-time Pad really unbreakable? ("Trevor L. Jackson, III")
Re: NTRU, continued... ("Daniel Lieman")
Re: Computing power in the world (Paul Schlyter)
Re: Cesar principle (br)
Re: One-time Pad really unbreakable? (Tim Tyler)
Re: One-time Pad really unbreakable? (Tim Tyler)
FIPS 140-1 does not adress eavesdropping (Frank Gerlach)
Re: FIPS 140-2 PRG (Tim Tyler)
Re: What do we mean when we say a cipher is broken? (Was Art of (Mok-Kong Shen)
Re: A literature pointer on anonymity and unobservability (David A Molnar)
Re: on-the-fly encryption (Paul Crowley)
Re: Security of IAPM, alone. (Paul Crowley)
Re: Defining a cryptosystem as "broken" ("Scott Fluhrer")
Re: Factoring RSA ("Michael Brown")
Re: SSL secured servers and TEMPEST (Frank Gerlach)
Re: Cesar principle ("John A. Malley")
----------------------------------------------------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: How to eliminate redondancy?
Date: Sat, 17 Mar 2001 17:17:54 GMT
"Douglas A. Gwyn" wrote:
> "Trevor L. Jackson, III" wrote:
> > The same complaint can be leveled against any lossless transform.
>
> No, compression really does increase the information per bit.
Yes, because of the term "latent". In order to utilize any of the
information that has been compressed one must reconstitute the original,
redundant form. Thus the redundancy is just as latent.
There is no sensible purpose to further teminology dispute.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Date: Sat, 17 Mar 2001 17:20:27 GMT
"Douglas A. Gwyn" wrote:
> Tim Tyler wrote:
> > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > : The impossibility is a straightforward consequence of *extremely*
> > : well verified observed phenomena. One way of looking at it is the
> > : nonzero commutator of conjugate operators. That is as reliable as
> > : it gets (direct consequence of Fourier theory).
> > You seem to be deluded on this issue. It is hubris to believe that you
> > know anywhere near enough to claim that such a thing is impossible.
>
> I'll match my physics credentials against yours any time.
Is this the test you were taught as the foundation of science? Were you
never warned of the dangers of the Aristotelean Fallacy -- research via
consultation of the ancients?
>
>
> > To make such statements about events being impossible, you apparently
> > mis-understand the nature of scientic knowledge - which is inherently
> > uncertain and open to doubt.
>
> I was a scientist before you were even born. Your problem is not
> one of science, it's one of bad philosophy, specifically skepticism,
> which I have commented on before.
And an Ad Hominem attack too. Now that's a good example of modern science in
action.
------------------------------
From: "Daniel Lieman" <[EMAIL PROTECTED]>
Subject: Re: NTRU, continued...
Date: Sat, 17 Mar 2001 17:21:49 GMT
>
> Rot-13 is also faster than ECC and RSA. Given the history of
> knapsack-based systems and their (lack of) security, this remark is
> very relevant.
>
Of course, ROT-13 is a symmetric system (not public-key), with a key of
"13," now isn't it?
I mean, just to be precise here. :)
More seriously, the weaknesses of the broken (or now impractical)
lattice-based schemes do not apply to NTRU. You don't have to take my word
for it - check out the Nguyen-Stern survey of last summer.
Daniel Lieman
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Computing power in the world
Date: 17 Mar 2001 17:34:36 +0100
In article <[EMAIL PROTECTED]>,
those who know me have no need of my name <[EMAIL PROTECTED]> wrote:
> <98vile$2e1$[EMAIL PROTECTED]> divulged:
>
>> But if a program runs in 3
>> months on a 1 MIPS computer, then one would expect it to run in 5
>> minutes on a 26 GIPS computer.
>
> data volume and bandwidth will probably become factors, as i doubt that
> the 26,000 times faster computer will have a corresponding increase in
> memory size or bandwidth (between memory and processor, at least).
Yes of course - I was assuming a CPU bound program, not an I/O bound
program.
So MIPS aren't sufficient -- we also need a measure of memory bandwidth.
What about MB/s ?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: br <[EMAIL PROTECTED]>
Subject: Re: Cesar principle
Date: Sat, 17 Mar 2001 12:34:34 -0400
Why not? Even if people have worked in this area professionally for
decades.
I know that other people are not idiots. But new ideas, everyone may
try.
All inventions when disclosed, professionnal people say " Schit! we did
not thought it!!!"
As newbie, I'm just trying to understand.
I read some articles about "plain text", cryptanalist etc...
How cryptanalist know that for any key k' that the deciphered text (
using DES i.e, not RSA)is english or spanish etc...?
"Douglas A. Gwyn" wrote:
> It's fine to be enthusiastic about a subject that is new to
> you, but it is not good to think that you bring greater
> insight to the subject than the people who have worked in
> this area professionally for decades (and who know about
> centuries of historical development).
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 17 Mar 2001 17:29:33 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> The issue with detecting randomness in fundamental physics is much
:> the same as testing for randomness in crypto. You can use tests to
:> demonstrate that a stream in non-random, but you can never conclude
:> from tests that it is genuinely random.
: I wonder whether it isn't the case that, through the
: act of setting up the concept of 'perfect randomness', we
: have from the very beginning deprived ourselves (by
: definition) the possibility of verifying the presence of
: 'perfect randomness' in any concrete case, since we know,
: among others, that human perceptions of the world (with
: biological capabilities assisted by whatever man-made
: apparatus) can never be perfect, there being not only
: errors but sometimes even illusions [...]
That seems to be a fair statement of the issue.
Not only is there no demonstration of the existence of randomness
or unpredictability today, it appears likely that there will not
ever be a conclusive demonstration of its existence.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 17 Mar 2001 17:43:40 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
[predicting physical phenomena]
:> : The impossibility is a straightforward consequence of *extremely*
:> : well verified observed phenomena. [...]
:>
:> You seem to be deluded on this issue. It is hubris to believe that you
:> know anywhere near enough to claim that such a thing is impossible.
: I'll match my physics credentials against yours any time.
:> To make such statements about events being impossible, you apparently
:> mis-understand the nature of scientic knowledge - which is inherently
:> uncertain and open to doubt.
: I was a scientist before you were even born. Your problem is not
: one of science, it's one of bad philosophy, specifically skepticism,
: which I have commented on before.
I don't see scepticism as a "problem". *Lack* of scepticism is what
I would call a problem.
A lack of scepticism leads to unquestioning acceptance of things - and
to faith. I see scepticism is an important component of the scientific
method. If you are not willing and able to doubt some things, you are
likely to never discover where you are wrong.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: FIPS 140-1 does not adress eavesdropping
Date: Sat, 17 Mar 2001 19:57:26 +0100
In response to the Paul Rubin's reference to the IBM 4758 cryptographic
coprocessor I have read a paper from IBM, describing the FIPS 140-1
validation process:
http://www.research.ibm.com/secure_systems/papers/nfips.pdf
It clearly states that FIPS 140-1 does not even adress power line analysis.
140-1 just has a different threat model: mainly active attacks conducted
physically (e.g. opening the device) or through stimuli (e.g. malicious
commands by application software).
I consider the stimuli-based threat model very important, but it is not
related to the threat model in this discussion threat.
A good discussion of a security issue should always define a threat model,
because discussion will otherwise be virtually useless.
FIPS 140-1 is also a very good sociologic example of how standards can be
misused. When I talked to some colleagues of mine, who know more about
crypto coprocessors, the "FIPS standard" was mentioned, as it happened in
this discussion thread. After looking at 140-1, I conclude that it does not
adress emanations/TEMPEST at all. It seems that even experienced engineers
like to believe into simple truths like "this device is FIPS 140-1
certified - don't worry".
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: FIPS 140-2 PRG
Reply-To: [EMAIL PROTECTED]
Date: Sat, 17 Mar 2001 17:47:53 GMT
John Myre <[EMAIL PROTECTED]> wrote:
: Benjamin Goldberg wrote:
:> If you run a filter on it so that any \r\n sequence is
:> replaced with just a \n, and THEN run your tests, the
:> problem should be fixed.
: Well - but the data will still be wrong (if less so).
: Any "real" \r\n sequences are now gone...
They would likely have been replaced with \r\r\n - and can be expected to
be recovered. A right royal mess, though :-(
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What do we mean when we say a cipher is broken? (Was Art of
Date: Sat, 17 Mar 2001 19:10:58 +0100
John Savard wrote:
>
[snip]
> What hasn't been found is any way, aside from using bigger prime
> numbers, etc., of arbitrarily increasing the strength of public-key
> systems. They can't just be made stronger by piling one complication
> on another. (Conventional cryptosystems can't _quite_ be made stronger
> that easily either; one does have to follow a few simple rules.)
Could you explain why you think it is not proper for
public key systems to increase strength via using larger
keys? (You seem to consider that some other, possibly
more elegant ways, should be used. Or did I misunderstand
you?) Block ciphers do that too, see AES vs. DES. On the
other hand, I suppose different ciphers, whether block
or not, could well have their own specific best ways of
enhancing strengths.
Thanks.
M. K. Shen
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: A literature pointer on anonymity and unobservability
Date: 17 Mar 2001 18:21:30 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> I like to call attention of those interested in the issue
> to a new book:
> H. Federroth (ed), Designing Privacy Enhancing Technologies.
> LNCS 2009, Springer, 2001.
> It contains among others a paper co-authored by David Molnar.
Thanks! Our paper is also available online at
http://www.freehaven.net/papers.html
-David
------------------------------
Subject: Re: on-the-fly encryption
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Sat, 17 Mar 2001 18:40:09 GMT
Neil Couture <[EMAIL PROTECTED]> writes:
> Christian Leber wrote:
>
> > On Wed, 14 Mar 2001 00:55:10 GMT, Neil Couture <[EMAIL PROTECTED]>
> > wrote:
> >
> > >It is always possible to Lock memory pages in memory so that the virtual
> > >memory system does not swap them.
> >
> > No, it is a big problem for user space applications.
> can you explain why or point to an url please?
Some operating systems don't allow this at all. Others require you to
have root privileges, to stop users exhausting the physical memory
with locked pages. GPG is setuid on most systems for this reason.
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Security of IAPM, alone.
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Sat, 17 Mar 2001 18:40:04 GMT
[EMAIL PROTECTED] (David Wagner) writes:
> Great question!
>
> I'm not sure, but I _think_ it might be quite secure,
> if we assume E(k1, .) behaves like a random permutation when
> k1 is fixed. The analogy to the Even-Mansour construction (which
> does have a proof of security) is quite intriguing.
Hmm. The original paper describing this construction:
http://link.springer.de/link/service/journals/00145/bibs/10n3p151.html
does not appear to be available online, but I get lots of hits on Joan
Daemen's paper:
http://www.esat.kuleuven.ac.be/~rijmen/pub91.html
If I ever get the leisure, I'd love to set up a service offering home
pages for crypto academics which took all the hard work out of putting
your papers online...
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Defining a cryptosystem as "broken"
Date: Sat, 17 Mar 2001 11:06:41 -0800
Paul Schlyter <[EMAIL PROTECTED]> wrote in message
news:98vipf$2l8$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
>
> > Dann Corbit <[EMAIL PROTECTED]> wrote in message
> > news:ifws6.141$xh6.657@client...
> >> "br" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> >>> You wrote :
> >>> "I can't say that I really understand how your algorithm works, since
S
> >>> does not change during the iterations. Perhaps I fail to understand
> >>> some
> >>> fundamental piece of the algorithm.
> >>>
> >>> Suppose as sample n=1633
> >>> you have to try gcd( (10^1633)- 1,1633)
> >>> gcd( (10^1632)-1,1633)
> >>> etc... until S= (10^816) - 1
> >>>
> >>> Is it clear?
> >>
> >> What you are trying is clear now.
> >>
> >> Suppose we are trying to factor a mere 56 bit number. How long will
your
> >> algorithm take? For instance, suppose you are wondering about this
> >> number:
> >>
> >> 72057594037927907 = 768467471 x 93767917
> >
> > Actually, by computing everything mod N, a single iteration of the above
is
> > actually feasible. However...
> >
> >> 10^72057594037927907-1 has a lot of bits! Do you have a computer at
your
> >> disposal that can hold this number?
> >
> > Far worse, he's cycling through 10^N-1 to 10^((N+1)/2) - 1. That's
(N-1)/2,
> > and since for a real problem, N will be a 1024 bit number, that's a
*lot* of
> > iterations. Unless you have some good reason that it's likely to find
an
> > answer in the first, say, 2**128 iterations or so, this doesn't look
likely.
>
> He won't even be able to complete the first iteration !!!!!!!!!!
Actually, he will, by using the observation at:
gcd(X, Y) = gcd(X mod Y, Y)
and so, computing (10^N)-1 mod N is quite sufficient, and is practical for
Ns of interest (say, of 1024 bits). Of course, whether it's *useful* to
compute is another matter entirely.
> > Glancing at the math behind it, one would expect it to take O(q)
iterations,
> > where q is the size of the smaller factor. This isn't any better than
trial
> > division.
>
> It's far worse than trial division, since trial division of N doesn't
> require you to compute (10^N)-1 ...... In trial division he'll at least
> be able to perform millions or billions of iteration within a reasonable
> amount of time.
It's somewhat worse than trial division, true, because computing 10^A mod N
is a somewhat more expensive operation than computing N mod A. Of course,
it's only worse by a couple order of magnitudes, and when we consider the
number of iterations either would take for an N of interest, a "couple
orders of magnitudes" is actually surprisingly insignificant.
--
poncho
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: Factoring RSA
Date: Sun, 18 Mar 2001 07:26:26 +1200
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Michael Brown wrote:
> >
>
> > I know I'm getting repetitive, but could someone also look at my
factoring
> > page :P
> >
> > http://odin.prohosting.com/~dakkor/rsa/
>
> Why don't you try it yourself on one of the RSA challenges?
> Another suggestion is that you provide a short succint
> description of the method.
>
> M. K. Shen
The trouble is (as I noted on the site), I am unable to implement the
algorithm on a computer, and I can't really imagine factoring even a 64 bit
composite on paper (boxes alnoe would take up a 5mx5m piece of paper!). As
for 512 bit, well ...
How would you suggest doing the short description. I tried to be as short as
possible on the website (while still showing that it does work), and it
would be nearly impossible to do without some graphics.
Thanks for your response.
---
Michael Brown
Physics is no fun if you disregard friction.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: SSL secured servers and TEMPEST
Date: Sat, 17 Mar 2001 21:04:05 +0100
Paul Rubin wrote:
> Otherwise, it's like saying you can't make a perfectly soundproof
> room: acoustic energy will always travel through the walls and radiate
> into the outside world, or if you surround the room completely by
> vacuum, there still have to be some floor mountings. Does that mean
> there's a way to eavesdrop on conversations happening in the Kremlin
> right now, using microphones where you're sitting thousands of miles
> away? If not, the theoretical issue is irrelevant.
If they were repeating their conversations very synchronously millions of
times, it might in fact be an interesting option to install microphones in
the basement of your moscow embassy. Unfortunately, they will most probably
neither repeat their conversations very often nor do that synchronously.
Indeed, attacking a parrot is easier from a theoretical point of view than
attacking a sane human...
Still, the emanations of Chrustchov might have been some repeating
characteristis - could have been used to track him :-)
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Cesar principle
Date: Sat, 17 Mar 2001 11:48:49 -0800
br wrote:
>
> Why not? Even if people have worked in this area professionally for
> decades.
> I know that other people are not idiots. But new ideas, everyone may
> try.
> All inventions when disclosed, professionnal people say " Schit! we did
> not thought it!!!"
> As newbie, I'm just trying to understand.
> I read some articles about "plain text", cryptanalist etc...
> How cryptanalist know that for any key k' that the deciphered text (
> using DES i.e, not RSA)is english or spanish etc...?
>
The answers to your questions are out in the open, in the references
supplied in the sci.crypt FAQ, in books recommended to you.
Cryptography is thousands of years old; cryptanalysis is slightly
younger :-) See Kahn's book for the most comprehensive history of
cryptography.
Written and spoken languages sport patterns. Some patterns appear more
often than others. The kinds and frequencies of patterns appearing in
the plaintext depend on the language. These are statistical and
structural properties.
For example, on the character (alphabet) level, certain symbols appear
more often than others in the plaintext (frequency of occurrence.)
Certain vowels almost always follow certain consonants, certain symbols
appear in pairs more often than other, certain symbols follow other
symbols more often than others. This can be quantified with contact
frequencies, digraph frequencies, trigraph frequencies, etc.
On the sentence level some languages hold to a strict subject - verb -
object pattern while other languages may be more flexible and allow
subject - verb - object or object - verb - subject or subject - object -
verb. This is the language's syntax.
On the "meaning" level, or context of the message, certain concepts and
thus words appear and others do not. In military traffic expect
coordinates, military unit designations, situation descriptions,
town/city/geographic feature names, officer names, etc. in the
plaintext. In business traffic expect financial terms, monetary
figures, corporate officer names, corporation names, town/city names,
etc. in the plaintext. In personnel traffic expect family names, friend
names, political discussion, food discussions, travel plans, terms
related to shared hobbies, etc. in the plaintext.
(Keep in mind high-level programming languages emulate human languages
with grammars and syntax. The binaries produced at compilation
themselves manifest encoded representations of the statistics and
syntactic structure of the programming language. Therefore the
statistics and structure of a binary can be used to identify what the
binary does/is. )
Ciphers (try to) produce ciphertext to disguise the statistics and
structure of the plaintext. Cryptanalyists (try to) detect the slightest
hint of the statistics and structure of the plaintext leaked into the
ciphertext and leverage this information to crack the cipher.
Cryptanalyists relate the statistics and structure of the ciphertext to
the statistics and structure of the plaintext using knowledge of the
cipher algorithm.
A Caesar substitution algorithm, for example, preserves the syntactic
structure of the plaintext in the ciphertext. It also preserves the
frequencies of occurrence of symbols and contact frequencies of symbols
in the plaintext in the ciphertext. In conjunction with a known message
context, one can also look for probable words. This makes cryptanalysis
somewhat "easy" and straightforward.
Statistics and syntax for most Indo-European languages (like English,
French, Italian, Russian ) can be found in many books on cryptanalysis
(and also on the www.) Statistics and syntax for binaries, images, etc.
may be built up in the same manner as for human languages.
See Gaines' book on classical cipher cryptanalysis for a rapid
introduction to the basic principles of cracking ciphers.
Hope this helps,
John A. Malley
[EMAIL PROTECTED]
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
