Cryptography-Digest Digest #163, Volume #10 Thu, 2 Sep 99 19:13:03 EDT
Contents:
Re: THINK PEOPLE ("Steven Alexander")
Re: n-ary Huffman Template Algorithm (Mok-Kong Shen)
I too need an algorithm :o) (was: Re: I need an algorithm!!!!) (Ranche)
Re: Odp: THINK PEOPLE (John Savard)
Re: THINK PEOPLE (John Savard)
Re: SQ Announcement (David Wagner)
Re: I too need an algorithm :o) (was: Re: I need an algorithm!!!!) (Eric Lee Green)
Re: Vigenere Variant Problem (John Savard)
Re: IDEA- safe? ([EMAIL PROTECTED])
Re: http://www.tmechan.freeserve.co.uk/wincrypt.html ([EMAIL PROTECTED])
Re: I need an algorithm!!!! ([EMAIL PROTECTED])
Re: Deniability (David A Molnar)
http://www.tmechan.freeserve.co.uk/wincrypt.html ("Terry Mechan")
Re: Pincodes (Keith A Monahan)
Re: Schneier/Publsied Algorithms (Bruce Schneier)
Re: I need an algorithm!!!! (David A Molnar)
Public/Private Encryption Win32 Control? ("forq")
Re: SQ Announcement ("Kostadin Bajalcaliev")
----------------------------------------------------------------------------
From: "Steven Alexander" <[EMAIL PROTECTED]>
Subject: Re: THINK PEOPLE
Date: Thu, 2 Sep 1999 12:02:01 -0700
According to the way you described this, they don't need the last 100 bytes
of the message anyway. The information that is different from the other
messages happens to be in the middle. The attackers can of course decrypt
up until the point that one of the blocks in incomplete. How would
Scott1X_U work any differently to prevent this? I don't see why they
couldn't still recover the message. Also, if they already have 2/3
messages, the key, and they're raiding your house, be very afraid.
-steven
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.image.processing,sci.math,alt.comp.compression
Subject: Re: n-ary Huffman Template Algorithm
Date: Thu, 02 Sep 1999 21:18:02 +0200
Alex Vinokur wrote:
>
> > Boolean Valued Rings and Boolean Metric Spaces ,Arch.Math
> 15(1964),3534-363
> >
> > Boolean Distance for Graphs,Discrete Math. 39(1982),123-127 (with
> > I.Tomescu,F.Harary,and U.Peled)
> >
> > Robert A. Melter
I'll look into these. They will be available to me in a week. I'll
see if there are indeed anything related or analogous to your
'non-numerical costs' (at the moment I doubt though that this can be
the case) and come back to this after having looked into them.
> > > Consider for example running the huffman algorithm over a set
> > > consisting of a giraffe, a cow, an orange, and a tulip. Don't assign
> > > weights to these, just assign a decision algorithm that can order
> > > subsets of them. The first pass would determine whether giraffe <
> cow
> > > or cow > tulip and so on, and would pick the two lowest and would
> take
> > > their union. Suppose it was cow and tulip. You then consider
> > > {cow, tulip} compared to {orange}, {giraffe} and {orange, giraffe}
> > > and so on.
If the 'world' of your applications is such that {cow, tulip} may
be compared to {orange} (excepting the fact that the first set has
cardinality 2 and the second 1), you can certainly have a function
named '>' that delivers a boolean value according to certain
semantics that you choose to define. But have you ever really dealt
with (i.e. have experience with) such a 'world'? I have yet never
met with such 'worlds' in my life!
At this point I must wonder what do you actually intend to do with
your (presumably generalized) Huffman encoding scheme in such (in my
humble opinion fancy) 'worlds' at all. A normal Huffman encoding maps
a sequence of symbols to a bit string such that the length of the bit
string is minimal; this is useful in practice. What does your encoding
scheme achieve? Can you explain with some details?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Ranche)
Subject: I too need an algorithm :o) (was: Re: I need an algorithm!!!!)
Date: Thu, 02 Sep 1999 18:40:57 GMT
Reply-To: [EMAIL PROTECTED]
are there any asymmetric ciphers out there that do not increase (double) the length of
the plaintext?
what I basically wanna do is:
* sign some data using a private key, but make sure the signature is as small as
possible (ideally 64bits or max. 128bits)
* distribute the data together with the signature
* verify the authenticity and integrity of the data using the signature and the public
key
I'm definitely not an expert, but as far as I can see:
* all asymmetric algorithms expand the ciphertext at least to the keysize (or to the
double the size of the key)
* symmetric ones are not an option as everybody could sign the data (that's what I'm
trying to prevent :o)
I've looked at HMAC's, MD's, etc. frankly, I'm puzzled even more now.
anybody that could sched some light in this dark and complex matter? PLEASE?
my previous messages were ignore, maybe they were not understood, maybe they were too
simple, maybe nobody knows?
Bruce? Eric L. Green? somebody? anybody?
again, please help me out here,
--Ranche
On Thu, 02 Sep 1999 16:49:48 GMT, Eric Lee Green <[EMAIL PROTECTED]> wrote:
>"Michaël Chassé" wrote:
>> I'm a programmer student and I really need a strong Public/private key
>> system algorithm that is unpatented and that do not use mod... Does someone
>> has a suggestion for me? In case that doesn't exist, an algorith other than
>> Diffie/Hellman or RSA should be appreciated....
>
>Diffie/Hellman is no longer patented (it expired). All public key systems that
>I'm aware of do use mod (or exp_mod). Nobody seems to have a general patent on
>elliptic curve cryptography, but note that all that's happening with these
>systems is that they're using a curve other than the exponential curve used in
>Diffie/Hellman and they do require the mod in order to distribute the results
>of the curve over a field, just as with Diffie/Hellman. ElGamal, a variant of
>Diffie/Hellman, is also available patent-free, I am currently looking at it to
>see if it will suit my own needs. The ciphertext is twice the size of the
>plaintext, so ElGamal would only be suited for transferring the key for a
>symmetric encryption algorithm, and for doing digital signatures. For a good
>private key encryption algorithm, look at any of the AES candidates such as
>Serpent, Twofish, etc. If it's for a commercial product to be exported, you'll
>need to use a less-good algorithm, 56-bit DES.
>
>-Eric Lee Green [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Odp: THINK PEOPLE
Date: Thu, 02 Sep 1999 19:35:08 GMT
"Bartek Z." <[EMAIL PROTECTED]> wrote, in part:
>Geee... I have a strange feeling during reding Mr. SCOTT19... (whatever)
>postings that I'm wasting my precious time. Don't You?
>Shall sci.crypt be available for everyone? Aren't there any filters for such
>boring and annoying people?
He is improving, though. In the past week, he has had a couple of
posts that made sense.
I am saddened that he is making it harder for his valid ideas, when
expressed by others, to be taken seriously: that it's a good idea to
use larger keys than strictly necessary, and large key-dependent
S-boxes are good for safety.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: THINK PEOPLE
Date: Thu, 02 Sep 1999 19:27:21 GMT
David A Molnar <[EMAIL PROTECTED]> wrote, in part:
>John Savard <[EMAIL PROTECTED]> wrote:
>> Anyhow, while OAEP is _related_ to this method and that patent, it
>> doesn't sound like it is the same thing from what I read about it. Is
>> there another patent on OAEP specifically?
>At the IEEE P1363 web site, there's a letter from Bellare and Rogaway
>indicating that they did not patent OAEP :
>http://grouper.ieee.org/groups/1363/letters/BellareRogawayMar98.txtp
>The minutes at at http://grouper.ieee.org/groups/1363/minutes/Jun99.txt
>suggest that OAEP is unpatented, but some uses of it may or may not fall
>under patents held by IBM. The letter at
>http://grouper.ieee.org/groups/1363/letters/IBM.html
>lists some patents, but doesn't seem to address that question directly.
Thanks for the information. I'll try to follow this up, to clear up
this tangle. I would like to sort out the exact patent status of what
seems to be an important and useful technique.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: SQ Announcement
Date: 2 Sep 1999 13:11:40 -0700
Ok, the cipher I attacked was just an example. Thanks for clarifying.
Note that the real SQ1 cipher is very hard to understand, and your
notation and terminology is non-standard. (What's a "variation"?
a "sum register"? what does "Sr<<1"mean? what's "MS"? which values
are keyed? what are the initial values of all variables?)
I recommend you separately post a very concise and concrete description
(20 lines?) in conventional terminology that requires no definitions
from your thesis to understand. (The reader may not learn the rationale
for the design without reading the thesis, but at least it will allow
for analysis.) A simple test: if one can't implement the cipher from
this description alone, it's not concrete enough.
Note also that the example cipher EC-1 that I broke with 2^8 chosen
inputs can also be broken with 2^16 known input/output pairs. (I suggest
you go find this attack, as an exercise.) Thus EC-1 is not secure even
in the mode you suggest (OFB mode). I don't quite understand how your
"Information Lose" theory (?) can prove it secure when it can be broken
so readily; it makes me suspect there may be a mistake in the theory.
Finally, you have no performance analysis. EC-1 was interesting because
it looks like it may be faster than RC4, but SQ1 looks likely to be at
least 2x slower than RC4, which means that SQ1 is much less interesting.
P.S. Apologies if this appears twice. My first try hung; this should
be the same, except for a few typos corrected.
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: I too need an algorithm :o) (was: Re: I need an algorithm!!!!)
Date: Thu, 02 Sep 1999 20:46:26 GMT
Ranche wrote:
>
> are there any asymmetric ciphers out there that do not increase (double) the length
>of the plaintext?
> what I basically wanna do is:
> * sign some data using a private key, but make sure the signature is as small as
>possible (ideally 64bits or max. 128bits)
> * distribute the data together with the signature
> * verify the authenticity and integrity of the data using the signature and the
>public key
>
> I'm definitely not an expert, but as far as I can see:
> * all asymmetric algorithms expand the ciphertext at least to the keysize (or to the
>double the size of the key)
> * symmetric ones are not an option as everybody could sign the data (that's what I'm
>trying to prevent :o)
>
> I've looked at HMAC's, MD's, etc. frankly, I'm puzzled even more now.
> anybody that could sched some light in this dark and complex matter? PLEASE?
> my previous messages were ignore, maybe they were not understood, maybe they were
>too simple, maybe nobody knows?
> Bruce? Eric L. Green? somebody? anybody?
You'd be much better off with Bruce, I'm too rusty on the math to be of much
use and I am definitely not an expert, but anyhow, here's the original version:
Jack:
MD5 the text
encrypt the 128-bit MD5 digest with your private key
Send the text plus the encrypted MD5.
Jill:
Receive the text plus the encrypted MD5
perform our own MD5 on the text
Decrypt the encrypted MD5 with your public key
check to see whether the decrypted MD5 matches
the actual MD5 of the text
Your complaint is that a) an MD5 is 128 bits to begin with, and b) if it's
doubled in size by ElGamal, it is now 256 bits (32 bytes, 64 hexadecimal
characters). Sorry. Anything else you try to do is going to reduce the strength
of the algorithm to the point where it's not worth doing (see Bruce's book page
430).
Anyhow, if your notion was that you would have to transfer 5,000 bytes to
authenticate a 2,500 byte file, no, encrypting the digest is fine. But a digest
has to have a certain length in order to be cryptographically secure, and
there's not much you can do about that.
-Eric Lee Green
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Vigenere Variant Problem
Date: Thu, 02 Sep 1999 19:25:09 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
>[EMAIL PROTECTED] wrote:
>> For the common letters in each alphabet, you could look
>> for variety of contact to sort out the consonants and vowels.
>Unfortunately, that doesn't work as well in such systems
>as it does for monoalphabetic substitutions.
>If the encipherment is known (or likely) to use fixed
>alphabets at different slides, then symmetry of position
>is the best available technique.
I thought that symmetry of position, while a very powerful technique,
is only applicable once one has a number of equivalents: thus, the
technique I described, which is useful at the very start to make the
first entry into a ciphertext, doesn't conflict with symmetry of
position: however useful symmetry of position may be later, this
technique or some other technique applicable to getting started will
still be necessary.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: IDEA- safe?
Date: Thu, 02 Sep 1999 16:30:10 -0400
Jim Butcher wrote:
> has anyone heard of a successful cryptanalysis of the IDEA algorithm? 128
> bit key, 64 bit block size
> for that matter Blowfish 256 bit key?
As I have learned in the past few months on this newsgroup...as long as the
key size is of sufficiant length (lets say 64 bits+), the keysize is really
irrelivant. There are other types of attacks on algorithms than brute force.
As for your question, there are some cryptanalysis on IDEA with reduced
rounds, however (as far as I know) there is no break on the full IDEA
algorithm (although a few weak keys). Blowfish is just as secure if not
more. As long as you stick with the tried and true algorithms, you should be
ok. Blowfish, IDEA, CAST-128, 3DES, RC4, RC5, or any of the AES candidates.
The security of an algorithm is not really a question as long as you use a
good algorithm...your main problem will be implementing these algorithms
securly.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: http://www.tmechan.freeserve.co.uk/wincrypt.html
Date: Thu, 02 Sep 1999 21:21:40 GMT
Terry Mechan <[EMAIL PROTECTED]> wrote:
: Wincrypt is practically unbreakable and now works on Win NT as well as 95/98
: Download from
: http://www.tmechan.freeserve.co.uk/wincrypt.html
This is the _source_, right? If not, nobody with a clue will
give it a second (or even first) thought.
--
Mike Andrews
Tired old sysadmin
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: I need an algorithm!!!!
Date: Thu, 02 Sep 1999 20:45:56 GMT
Michaël Chassé wrote:
> I really need a strong Public/private key
> system algorithm that is unpatented and
> that do not use mod... Does someone
> has a suggestion for me? In case that doesn't
> exist, an algorith other than
> Diffie/Hellman or RSA should be appreciated....
I'm not sure about the patent status, but
I suppose McEliece arguably qualifies on the
encryption side. For signatures you could
use a zero knowledge proof based scheme, with
some underlying problem that doesn't use mod,
such as Hamiltonian Circuit.
But are you sure that's what you want? How did
the "no mod" requirement come about?
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Deniability
Date: 2 Sep 1999 20:55:47 GMT
Gideon, S. <[EMAIL PROTECTED]> wrote:
> Anyone knows of publications regarding 'deniability' other than the IBM
> article in Crypto '97?
There is an extended abstract on "Deniable Authentication" by Michael
Rabin and Yonatan Aumann in Crypto '98 :
"Authentication, Enhanced Security, and Error Correcting Codes" M. Rabin
and Y Aumann, CRYPTO '98 p.301 LNCS 1462
The talk given at CRYPTO '98 didn't correspond to this abstract, but
slides are available
http://www.iacr.org/publications/dl/rabin98/rabin98.html
and a video of another talk is at
http://www.cs.cityu.edu.hk/dept/video.html
I've seen a reference to a paper in PragoCrypt '96 on "Plausible
Deniability" by Donald Beaver.
You may also want to look at "designated verifier proofs", which make it
impossible for the recipient to repeat the proof to anyone else. Useful if
you need to convince some party of something, but deny it to everyone else
later.
"Designated Verifier Proofs and their Applications" M. Jakobsson, K. Sako,
R. Impagliazzo
http://www.bell-labs.com/user/markusj/dvp.ps
-David
------------------------------
From: "Terry Mechan" <[EMAIL PROTECTED]>
Subject: http://www.tmechan.freeserve.co.uk/wincrypt.html
Date: Thu, 2 Sep 1999 22:03:55 +0100
Wincrypt is practically unbreakable and now works on Win NT as well as 95/98
Download from
http://www.tmechan.freeserve.co.uk/wincrypt.html
--
Regards
TJM
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: Pincodes
Date: 2 Sep 1999 22:19:18 GMT
Actually,
A few years back a friend and I were using a card reader and examining some
card specifications on VISA/MC which closely matched the ATM card format
that were in use at the time.
Everything was stored in plaintext, including the NAME, the account number,
and even the PIN. I read the specification released from the standards
authority which read something to the effect, "The PIN field should be
encrypted, however this is not a requirement".
In fact, we checked about 30 different cards over a period, and found that
a very few actually encrypted the PINs. This may have changed since then,
but it doesn't give me a warm and fuzy feeling.
Keep in mind there is a difference between a ATM account number and your
actual account number - and now one ATM account number can be associated
with multiple <real> account numbers. "Back in the day", only one number
could be associated.
Incidentally, the account number printed on ATM cards (and written on the
mag stripe) is related to your account number and local banks used to make
an association between the two numbers on a bank statement, but they stopped
doing that because supposedly "it was a security" problem.
I had alot of fun playing around with that at the time - and can remember
they had 3 tracks, 2 of the same size, and 1 of a small size. I wanna
say 128 bytes, 79 bytes, and 128 bytes. The last track was a compressed
version of the first two used for redundancy purposes..
Keith
John Savard ([EMAIL PROTECTED]) wrote:
: "JuDa$" <[EMAIL PROTECTED]> wrote, in part:
: >I need help to break pincodes, can somebody help me please ?
: a) Why do you think that anyone would want to help you steal money
: from people's bank accounts, and
: b) what makes you think there is a code to break: surely it would be
: safer to store a hash of the PIN number at a central site than on the
: magnetic stripe of the card.
: Of course, if the bank absolutely insists on letting people withdraw
: some small sum of money when the lines are down, they could still
: protect against hackers as follows:
: 1) Record only a hash of the PIN on the card, not the PIN itself.
: 2) Encrypt that hash - with one of a thousand or more keys, stored on
: a hard disk at each bank machine - with an indication of which key to
: use placed on the card.
: That ought to protect against a dictionary-search attack.
: John Savard ( teneerf<- )
: http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Schneier/Publsied Algorithms
Date: Thu, 02 Sep 1999 22:09:08 GMT
On Wed, 01 Sep 1999 16:25:20 GMT, [EMAIL PROTECTED] wrote:
>What is your problem DS? The question was how can bugs be in Bruce's
>source code printed in the book. Yes I did see the embedded about TEST
>VECTORS, but this was not the primary question. Why don't you re-read
>the post and look at the very first question "How is it posible that
>some of your published algorithms...2fish have bugs in your source
>code?" and the very last question "But please Bruce...explain to us How
>is it that there are bugs in your own published algorithms..."
>
>I am sure this is a waste of time asking you this since you have such
>an "I am better than everyone attitude" and will probably now start to
>personnaly attack me, even though you have no idea who I am.
There are Twofish test vectors on the Twofish website; they have been
there for over a year now. All Twofish implementations that I have
been generate those test vectors.
The Twofish test vectors are also in the Twofish book, and are on the
NIST CD-ROM.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: I need an algorithm!!!!
Date: 2 Sep 1999 22:29:51 GMT
Steven Alexander <[EMAIL PROTECTED]> wrote:
> If you're not so mathematically inclined, you could implement a knapsack
> algorithm as the public key side of your system. Be warned that knapsacks
> are not secure.
More precisely, the original Merkle-Hellman knapsack (which is what you
get out of Applied Cryptography) can be broken in minutes by an
Apple II. The Chor-Rivest knapsack was reported broken in 15 minutes on
"an old laptop." Those are the only two reports I know off the top of my
head.
------------------------------
From: "forq" <[EMAIL PROTECTED]>
Subject: Public/Private Encryption Win32 Control?
Date: Thu, 2 Sep 1999 18:26:31 -0400
I'm looking for a public/private encryption control for use in Windows in
VB/Access/etc. Not too concerned with the algorithm, just need to be able
to generate key pairs, and encrypt/decrypt data. If one doesn't exist,
maybe somebody might think about doing it, as it would be useful. I would do
it myself, but my kung-fu is not nearly as skillful as I'd like to think.
What do I need this for? I'd like to be able to encrypt data as it's
entered into a database from the web, and only be able to decrypt it if I
have the private key available (stored on a floppy). To make sure that the
data remains safe even if the web server is compromised (physically or over
the network)
The webserver will have SSL sessions, and the data is encrypted into the
database using said control and a blowfish cipher. There is already a
blowfish .dll available written by Roger Carbol.
I suppose I could make external calls to PGP, but I'd rather not, as it
isn't nearly as elegant, and I'm not even sure I can do that from .ASP
pages. Why am I using NT & ASP? Well, that isn't my choice...
Any ideas or suggestions on how I might accomplish these goals?
Forq <[EMAIL PROTECTED]>
------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Re: SQ Announcement
Date: Fri, 3 Sep 1999 00:28:41 +0200
OK
I am will rewrite so parts that look confuse.
MS is inner word lenght, is it permutation 0..255, 0..512 etc
Variation is K[0..n] where K[i]=[0..n] any value between 0 and MS
sum register is the "input" to the generator, Sr=SUM(O[i]) i=0 to n-1 where
O[i] is the value produced by the generatoe in its i-th itteration
Sr<<1 (should be Sr<<<1) this is standard notation
Permutation, Variation and Sr are keyed variables.
Information Lose theory is:
If we need more information than the output carry about them inner state of
the generator in order to reconstruct the inner state then the Cipher is
"secure".
Or simply
In order to recover the inner state we need more information than a the
output sequence carry.
SQ1 using my Celeron 300 need 1.3 sec to genrate 1MB, I have not test ASM
implementation.
If SQ1 is not interesting about the speed try EC-6.
My point is not to design faster algorithm, All thing is how to design
secure Stream cipher, if theory is defined and design are made they can be
optimized.
>I recommend you separately post a very concise and concrete description
>(20 lines?) in conventional terminology that requires no definitions
>from your thesis to understand. (The reader may not learn the rationale
>for the design without reading the thesis, but at least it will allow
>for analysis.) A simple test: if one can't implement the cipher from
>this description alone, it's not concrete enough.
>
>Note also that the example cipher EC-1 that I broke with 2^8 chosen
>inputs can also be broken with 2^16 known input/output pairs. (I suggest
>you go find this attack, as an exercise.) Thus EC-1 is not secure even
>in the mode you suggest (OFB mode). I don't quite understand how your
>"Information Lose" theory (?) can prove it secure when it can be broken
>so readily; it makes me suspect there may be a mistake in the theory.
>
>Finally, you have no performance analysis. EC-1 was interesting because
>it looks like it may be faster than RC4, but SQ1 looks likely to be at
>least 2x slower than RC4, which means that SQ1 is much less interesting.
>
>
>
>P.S. Apologies if this appears twice. My first try hung; this should
>be the same, except for a few typos corrected.
------------------------------
** 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
******************************
