Discussion:
Question on the security of sequentially hashing
David
2004-11-22 08:36:04 UTC
Raw Message
Hi all,

I am calculating keys derived from the same initial secret S for a
group of N users. I want the N users to be able to generate in
sequential time intervals Ti the same key Ki without even having to
communicate. For this purpose, I calculate sequentially Ki = h(S+i),
being Ki each different key to be calculated, S the initial secret, i
an integer and h () a hash function. For instance:
K0 = h(S),
K1 = h(S+1),
K2 = h(S+2),
...
Kn = h(S+n).

Knowing this the pattern of Ki's:
- Is the scheme forward secure, assuming the attacker cannot ever
compromise S? i.e. assuming the attacker compromises a set of Ki's,
can he then infer any Kj with j>i (or even S) by knowing the pattern?

David
David Wagner
2004-11-24 06:59:42 UTC
Raw Message
Post by David
I am calculating keys derived from the same initial secret S for a
group of N users. I want the N users to be able to generate in
sequential time intervals Ti the same key Ki without even having to
communicate. For this purpose, I calculate sequentially Ki = h(S+i),
being Ki each different key to be calculated, S the initial secret, i
an integer and h () a hash function.
If h is a cryptographic hash with strong properties and S is long enough,
then this will probably work in practice. However, I'd recommend a slight
variant on it as more robust: Ki = F(S,i), where F is some PRF (pseudorandom
function), such as SHA1-HMAC, AES-OMAC, etc. Your construction uses the
hash function in a way it wasn't really designed for. The latter construction
uses the PRF in exactly what it was intended for. The risk of using your
approach is probably minor in practice, but I prefer using primitives that
are best-matched to your requirements -- this reduces the likelihood they
will fall short of what you were hoping for.
Michael Amling
2004-11-24 07:00:27 UTC
Raw Message
Post by David
Hi all,
I am calculating keys derived from the same initial secret S for a
group of N users. I want the N users to be able to generate in
sequential time intervals Ti the same key Ki without even having to
communicate. For this purpose, I calculate sequentially Ki = h(S+i),
being Ki each different key to be calculated, S the initial secret, i
K0 = h(S),
K1 = h(S+1),
K2 = h(S+2),
...
Kn = h(S+n).
- Is the scheme forward secure, assuming the attacker cannot ever
compromise S? i.e. assuming the attacker compromises a set of Ki's,
can he then infer any Kj with j>i (or even S) by knowing the pattern?
If h() is good, then S and all the other keys are safe from an
attacker who has some set of the keys.
Note: What is the "forward secure" property? Apparently it is
secrecy, then previous keys could not be derived by an attacker who got
S. Your scheme does not have forward secrecy.

--Mike Amling
David Wagner
2004-12-14 04:14:25 UTC
Raw Message
as, as we
pointed out in paragraph 61, must spend their days doing what they are
told to do in the way they are told to do it. Even most people who are
in business for themselves have only limited autonomy. It is a chronic
complaint of small-business persons and entrepreneurs that their hands
are tied by excessive government regulation. Some of these regulations
are doubtless unnecessary, but for the most part government
regulations are essential and inevitable parts of our extremely
complex society. A large portion of small business today operates on
the franchise system. It was reported in the Wall Street Journal a few
years ago that many of the franchise-granting companies require
applicants for franchises to take a personality test that is designed
to EXCLUDE those who have creativity and initiative, because such
persons are not sufficiently docile to go along obediently with the
franchise system. This excludes from small business many of the people
who