Cryptography-Digest Digest #842, Volume #9 Wed, 7 Jul 99 18:13:03 EDT
Contents:
Re: Is it possible to combine brute-force and ciphertext-only in an (Jim Gillogly)
Re: Is it possible to combine brute-force and ciphertext-only in an (Jim Gillogly)
Re: I don't trust my sysadmin (Patrick Juola)
Re: Standard Hash usage ([EMAIL PROTECTED])
Re: Is it possible to combine brute-force and ciphertext-only in an attack?
([EMAIL PROTECTED])
Re: More secure UNIX style authentication (Janusz A. Urbanowicz)
An inconsequential hack (John Curtis)
Properties of Chain Addition? (John Savard)
Re: Is it possible to combine brute-force and ciphertext-only in an attack? (John
Savard)
Re: Is it possible to combine brute-force and ciphertext-only in an attack?
([EMAIL PROTECTED])
Re: Help!! Looking for a modular exponentiation algorithm. (S.T.L.)
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Is it possible to combine brute-force and ciphertext-only in an
Date: Wed, 07 Jul 1999 13:12:25 -0700
Jim Gillogly wrote:
>
> Morgan wrote:
> > In reality, .wav files, MPEG-2 video, etc. will have headers, so you have
> > a small crib (some plaintext to work with), so the attack *is* possible,
> > but the known-plaintext is very small compared with the ciphertext.
>
> You don't really need known plaintext. .WAV files, for example, have
> an enormous excess of both 0x00 and 0xFF bytes.
That was just the first few I looked at -- sounds from Win95. A couple
of longer .WAV files decrypted from the Idaho/Harris traffic of a year ago
didn't have high 00 and FF, but rather had a bell-shaped curve of frequencies
across the 00-FF spectrum, which is different but equally distinctive.
Certain kinds of compressed files (e.g. .Z files) have other
exploitable statistical oddities. Others (e.g. .gz) look pretty
random to me, but are still crackable: for each new key, try
decompressing the first few dozen bytes with the expected decompressor,
which you will presumably have identified with traffic analysis.
--
Jim Gillogly
Sterday, 14 Afterlithe S.R. 1999, 20:06
12.19.6.6.2, 13 Ik 10 Tzec, Fifth Lord of Night
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Is it possible to combine brute-force and ciphertext-only in an
Date: Wed, 07 Jul 1999 12:38:46 -0700
Morgan wrote:
> Suppose you have a DES 56-bit key encrypted stream that contains
> something like music or video. Is it possible to discover the key
> by searching the entire keyspace?
Yes. They have very distinctive frequency patterns. It's more
expensive than a known plaintext search, but a "known statistics"
search is quite feasible.
>
> In reality, .wav files, MPEG-2 video, etc. will have headers, so you have
> a small crib (some plaintext to work with), so the attack *is* possible,
> but the known-plaintext is very small compared with the ciphertext.
You don't really need known plaintext. .WAV files, for example, have
an enormous excess of both 0x00 and 0xFF bytes.
> In theory, though, if you have a totally random stream, how do you
> know when you've come up with the correct key?
You don't. Fortunately that's not the case with the examples you've given.
The EFF DES-cracker works with more general patterns than just known
plaintext (although that's what was used for the RSA challenges), so
I think it's not unlikely that it could be adapted to this problem as
it stands. Somebody who's looked at its pattern-matching specs can
answer this more specifically than I can.
--
Jim Gillogly
Sterday, 14 Afterlithe S.R. 1999, 19:34
12.19.6.6.2, 13 Ik 10 Tzec, Fifth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: I don't trust my sysadmin
Date: 7 Jul 1999 15:36:53 -0400
In article <7lvqnj$7bn$[EMAIL PROTECTED]>,
Vernon Schryver <[EMAIL PROTECTED]> wrote:
>In article <7lvjh7$bed$[EMAIL PROTECTED]>,
>Patrick Juola <[EMAIL PROTECTED]> wrote:
>
>> ...
>>>No, those don't work either. I've seen a commercial UNIX system certified
>>>by the U.S. government, and I don't mean the easy stuff but full MAC
>>>(mandatory access controls), capabilities, and so forth.
>>
>>Hmm. I think that one of the problems with the system you describe
>>is that it wasn't secure *enough*. The DoD has created a set of
>>guidelines (the so-called Orange Book, more formally the Trusted
>>Computer System Evaluation Criteria) describing a half-dozen levels
>>of increasing security.
>>
>>The problem (and I think your tale makes that woefully apparent)
>>is that the useful levels are almost impossible -- in the case of
>>B2 and beyond, *formally* impossible -- to retrofit onto an existing
>>(insecure) system. Unix can never be made more secure than B1 because
>>the basic security policies don't permit. And the B1 systems themselves
>>are a total mess, partially because they're a series of kluge upon
>>kluge in an attempt to secure what is fundamentally a leaky sieve.
>
>It is true that you cannot simply glue stuff on the outside of UNIX to
>get it certified. The UNIX system I'm talking about was heavily modified.
>Every interface was mangled--er--examined and changed as necessary. Every
>access to a file or other data was fitted with auditing and MACs. You
>name it, and it was probably touched, including odd corners like the format
>of /etc/inetd.conf. Many internal kernel functions had extra args. In
>the first years, the secure version of the system was mostly based a
>million bazillion ifdefs. The normal version did not have the extra grot
>on the tapes and (eventually) CDROMs.
>
>>You can buy more secure systems; I've never heard of an A1 system (the
>>highest level), but B2 and B3 *are* available. They just don't run
>>Unix.
>
>You are mistaken, unless you mean essentially unmodified UNIX.
No, I'm simply distinguishing between B1 and the higher levels
(B2-3); I do not believe that it's possible to retrofit *any* OS
to achieve B2 security; according to the guidelines, B2 (and better)
security has to be planned into the design from day 1. Simply
taking code and putting in "a million bazillion ifdefs" -- even
if they all worked -- doesn't fulfil the B2 guidelines. And
part of the reason that the B2 guidelines are written that way is
because the folks at the DoD &c. don't believe that a million
bazillion ifdefs are an acceptable way to write secure, reliable
code.
A sentiment I (and you, apparently) also share.
>That outfit
>sold and still sells the DOD many $M of certified UNIX systems, along with
>so called super computers. I don't remember which B#'s; "B2" sounds
>familiar, but it might have been 1 or 3.
I strongly suspect it was B1; B1 is essentially the highest level that
can be retrofitted onto an existing OS.
>
>> So you can get real, usable, security at the expense of an
>>operating system that no one knows and that's incompatible with everything.
>
>No, the system I'm talking about was still nominally one of the big-5
>commercial UNIX boxe. The security stuff does get in the way when it's
>present and on, which is one reason why there are magic knobs to turn it
>off.
The knobs themselves which itself suggests that it wasn't a B2 system.
My point is fairly simple -- and compatible with yours. UNIX by itself
is C1, I recall correctly. You can hack it up, almost beyond recognition
and usability, to achieve B1 security. If you want something better,
they *are* available, but not as anything Unix-alike. Which means
most people don't want them.
-kitten
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Standard Hash usage
Date: Wed, 07 Jul 1999 20:21:55 GMT
In article <7m06qr$bqo$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Keith A Monahan) wrote:
> Ok. I understand this - but what if your password has an odd number of
> bytes. Where is the half way point? Is there any type of convention
> for doing this?
I will stick with my previous suggestion. do this
H1 = SHA-1(M)
H2 = SHA-1(M||H1)
This is kinda a standard for making larger hashes. It is also
documented in a paper about 'key stretching' by Bruce Schneier. (only
hwe used a private key and salt...)
> : If you don't have 320 bits of information your hash output will not
> : have 320 bits of information, no matter what algorithm you use.
>
> I'm in over my head with this project. And the source that everyone
> is recommending I have no idea to how to use. People say look at the
ssleay
> implementation of SHA1. Well, I've looked, downloaded, messed around
I think Jim Golligy (sorry I forgot the spelling) has a good copy of
SHA-1. Ask around in this group I know I saw a Good copy...
You could always read FIPS-180 and implement it yourself? MD5 (RFC
1321 I think...) has C source code included. I have a copy of MD5 (the
RFC) if you want I could email it in private...
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: [EMAIL PROTECTED]
Subject: Re: Is it possible to combine brute-force and ciphertext-only in an attack?
Date: Wed, 07 Jul 1999 20:24:19 GMT
In article <37839fac$0$[EMAIL PROTECTED]>,
"Morgan" <[EMAIL PROTECTED]> wrote:
> I've consulted Schneier's Applied Cryptography & found no answer.
>
> Suppose you have a DES 56-bit key encrypted stream that contains
> something like music or video. Is it possible to discover the key
> by searching the entire keyspace?
Normally yes. Check out cracks on CMEA, ORYX and A5 they work against
audio and control streams...
> In theory, though, if you have a totally random stream, how do you
> know when you've come up with the correct key?
In theory, though, the plaintext is never truly random :)
> Still thinking....
That's good. Thinking hurts sometimes... :)
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: [EMAIL PROTECTED] (Janusz A. Urbanowicz)
Subject: Re: More secure UNIX style authentication
Date: 07 Jul 1999 23:37:09 +0200
[EMAIL PROTECTED] writes:
> As I'm sure most know, UNIX uses a method of password authentication
> with DES. It takes a string of NULL characters and uses the user's
> password as DES's key. (here I am omitting the SALT value, which has no
> relevance to my question) The encrypted NULL string is saved to the
> /etc/passwd (or shadow if you are smart). When a user logs in, it
> encrypts the NULL str with the password that they entered. That
> encrypted text is then compared to the one in /etc/passwd (shadow) to
> authenticate the login. My question is, if the algorithm was changed
> from DES to something a little more modern (and hopefully secure) like
> IDEA or CAST, would that create a more secure algorithm? One thing I
> could think of that would make this method insecure: does the way that
> UNIX verifies it's logins rely on the DES algorithm, and if I change it
> to another algorithm, would the algorithm itself be insecure when
> encrypting a string of just NULLs?
There are versions of login and associated programs that use MD5 instead of
DES encryption. When stored into passwd/shadow such encrypted password begins
with "$1$". This method has one advantage: it allows much longer passwords (up
to 128 characters). DES encrypted passwords can be only 8 bytes long (you
could type in more but the rest is ignored), and it is safe to assume that 64
bit key can be cracked by a brute force attack, for any algorithm. Of course
you could use algorithm such as Blowfish - that has very time-consuming key
setup phase which makes it harder to crack with exhaustive search. OTOH, most
unix passwords can be cracked with dictionary attacks and this could balance
the longer keysetup effect.
IMHO, the right way is to increase the key length as in the MD5-using
implementation.
Hope this helps
Alex
------------------------------
From: [EMAIL PROTECTED] (John Curtis)
Subject: An inconsequential hack
Date: 7 Jul 1999 21:05:05 GMT
Hit 'n' now, if you are looking for serious cryptography.
I use a small Unix tool, produced by a now defunct company
for a translation task. The tool is protected by a
32-bit "p code", inserted on the command line. I had reason
to believe that this p-code was related to a specific
hostid on a specific workstation. Using gdb (a debugger),
I was able to inspect many thousands of lines of disassembled
code, with the original comments intact. After a few hours of
examination, I concluded that it might in principle be possible
to back engineer the p-code checking code, it would not be
entertaining. Various routines were coupled with repetitive
housekeeping tasks and various techniques of obfuscation were
used. It was very tedious.
I did notice that the top byte of the p-code equalled the top
byte of the hostid for the one system/p-code instance that I had
available. This reduced the key space to 24 bits.
Wrote a Perl script to run the tool with incrementing p-codes,
piped to a second script that tested for the error message,
set to send mail to me upon success. Running 4 of these
processes on a single Ultra Sparc 300 Mhz machine, we found a
good code after searching 80% of the code space, which took
11 days.
This was pretty entertaining and a second brute force search is
now running on a different station.
ciao,
jcurtis
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Properties of Chain Addition?
Date: Wed, 07 Jul 1999 21:32:40 GMT
The VIC cipher used by Russian spies involved a technique for
generating pseudorandom numbers known as "chain addition".
One starts with a number of a certain number of digits...
such as 8492
and continues to produce new digits by appending the modulo-10 sum of
the first two digits to the end of the number, and deleting the first
digit of the number.
Thus 8492 generates 2 (8+4=12), then 3 (4+9=13), then 1 (9+2=12), then
4 (2+2=4), and so on.
The technique was mentioned in The Codebreakers, but in a comment on
the future of cryptography. (Its author, David Kahn, was later
responsible for an extensive description of the VIC cipher.)
If one writes the new digits below the number, in columns, it becomes
easier to avoid mistakes: every digit, except those in the last
column, is produced by the digit above and the digit to the right of
the one above...
8492
2314
5459
9948
...
This is really a simple kind of modulo-10 shift register:
---------------
| 8 | 4 | 9 | 2 |<--
--------------- |
| | |
--(+)------------
which prompts me to ask...
is it known that polynomials of the form x^n + x + 1 are likely to
give rise to shift registers with reasonably long periods even if not
maximal ones?
The reason I'm asking, of course, is that I've used chain addition -
modulo 256 instead of modulo 10 - as the main element in the key
schedule of Quadibloc S, a "toy" cipher for analysis purposes that
I've recently described on my web site to illuminate whether or not
the basic constructs I'm using in some of the block ciphers to which
I've given the Quadibloc name.
Of course, there is *one* thing that the above shortcut manual method
illustrates about chain addition...
000000001
000000011
000000121
000001331
000014641
000150051
001650561
017155171
188606882
964664601
what it produces (from a simple but nonzero starting value) is a
modulo-n wrapped-around version of Pascal's triangle, and this perhaps
provides some insight into the period.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is it possible to combine brute-force and ciphertext-only in an attack?
Date: Wed, 07 Jul 1999 21:35:50 GMT
"Morgan" <[EMAIL PROTECTED]> wrote, in part:
>In theory, though, if you have a totally random stream, how do you
>know when you've come up with the correct key?
If one's plaintext were so well compressed as to be indistinguishable
from random data, it would not be possible to be confident of any
decipherment. (Of course, the possible decipherments would still be
limited to those which could be produced from the system used.)
This is one of the limiting cases of encryption deducible from
information theory, just like the more famous case of the one-time
pad.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is it possible to combine brute-force and ciphertext-only in an attack?
Date: Wed, 07 Jul 1999 21:39:13 GMT
In article <[EMAIL PROTECTED]>,
Jim Gillogly <[EMAIL PROTECTED]> wrote:
> That was just the first few I looked at -- sounds from Win95. A
couple
> of longer .WAV files decrypted from the Idaho/Harris traffic of a
year ago
> didn't have high 00 and FF, but rather had a bell-shaped curve of
frequencies
> across the 00-FF spectrum, which is different but equally distinctive.
>
You will notice that with PCM and ULAW type files. That's because they
center around 0x80 most of the time and deviate only for brief periods.
> Certain kinds of compressed files (e.g. .Z files) have other
> exploitable statistical oddities. Others (e.g. .gz) look pretty
> random to me, but are still crackable: for each new key, try
> decompressing the first few dozen bytes with the expected
decompressor,
> which you will presumably have identified with traffic analysis.
Depends. If you compress some unpredicatble data (i.e data that's not
likely to be guessed) then if you compress it, the attack is much
harder. Good for the attacker that most files have known bad
statistics...
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: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: Help!! Looking for a modular exponentiation algorithm.
Date: 05 Jul 1999 23:42:19 GMT
Here's the usual suspect, in pseudoBASIC form.
Calculates X^N mod P. Y is a local variable. X, N, and P are passed to the
function
MODPWR(X,N,P)
Let Y = 1
Label S
If N mod 2 = 1 Then
Let Y = X*Y mod P
Let N = (N - N mod 2) / 2
If N = 0 Then
Return the value of Y
Let X = X^2 mod P (^2 means squared)
Goto S
I don't think I made any mistakes in copying this from my TI-92+. Have fun!
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^6972593 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
***Congratulations to Nayan Hajratwala!***
Card-holding member of the Dark Legion of Cantorians, the Holy Order of the
Catenary, the Great SRian Conspiracy, the Triple-Sigma Club, the Union of
Quantum Mechanics, the Polycarbonate Syndicate, the Roll-Your-Own Crypto
Alliance, and People for the Ethical Treatment of Digital Tierran Organisms
Avid watcher of "World's Most Terrifying Causality Violations", "When Kaons
Decay: World's Most Amazing CP Symmetry Breaking Caught On [Magnetic] Tape",
"World's Scariest Warp Accidents", "World's Most Energetic Cosmic Rays", and
"When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #11: The Strong Force Is Carried By Gluons.
------------------------------
** 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
******************************
