The Random Oracle Methology for designing cryptographic protocols
consists of two steps:
1. design an ideal system in which all parties (including the
adversary) have oracle access to a truly random function, and proves
the security of this ideal system.
2. replaces the random oracle by good cryptographic hashing function
such as SHA-1.
Thus, one obtains an implementation of the ideal system.

It's pointed out that a cryptographic protocol may be secure in random
oracle model, but not secure when the random oracle is replaced by a
cryptographic hash function. (The Random Oracle Methodology,
Revisited).

Maybe we can revise the Random Oracle Methology to a "Pseudorandom
Oracle Methology":
1. design an ideal system in which all parties (including the
adversary) have oracle access to a pseudorandom function, and proves
the security of this ideal system.
2. replaces the pseudorandom oracle by a good cryptographic hashing
function such as SHA-1.

Based on the assumption that a good cryptographic hash function is a
pseudorandom function, the above method should be able to guarantee
the security of the implementation of the scheme. In fact, it's an
analogy to modeling the block cipher as pseudorandom permutation to
analyze the security of protocols based on block cipher, a method
presented in some literatures.

My questions are:
1. Is it a commonly accpeted assumption that a good cryptographic hash
function such as SHA-1 is pseudorandom function?
2. Is the "Pseudorandom Oracle Methology" discussed or implied in any
paper/textbook?

Thanks,
Jiang

From:	jwu1 at lakeheadu.ca
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	23 Jan 2005 02:07:22 -0800

David Wagner wrote:
> >In short, my question should be modified as follows:
> >Is it a commonly accpeted assumption that a good cryptographic hash
> >function such as SHA-1 is an instance of pseudorandom function, to
> >which only oracle access is permitted, and whose key is unknow to
any
> >party?
>
> I don't understand the question, but I am certain that your idea
> doesn't work.
>
> Do you mean, Is F(x) = SHA-1(x) a pseudorandom function? No, clearly
> not. If I am given a function f and want to know whether it is truly
> random or not, I can compute f("hello") and check whether f("hello")
> = aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d. In case equality holds,
> I conclude that it is not a random function. Note that if f = SHA-1,
> then I will always successfully reject f as "not random", while if
> f = a random function, then I will successfully accept f as "random"
> (except with probability 1/2^160). So SHA-1 is not pseudorandom.
>
> Do you mean, Is F_k(x) = SHA-1-HMAC_k(x) a pseudorandom function?
> The answer in this case is yes, it is pseudorandom. If a
computationally
> limited adversary is given an oracle for F_k (but is NOT given k),
> the adversary cannot distinguish F_k from random.
>
> However, the latter fact doesn't help you build a Pseudorandom Oracle
> Methodology, because you are between a rock and a hard place. When
you
> instantiate the Pseudorandom Oracle to get a real concrete scheme,
> do you publish k? If k is kept secret, then you cannot instantiate
> the Pseudorandom Oracle by SHA-1-HMAC_k(.), since no one (not even
> the good guys) will be able to compute this function without
knowledge
> of k, so you are stuck. If you publish k and reveal it to the world,
> then SHA-1-HMAC_k(.) is no longer pseudorandom once k is known to the
> adversary, so you are again. Either way, your idea doesn't work.

Understand. In short, a pseudorandom function can not be instantiated
as a hash function.

My problem arised from the expression in Step 1:
1. design an ideal system in which all parties have oracle access to a
"pseudorandom function".

By saying the "pseudorandom function", I actually mean a "pseudorandom
oracle", which is an instance randomly selected from the subgroup of
all the functions X->Y. By contrast, a random oracle is an instance
randomly selected from all the functions X->Y.

With this correction, the "Pseudorandom Oracle Methodology" should work
since the "pseudorandom oracle" can be instantiated as a hash function
(just like the random oracle is instantiated as a hash function in the
Random Oracle Methodology). But as Aldar pointed out below,
"Pseudorandom Oracle Methodology" doesn't seem to improve the Random
Oracle Methodology. It's the same as the Random Oracle Methodology
except in modeling it uses "pseudorandom oracle" instead of the true
random oracle. It will encounter the same difficulties as the Random
Oracle Methodology.

>
> I think you are overlooking the difficulty of taking an ideal scheme
> proven secure in the (Pseudo)Random Oracle Model and instantiating it
> to get a real, concrete protocol.

From:	jwu1 at lakeheadu.ca
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	22 Jan 2005 17:32:13 -0800

astiglic@okiok.com wrote:
> Jiang Wu wrote:
> > My questions are:
> > 1. Is it a commonly accpeted assumption that a good cryptographic
> hash
> > function such as SHA-1 is pseudorandom function?
>
> You can construct a secure PRF from SHA-1, but the resulting
> construction needs a cryptogrpahic key which you need to pick
> uniformaly at random and keep secret.
>
My question is somewhat vague. It's about how to model a hash function.
I explain it as follows:

The Random Oracle Model expresses a hash function as a random function:
an instance function randomly taken from all possible functions
X->Y (X is the message set and Y is the hash value set), and we have
only oracle access to it. "Have only oracle access" implies we cannot
invert it.

Since Random Oracle Model is an ideal model, we may define a more
realistic model for hash function:
Hash function is a an instance function randomly taken from a subset of
of all possible functions X->Y (this matches the definition of
pseudorandom function), and we have only oracle access to it.

In both of the two models, the key (the index of the instance function)
can be unknown to any parties.

In short, my question should be modified as follows:
Is it a commonly accpeted assumption that a good cryptographic hash
function such as SHA-1 is an instance of pseudorandom function, to
which only oracle access is permitted, and whose key is unknow to any
party?

> > 2. Is the "Pseudorandom Oracle Methology" discussed or implied in
any
> > paper/textbook?
>
> The proofs of security for modes of encryption (like CBC) are based
on
> the use of a PRF, and then in practice the PRF is replaced by a
secure
> block cipher (which acts more like a PRP, but there is a known
> reduction from PRF to PRP security). But in those cases, you need to
> pick a key that you keep secret. If you just use SHA-1 with no key,
> then it is clear that you don't have a PRF and all bets are off.
> --Anton

From:	David Wagner
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	Sun, 23 Jan 2005 02:07:16 +0000 (UTC)

>In short, my question should be modified as follows:
>Is it a commonly accpeted assumption that a good cryptographic hash
>function such as SHA-1 is an instance of pseudorandom function, to
>which only oracle access is permitted, and whose key is unknow to any
>party?

I don't understand the question, but I am certain that your idea
doesn't work.

Do you mean, Is F(x) = SHA-1(x) a pseudorandom function? No, clearly
not. If I am given a function f and want to know whether it is truly
random or not, I can compute f("hello") and check whether f("hello")
= aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d. In case equality holds,
I conclude that it is not a random function. Note that if f = SHA-1,
then I will always successfully reject f as "not random", while if
f = a random function, then I will successfully accept f as "random"
(except with probability 1/2^160). So SHA-1 is not pseudorandom.

Do you mean, Is F_k(x) = SHA-1-HMAC_k(x) a pseudorandom function?
The answer in this case is yes, it is pseudorandom. If a computationally
limited adversary is given an oracle for F_k (but is NOT given k),
the adversary cannot distinguish F_k from random.

However, the latter fact doesn't help you build a Pseudorandom Oracle
Methodology, because you are between a rock and a hard place. When you
instantiate the Pseudorandom Oracle to get a real concrete scheme,
do you publish k? If k is kept secret, then you cannot instantiate
the Pseudorandom Oracle by SHA-1-HMAC_k(.), since no one (not even
the good guys) will be able to compute this function without knowledge
of k, so you are stuck. If you publish k and reveal it to the world,
then SHA-1-HMAC_k(.) is no longer pseudorandom once k is known to the
adversary, so you are again. Either way, your idea doesn't work.

I think you are overlooking the difficulty of taking an ideal scheme
proven secure in the (Pseudo)Random Oracle Model and instantiating it
to get a real, concrete protocol.

From:	David Wagner
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	Fri, 21 Jan 2005 19:36:10 +0000 (UTC)

Jiang Wu wrote:
>Maybe we can revise the Random Oracle Methology to a "Pseudorandom
>Oracle Methology":
>1. design an ideal system in which all parties (including the
>adversary) have oracle access to a pseudorandom function, and proves
>the security of this ideal system.
>2. replaces the pseudorandom oracle by a good cryptographic hashing
>function such as SHA-1.

I don't see how. A pseudorandom function is a keyed function
F(k,x). Are you going to give all parties oracle access to the
function F(k,.) in step 1.? If so, how are you going to implement
this in step 2.? You can't just pick a key k and publish it, since
the security of a pseudorandom function rests on the secrecy of the
key.

I don't think this idea works.

From:	jwu1 at lakeheadu.ca
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	23 Jan 2005 02:20:19 -0800

David Wagner wrote:
> >In short, my question should be modified as follows:
> >Is it a commonly accpeted assumption that a good cryptographic hash
> >function such as SHA-1 is an instance of pseudorandom function, to
> >which only oracle access is permitted, and whose key is unknow to
any
> >party?
>
> I don't understand the question, but I am certain that your idea
> doesn't work.
>
> Do you mean, Is F(x) = SHA-1(x) a pseudorandom function? No, clearly
> not. If I am given a function f and want to know whether it is truly
> random or not, I can compute f("hello") and check whether f("hello")
> = aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d. In case equality holds,
> I conclude that it is not a random function. Note that if f = SHA-1,
> then I will always successfully reject f as "not random", while if
> f = a random function, then I will successfully accept f as "random"
> (except with probability 1/2^160). So SHA-1 is not pseudorandom.
>
> Do you mean, Is F_k(x) = SHA-1-HMAC_k(x) a pseudorandom function?
> The answer in this case is yes, it is pseudorandom. If a
computationally
> limited adversary is given an oracle for F_k (but is NOT given k),
> the adversary cannot distinguish F_k from random.
>
> However, the latter fact doesn't help you build a Pseudorandom Oracle
> Methodology, because you are between a rock and a hard place. When
you
> instantiate the Pseudorandom Oracle to get a real concrete scheme,
> do you publish k? If k is kept secret, then you cannot instantiate
> the Pseudorandom Oracle by SHA-1-HMAC_k(.), since no one (not even
> the good guys) will be able to compute this function without
knowledge
> of k, so you are stuck. If you publish k and reveal it to the world,
> then SHA-1-HMAC_k(.) is no longer pseudorandom once k is known to the
> adversary, so you are again. Either way, your idea doesn't work.

Understand. In short, a pseudorandom function can not be instantiated
as a hash function.

My problem arised in Step 1:
1. design an ideal system in which all parties (including the
adversary) have oracle access to a "pseudorandom function", and proves
the security of this ideal system.

By saying the "pseudorandom function", I actually mean a "pseudorandom
oracle", which is an instance randomly selected from the subgroup of
all the functions X->Y. By contrast, a random oracle is an instance
randomly selected from all the functions X->Y.

With this correction, the "Pseudorandom Oracle Methodology" should work
since the "pseudorandom oracle" can be instantiated as a hash function
(just like the random oracle is instantiated as a hash function in the
Random Oracle Methodology). But as Aldar pointed out below,
"Pseudorandom Oracle Methodology" doesn't seem to improve the Random
Oracle Methodology. It's the same as the Random Oracle Methodology
except in modeling it uses "pseudorandom oracle" instead of the true
random oracle. It will encounter the same difficulties as the Random
Oracle Methodology.

>
> I think you are overlooking the difficulty of taking an ideal scheme
> proven secure in the (Pseudo)Random Oracle Model and instantiating it
> to get a real, concrete protocol.

From:	Aldar C-F. Chan
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	Sat, 22 Jan 2005 02:54:10 GMT

When random oracle is used in proof, we implicitly assume
that the attacker won't use any property of the hash function
to mount his attack. But in practice, the adversary could somehow
make use of the knoweldge about how the hash function is
implemeted. Just don't see how different your idea is from
random oracle! Would it help to use a (less) ideal model of
the hash function in the proof while still assuming the attacker
won't be able to make use of any property of the hash funcion
in practice?? (Maybe David will have something to comment.)

From:	jwu1 at lakeheadu.ca
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	23 Jan 2005 02:32:57 -0800

From:	jwu1 at lakeheadu.ca
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	22 Jan 2005 16:04:15 -0800

David Wagner wrote:
> Jiang Wu wrote:
> >Maybe we can revise the Random Oracle Methology to a "Pseudorandom
> >Oracle Methology":
> >1. design an ideal system in which all parties (including the
> >adversary) have oracle access to a pseudorandom function, and proves
> >the security of this ideal system.
> >2. replaces the pseudorandom oracle by a good cryptographic hashing
> >function such as SHA-1.
>
> I don't see how. A pseudorandom function is a keyed function
> F(k,x). Are you going to give all parties oracle access to the
> function F(k,.) in step 1.?
Yes, it's the same as in the Random Oracle Methology. The only
difference is, in Random Oracle Methology, the instance function is
taken from all possible functions from X to Y (X is the message set and
Y is the hash value set), while in "Pseudorandom Oracle Methology", the
instance function is taken from a subset of all possible functions from
X to Y.
> If so, how are you going to implement
> this in step 2.? You can't just pick a key k and publish it, since
> the security of a pseudorandom function rests on the secrecy of the
> key.
In step 2, use a hash function to replace the oracle, it's the same as
in Random Oracle Methology. I'm not sure whether it's equivalent to
picking a key k and publishing it. If yes, then the Random Oracle
Methology is at the same risk (which doesn't seem true); if no, your
conclusion below is not sufficiently supported.
> I don't think this idea works.

From:	newstome at comcast.net
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	Sun, 23 Jan 2005 11:35:34 -0600

jwu1@lakeheadu.ca wrote:
> David Wagner wrote:
>> Jiang Wu wrote:
>> >Maybe we can revise the Random Oracle Methology to a "Pseudorandom
>> >Oracle Methology":
>> >1. design an ideal system in which all parties (including the
>> >adversary) have oracle access to a pseudorandom function, and proves
>> >the security of this ideal system.
>> >2. replaces the pseudorandom oracle by a good cryptographic hashing
>> >function such as SHA-1.
>>
>> I don't see how. A pseudorandom function is a keyed function
>> F(k,x). Are you going to give all parties oracle access to the
>> function F(k,.) in step 1.?
> Yes, it's the same as in the Random Oracle Methology. The only
> difference is, in Random Oracle Methology, the instance function is
> taken from all possible functions from X to Y (X is the message set and
> Y is the hash value set), while in "Pseudorandom Oracle Methology", the
> instance function is taken from a subset of all possible functions from
> X to Y.
>> If so, how are you going to implement
>> this in step 2.? You can't just pick a key k and publish it, since
>> the security of a pseudorandom function rests on the secrecy of the
>> key.
> In step 2, use a hash function to replace the oracle, it's the same as
> in Random Oracle Methology.

Which isn't secure (or at least, it's not foolproof). In fact, just
using a hash function in a simplistic way isn't secure at all because
of some extensibility properties of hash functions based on repeatedly
applying a compression function (like MD5 and SHA1) -- this was noted
in the original Random Oracle paper.

> I'm not sure whether it's equivalent to
> picking a key k and publishing it. If yes, then the Random Oracle
> Methology is at the same risk (which doesn't seem true); if no, your
> conclusion below is not sufficiently supported.

Yep -- which is really the key point of the "Random Oracle Model
Revisited" paper. They show that, in a certain sense, you *can't*
instantiate the random oracle in the "real world" in a way that
accurately reflects the important properties of a true random oracle.
Doesn't matter if you use an unkeyed hash function, or HMAC, or a
pseudorandom generator...

--

That's News To Me!
newstome@comcast.net

From:	jwu1 at lakeheadu.ca
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	23 Jan 2005 02:05:26 -0800

From:	jwu1 at lakeheadu.ca
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	23 Jan 2005 02:12:08 -0800

From:	astiglic at okiok.com
Subject:	Re: from random oracle model to pseudorandom oracle model
Date:	21 Jan 2005 13:13:07 -0800

Jiang Wu wrote:
> My questions are:
> 1. Is it a commonly accpeted assumption that a good cryptographic
hash
> function such as SHA-1 is pseudorandom function?

You can construct a secure PRF from SHA-1, but the resulting
construction needs a cryptogrpahic key which you need to pick
uniformaly at random and keep secret.

> 2. Is the "Pseudorandom Oracle Methology" discussed or implied in any
> paper/textbook?

The proofs of security for modes of encryption (like CBC) are based on
the use of a PRF, and then in practice the PRF is replaced by a secure
block cipher (which acts more like a PRP, but there is a known
reduction from PRF to PRP security). But in those cases, you need to
pick a key that you keep secret. If you just use SHA-1 with no key,
then it is clear that you don't have a PRF and all bets are off.
--Anton