Cryptography-Digest Digest #823, Volume #9 Fri, 2 Jul 99 15:13:03 EDT
Contents:
Re: How do you make RSA symmetrical? (David A Molnar)
Re: A few questions on RSA encryption (Francois Grieu)
Jim's Published Papers on Security & Crypto ("Big Malc")
Re: Quantum Computers ([EMAIL PROTECTED])
Re: Can Anyone Help Me Crack A Simple Code? (Medical Electronics Lab)
Re: How do you make RSA symmetrical? (Patrick Juola)
Re: Decorelation again (Medical Electronics Lab)
Re: The One-Time Pad Paradox (Jim Gillogly)
Re: Quantum Computers (John Curtis)
Re: I don't trust my sysadmin ([EMAIL PROTECTED])
Re: OTP is it really ugly to use or not? ("Dr.Gunter Abend")
Re: Quantum Computers ([EMAIL PROTECTED])
Re: Quantum Computers (Anti-Spam)
Re: The One-Time Pad Paradox (Mok-Kong Shen)
Re: Quantum Computers (Anti-Spam)
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: How do you make RSA symmetrical?
Date: 2 Jul 1999 17:42:29 GMT
[EMAIL PROTECTED] wrote:
> You cannot remove 0 bits from the ciphertext if you do you will not be
> able to decrypt it (I believe this is the halting problem?). You will
Not all 0s, just the leading ones.
0000000000000000011011 is the same as 11011 in the sense that
they both have the same numerical value, but one has a lot of
0s in front and the other doesn't.
Why do you think this is the halting problem ?
> have to store the length with it so you might as well just store the
> zeroes...
The length could be quite short to store - say 2 = "10", while
if you're referring to _all_ the zeroes and their positions,
that might be large. My point is that it's plausible that
one might have enough storage for the length, but not for
the zeroes.
forgetting for the moment that the number is a little
ambiguous without the zeroes in it. :-)
-David Molnar
------------------------------
From: [EMAIL PROTECTED] (Francois Grieu)
Subject: Re: A few questions on RSA encryption
Date: Fri, 02 Jul 1999 20:12:28 +0200
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> Let's say you're encrypting 20 bits with a 512 or 1024 bit key.
> Is the small size of the plaintext relevant ? Will the encrypted
> message be easier to crack than, say, an entire document encoded
> by the same RSA key ?
The evil is in the details, as usual in crypto; the answer can be either
> Very much so. [Patrick Juola]
> No. [Bob Silverman]
Straight RSA encryption, as simplified in "take message and raise it to
the power e mod n" is indeed trivialy broken by trying all possible
messages. This message exhaustion problem is not specific to RSA.
Better though encryption methods, as in "left pad message with 128 randomly
choosen bits, then raise it to the power e mod n" will resit this attack.
Well thought programs do this.
Francois Grieu
------------------------------
From: "Big Malc" <[EMAIL PROTECTED]>
Subject: Jim's Published Papers on Security & Crypto
Date: Fri, 02 Jul 1999 18:06:31 GMT
check out the Papers section at:
http://home.freeuk.net/jpress
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Quantum Computers
Date: 2 Jul 1999 14:06:44 -0400
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> In a Quantum World, Quantum Crypto is unconditionaly secure.
> In fact, Quantum Crypto is already publicaly implemented
> (Los Alamos and other places). It is much easier to implement
> than a Quantum Computer (it's not the same thing at all either).
Secure courier: One who can take a message and transfer it to the receiver
without it being intercepted.
Reliable courier: One who can take a message, take to the receiver but he
may be intercepted ... if he is, however, he will tell
you he was intercepted.
One can use the Heisenberg Uncertainty principle to implement a reliable
courier (e.g. One random sequence: x,y,y,y,x,x,...
The data being transferred: 0,1,1,0,1,0
Electrons are sent with the spin on the axis specified by the random
sequence determined by the data being sent.
An electron is sent (e.g. the first). AFTER the recipient has received it
(and broadcasts that info to the sender) the sender indicates on which
axis to measure the spin.
An interceptor would have to make the measurement before knowing what to
measure, and as the x,y spins are non-commuting observables, doing so
would corrupt the data. Corruption (found by an included checksum in the
data, say) would indicate that it had been intercepted.
No cryptography involved at all. Anyone can intercept and when the
indication is sent as to which axes are to be used to recover the data,
the interceptor can look at his intercepted data and realize he has gotten
(on average) half the data.
Of course, a reliable courier can be used in a cryptographic protocol
(send a key, not a message, using a reliable courier ... if it was
intercepted, don't use it ... but send another key: sending a key for a
OTP, which is secure, gives a secure protocol -- as does using any other
reliable courier, whether based on QM or not) but is not itself
cryptographic.
I suppose it is "sexier" to ask for funding for:
Unbreakable Secure Encryption using advanced Quantum Physics
instead of:
Implementing a reliable courier with the Heisenberg Uncertainty Principle
(and will get more funding!)
but Quantum Cryptography (at least the Quantum part) isn't cryptography
but a tool that is quite useful in implementing a cryptographic protocol
(secure key transfer rather than cryptography itself) and could be used to
send plain-text (in that case, where's the cryptography?).
Is that what you mean (as most do) by Quantum Cryptography?
(and I know, "practical" implementations use photons and polarization
rather than electron spins, but when I think of non-commuting
observables, my first thought is of electron spins ... it requires a
transmission channel with properties that can be exploited for the Heisenberg
Uncertainty principle, making it rather difficult to implement on a
system where messages have to transit several different media/networks)
The reason I am posting is that the term "Quantum Cryptography" always
irks me since there is no "Quantum" stuff used in the encryption algorithm
but rather in the key exchange/protocol (where's the quantum in the
encryption?). Of course it sounds "sexier" to say "Quantum Cryptography"
rather than "reliable courier". I just hate that Quantum Cryptography
doesn't use any "Quantum" in the cryptography (encryption: which may be a
one time pad or a symmetric cipher or whatever) and that any other
"reliable courier" is an implementation of so-called Quantum Cryptography
even if the reliable courier has nothing to do with Quantum mechanics.
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Can Anyone Help Me Crack A Simple Code?
Date: Fri, 02 Jul 1999 12:22:45 -0500
mercury wrote:
> Some people are interested in studying
> the the major "unbreakable" codes, some are interested
> in the political issues of cryptography, some are interested
> in the history of codes during war ... I'm interested in
> learning how to break "simple" codes and what makes
> a weak algorithm weak. This is not a money issue.
>
> It costs me nothing to get codes, but I can not get large
> amounts of them. It costs me nothing to try codes out if
> I think I am on to something. It will cost me plenty if I
> break a Black Box trying to solder wires under the key pad.
> (I have not completely ruled this option out, but I would
> rather avoid it if possible)
It sounds like non-destructive testing isn't getting very far.
If it's possible to get into the keypad, or even into the
interface between the black box and computer, you can set
up the computer to at least record responses from specific
inputs. Since you can forward date it to DEC'99, you should be
able to pre date it for a while and compare many dates to the
same code samples. To start with, you can pound on the keypad
by hand, but I still think hooking up a computer to run thru
lots of codes will get you further faster.
Is this black box patented? If so, you should be able to find
the algorithm at the IBM patent site. The algorithm isn't
secret, only the keys are. That should help you a lot, I'd think.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: How do you make RSA symmetrical?
Date: 2 Jul 1999 13:33:42 -0400
In article <7lirvj$h7q$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>
>> Cyphertext length in RSA is always going to be approximately the
>length
>> of N-- it will be very rare for it to be shorter by an appreciable
>number
>> of bits. ( Another way of thinking about it is say I use an X bit
>block
>> cypher on my data my output will pretty much always be X bits long--
>if I
>> make a policy of discarding leading 0's there will be occasional
>shorter
>> cyphertexts, but the will also be rare). Thinking of it this way RSA
>has
>> a block size of log2(N) bits.
>
>You cannot remove 0 bits from the ciphertext if you do you will not be
>able to decrypt it (I believe this is the halting problem?). You will
>have to store the length with it so you might as well just store the
>zeroes...
Sure you can; you know how many digits there are supposed to be, and
you only delete the *leading* zeros, just as when I write a check,
I don't write that it's for zero million, zero thousand, zero hundred
fourteen dollars.
It just doesn't buy you anything in the long run, because numbers with
a worthwhile number of leading zeros are so rare.
-kitten
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Decorelation again
Date: Fri, 02 Jul 1999 13:05:03 -0500
[EMAIL PROTECTED] wrote:
>
> If the module is provably secure to linear and diff types attacks
> then...
>
> a) what are the known weaknesses (i.e expansion variables...)
>
> b) would it not make a good building tool for hash functions?
Check out the NIST AES papers and attacks.
You should find some answers to these questions
there.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Fri, 02 Jul 1999 11:42:41 -0700
Dr.Gunter Abend wrote:
> The proposed technique of appending some garbage at the beginning
> of the plaintext in case of an intelligible ciphertext surely
> weakens the keystring, no matter if it is done automatically
> or by hand. You refused to quantify this loss of strength.
Actually, a quantification did just occur to me. Your
algorithm could be something like "If the ciphertext is all
ASCII and says something coherent, skip the first OTP bit and
try again." The cryptanalyst will know or guess that you've
done this, and immediately has one bit of known data from
every byte -- the low bit, which is where the 8th bit got
shifted from the first try. It's not much less likely that
you would have had to do this shift eight times, which would
give away the complete plaintext. So doing this shift once
would give away 1/8 of the bits, enough to do some
useful things like place longish cribs and eliminate
impossible messages; a few more would be enough to <really>
know the whole plaintext. So you can't just shift. You
would be safer in saying "Well, this pad didn't work out for
my N-byte message. Skip the whole damned thing and start
over N bytes down. You're now back in the dicey business of
pre-qualifying pads because of perceived patterns, but that's
a much lower risk than giving away 1/8 of your message.
And, of course, you still wouldn't ever actually be in that
position, for the same reason that the oxygen in your office
didn't leap into the opposite corner a moment ago.
--
Jim Gillogly
9 Afterlithe S.R. 1999, 18:28
12.19.6.5.17, 8 Caban 5 Tzec, Ninth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (John Curtis)
Subject: Re: Quantum Computers
Date: 2 Jul 1999 18:09:09 GMT
In article <7lgi06$p9r$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Patrick Juola)
writes:
>>>
>>> There is recently published in the Springer Lecture Notes a
>>proceedings
>>> of a conference on quantum computing. It should reflect the state
>>> of the art quite well.
>>
>>In the public sector?
>
>On what basis do you assert a difference between the public and
>secret sectors? The public sector is better funded....
>
> -kitten
Why do you believe that public sector research on
quantum computing is better funded than secret sector
research on the same topic?
I'm not disagreeing, I am just interested in the source
of your knowledge.
ciao,
jcurtis
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: I don't trust my sysadmin
Date: Fri, 02 Jul 1999 17:53:22 GMT
In article <[EMAIL PROTECTED]>,
"David N. Murray" <[EMAIL PROTECTED]> wrote:
> Greetings, all:
>
> I'm in search of a protocol to implement the following scenario:
>
> I have an automated task that connects to a database.
> The database requires a username/password combination.
> I need to store the username/password with the automated task.
> My system administrator (who needs to be able to read the
> automated task to do backups) is not authorized to access
> the database. (Protecting the database is not my concern.
> Just protecting the automated login.)
Hash the password and store the hash on the protected side. So you
type the password on Machine A, it gets hashed goes thru the middle man
and compared with the HASH on Machine B.
Unless the sysadmin can get access to stuff you type (which I doubt
they can) they will not be able to tell what the password was.
However now you get into hash spoofing. You could try using RSA to
encrypt the hash (so only the server can decrypt...) or you could do a
password list (say 100 passwords) and each time you login you use a new
one. You would have to have secure access to the machine to upload new
passwords though....
> How do I store the uname/password to make it as difficult as
> possible for the sysadmin to retrieve? My basic assumption
> is that if I encrypt the password, I have to decrypt it to
> present it to the DBMS. That means that the key, algorithm,
> and ciphertext are all in the same place, right? Isn't that
> a Bad Thing?
If you only store the HASH no highly useable information is present.
If the sysadmin can spoof the HASH (to the server or database app
whichever...) then they DO NOT need to know the password.
Generally I would use a PKC to access the remote server so only that
server can decrypt the msg (in this case HASH). If spoofing is not
possible (i.e the sysadmin cannot fake sending the HASH, ?) then use
the HASH method because by just observing the HASH the sysadmin will
not know the password...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Dr.Gunter Abend" <[EMAIL PROTECTED]>
Subject: Re: OTP is it really ugly to use or not?
Date: Fri, 02 Jul 1999 20:51:11 +0200
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen wrote:
> Given a keystream K and n plausible messages M_1, M_2, .... M_n
> and one real message M_r. If we XOR all of them together to form
> the ciphertext C, what chance has the analyst to find M_r, even
> if K is not ideally random as required by the definition of OTP?
How does the addressee decrypt this ciphertext? The hardest
problem of OTP is the secure transfer of the keystring. If you
can do that in advance, over a slow but secure channel, then it
might work. Do you transmit K + M1...Mn in advance? How do you
solve the problem of individual lengths of the real messages?
The best I can see is to use a prefabricated correspondence of
successive messages M_1 .. M_n plus a OTP of about the same
total size, all put onto two CDs. Each real message is XORed
with a part of the OTP and with the next M_j.
As long as the adversary doesn't find the CDs, you can present
him a fake OTP-CD which decodes all j ciphertexts to M_1 .. M_j.
Of course, the double XORing must be done *manually*, e.g. by
running the same XOR-program twice (CD1, CD2, same offset).
Would that be a perfect denyable cryptosystem? It is restricted
to messages of preselected length -- you can send shorter ones
by padding them with garbage. The hardest problem would be to
forge a mildly compromising conversation M1 .. Mn -- beforehand.
All traces of the production of the M_j and the calculation
of the offsets must be carefully removed from your computer.
Ciao, Gunter
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Quantum Computers
Date: Fri, 02 Jul 1999 17:47:41 GMT
> Do you have any proof that your algorithm is better? I've never even
> seen an analysis of your algorithm.
Want to know why? Because his cipher is the best. Who cares. It's
slow and requires a lot of ram. It doesn't even resemble a block
cipher and it isn't a stream cipher. No what this suggests to me,
*snake oil*.
Personally I trust PGP to get DH and CAST right and I trust DH and
CAST. For my private email it does just fine. Why switch? Why use
his bad algorithm? (oh yeah, his is much better. Hmm he has never
proved that. but he claims ALL AES ciphers are weak too :) ).
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Fri, 02 Jul 1999 10:27:16 -0700
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Ed Yang wrote:
>
>
> I looked at this book for 10 minutes without buying it.
> My impression of the book is that it reveals that Quantum
> Computing (QC) is in very early stages. The book does not tell you
> how to make anything that is useful with current hardware.
> The chapters discuss plans and conjectures about possible
> future developments. This is an embrionic technology which may
> fail to become practical. Error correction discussions in the book
> reveal how flawed the plans are, how impractical the techniques
> are in 1999. The book is a disapointment for those who wish
> for QC to be a success today. It has state-of-the-art discussions
> of QC, and the state is shaky and undeveloped.
> --
> Oxygen : Love It Or Leave It !
The book in question, "Explorations in Quantum Computing" by Colin P.
Williams and Scott H. Clearwater, instructs us in the physics and
information theory foundation for QC. That's the first step to practical
engineering of a QC. Research I've followed to date on the WWW
struggles with the transition from concept and physics to actual
engineered implementation. The book addresses the information science
aspects of QC - and without that understanding it is impossible to
successfully engineer such a device. Physics sets the bounds to the
problem - it helps define the problem that the implementation tries to
solve. If we know what the error sources are (such as decoherence
relaxation times and the physical rmechanisms responsible for example)
we can steer our implementations away from some solution paths and into
other solution paths that use genuine hardware, cryogenics, etc. That is
engineering.
Understanding the information theory backing a cryptosystem or a
cryptanalysis system is essential. If we conjecture an attacker will use
such a system to crack ciphertext produced by another system, knowledge
of what that cryptanalysis can theoreticlly achieve helps us better
defend our cryptosystem or decide when to abandon it altogether.
If we are looking for a engineering cookbook - a "How to Build a QC"
ready-to-go blueprint - we won't find it now or anytime soon. The QC
situation is similar to the early days of our current electronic
computers. 1930s and 1940s R&D engineered radically different
solutions. The "reconfigurable" computer "concept" eventually settled
on the von Neumann architecture (1940s), an information-theory approach
based on Turing's research and exploration into the general theory and
provable behaviors/limits of computation (Turing Machines, 1930s). This
architecture took physical form in relays, then tubes, then discrete
transistors and finally complex transistor packages appeared. QC R&D
focuses on the information-theoretic architecture (which is actually
very very limited in the kinds of problems it can solve - this was an
amazing realization!) That pins down the current technologies that
enable that architecture and points us in the direction of promising
technologies for future engineering solutions.
Most people overlook the theory that is the foundation of the physical
computer. The von Neumann architecture tightly constrained and
directled the evolution of technolgies to support the von Neumann
architecture. We will see the same with the QC.
That's why I recommend this book. QC comes across as a very very
powerful searchlight that can only point in a few select directions.
Only a handful of algorithms work on a QC, but when they work - watch
out. If we use cryptosystems "orthogonal" or independent of those
QC-acceptable algorithms attacks, then our cryptosystems are immune.
QCs pose no threat if we are careful.
That is valuable information.
[EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Fri, 02 Jul 1999 21:02:20 +0200
Coen Visser wrote:
>
> > If the statistics of all M's differ much, that means that in the
> > best situation the analyst could recover all M's (each completely).
> > Now how does he, having achieved this, decide which is the real
> > message?
>
> Theoretically, I don't know. It is an interesting idea to hide
> fake data in your encryption. But practically
> speaking you can count on the adversary to select the most
> usefull information. Consider an encrypted file which, after being
> cracked, gives us 10 chapters of the Koran and 1 chapter describing
> the design of an experimental nuclear warhead. What would be the
> secret? The strength of your scheme lies in the strength of the OTP.
> You just need OTP (+) M_fake (+) M_secret. Adding more than 1 M_fake
> doesn't make things much safer. Improving the OTP does.
I can use M_i such that they may all plausibly be the real message.
How large is the chance that the analyst be able to obtain all the
n+1 messages completely, if n is, say, of the order of 10, instead
of getting probably none, even if the keystream is quite a bit less
perfect than an ideal OTP (e.g. from a PRNG)? I wonder if anyone has
considered this problem realistically instead of basing arguments on
words which cannot be quantified.
M. K. Shen
------------------------------
Date: Fri, 02 Jul 1999 11:32:36 -0700
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Ed Yang wrote:
>
> I looked at this book for 10 minutes without buying it.
> My impression of the book is that it reveals that Quantum
> Computing (QC) is in very early stages. The book does not tell you
> how to make anything that is useful with current hardware.
> The chapters discuss plans and conjectures about possible
> future developments. This is an embrionic technology which may
> fail to become practical. Error correction discussions in the book
> reveal how flawed the plans are, how impractical the techniques
> are in 1999. The book is a disapointment for those who wish
> for QC to be a success today. It has state-of-the-art discussions
> of QC, and the state is shaky and undeveloped.
The book in question, "Explorations in Quantum Computing" by Colin P.
Williams and Scott H. Clearwater provides a solid introduction into the
physics and information theory behind QC. Understanding the physics and
information theory supporting the QC concept helps us set boundaries to
the QC engineering problem. The physics and information theory behind
QC tells us what behaviors and characteristics must be present in any
physical devices we intend to use to build a QC. We can rule out some
technologies and delve into others. This is engineering.
The path and direction of QC R&D is similar to that followed by
electronic computers. Early computer R&D focused on a varitey of
solutions to specific problems and ways to automate those solutions
(late 1930s, 1940s.) The von Neumann architecture, a concept formed in
the 1940s (?), served as the information theoretical foundation of all
subsequent physical computers. That concept shaped and directed the
path of computer engineering. Relays gave way to tubes, which yielded
to discrete transistors and finally complex assemblies of transistors in
small packages. Yet all along the way we relied on the von Neumann
architecture to guide our engineering attempts. The von Neumann
architecture follows from information theory work by Turning (Turing
machines, decidability, computatbility - 1930s, 1940s) and Shannon
(information carrying capacity of channels with and without memory,
1940s.)
A good understanding of the information theory behind any new
cryptosystem or crytanalysis system is necessary to gauge the security
of the new cryptosystem or the potential damage an attacker could do to
our current cryptosystems with the new cryptanalysis system. That's what
this book offers us. If we are looking for a cook book - a "How to
Build a QC in 26 Days" - then we will wait a long, long time.
Meanwhile, we are not preparing for the threats/joys QC offers.
There are only a handful of algorithms that can theoretically run on a
QC - that's an amazing revelation! QC is a very very bright spotlight
that points in just a few directions. If we use cryptosystems
"orthogonal" to or independent of the components the QC algorithms can
analyize, then we are still (proveably) secure.
That is valuable information.
That's why I recommend this book to any and all curious about QC. Get
to know its information theoretic limits.
Forewarned is forearmed.
[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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
