Cryptography-Digest Digest #423, Volume #10 Sun, 17 Oct 99 17:13:04 EDT
Contents:
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Jerry
Coffin)
Strengthening passwords against dictionary attacks ([EMAIL PROTECTED])
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Terry
Ritter)
Re: The Quad. in RC6 ([EMAIL PROTECTED])
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Terry
Ritter)
Re: Character Frequencies Tables for languages other than English (Mok-Kong Shen)
Re: Biometric Keys are Possible (Mok-Kong Shen)
Re: accurate decryption (Mok-Kong Shen)
Re: accurate decryption (Anthony Stephen Szopa)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Sun, 17 Oct 1999 10:19:20 -0600
In article <7ub0nt$9ep$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> In article <[EMAIL PROTECTED]>,
> Jerry Coffin <[EMAIL PROTECTED]> wrote:
> > I doubt it takes more than 100 lines of code on average to implement
> > the AES finalist algorithms.
>
> In software, it's easy; in hardware, it's a huge added cost.
The TwoFish FPGA implementation uses an equivalent of roughly 28,000
gates. If we assume that's about average for the five finalists (RC-6
could probably be smaller, Serpent likely larger, ...) and that we
can't share any noticeable amount of logic between implementations,
that means implementing all five should take around 150,000 gates
(rounding up). Adding in even some fairly complex logic to handle
selecting between them, possibly a bit of caching, etc., we should be
able to fit all five into, say, 200,000 gates.
In a modern .18 micron fabrication, 200,000 gates should fit in less
than 4.5 square millimeters, which can be fabricated in reasonable
quantities at a cost of approximately one dollar per chip. That
ignores things like packaging costs and such, but these should be
_close_ to constant -- we'd only need a few extra pins to deal with
selecting the algorithm(s) to use.
Of course, in a real chip, you'd probably want to build in something
like a PCI interface, so the chip would be easy to hook up to existing
peripherals. That'll add on around 4 to 5 square millimeters or so by
itself -- I.e. close to the area needed to implement the encryption
algorithms. This would increase the cost to around two dollars per
chip.
Unless the product involved was being built in relatively limited
quantities, the cost of including all five algorithms would NOT be
terribly high. When dealing with limited quantities, unles extremely
high performance was needed, it would probably be easier to simply
embed a processor core and put the algorithms in ROM.
Just for example, the MicroSPARC IIep is available under Sun's
Community Source License, making it easy for even a very poorly
financed startup company (e.g. a college kid in his dorm room) to
download and start a design. It uses around 208,000 gates for the
core and licenses for 3% of the selling price of the chip into which
it's embedded IIRC. You could probably even reduce their estimated
gate count somewhat, because in this situation you probably wouldn't
need some things they normally include such as PCI and S-bus.
In the end, I just don't buy the idea that the cost of including all
five in a hardware design would be prohibitive unless the quantity
being produced was _extremely_ limited so the initial design cost
predominated overall costs. In this case, I think a design based on
an embedded microprocessor core would eliminate the problems, though
of course at some cost in licensing the core. Given that products
produced in such limited quantities are generally quite expensive
anyway, I doubt the incremental cost of including more algorithms
would be particularly noticeable.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Subject: Strengthening passwords against dictionary attacks
Date: Sun, 17 Oct 1999 16:44:51 GMT
Strengthening passwords against dictionary attacks
Addressing the problem of dictionary attacks on low entropy passwords in
October 15, 1999 issue of the Crytpo-Gram, Bruce Schneier states:
"Some have dealt with this problem by requiring stronger and stronger
passwords, but that is no longer effective. Over the past several
decades,Moore's law has made it possible to brute-force larger and
larger entropy keys. At the same time, there is a maximum to the
entropy that the average computer user (or even the above-average
computer user) is willing to remember. You can't expect him to memorize
a 32-character random hexadecimal string, but that's what has to happen
if he is to memorize a 128-bit key. These two numbers have crossed;
password crackers can now break anything that you can reasonably expect
a user to memorize. Good passwords are difficult to memorize, he will
complain, but this difficulty is precisely why they are considered
good."
Here is a brief idea to make regular passwords stronger.
Currently 'salt' is used to increase the possible number of outputs from
a given input. Most Unix systems use 4096 possible salts concatenated
to a single password. So the password 'weak' can have 4096 or 2^12
possible entries in to password file.
If the amount of salt were dramatically increased, creating an off-line
dictionary of common passwords would be infeasible. So the first step
is to increase the salt to 1K bits. Now the password 'weak' can have
2^1024 combinations. No effective off-line dictionary could be created.
The salt is not secret but should be evenly distributed across the
2^1024 space.
If the amount of time to check a password was relatively long, say 5
seconds on the average, then a dictionary attack would be infeasible to
do in real time. Checking one million passwords would take about 57
days instead of a minute or two. At the same time, waiting 5 seconds
after typing in the correct password should not be too much of an
irritation.
In order to slow down the password check, the last N bits of the salt
should be thrown away. About (2^N)/2 hashes would have to be done to
check a password. So if N is 16 then 2^N = 65536 and (2^N)/2 = 32768.
It would take 32768 hashes on average to determine if a given password
is correct. N can be tuned to be larger and larger as computing power
grows. By increasing N, the amount of time to check a password could be
held nearly constant. The number of bits N is not secret but the value
of the bits is secret. If Moore's law holds, one bit would be added
every year and a half.
All passwords would be required to have upper case, lower case, a number
and a special character.
To summarize
1. Increase the amount of salt to a huge number like 2^1024.
2. No off-line dictionary can be created if the huge salt is randomly
distributed.
3. Throw away the last N bits of salt. If 16 bits are thrown away,
32768 hashes must be computed on the average to check a password.
Timing tests with the fastest available password checker would give a
practical value for N.
4. If N is large enough the password check will be quite slow therefore
a real time dictionary attack will be too slow to be practical.
5. Don't allow the user to select weak passwords.
With the above modifications, even an 8 byte password should be modestly
resistant to dictionary attack. A 16 byte password should be very
strong against dictionary attack. A 32 byte passphrase should be too
strong to attack.
Quoting Mr. Schneier's numbers from the Crypto-Gram:
"L0phtcrack is a password-cracking program that does this; on a Pentium
Pro 200 it can test a 200-entry password file against an 8 Megabyte
dictionary of popular passwords in under a minute. Testing the entire
26-character alphabet space takes 26 hours, and the 36-character
alphanumeric space takes about 250 hours."
Under the new method with 16 bits of salt being thrown away, the
check should be about 26 hours * 65536 == ~190 years. For the 36
character set, 250 hours * 65536 == ~18703 years. Much better :-)
A password checker using these rules would be fun to write for Linux or
ScramDisk. Perhaps, I'll get to it.
--Matthew E Fisher
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Sun, 17 Oct 1999 17:05:02 GMT
On 16 Oct 1999 16:11:57 -0700, in
<7ub0nt$9ep$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David Wagner) wrote:
>In article <[EMAIL PROTECTED]>,
>Jerry Coffin <[EMAIL PROTECTED]> wrote:
>> I doubt it takes more than 100 lines of code on average to implement
>> the AES finalist algorithms.
>
>In software, it's easy; in hardware, it's a huge added cost.
There is "hardware," and then there is hardware: Many "hardware"
systems now use embedded processors to perform the "hardware" task,
and there may be multiple such processors. Typically such systems
load from flash and save state in flash; there is no floppy or hard
drive or file system, but in a real sense, everything is software
inside.
In engineering design we are even seeing very complex single-chip
systems which take initialization from flash and save state in flash.
It is not much of a leap to talk about a stand-alone ciphering chip
which takes as its state a flash of various ciphers which it can then
execute.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Quad. in RC6
Date: Sun, 17 Oct 1999 16:56:31 GMT
In article <7u7jin$o3t$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Ok to sumarize the quad in RC6 is
>
> F(x) = x(2x + 1)
>
> Which has been shown to be a function (multiplication of any variable
by a
> odd number is a function mod 2^w).
>
> However have any weaknesses been found? What if you change it to
>
> F(x) = x(ax + b)
>
> Where (a, b) are round/key dependant integers (a being even and b
being odd
> of course)? Would that make it any harder to attack/model? Would it
still
> be a function (as shown in RC6)?
I see a couple of problems with this because there will be a limited
number of possible a's and b's that you can choose. The problem stems
from the fact that multiplication by powers of two acts as a left shift,
or right shift depending on endienity. In the case of the original
quad, x is shifted left by one bit. Now, for every bit we shift, we
lose a bit. In the case of a one bit shift, we lost the highest bit.
If we multiply by 256, or shift by 8 bits, we lose 8 bits of
information. As far as I remember, the quad is primarily used to
generate 5 bits for the rotates that come next, with some additional
mixing included. Thus, you want to use as much information from the
data as possible, so by multiplying by larger values, you lose
information. Now, I'm not sure of the exact mathematics behind this,
but the lost information may provide an attacker a means of attack.
As for b, or the odd number, that will probably have to relate to how
much information is lost by the multiply. Assuming we limit a to a
maxmimun value of 256, you will have to have at least 8 good odd values
to obtain the desired effect of the quad. More than likely, you will
have to predefine these. If an attacker can force certain values for a,
he or she can then guess b.
Anyway, that's what I came up with as a possibility as to why x(ax+b) is
bad. If anyone can prove me wrong, or help refine what I said, I'd
appreciate it.
csybrandy
>
> Is 'ax + b' called an affine transformation ? (Trying to get some
> terminology down).
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Sun, 17 Oct 1999 17:06:54 GMT
On 16 Oct 1999 18:52:33 -0400, in <7uavjh$fs8$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Patrick Juola) wrote:
>In article <[EMAIL PROTECTED]>,
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>Roger Schlafly wrote:
>>>
>>> Exactly. No interoperability.
>>
>>Why do you care so much about interoperability? For a specific group
>>of communication partners to communicate securely, it suffices that
>>they argree on a specific software/hardware to use.
>
>Because the whole point of computer -- or more generally, communications --
>networks is to permit communication between widely distant and possibly
>unfamilar parties. One of the nice things about the telephone is that
>someone can telephone me from almost anywhere in the world, irrespective
>of whether or not they've communicated with me before or whether or not
>I have the same sort of telephone that they do. I can pass out my
>phone and fax numbers on my business cards, confident that anyone
>can communicate with me -- or that they can tell other people how to
>communicate with on the basis only of that information.
>
>I can drive almost anywhere, secure in the knowledge that no matter
>where I go, I will find a gas station that interoperates with my
>car. I didn't have to put some sort of special doohickey in my
>engine to make sure that the gasoline I put in in Denver will run
>in the engine I bought in New York.
And, if there were a standard cipher *interface*, anytime you needed
to use a different cipher to "interoperate," you could just plug that
cipher in.
As to knowing which cipher to use, that information should come along
with the key.
If you do not have that cipher, you might negotiate a cipher you both
have, or drop down to triple-AES or triple-DES (which you both will
have), or get the cipher itself sent along with the key.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Character Frequencies Tables for languages other than English
Date: Sun, 17 Oct 1999 20:17:21 +0200
Stu Jenkins wrote:
>
> I am looking for character frequency tables for european and other
> languages. Does anyone know where these are available?
There are some tables for a few European languages in a number
of crypto books, e.g. F. L. Bauer, Decrypted Secrets, Springer-Verlag.
But these tables may deviate more or less strongly from the
frequencies of the applications you actually have. So a better way
seems to be to do counts oneself.
I am ignorant of frequency tables for other languages. I doubt
that a frequency count of a substantial corpus exists e.g. for
Chinese.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Biometric Keys are Possible
Date: Sun, 17 Oct 1999 20:17:06 +0200
[EMAIL PROTECTED] wrote:
>
> Pattern recognition can do certain things for you, but the problem I
> outlined is fundamental where the underlying measurement is analog. A
> technique such as that I outlined is necessary, and no amount of pattern
> recognition can avoid it, to produce a cryptographic key (however
> short) from hand geometry, for example.
Just a remark: Pattern recognition has to deal with the fundamental
problem of classification in the presence of variations (due to
naturally present diversity, errors of measurement or noises
arising from poor observational conditions) and often limited
availability of data, whether these are analogue or digital.How the
classification is best defined is itself an important issue.
Coding theory does in principle similar stuff but restricting on
binary bit sequences (to be used as codes of symbols) and concentrates
itself on optimality of code size, error detection/correction and
like topics.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: accurate decryption
Date: Sun, 17 Oct 1999 20:17:15 +0200
eminor54 wrote:
>
> This may be slightly off- topic, but I was wondering - how can one
> defend against this scenario - you have a decrypted mesage intercepted
> by someone in authority who wants to accuse you of a crime. They are
> unable to decrypt the message themselves and of course, you dont give
> them the key. However, they then contrive a phony decryption that is
> incriminating, yet you cant prove to anyone that it's a fake without
> revealing the true message. What defenses exist in a case like this? Is
> it possible to show that the fake message is indeed a fake without
> revealing the true text?
I don't think it is that simple to construct a phony decryption for
messages encrypted with modern ciphers. But experts may like to
correct me.
If the authority wants to incriminate you, they can better construct
a phony plain text and use a common cipher. I don't know whether
there is a good way to prove that you have never sent the ciphertext.
M. K. Shen
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.misc,talk.politics.drugs,alt.privacy
Subject: Re: accurate decryption
Date: Sun, 17 Oct 1999 12:23:19 -0700
Reply-To: [EMAIL PROTECTED]
eminor54 wrote:
> This may be slightly off- topic, but I was wondering - how can one
> defend against this scenario - you have a decrypted mesage intercepted
> by someone in authority who wants to accuse you of a crime. They are
> unable to decrypt the message themselves and of course, you dont give
> them the key. However, they then contrive a phony decryption that is
> incriminating, yet you cant prove to anyone that it's a fake without
> revealing the true message. What defenses exist in a case like this? Is
> it possible to show that the fake message is indeed a fake without
> revealing the true text?
>
> Thanks
>
> Bill Heiss
You lose.
If they are willing to do this, they are willing to frame you in other
ways such as planting drugs on you, etc.
They might also simply kill you outright.
Once the "authorities" break the law coming after you or in order to
get you, I just don't see any logical reason why they should stop at
anything to accomplish their goal.
In this scenario, you may have no choice but to break the law
yourself.
But if comes to this you probably have no options except revenge.
Did you hear about the guy in Texas who called 911 and when the
police arrived he killed three outright and wounded two others before
being killed himself.
They spotted him with thermal infrared from a helicopter.
Excellent plan on his part except he didn't count on the aerial
infrared.
There are techniques to evaded and decoy thermal infrared.
------------------------------
** 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
******************************
