Cryptography-Digest Digest #235, Volume #11 Thu, 2 Mar 00 05:13:01 EST
Contents:
Re: brute force attack on a 128 bit SSL key? ("Harvey Rook")
Re: Far out crypto claims ("Douglas A. Gwyn")
Re: very tiny algorithm - any better than XOR? (David A. Wagner)
Re: very tiny algorithm - any better than XOR? (Carl Byington)
I was just wondering... ("Julian Lewis")
Re: CRC-16 Reverse Algorithm ? ("Douglas A. Gwyn")
Re: brute force attack on a 128 bit SSL key? ("Douglas A. Gwyn")
Re: Best language for encryption?? (Paul Schlyter)
Re: Best language for encryption?? (Paul Schlyter)
Re: Best language for encryption?? (Paul Schlyter)
Re: ...but what about my cipher? ([EMAIL PROTECTED])
Re: very tiny algorithm - any better than XOR? (Terje Mathisen)
Re: ...but what about my cipher? ([EMAIL PROTECTED])
Re: OAP-L3 Version 4.2: Updated OverWrite / Delete method (Anthony L. Celeste)
----------------------------------------------------------------------------
From: "Harvey Rook" <[EMAIL PROTECTED]>
Subject: Re: brute force attack on a 128 bit SSL key?
Date: Wed, 1 Mar 2000 21:30:40 -0800
"Randy Given" <[EMAIL PROTECTED]> wrote in message
news:89jrge$[EMAIL PROTECTED]...
> > Assume the following:
>
> That's the problem. You remember what
> "assume" represents, right?
>
> For example, wasn't it 30 years ago that
> some "expert" said it would take 40 quadrillion
> years (40,000,000,000,000,000 years) to break
> DES. Hmmm. Was he right? I don't think so.
>
Instead of calculating brute force difficulty using time, try use energy
consumed. The following argument is Bruce Schnieners...
How much energy can the most efficient computer consume per operation? This
computer must run at 3.2K (The background temp of the universe). any cooler,
and you would need a cooling unit. The least energy this computer can
consume per operaton is
3.2K * Boltzman Constant = 3.2K*( 2^-76 J/K-1)
So How much energy does it take to crack a 128 bit key...
=2^127 * 3.2 * 2^-76J
=3.2*2^51J
or about 2 billion Kilowatt Hours. This is about the same amount of energy
that the entire world consumes in 15 minutes
How much energy does it take to crack a 256 bit key...
=2^255 * 3.2 * 2^-76J
=3.2*2^179J
This is more energy than is released in a super nova.
So, brute force cracking a 128 bit key will be impractile until there is a
revolution in energy production. Brute force cracking a 256 bit key will be
impossible forever.
Harv
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Far out crypto claims
Date: Thu, 02 Mar 2000 07:03:27 GMT
[EMAIL PROTECTED] wrote:
> 5 star admiral Lord Hill-Norton, the former
> head of the UK's MOD, MI-5, and MI-6 said that
> while he was head of the MOD he knew of on-
> going projects invovling alien technology but
> was kept in the dark about them. What does
> this have to do with cryptography? Well, there
> is a U.S. Army Major and lawyer who claims to
> have been an Army cryptographer in the
> Pentagon during 1959-61. Like the Admiral, he
> is willing to appear on the same documentary
> movie series and would speak about the
> Army's efforts to decrypt the series of
> hieroglyphic- like symbols found on the
> recovered alien debris from the Roswell crash.
> Before believing his claims I would require
> independent confirmation, but if you want to
> see more about this then go to the following
> website and scroll down to the partial list of
> witnesses at about the bottom third of the
> page: www.cseti.org/position/greer/
> discosure_moviesummary.htm
You left an "l" out of "disclosure" in the above URL.
I looked at that page and the rest of the Web site,
which actually I had seen before. It is typical of
the "true believer" lampooned by early X-Files
episodes, including completely incorrect descriptions
of "establishment" physics, and far too much taking
of claims at face value without critical testing to
see if they hold up when confronted with reality.
There is no doubt that many people have seen "UFOs"
in the sense of difficult-to-explain aerial
phenomena, including radar returns. But to assume
that these are alien spacecraft is to make a huge
unjustified leap of faith. Heck, one of my friends
has a UFO she flies around inside her house by
remote control, although it is now an IFO to me
since I know what it is. Similarly, many UFOs that
have been objectively investigated have become IFOs.
None of the IFOs has turned out to be an alien
spacecraft, although several of them have been found
to be secret military aircraft of various kinds
(like the balloons I mentioned in a previous post).
To get back to cryptology, and to provide an example,
UFO fanatics have interpreted as evidence that the US
government has been covering up knowledge of UFOs as
actual alien spacecraft the two FOIA-released papers
by Callimahos (see below), one concerning the technical
possibility of communication with extraterrestrials
who share no common cultural background with humans,
the other a philosophical speculation on possible
implications of the UFO phenomenon (not necessarily
implying existence of extraterrestrial beings) on
the survival of the human species. But the facts are
that the first paper was the result of Callimahos
being invited to advise on a Congressional panel
investigating the subject (resulting in a report that
I have on file, containing among other articles one
that is very similar to the one from NSATJ released
under FOIA), which Callimahos seems to have taken on
originally as an interesting intellectual challenge,
and the second paper (unpublished) was not pursued
as part of his official duties, but apparently was
the result of continuing to muse on UFO issues.
There is also one more NSATJ article (by the first
Editor of the NSATJ) that continues the train of
development of Callimahos's first paper, but is
still classified (for cryptologic security reasons,
not as any sort of UFO cover-up). There are no
other articles on this subject in NSATJ nor its
successor publication. It was simply an amusing
exercise, not at all indicative of government
knowledge of actual alien spacecraft.
I have prepared a Word-format document (thus PDF,
etc.) of the classic NSATJ paper, which may appear
on my Web site some day, but meanwhile has appeared
as bitmap scans:
http://www.nsa.gov/docs/efoia/released/ufo/ufo34.pdf
The second paper can be found as reformatted HTML:
http://www.cufon.org/cufon/fmovsnsa.htm
or bitmap scans of the original:
http://www.nsa.gov/docs/efoia/released/ufo/ufo35.pdf
If you really want another essay, this one concerns
implications for normal military intelligence from
examining responses to the UFO phenomena; I don't
know the author:
http://www.nsa.gov/docs/efoia/released/ufo/ufo36.pdf
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: very tiny algorithm - any better than XOR?
Date: 1 Mar 2000 22:49:51 -0800
In article <89kjtn$[EMAIL PROTECTED]>,
Harvey Rook <[EMAIL PROTECTED]> wrote:
> Hmmm. Speaking of Tiny Algorithms. How effective is RC-4 with only 16, 24,
> or 32 bytes in the SBox.
If I recall correctly, a regular poster here has done some work
on this and found that at least the case of 16 bytes is much less
secure than you can expect. Search the archives for hillclimbing
and RC4.
> To save memory, the key would be the permutation,
> rather than a the standard RC-4 key hash.
Yikes, I don't think that's such a good idea.
------------------------------
From: [EMAIL PROTECTED] (Carl Byington)
Subject: Re: very tiny algorithm - any better than XOR?
Date: 2 Mar 2000 07:29:18 GMT
=====BEGIN PGP SIGNED MESSAGE=====
I wish to thank everyone for their suggestions. This will be running on
an Atmel AT90S8515 <http://www.atmel.com/atmel/acrobat/doc0841.pdf>.
I have added an outer round loop, and changed to overlapping 16 bit
blocks. This should give better diffusion. The decrypt code is now 78
bytes, 22 bytes used by the calling sequence overhead, and 56 bytes for
the actual code. Given that this is already too large, I don't think I
can add a more complicated key schedule. The target was 50 bytes of
code space.
I did look at TEA, but I don't see any way to get that into anything
like 50 bytes on this processor.
I still need to investigate PIKE, but it seems to use 32 bit operations,
and this processor only has 8 bit ones, so the code quickly gets large.
/**********************************************************
Input values: k[16] 128-bit key
v[8] 64-bit plaintext block
Output values: v[8] 64-bit ciphertext block
**********************************************************/
void encrypt(word8 *k, word8 *v)
{
int i, j, r;
for (r=0; r<16; r++) {
for (i=0; i<7; i++) {
for (j=0; j<16; j++) {
// feistel network v[i], v[i+1] form the 16 bit block
// L = v[i]
// R = v[i+1]
word8 t = v[i+1];
v[i+1] = v[i] ^ ((rotate_left(t) + k[j]) & 0xff);
v[i] = t;
}
}
}
}
- --
PGP key available from the key servers.
Key fingerprint 95 F4 D3 94 66 BA 92 4E 06 1E 95 F8 74 A8 2F A0
=====BEGIN PGP SIGNATURE=====
Version: 4.5
iQCVAgUBOL4YQdZjPoeWO7BhAQGPAwP/QPUjo5RGUTG9uxu/XAYCF1UEptVWxKbM
XZrVMt2iANDPSHx9Ogn8SH+6CXIHBHlW9KAFEJFEZVp8xLBrL5mhPg+fATG0Pmjg
ePYWi7fzN28xQfsbbtn3IAp2mqrN6N2isgURZP1kwuQgJQ9KejI7BAsOWbUFOkqi
kCKoKabRbPw=
=yRB6
=====END PGP SIGNATURE=====
------------------------------
From: "Julian Lewis" <[EMAIL PROTECTED]>
Subject: I was just wondering...
Date: Thu, 2 Mar 2000 08:21:22 +0100
Reply-To: "Julian Lewis" <[EMAIL PROTECTED]>
Once upon a time, there was a guy who read a book by Simon Singe
called the code book, and as a result he got interested in encryption.
Naturally he installed PGP on his computer, and got some of his friends
to do likewise, so that he could have fun exchanging encrypted emails,
well boys will be boys, you know how it is. One day he sent an encrypted
email to a friend, and guess what, although it was encrypted in his out
box, it arrived in plain text at his friends in box. Ohhh replied his friend
"careful, you forgot to encrypt that one !!". "No I didn't", the man
replied,
I guess it must just be a bug in outlook !!!
=============================================================
Julian Lewis
Division PS Group CO Building 8 1-022
CERN - 1211 Geneva 23 Switzerland
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: CRC-16 Reverse Algorithm ?
Date: Thu, 02 Mar 2000 07:51:41 GMT
"D. J. Bernstein" wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > The simple fact is, there are some garbles that *any* CRC scheme
> > will fail to detect.
> False. If you have two different messages up to a billion bits long, for
> example, then that difference will be detected by more than 99.99999% of
> the possible CRC-64 polynomials.
I'm sorry; you didn't parse it the way I meant it:
For *any* CRC scheme, there are some garbles that it will fail to
detect.
Which is meant to be an almost-trivial observation,
but nevertheless one that was relevant to the discussion.
It is the *probability* of garbles like a run of 0s or 1s
that made it especially important to guard against those.
(Answering the unasked question, "Why are we so concerned
about those garbles when there are so many other garbles?".)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: brute force attack on a 128 bit SSL key?
Date: Thu, 02 Mar 2000 07:55:40 GMT
Harvey Rook wrote:
> Instead of calculating brute force difficulty using time,
> try use energy consumed.
No, please don't. That's a spurious approach.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Best language for encryption??
Date: 2 Mar 2000 08:08:51 +0100
In article <[EMAIL PROTECTED]>,
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
>
>> In article <89ihfs$3m7$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Paul
>> Schlyter) wrote:
>>
>>> In article <1SYu4.12$[EMAIL PROTECTED]>,
>>> Adam Durana <[EMAIL PROTECTED]> wrote:
>>>
>>>> BASIC is great for learning structured programming,
>>>
>>> :-) ... no, it's indeed not! But it's great for learning
>>> spagetti programming....
>>>
>> Basic allows that like Fortran as it is very forgiving, but you do not
>> need it. I notice that C does not easly allow goto's to be as effective
>> as they would be in Basic. I see that as a weakness of C, not a
>> strength.
>
> How does one measure the effectiveness of a goto?
By the amount one can obfuscate the code with these goto's... :-)
> Whatever the units are, I suspect that between signal() and longjump()
> C can probably match it.
Not quite: a BASIC program can GOTO a line number it hasn't executed
yet, while C cannot longjump() to a place it hasnt setjump()'ed yet.
--
================================================================
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: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Best language for encryption??
Date: 2 Mar 2000 08:09:15 +0100
In article <[EMAIL PROTECTED]>,
lordcow77 <[EMAIL PROTECTED]> wrote:
> In BASIC, I believe that goto can transfer control to arbitrary
> parts of the code (which is not much of a problem..."Functions?
> What functions? Execution contexts? Threads? External linkage?
> What's that?"), whereas in C, the goto can only go to a label in
> the same block or function.
If you want to go farther than that in C, use setjump/longjump instead.
These are library functions which allow you to jump between functions.
longjump() is most often used to directly jump out of several nested
function calls, in e.g. an error situation.
And then you also have signal().....
--
================================================================
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: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Best language for encryption??
Date: 2 Mar 2000 08:09:51 +0100
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
>> ... I notice that C does not easly allow goto's to be as effective
>> as they would be in Basic. I see that as a weakness of C, not a
>> strength.
>
> If only it were so, but that's contrary to your promotion of BASIC
> for structured programming. However, it is *easy* to write a C
> program to mimic all of the GOTOability of BASIC *except* for the
> ability to branch into the middle of a subroutine -- which isn't
> something that should be encouraged (for reasons that were evident
> in the 1960s).
What about:
#include <stdio.h>
#define PRINT int main() { printf (
#define END "\n" ); return 0; }
PRINT "Hello, world"
END
:-)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
--
================================================================
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: [EMAIL PROTECTED]
Subject: Re: ...but what about my cipher?
Date: 2 Mar 2000 09:36:21 GMT
In a previous article, "Harvey Rook" <[EMAIL PROTECTED]> writes:
>Look again. David A. Wagner post a reply. Your cipher can be cracked in
>O(2^33) time
I find no "Re:How weak is WeakCipher?" from David A. Wagner.
I have found mentions of a technique to separate the effect of "shuffling two
congruential generators", but I can't find any references to either the
algorithm in question or the technique of this attack. Maybe this could be
relevant in my case, but actually I don't know. Can anyone help me out here,
please?
However the number O(2^33) buffles me. As far as I can tell it could be
cracked in less time if the initvector is known (and I do use a constant init
vector in my example for the sake of demo clarity). In particular, a known
plain text attack might exploit a known init vector to an even higher
extent.
If I had used a 32-bit discrete power in ordinary CFB-mode, it could of course
have been cracked in O(2^31) time by brute force. But I keep the encrypted
vector instead of the unencrypted, thereby making the cipher error
propagating. In the present version every byte from the second byte is
completely dependent on both 32-bit discrete powers, in the sense that you,
for any fixed value of one base, might alter the other and thereby get any
output.
----- Posted via NewsOne.Net: Free Usenet News via the Web -----
----- http://newsone.net/ -- Discussions on every subject. -----
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: very tiny algorithm - any better than XOR?
Date: Thu, 02 Mar 2000 10:44:16 +0100
Carl Byington wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
>
> I wish to thank everyone for their suggestions. This will be running on
> an Atmel AT90S8515 <http://www.atmel.com/atmel/acrobat/doc0841.pdf>.
>
> I have added an outer round loop, and changed to overlapping 16 bit
> blocks. This should give better diffusion. The decrypt code is now 78
> bytes, 22 bytes used by the calling sequence overhead, and 56 bytes for
> the actual code. Given that this is already too large, I don't think I
> can add a more complicated key schedule. The target was 50 bytes of
> code space.
>
> I did look at TEA, but I don't see any way to get that into anything
> like 50 bytes on this processor.
>
> I still need to investigate PIKE, but it seems to use 32 bit operations,
> and this processor only has 8 bit ones, so the code quickly gets large.
What about using something like the DVD CSS algorithm:
Use a pair (or three?) of relatively prime length LFSR generators, if
you work with single bits then you don't need any lookup tables at all.
Yes, CSS was cracked, but since you actually contemplated XOR, it seem
like you primarly want whatever security you can get from 50 bytes of
code, right?
Terje
PS. I've taken a look at the instruction set for your Atmel cpu:
There is no rotate register opcode, so your rotate_left() must be
synthesized. I am not sure what the best way to do this would be, but it
seems like it would take several instructions, and/or a temporary
register:
MOV temp,reg
ADD temp,temp
ROL reg ; reg = reg*2, new bottom bit from carry
It should be possible to code up an LFSR fairly simply:
You have 32 8-bit registers, so it is feasible to use 3 or 4 of them to
store the current state of the shift register:
; Update one bit:
add s0,s0 ; Do a 32-bit wide shift left
adc s1,s1
adc s2,s2
adc s3,s3
; Remember the top bit
sbc t0,t0 ; t0 = -1 if carry
; Go through the LFSR tap points (assume 4 taps)
sbrc T0_REG,TAP0 ; Skip the next instruction if bit is clear
inc t0 ; Conditionally invert the bit accumulator
sbrc T1_REG,TAP1 ; Skip the next instruction if bit is clear
inc t0 ; Conditionally invert the bit accumulator
sbrc T3_REG,TAP2 ; Skip the next instruction if bit is clear
inc t0 ; Conditionally invert the bit accumulator
sbrc T3_REG,TAP3 ; Skip the next instruction if bit is clear
inc t0 ; Conditionally invert the bit accumulator
; Update the bottom bit of the shift register
andi t0,1 ; We only want a single bit
add s0,t0 ; Increment if (t0 == -1)
This is 15 instructions for the inner loop, probably about 20 (?) bytes
of code.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: ...but what about my cipher?
Date: 2 Mar 2000 09:48:20 GMT
In a previous article, <[EMAIL PROTECTED]> writes:
>Read the FAQ.
>
>You might better response if you posted a concise, easy-to-follow
>description of the cipher,
I have. "How weak is WeakCipher?", posted 2/29/0 21:02:34 GMT.
>along with any analysis you've done.
>I didn't see any of that at the web site you listed.
Yes, I have performed both simulations and pure mathematical equation solving.
I just did not consider the cipher all too original, and figured that chances
are someone already hade invented and tested it. References, anyone?
>(You HAVE done some analysis, right? If not, why are you designing
>yet another cipher?)
It is a spin-off product from another project. It made nice pascal code. And
it would actually serve it's purpose even if it could be cracked in O(2^31)
time.
----- Posted via NewsOne.Net: Free Usenet News via the Web -----
----- http://newsone.net/ -- Discussions on every subject. -----
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: Anthony L. Celeste <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.privacy
Subject: Re: OAP-L3 Version 4.2: Updated OverWrite / Delete method
Date: 2 Mar 2000 04:02:01 -0600
Reply-To: [EMAIL PROTECTED]
On Wed, 1 Mar 2000 01:45:30 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>27 is one more than 26 ;-)
>
>Perhaps someone will soon offer us the option of 28 consecutive
>overwrites. Or perhaps - more likely - someone's done it already.
Eraser www.east-tec.com uses 34 consecutive overwrites. hex zero, hez
255, text strings, inverted text strings, random hex patterns, etc...
A little anal retentive for my taste...
Tony
------------------------------
** 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
******************************
