Re: Any pitfals of my stream cipher?

On Sun, 24 Jan 2010 12:55:37 -0800, Joseph Ashwood wrote:

"Captain Data" <sorry@xxxxxxxxxx> wrote in message
news:00045131$0$2175$c3e8da3@xxxxxxxxxxxxxxxxxxxx
Any problems with this proposed setup?


Probably. If you had actually described a cipher system then a more
certain answer could be given. Just to cover the problems I see
immediately:

Alice wants to send a message to Bob. In the past they have either
meeting each other to agree on a secret master key, or via an
asynchronous encryption system perhaps, so they have some shared secret
but it is no where near big enough to use as a OTP. Maybe it is just a
shared password or something.

Just say that there is a key K, and its length. Anything more ans you're
just trying to hide things when you should be revealing them.

Alice has a presumably-truly random number source, and wants to send
encrypted messages to Bob every so often.

1) Alice grabs a truly random number (probably doesn't have to be truly
random but it will be in this example) 2) Alice sends this value
directly to Bob as cleartext 3) Now both Alice and Bob use this value
as a salt, with which they use their master password to derive the
session key.

"This value" is known as an IV or Initialization Vector, just say there
is one, and its length.

If the hash algorithm (WHIRLPOOL) isn't broken then this should be
perfectly safe.

That's what your disclosure is supposed to prove, stating it just makes
it look like you're hiding something, in this case nearly everything.
Just say that the hash(...) is WHIRLPOOL.

Random numbers *probably* mean no same value twice, at least not
predictably.

Actually that's not what it means.

4a) Alice uses the first portion of this session key to seed a PRNG to
generate a keystream.

Which PRNG? How is the session key derived? How long is the session key?
How long is the keystream?

The PRNG is presumed to probably not generate any detectable patterns
until maybe around 13kb of output or so.

That's horrible security requirements for a CSPRNG, if your system was
fully described maybe it would be better.

4b) Another portion of the session key is used as a negative offset on
the default number of bytes to transmit before expiring the session
key.

How long is the session key? Which portion of the session key? Why is it
just the "default?" This is the disclosure it should be the actual
number.

4c) Another 2 portions of the session key are reserved for the MAC.

What MAC? Which portions of the session key? How long is the session
key? How long are these portions of the session key? How are the
portions derived? etc.

4d) The final portion of the session key is an XOR mask for the
transmission code.

What is the transmission code? How long is the session key? How long is
the "final portion" of the session key? How is the "final portion"
derived?

5) Once the final length is reached, a certain portion of truly random
data is added to the end of the message so far.

What is the "final length?" How is it known how much data is to be
removed? Have you thought of just actually using variable names? It
really does help.

6) Now the transmission code is added, more on this soon.

Read further on, that's not what a transmission code it. It’s a sequence
indicator, and a horribly weak one at that.

7) Now Alice appendeds the MAC using the 2 session key portions, skp1,
skp2. MAC = hash(skp1.hash(skp2.message)), where "." means
concantenation.

If you generate skp1 and skp2 correctly then this is secure, and called
HMAC.

8) So now the MAC covers the portion of the message in this
transmission, the transmission code, and the truly random "salt" to
generate the next successive session key from, using the shared master
key.

And what do you do with the MAC?

Also this isn't a stream cipher, it appears to be a method of using a
stream cipher to build a block system, just use a block system it will
save you a lot of headaches and errors.

Normally the transmission code is just zero (after re-applying its XOR
mask from the session key), to indicate that this is not the final
message.

So there is a terminal length for the system.

However, when the transmission code is not zero, it is used as a
negative offset to separate what portion of the final transmission
session is the end of the message, and the rest is just junk.

This needs to be stated much earlier, its called "padding", is not a
"negative offset" it is a padding length.

I think that so long as the hash and the PRNG are not rubbish, then the
only way is to brute force the master key

Actually you've got other avenues for attack already available. I'll
introduce KDF the Key Derivation Function. You have relations between
the keys, specifically there is a series of equations that you haven't
described SKP[i] = KDF[i](K, IV)
so a small weakness in the PRNG will show biases in this series and some
fairly basic algebra says that it is likely reducable.

And that Alice and Bob can keep the same master key for as long as they
are comfortable with.

Far from it. Once the system has reached the point where a key can be
derived the rest of the system fails quickly.

Based on the description I wouldn't trust it with anything. Once a
complete description has been made it is possible that my mind will
change.
Joe


Thankyou for your indepth reply. My goal here was to come up with a
fairly simple encryption cipher all on my own, but designing a block
cipher with various rounds etc is way out of my league, so my idea was to
use the output of a CSPRNG as a XOR mask generator to encypt plaintexts
with (like a stream cipher). I do not plan to make my own hash or PRNG
function either.

Right now I'm thinking of using WHIRLPOOL for all hashes, and also using
WHIRLPOOL as the CSPRNG by running it in "counter mode" (however I am
playing around with relevant bits of the Keccak source code, because I
just have a hunch that it is probably better to use a different alorithm
to generate the XOR mask which I called the "key stream" above, although
I don't know if that is correct terminology).

I appologise to you if I fail to explain things concisely enough. I think
this system is very simple, but I am sharing my idea because I need help
in understanding if it is broken or not.

I'll continue by listing some assuptions:

1) Sharing of a common secret (the master key) is out of scope of my
system. I assume that they have one already, but they don't want to use
it up quickly because it is inconvenient to share further secrets.

2) So long as malicous Martin is reduced to brute forcing the master key
without any useful hints via either the cipher text or transmission
protocol, then I consider the system as secure as I want it (or could get
it).


The reason why it wants some truly random numbers is because otherwise it
will have to maintain a database of used nonces. And if Alice uses the
same master key on multiple installs of the program then obviously the
program has no way of knowing what other instances have used. If the
program uses a block of say 256 truly random entropy bits (from a
computerised geiger counter perhaps), then how long is martin going to
have to monitor Alice's communications before he is likely to get a
repeat? Maybe only once but hopefully much much *much* longer. I know
that this isn't theoritcally safe but I assumed that it was okay to
pretend it probably will be in practice.

If you say it really isn't, then I'll just implement a database of used
nonces and add a warning saying to never re-use a master password on
different installs of the program without surviving the used-nonce
database.


Here is your better description, I hope it is clear enough. Comments are
right above the line that they pertain to.

The intended use:

I am going to create a computer program, for hobyist reasons, that will
ask for A) filename for the master key, B) plaintext filename, C) large
file of truly random numbers, D) IP address where receiver is also
running the same program in listen mode.

Master-Key is variable length, it's what ever the users decide on, from
bytes to gigabytes.
IV is variable length, it's what ever I the programmer decide on, from
bytes to gigabytes.


PSUEDO-CODE:

path_to_MK = <user_input>
path_to_IV = <user_input>

char* MK = fopen(path_to_MK,"r"), fread etc, untill we have it all.
char* IV = fopen(path_to_IV,"r"), fread etc, let's say 512 bytes.

/* Now Bob has what he thinks is the same IV as the sender (us), the IV
_should_ be a nonce. */

transmit(Bob, IV);

/* Bob will be doing this too. If the transmission wasn't adulterated
then he will be able to decrypt our message, if it was then he won't be
able to decrpyt but that shouldn't help the attacker except as a denial
of service against poor Bob. */

char SessionK[512] = WHIRLPOOL(MK || IV);

size_t expire_after = get_session_expiry_count(SessionK);

PRNGInstance* prng = seed_CSPRNG(SessionK);

size_t bytes_sent;

/* Transmit our encrypted data for as long as this session will last */

for(bytes_sent = 0; bytes_sent < expire_after; bytes_sent++)

{

char out = plaintext[pos] ^ get_next_byte_from_CSPRNG(prng);

transmit(Bob,out);

}

/* Now our session has expired, so we grab a new IV. It will first get
new possible IV values, but then check them against the list that have
already been used for this master key, until it finds an acceptable one */

IV = get_new_IV(possible_IV_values, path_to_used_nonce_db(MK));

NextSessionKey = WHIRLPOOL(MK || IV);




And so it continues, by transmitting the IV to Bob, and then more cipher
text using the new sessionKey.

Session keys change frequently enough so that the CSPRNG won't be over
used, and so that each transmission isn't too long.

The transmit function will buffer output and send as much as it can in
each packet. So all of these transmitted values run together. If the IV
is a nonce sourced from a Truly random number generator (instead of just
being a linearly counting nonce), then how does martin even notice that
maybe the next transmission sequence using a new session key has started,
unless he has already derived the first session key himself?


Transmission code / Sequence Indicator:

Now then, because the length of each transmission sequence is determiend
by a portion of the session key, it's just the luck of the draw, there is
no way to assume that the plaintext will somehow magically be of the
exact same length, therefore there needs to be a way to say how much of
the last transmission is just padding. When Bob's program checks the
Sequence Indicator and sees that it is not zero, then he knows that it
must be the last transmission block, and can now determine where the
plaintext ends so that he can write out the original file, without an
essentialy random amount of junk padding appended to the end of it.

However, I thought that if every transmission sequence that was not the
last would have a block of zeroes of the bit width that the Sequence
Indicator is (let's say it's 16 bits because that handles transmission
blocks of a few kB each), then Martin might learn something about the
ciphertext, because of that structure.

Some more notes or assumptions:

However, if the Sequence Indicator (which is usually zero) was to be
XOR'd with the CSPRNG mask, then that might be a tiny portion of a known
plaintext attack, so it is instead XOR'd with a separate portion of the
SessionKey.

If 512 bytes of SessionKey isn't enough to be divided up amongst these
myriad uses, then the SessionKey might be 10 different hashes appended
together. It can be upsized as much as I need to, to get a working design.

Also every transmission sequence has a HMAC on the end that covers the
Sequence Indicator and the cipher text, the HMAC could also be obscured
by a portion of the session key if need be but I don't think that is
necesary.

So sure, bits of the SessionKey are readily available in the transmission
text, but so what? It is generated by a secure hash of the IV using a
common secret as a salt. So I will pretend that different portions of the
session key are independant.

Also, sure the first IV is also the first segment of data, and it is sent
as cleartext, so Martin has the first IV. But he needs to secret key MK
because MK is the salt for the hash of the IV that derives the first
SessionKey.

So in the end the system is safe enough so long as WHIRLPOOL isn't
broken. Safe being martin has no better method than brute forcing hash
salts (the MK).

If I am fundamentally wrong can you please tell me where?

.

Relevant Pages

  • Re: Hashing methods for giant keys
    ... Since there is a different session key for every message I ... Simply XORing each character of the password with a different ... The cipher text is twice the length ... second byte holds a composite key that is loaded into a simple array. ...
    (sci.crypt)
  • Re: SRP + 3DES - secure enough?
    ... It will not be feasible to recover the keys given only ... cipher text from the handshakes. ... You can read the wikipedia description of DES for more information on how the session key is used to produce the pseudo-random cipher-text from the plain-text. ...
    (sci.crypt)
  • Re: Any pitfals of my stream cipher?
    ... their master password to derive the session key. ... How long are these portions of the session key? ... What is the transmission code? ... Also this isn't a stream cipher, it appears to be a method of using a stream cipher to build a block system, just use a block system it will save you a lot of headaches and errors. ...
    (sci.crypt)
  • Re: Any pitfals of my stream cipher?
    ... but I think it would be bad to use the master key ... Alice and Bob have to assume that Martin ... The direction that I was coming from was that OTP is the best, ... possible salts untill he finds one that generates the right session key ...
    (sci.crypt)