keys and counters
Antony Clements
assume an unlimited counter
the user inputs a key... my name for example, the question is this.
K = sha256( key && counter)
would this constitute an OTP?
Greg Rose
No. It would constitute a stream cipher. Since you
probably want to transmit the counter in the
clear, an attacker can break it by guessing the
key, running it through sha256, XORing with the
ciphertext, and looking for non-random
distribution of the output. Even if you don't
transmit the counter value, the attacker just has
to guess correctly for this input, and the
legitimate receiver has to too, so it can't be too
hard.
All the ways to misuse an OTP still apply, but the
proof of security of OTP does *not* apply.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
Antony Clements
"Greg Rose" <g...@nope.ucsd.edu> wrote in message
news:gapd24$11c0$1...@ihnp4.ucsd.edu...
> No. It would constitute a stream cipher. Since you
> probably want to transmit the counter in the
> clear, an attacker can break it by guessing the
> key, running it through sha256, XORing with the
> ciphertext, and looking for non-random
> distribution of the output. Even if you don't
> transmit the counter value, the attacker just has
> to guess correctly for this input, and the
> legitimate receiver has to too, so it can't be too
> hard.
>
> All the ways to misuse an OTP still apply, but the
> proof of security of OTP does *not* apply.
Thanks Greg for catching me out on misusing the OTP term.
would the output of the hash always be unique with an unlimited counter?
Ertugrul Söylemez
As Greg already pointed out, no. That constitutes a stream cipher, and
not even a particularly secure one, because it doesn't provide forward
secrecy. You'll want to use some kind of chaining, for example:
keyStream key = iterate (\x -> sha256 (key ++ x)) ""
Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
Stefan Pinzel
>
> would the output of the hash always be unique with an unlimited counter?
>
>
Antony Clements
"Stefan Pinzel" <stefan...@iehk.rwth-aachen.de>
> No, since SHA256 is limited to 256 bits.
sha256 has 256 bit output, just like sha512 is a 512 bit output.
but that was not the question.
if you have a string "hello world!" and append a counter and then hash it,
how many times can the counter be incremented before there is a collision in
the hash, that is what i am asking. it has nothing to do with the size of
the hash output.
as Mr Rose pointed out that if the counter is transmitted in the clear, then
the attacker can guess the key and recreate the hash, while it's possible,
it's not exactly in the realms of feasable, neither your answer or his
answer the two fundamental questions being asked..
question 1) if there is a counter of unlimited size that is incremented
every time the key function is run, would each >unique< hash result
constitute an OTP
question 2) how many times can the counter be incremented before there is a
collision in the sha256 output. ie producing the same output twice.
Paulo Marques
You mean "One Time Password" or "One Time Pad"?
--
Paulo Marques
Software Development Department - Grupo PIE, S.A.
Phone: +351 252 290600, Fax: +351 252 290601
Web: www.grupopie.com
"Who is general Failure and why is he reading my disk?"
David Eather
> "Stefan Pinzel" <stefan...@iehk.rwth-aachen.de>
>> No, since SHA256 is limited to 256 bits.
>
> sha256 has 256 bit output, just like sha512 is a 512 bit output.
>
> but that was not the question.
I think that was the question. From what you say below I think you did
not phrase it very well.
>
> if you have a string "hello world!" and append a counter and then hash it,
> how many times can the counter be incremented before there is a collision in
> the hash, that is what i am asking. it has nothing to do with the size of
> the hash output.
>
> as Mr Rose pointed out that if the counter is transmitted in the clear, then
> the attacker can guess the key and recreate the hash, while it's possible,
> it's not exactly in the realms of feasable, neither your answer or his
> answer the two fundamental questions being asked..
>
> question 1) if there is a counter of unlimited size that is incremented
> every time the key function is run, would each >unique< hash result
> constitute an OTP
No. A OTP has very specific requirements that might be summarised as
each bit being totally unpredictable regardless of how many bits you
know that were generated before or after the one you are guessing. A
hash function operated in such a counter mode as you suggest does not
have this property - if I can guess or discover the input to the first
block then I will know all the other blocks.
You might think that some attacks are unreasonable/infeasible but do you
really know what is possible to the world's largest employer of
mathematicians, who have had for many years the world's largest computer
budget and unlimited access to 60 plus years of classified research or
what is possible for any of the other multi-billion dollar "smaller" big
brothers?.
If you receive a valid answer that is not what you wanted, whose fault
is that? More accurate questions and if needed, follow questions would
be appropriate. Serious crypto has a serious standard because of the
type of attacks and types of opponents possible. Recreational
cryptography is different and if that is what you want you could join
the ACA.
>
> question 2) how many times can the counter be incremented before there is a
> collision in the sha256 output. ie producing the same output twice.
>
>
As a general guide, a collision is expected after approximately the
square root of all possible outputs has been generated. In the sha256
case, after about 2**128 iterations you would expect a collision. After
that collisions come much faster.
Also, 2**128 also represents the brute force approach - there may be
algorithmic techniques that will get you there much sooner. An example
of this happening is the 128 bit hash function MD4. At first MD4 was
thought secure, even if wasn't very conservative. Collisions which
should have taken 2**64 computations can now, in some cases, be done in
ten minutes with a pen and pencil.
David Eather
> "Stefan Pinzel" <stefan...@iehk.rwth-aachen.de>
>> No, since SHA256 is limited to 256 bits.
>
> sha256 has 256 bit output, just like sha512 is a 512 bit output.
>
> but that was not the question.
>
> if you have a string "hello world!" and append a counter and then hash it,
> how many times can the counter be incremented before there is a collision in
> the hash, that is what i am asking. it has nothing to do with the size of
> the hash output.
No, it has everything to do with the size of the hash output.
Unruh
>"Stefan Pinzel" <stefan...@iehk.rwth-aachen.de>
>> No, since SHA256 is limited to 256 bits.
>sha256 has 256 bit output, just like sha512 is a 512 bit output.
That means that the hash output can only have 2^256 outputs. If you feed in
more than that in inputs, some of the outputs must be the same.
>but that was not the question.
>if you have a string "hello world!" and append a counter and then hash it,
>how many times can the counter be incremented before there is a collision in
>the hash, that is what i am asking. it has nothing to do with the size of
>the hash output.
It certainly does. See above. In general for a 256 bit output, you will get
a collision after 2^128 inputs (birthday paradox).
>as Mr Rose pointed out that if the counter is transmitted in the clear, then
>the attacker can guess the key and recreate the hash, while it's possible,
>it's not exactly in the realms of feasable, neither your answer or his
>answer the two fundamental questions being asked..
>question 1) if there is a counter of unlimited size that is incremented
>every time the key function is run, would each >unique< hash result
>constitute an OTP
No.
>question 2) how many times can the counter be incremented before there is a
>collision in the sha256 output. ie producing the same output twice.
2^128 times on average.
rossum
<antony....@bigpond.com> wrote:
>
>"Stefan Pinzel" <stefan...@iehk.rwth-aachen.de>
>> No, since SHA256 is limited to 256 bits.
>
>sha256 has 256 bit output, just like sha512 is a 512 bit output.
>
>but that was not the question.
It was the question you asked: "would the output of the hash always be
unique with an unlimited counter?"
The anser is indeed "no", as Stefan said. There are only 256 bits in
the SHA256 output, which means that there are a maximum of 2^256
possible outputs from SHA256 and no more. At some point as you
increment your counter you will get a duplicate output which will not
be unique. Normally you will start seeing collisions (i.e. duplicated
outputs) after about 2^128 outputs. Even if you have a very carefully
chosen input then you must start seeing duplicates after 2^256 inputs.
You do not need a counter bigger than the output from your hash
function.
>
>if you have a string "hello world!" and append a counter and then hash it,
>how many times can the counter be incremented before there is a collision in
>the hash, that is what i am asking. it has nothing to do with the size of
>the hash output.
Yes it does. Suppose your hash output had a size of 4 bits: SHA004.
The output can only take sixteen values so after your seventeenth
input you must have at least one collision. The size of the hash
determines the maximum number of different outputs and hence the
probability of collisions.
rossum
Antony Clements
your answers.
I have two additional questions, is it possible to create an OTP without
some source of true randomness (ie radioactive decay)? My inclination at
this point, is no. But since I have been wrong about so many things before,
I will ask a conditional question. If it is possible to create an OTP
without a source of true randomness, how would someone such as myself go
about it?
rossum
<antony....@bigpond.com> wrote:
>thank you one and all for your answers to my questions, and the reasons for
>your answers.
>
>I have two additional questions, is it possible to create an OTP without
>some source of true randomness (ie radioactive decay)? My inclination at
>this point, is no.
You are correct. An OTP requires a source of true randomness to
generate the keystream.
>But since I have been wrong about so many things before,
>I will ask a conditional question. If it is possible to create an OTP
>without a source of true randomness,
Not as far as I am aware.
>how would someone such as myself go about it?
Possibly use quantum entanglement to make two radioactive sources that
produced exactly the same true random stream. This would not be easy.
rossum
Greg Rose
In reality no, but for practical purposes yes. You
should be able to generate about 2^128 outputs
before one of them is repeated, and in practice
this is good enough.
Mark Wooding
> "Antony Clements" <antony....@bigpond.com> wrote:
[snip]
>> K = sha256( key && counter)
>>
>> would this constitute an OTP?
>
> As Greg already pointed out, no. That constitutes a stream cipher, and
> not even a particularly secure one, because it doesn't provide forward
> secrecy. You'll want to use some kind of chaining, for example:
>
> keyStream key = iterate (\x -> sha256 (key ++ x)) ""
I'll assume the above is Haskell. This is worse than Antony Clements'
counter-based scheme. Suppose we pretend that F(K, x) = SHA256(K || x)
is a pseudorandom function for fixed-length x. (I don't know of any
evidence to the contrary: the usual extension attack against Merkle-
Damgaard hashes doesn't apply because I fixed the input length.)
Then Clements' construction
G(K) = F(K, 0) || F(K, 1) || ... || F(K, q - 1)
is a pseudorandom generator, with
insec(prg, G, t + O(q)) <= insec(prf, F, t, q)
On the other hand, your feedback construction
s_0 = F(K, I), s_{i+1} = F(K, s_i) (for 0 <= i < q)
G'(K) = s_0 || s_1 || ... || s_{q-1}
is distinguishable (it falls into a cycle) if the PRF encounters a
collision s_i = s_j (for i /= j). This happens with probability at most
q (q - 1)/2, and there's no other problem, so
insec(prg, G', t + O(q)) <= insec(prf, F, t, q) + q (q - 1)/2
(security proofs left as easy exercises).
So your feedback construction has security which degrades quadratically
for no especially apparent reason. (It also introduces a data
dependency which inhibits parallel implementation, and complicates the
description.)
I've cheated slightly. Clements' scheme actually wanted an `unlimited
counter', which would lead to a distinguisher based on the extension
attack for sufficiently large messages, not to mention eventually
exceeding the domain of SHA256.
-- [mdw]
Ertugrul Söylemez
I don't understand this. If I'm not totally wrong, then where
h k x = sha256 (k ++ x)
the function h k is a hash function with 2^256 possible outcomes. A
cycle in repeating it should have a length of 2^254 in average. There
may be short cycles, but the probability of encountering them should be
neglible.
> (It also introduces a data dependency which inhibits parallel
> implementation, and complicates the description.)
Indeed, that is true.
> I've cheated slightly. Clements' scheme actually wanted an `unlimited
> counter', which would lead to a distinguisher based on the extension
> attack for sufficiently large messages, not to mention eventually
> exceeding the domain of SHA256.
This is just as neglible. There is really nothing wrong with Anthony's
generator, unless an attacker manages to learn the internal state.
Ertugrul Söylemez
> This is just as neglible. There is really nothing wrong with
> Anthony's generator, unless an attacker manages to learn the internal
> state.
That typo is embarrassing. It's "Antony" of course. =)
Sorry.
Greg Rose
Ertugrul Söylemez <e...@ertes.de> wrote:
>Mark Wooding <m...@distorted.org.uk> wrote:
>> On the other hand, your feedback construction
>>
>> s_0 = F(K, I), s_{i+1} = F(K, s_i) (for 0 <= i < q)
>> G'(K) = s_0 || s_1 || ... || s_{q-1}
>>
>> is distinguishable (it falls into a cycle) if the PRF encounters a
>> collision s_i = s_j (for i /= j). This happens with probability at
>> most q (q - 1)/2, and there's no other problem, so
>>
>> insec(prg, G', t + O(q)) <= insec(prf, F, t, q) + q (q - 1)/2
>
>I don't understand this. If I'm not totally wrong, then where
>
> h k x = sha256 (k ++ x)
>
>the function h k is a hash function with 2^256 possible outcomes. A
>cycle in repeating it should have a length of 2^254 in average. There
>may be short cycles, but the probability of encountering them should be
>neglible.
I'm afraid you're mixed up. You're quoting the
result for a pseudorandom *permutation*, but the
hash function (keyed or not) is not a permutation.
Chapter 2 of the Handbook of Applied Cryptography
explains both cases very well.
Ertugrul Söylemez
> In article <20080930160...@ertes.de>,
> Ertugrul Söylemez <e...@ertes.de> wrote:
> >Mark Wooding <m...@distorted.org.uk> wrote:
> >
> >> On the other hand, your feedback construction
> >>
> >> s_0 = F(K, I), s_{i+1} = F(K, s_i) (for 0 <= i < q)
> >> G'(K) = s_0 || s_1 || ... || s_{q-1}
> >>
> >> is distinguishable (it falls into a cycle) if the PRF encounters a
> >> collision s_i = s_j (for i /= j). This happens with probability at
> >> most q (q - 1)/2, and there's no other problem, so
> >>
> >> insec(prg, G', t + O(q)) <= insec(prf, F, t, q) + q (q - 1)/2
> >
> > I don't understand this. If I'm not totally wrong, then where
> >
> > h k x = sha256 (k ++ x)
> >
> > the function h k is a hash function with 2^256 possible outcomes. A
> > cycle in repeating it should have a length of 2^254 in average.
> > There may be short cycles, but the probability of encountering them
> > should be neglible.
>
> I'm afraid you're mixed up. You're quoting the result for a
> pseudorandom *permutation*, but the hash function (keyed or not) is
> not a permutation. Chapter 2 of the Handbook of Applied Cryptography
> explains both cases very well.
Indeed. I missed this. Ertugrul is going to read. Thank you.
David Wagner
>... forward secrecy ...
I think you've misunderstood or misapplied the notion of forward
secrecy.
I also endorse Mark Wooding's comments.
Ertugrul Söylemez
> Ertugrul Söylemez wrote:
>
> >... forward secrecy ...
>
> I think you've misunderstood or misapplied the notion of forward
> secrecy.
I misapplied it, because I confused it with something different, which I
used to call "forward secrecy" until now. Now I'm unsure what to call
it. I think you know what I mean.
> I also endorse Mark Wooding's comments.
Yes, I'm reading the HAC again. How would one achieve what I wrongly
called "forward secrecy" above? If it's not clear what I meant: If an
attacker learns the state of the generator, they can easily reconstruct
the entire key stream. A method with feedback would prevent that.
Maybe feedback together with a counter?
Mark Wooding
> If an attacker learns the state of the generator, they can easily
> reconstruct the entire key stream. A method with feedback would
> prevent that.
I think I see what you want; this isn't a commonly expected property of
PRGs, though it is expected of things like Yarrow and Fortuna [1].
Correct me if I'm wrong: You want an adversary to be unable to deduce
the start of an output stream if he compromises the generator part-way
through (and learns its entire state).
Your design didn't actually achieve this. Let me recall it:
s_0 = I s_{i+1} = F(K, s_i) for 0 <= i < n
G'(K) = s_0 || s_1 || ... || s_{n-1}
for a fixed value of I (you chose the empty string). So an adversary
who compromises the generator learns K (obviously, since that's needed
to compute every block) and already knows I (because it's fixed);
therefore he can reconstruct the stream from the beginning.
> Maybe feedback together with a counter?
That would avoid the quadratic security loss.
The intuition I find useful when thinking about PRFs is: every use of a
PRF can be replaced by a fresh independent uniformly random string if
every input to the PRF is distinct. So arrange for the inputs to be
distinct, and you have random output; if inputs collide, you usually
lose. The security proof is then an effort to bound the probability of
a collision.
Counters are good because you can arrange for them always to be
distinct. Adding a counter to your design, in addition to the feedback,
i.e.,
s_0 = F(K, I, 0) s_{i+1} = F(K, s_i, i) for 0 <= i
ensures collisions are impossible, but doesn't actually provide the
security against compromise; however, choosing I unpredictably and
keeping it secret would do fine.
[1] What are these called? Pseudorandom generators are something
different.
-- [mdw]