Cryptography-Digest Digest #255, Volume #11 Sat, 4 Mar 00 23:13:01 EST
Contents:
Re: 'Free' services with tokens/puzzles ("Adam Durana")
Re: RC4 and salt ("Adam Durana")
Re: 'Free' services with tokens/puzzles ([EMAIL PROTECTED])
Re: Random bit generators ([EMAIL PROTECTED])
Re: Random bit generators ([EMAIL PROTECTED])
Re: Random bit generators (Guy Macon)
Re: very tiny algorithm - any better than XOR? (Paul Rubin)
Re: 'Free' services with tokens/puzzles ("Joseph Ashwood")
bio-com. L.G.Lawrence: borderlands.com (Albert Jones)
Re: very tiny algorithm - any better than XOR? (Carl Byington)
----------------------------------------------------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: 'Free' services with tokens/puzzles
Date: Sat, 4 Mar 2000 21:12:33 -0500
I don't see RSA's solution really solving the problem. Personally I think
the folks at RSA saw how much attention the media was giving these recent
denial of service attacks and hoped by claiming they had a solution to the
problem, they would recieve some publicity. There are a few reasons why I
don't think thier puzzle system will work. These puzzles have to be
generated by the server in such a way that they have unique solutions for
the most part. Ofcourse puzzles will have to be reused eventually. Another
problem is these puzzles have to be sent to the client, causing more network
traffic. I'm not sure if of the exact details but I would imagine the size
of the puzzle would be bigger than the standard reply to a TCP connection
request. These puzzles will also have to be checked by the server, surely
each puzzle handed out will have an ID number of some sort, so the solution
can be verified and the server can verify if it handed out the puzzle or
not. Even with this sort of checking someone could flood a server will fake
answers to puzzles that the server never assigned. Checking to see if the
answer to the puzzle, is one to a puzzle that was actually assigned will use
some CPU. Now say someone floods the server will connection requests, aka
SYN flooding. The server's list of puzzles and solutions will run out
eventually, it will either have to start handing out the same puzzles or
start making new ones, if it starts making new ones its going to use more
CPU. And this still does not solve the problem of filling up someone's pipe
to the internet. Even with RSA's puzzle system in place someone could still
totally saturate your connection to the internet. If I wanted to attack
someone using RSA's puzzle system, I would flood them with connection
requests, and bogus solutions to puzzles it never assigned, and ofcourse
these would all be comming from random IP addresses. So the CPU and
bandwidth my SYN flooding eats up would be increased by the server
generating new puzzles and trying to send them to the random IPs. Then the
bogus puzzle solutions would eat up some more CPU, note if you were not
using the RSA puzzle system I couldn't use up CPU this way. So you could do
a lot more damage to a server using RSA's puzzle system.
Well back to your question, I would say it would be better to "evolve" your
users' rights as they use it more. I've experimented with things like this
and found it does work well, but it upsets a lot of users when they don't
have instant access to everything. The average user doesn't care about
attacks or how they are prevented as long as it does not affect them and
this way directly affects them. Personally I would say you should setup
some "smart filters" for your traffic, if your filtering software detects
and attack it calculates about how many requests are part of the attack to
how many requests are from valid users. Say its a 500 to 1 ratio, then your
filter would only allow 100 requests to pass through for every 500. So a
user would have a 1 in 5 chance of getting his/her request answered by the
server. Yeah this would cause some problems but a determined user would
eventually get through, I think a 1 in 5 chance would be better than no
chance, which would be the case if you didn't filter and an attacker was
able to totally disable your server.
- Adam Durana
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: RC4 and salt
Date: Sat, 4 Mar 2000 21:19:25 -0500
> system. The time() function is a bad idea since most systems end up doing
> most of the work at roughly the same times every day.
time(NULL) would give you a unique 32bit number, until the year 2032. But
if your system is going to be around for longer than 32 years without
modification, or if its going to be doing more than 1 encryption per second
with the same key, you shouldn't use time() as a salt.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 'Free' services with tokens/puzzles
Date: 5 Mar 2000 02:16:54 GMT
In a previous article, "Joseph Ashwood" <[EMAIL PROTECTED]> writes:
---snip---
>Needed: Source of assumed randomness (it is only necessary
>that the clients are not able to compute the values). A
>trusted network for server(s) and absolutely trusted
>client(s).
---snip---
Your solution will only work if there ARE trusted clients.
What if a formerly trusted client becomes corrupted? It is not at all unlikely
that a client behaves well only when he knows he is being monitored, i.e. in
the initial phase of the relation with the service provider.
----- 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: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Random bit generators
Date: Sat, 04 Mar 2000 18:47:18 -0800
Well, if the attacker can predict one of the streams and choose another then he has
already broken the cipher since he can
isolate the third. The very objective of combining streams is to obscure the
individual components.
So I think the issue is not if the resulting stream will be random if two of the three
are not but if it is indeed possible
predict one stream and select another.
Guy Macon wrote:
> In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] ([EMAIL PROTECTED]) wrote:
>
> >I do not think I am XORing anything.
>
> I never said that you were.
>
> >I am pseudorandomly selecting bits from one or the other.
>
> I understand that. I am just bringing up the question of how this
> method is better or worse than the XOR method so that I may learn
> more about the concept.
>
> Lets take an extreme example.
>
> Assume that we both have three sources of what we beilieve are
> random bits. You use the "chooser" method to arrive at a single
> bit stream. I XOR two of the bitstreams, then XOR the result
> with the third.
>
> Unknown to us, an attacker has partially compromised our security,
> and can predict one of the "random" bitstreams and can choose the
> other. Assume the third is true random. With my XOR systyem, the
> output is also true random. With your chooser method, the output
> is not true random.
>
> I picked this example to make XOR look good. I am in no way implying
> that XOR is better in more likely situations. As I said, I am just
> trying to get a handle on the advantages and disadvantages of what
> you are describing.
------------------------------
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Random bit generators
Date: Sat, 04 Mar 2000 19:02:19 -0800
Another way to express my function is this
F(x1, x2, x3) = x1.x3 + x2.~x3
It is susceptible to correlation attack since F agrees with x1 75% of the time and
with X2 75% of the time. So you may be right
that this is not any better than XOR. I was inpired by the idea of changing the length
of the bit string in each round and
thought that the formula above would be easier to implement. Well, it was just an idea.
BTW, how do you break 3 XORed congruential random number generators?
Guy Macon wrote:
> In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] ([EMAIL PROTECTED]) wrote:
>
> >I do not think I am XORing anything.
>
> I never said that you were.
>
> >I am pseudorandomly selecting bits from one or the other.
>
> I understand that. I am just bringing up the question of how this
> method is better or worse than the XOR method so that I may learn
> more about the concept.
>
> Lets take an extreme example.
>
> Assume that we both have three sources of what we beilieve are
> random bits. You use the "chooser" method to arrive at a single
> bit stream. I XOR two of the bitstreams, then XOR the result
> with the third.
>
> Unknown to us, an attacker has partially compromised our security,
> and can predict one of the "random" bitstreams and can choose the
> other. Assume the third is true random. With my XOR systyem, the
> output is also true random. With your chooser method, the output
> is not true random.
>
> I picked this example to make XOR look good. I am in no way implying
> that XOR is better in more likely situations. As I said, I am just
> trying to get a handle on the advantages and disadvantages of what
> you are describing.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Random bit generators
Date: 04 Mar 2000 22:02:52 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
([EMAIL PROTECTED]) wrote:
>Well, if the attacker can predict one of the streams and choose another
>then he has already broken the cipher since he can isolate the third.
Nonsense. Using the XOR method, he most certainly cannot.
>The very objective of combining streams is to obscure the individual
>components.
No. The very objective of combining streams is to make it harder for
an attacker to figure out what the result is.
>So I think the issue is not if the resulting stream will be random
>if two of the three are not but if it is indeed possible predict one
>stream and select another.
which is more likely, that an attacker can figure out one out of the
three streams, two out of the three, or all three? Isn't the point
of the exercise making an attackers job harder?
Of course I am very much open to the idea that the chooser method might
make the attackers job harder in situations other than the artificial
extreme case I wrote about, but to miss the point that making the
attacker's job harder is the purpose of the exercise does not give me
a great deal of confidence.
>
>Guy Macon wrote:
>
>> In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] ([EMAIL PROTECTED]) wrote:
>>
>> >I do not think I am XORing anything.
>>
>> I never said that you were.
>>
>> >I am pseudorandomly selecting bits from one or the other.
>>
>> I understand that. I am just bringing up the question of how this
>> method is better or worse than the XOR method so that I may learn
>> more about the concept.
>>
>> Lets take an extreme example.
>>
>> Assume that we both have three sources of what we beilieve are
>> random bits. You use the "chooser" method to arrive at a single
>> bit stream. I XOR two of the bitstreams, then XOR the result
>> with the third.
>>
>> Unknown to us, an attacker has partially compromised our security,
>> and can predict one of the "random" bitstreams and can choose the
>> other. Assume the third is true random. With my XOR systyem, the
>> output is also true random. With your chooser method, the output
>> is not true random.
>>
>> I picked this example to make XOR look good. I am in no way implying
>> that XOR is better in more likely situations. As I said, I am just
>> trying to get a handle on the advantages and disadvantages of what
>> you are describing.
>
>
>
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: very tiny algorithm - any better than XOR?
Date: 5 Mar 2000 03:04:36 GMT
In article <[EMAIL PROTECTED]>,
David Hopwood <[EMAIL PROTECTED]> wrote:
>> Each device has the cpu, 512 bytes of ram, and 1MB of eeprom. [...]
>> Since the key(s) are stored in eeprom, it does not count against the
>> 50 byte code space restriction. All the instructions on this processor
>> are either 16 or 32 bits long, so we have 25 instructions to work with.
>
>I assume that access to the EEPROM is slower than to the RAM, that it
>has a limited number of writes before expected failure, and that it may
>have to be erased/rewritten in blocks, rather than a byte or word at a time.
EEPROM is quite slow to write, and there is write wear as you mention.
Reading can be pretty fast. The idea is to use it read-only.
>The 20-30 byte RAM limitation is a more severe constraint than the 50 byte
>code size, and I'm not aware of any well-respected modern ciphers that
>would satisfy it directly.
The 50 byte code size limit is a MUCH harder constraint. There are
plenty of ciphers that can work fine with 20-30 bytes of RAM. DES/3DES,
Skipjack, GOST, TEA, Skipjack, etc. can all be done in that.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: 'Free' services with tokens/puzzles
Date: Sat, 4 Mar 2000 19:13:10 -0000
You'd need to modify the approach. I've been thinking on
just such a problem. So far the solution is as follows. When
a challenge block is needed, send it to several systems, if
your network has minority corruption you can use a simple
majority, which is likely to be a rather extreme majority in
most circumstances. The problem is that after a certain
corruption point, you start eliminating non-corrupt clients.
Alternately I see no reason that you could not run the
trusted client inside of your trusted server, but it doesn't
really solve the problem.
I did not mean that you designate certain long-term
customers as having trusted clients. I meant that you have a
private store of a small handful of computers, dedicated to
purely being the trusted clients. I was assuming that
somewhere in the budget of doing this, the money for a $300
(US) extra computer could be found, and that system could be
used as the trusted client.
Like I said there are a multitude of possible solutions, at
least 2 have been proposed on here, and I'm sure that almost
everyone has their own favorite.
Joe
------------------------------
From: [EMAIL PROTECTED] (Albert Jones)
Subject: bio-com. L.G.Lawrence: borderlands.com
Date: Sat, 4 Mar 2000 19:42:56 -0700 (MST)
------------------------------
From: [EMAIL PROTECTED] (Carl Byington)
Subject: Re: very tiny algorithm - any better than XOR?
Date: 5 Mar 2000 04:00:48 GMT
=====BEGIN PGP SIGNED MESSAGE=====
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>I assume that access to the EEPROM is slower than to the RAM, that it
>has a limited number of writes before expected failure, and that it may
>have to be erased/rewritten in blocks, rather than a byte or word at a
time.
Correct on all counts.
>The 20-30 byte RAM limitation is a more severe constraint than the 50 byte
>code size, and I'm not aware of any well-respected modern ciphers that
>would satisfy it directly. However, how about storing precomputed
keystream
>from a stream cipher in the EEPROM, as if it were a one-time pad? As
>content is decrypted, it replaces the corresponding part of the keystream.
>Decryption only requires the EEPROM to be read at the same rate as the
>encrypted content becomes available, so it should be reasonably fast.
We would need to have a block of data ready to write to eeprom, then
read the keystream block from eeprom, xor them, and write it back. That
would work but we only have one eeprom ram buffer. Hm, I will talk to the
hardware folks about this.
I presume you are talking about running the encryption offline, on some
more powerful processor, then loading that keystream into the eeprom.
We need to be able to load content multiple times into eeprom, so the
first load would clobber our precomputed keystream, and I don't think
we can afford to double the eeprom memory.
>While you're generating the stream (i.e. initially, and when the memory
>becomes "full", so that space for deleted data needs to be recovered),
>store any temporary data in the EEPROM if necessary, and load it back
>afterwards. That way you have the whole 512 bytes of RAM to play with
>for the encryption itself, and can use standard RC4 as the stream cipher
>(for example, 256 bytes of table space plus some space for buffering, if
>necessary).
We intended to encrypt on the fly as the data comes in to be loaded into
eeprom. I don't know if we can switch to an overlay structure like this
but will check.
>Of course this assumes that it is possible to put the device into a mode
>where it is not doing anything else, for long enough to precompute
>sufficient keystream and write it to EEPROM. (An alternative would be to
>make this part of the process of deleting stored content.)
It may be possible to have an "encrypting" state where the device does
little else.
>To reduce code size, I would recommend storing the RC4 state (i.e. S-box
>array and i, j) in the EEPROM, rather than the original key. Make sure
>to start with a state that it is actually the expansion of a key using
>the normal key schedule, because RC4 has some bad states otherwise.
We will be transmitting keys to the device, so the device will need to
compute its own s-box state. These keys are encrypted with the device
specific key before transmission to the device.
>Note that it is essential not to encrypt using a given piece of keystream
>more than once (so it would not be secure for the decryptor just to tell
>the encryptor what the current stream position is, for example). If there
>is only one entity encrypting content, all it needs to do is store the
>current RC4 state for each user. If there is more than one entity
encrypting
>content, this approach probably won't work as it stands.
>
>> >For example, RC4 can certainly be implemented in 50 bytes of code space
>> >(probably much less), so the only potential problem is its RAM
requirement.
>[...]
>> >Note that, as for any stream cipher, you should not use the same key
for
>> >more than one message, without adding a random salt.
>>
>> Thanks for the pointer to RC4. However, the system design at this time
>> implies that we will use the same key for all the content owned by the
>> same entity (person, family, whatever). It will not be unusual for one
>> key to protect a few megabytes of content.
>
>That's not a problem in itself, provided you don't use any part of the
>keystream more than once.
>
>> I presume that we need some secure mechanism of passing the random salt
>> to the decryptor.
>
>You don't really need salt for the approach suggested above.
>
>> We don't have 64 bytes of ram. From your comments above I take it you
>> would not use 5-bit RC4?
>
>IIRC, up to 4-bit RC4 has been broken, so no, I wouldn't.
>
>If you need more detailed design advice or programming, I'd be happy to
act
>as a consultant (under NDA if necessary).
I will ask about this. I would be more than happy to have someone that
knows what they are doing help with this. When this project started,
everyone assumed we had enough code space to do TEA. The failure of that
assumption has pushed me into trying to design a moderately secure but
very tiny algorithm, which is clearly outside the boundaries of my area
of competence.
- --
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
iQCVAgUBOMHbydZjPoeWO7BhAQEWvgP/b59rpPifgR2sQqXw111wOQCk6i+1/dRd
zcfGN1+Dct/mVlsJ4zELjX/JiWSpWkBLTvC7gNyXPw+zdzSmAd5YsyIjxoFnhdq6
ONNsntv/qJb73SXXITpF5QaRRAFqe8zOfUmDzUaf4sUP1GXDYms1MqY+3bBOmYUu
htF2YgJau6E=
=daNO
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
