Questions tagged [pseudo-random-function]

A pseudo-random function (PRF) is a family of deterministic functions indexed by a parameter, such that a randomly selected instance is computationally indistinguishable from a uniformly random function with the same input and output spaces.

Filter by
Sorted by
Tagged with
31
votes
6answers
5k views

What is the practical impact of using System.Random which is not cryptographically random?

I recently noticed a .NET software using PBKDF to derive an encryption key from a password string. This password string was ...
31
votes
4answers
27k views

What is difference between PRG, PRF, and PRP

Until what I have gotten is: A PRG is generator is a part of PRF that produces pseudo-random values for the function. PRF is semantically secure and has no worries of being invertible. Fine, then ...
16
votes
1answer
4k views

Security of KDF1 and KDF2 (hash based KDF's)

It's still common to come across implementations of KDF1 and KDF2. Basically these are KDF's that simply derive multiple keys from the key seed and a counter: $K_i = \operatorname{KDF}(K_{master}, i) ...
15
votes
3answers
594 views

Expected entropy in $P(x)\oplus x$ for random $x$, where $P$ is a random permutation

Let $P$ be a random permutation of $n>1$ bits. Let $F$ be the function on the same domain $\{0,1\}^n$, defined by $F(x)=P(x)\oplus x$. When $P$ is a block cipher with key a message block, that's ...
13
votes
3answers
2k views

How to construct a good PRF from a block cipher?

We want to explicitly construct a good (as tentatively defined below) Pseudo-Random Function $F$ with $b$-bit input and output, from (preferably just) one Pseudo-Random Permutation $E$ of $b$-bit, as ...
13
votes
3answers
1k views

What is the difference between PRF and a Random Oracle?

What is the difference between Pseudo Random Functions and Random Oracles? Is the difference only about the domain of PRFs and Random Oracles, former having a fixed domain and latter can act on any ...
12
votes
1answer
4k views

Is there a difference between PRF and a hash function?

Is there a difference between PRF and a hash function? For example: Creation of a secret key is using PRF and creating a secret key is using hash function.
11
votes
1answer
6k views

Cryptographic security of PHP mt_rand() function using Mersenne Twister algo

At stackoverflow this question has been asked. It uses additional random entropy and a hash method (among others) to try and create a cryptographically secure pseudo-random number generator for PHP. ...
11
votes
1answer
872 views

Does IND-CPA imply PRF?

It is well-known that a pseudorandom function (PRF) can be used to build a CPA-secure symmetric cryptosystem. My question: is PRF necessary for this, i.e., can one show something like "If there exists ...
11
votes
1answer
439 views

Which compression functions are PRFs?

In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs. The Wikipedia article on cryptographic hash functions ...
10
votes
2answers
3k views

Is 512 bits a more secure hashing than 256 bits?

I know that 512 bit hashing is more secure, but I don't really know why. I hope someone can help me to better understand it in more detail.
10
votes
3answers
7k views

Estimating bits of entropy

I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy. What I'm having a hard time finding is any particular literature ...
10
votes
1answer
5k views

Luby-Rackoff theorem confusion

The Luby-Rackoff theorem states that if a round function is a secure pseudorandom function (PRF) then 3 rounds are sufficient to make the block cipher a pseudorandom permutation (PRP). PRPs are ...
10
votes
1answer
880 views

Are there any authoritative definitions of “key stretching”?

This is mostly a terminology question, but I suppose that it is best asked and answered here. After browsing the Internet I have come across a fair number of completely different definitions of the ...
10
votes
0answers
332 views

What might be assumed about a PRF if the key has been chosen?

The defining feature of a PRF $f:\{0,1\}^k\times\{0,1\}^s\mapsto\{0,1\}^*$ is that, if the first parameter is selected at random, it should be indistinguishable from a function $g:\{0,1\}^s\mapsto\{0,...
9
votes
1answer
329 views

State recovery of Micalli-Schnorr random number generator modulo a prime

Let $p$ be a public prime of $n$ bits. Define the sequence $x_i=z_{i-1}^e \bmod p$, where $z_i$ is the $k$ high-order bits of $x_i$, and $r_i$ the remaining $n-k$ bits of $x_i$ (thus $z_i=\Big\lfloor\...
8
votes
2answers
2k views

(updated) Utilizing a non-computable function to create a one-way function

Why can't uncomputable functions be adapted to serve as theoretically perfect one-way functions? This has been bugging me for years, and I've never been able to track down an explanation of why it ...
8
votes
3answers
2k views

Is a secure deterministic MAC always a PRF?

Given a secure MAC scheme $ \Pi=(Gen, Mac, Vrfy) $, wheres $ Gen $ produces uniformly distributed keys, and the algorithm $ Mac $ is deterministic, is $ Mac $ necessarily a pseudorandom function? I ...
8
votes
1answer
515 views

Is $F'_k(x) = F_k(x) \oplus k$ a pseudo random function?

Let $F_k$ be a pseudo random function. Is $F'_k(x) = F_k(x) \oplus k$ necessarily a pseudo random function? I think that it is a PRF, but I just can't find a reduction that works with it.
8
votes
2answers
937 views

Why is this function pseudo random (PRF)?

First, I want to clarify this is not homework. I encountered this question (here How can I prove that a function F isn't a pseudo random function?) while studying for a test coming soon. $F'_k(x) ...
7
votes
2answers
339 views

Do you really need a KDF when you have a PRF?

My understanding is that a KDF is like a PRF, except that it has a preliminary step that "extract" entropy. It is thus needed when the entropy is non-uniform (for example the output of ECDH is modulo ...
7
votes
2answers
4k views

How can I prove that a function F isn't a pseudo random function?

Let $F$ be a length-preserving pseudorandom function. For the following constructions of a keyed function $F' : \{0, 1\}^n \times \{0, 1\}^{n−1} \to \{0, 1\}^{2n}$, state whether $F'$ is a ...
7
votes
2answers
453 views

Does a hash function in chaining mode or in counter mode make a better pseudo-random number generator?

I have two pseudorandom generators: $f_1$ takes a random seed $l_0||r_0$ $\in \{0,1\}^{160}$ as input and outputs $r_1||r_2|| \dots ||r_k$, where $l_i||r_i = \operatorname{SHA-1}(l_{i-1}||r_{i-1})$ ...
6
votes
4answers
2k views

The difference between MACs vs. HMACs vs. PRFs

I have some confusion regarding the difference between MACs and HMACs and PRFs and when to use which term. If the function is computed using a hash and secret key like the following, is this a HMAC ...
6
votes
2answers
2k views

Questions about Key Derivation Functions

My understanding is that a KDF is a function that takes a master secret and generates multiple keys. It is secure as long as the keys are "independent". If this is true, the following definition would ...
6
votes
2answers
606 views

What is the sponge construction in simple terms?

I suggested to my client to use SHA3 instead of SHA2. I know that SHA3 is based on Keccak algorithm which won the NIST's competition. I want to explain the structure of sponge functions in very simple ...
6
votes
1answer
480 views

Pseudorandom Generator

In a cryptographic application, two types of (pseudo)random bit streams are needed: a stream $A= a_{1}a_{2}a_{3}\ldots$ in which $\Pr[a_{i}=0]=\Pr[a_{i}=1]= 1/2\ \forall i$ and a stream $B= b_{1}b_{2}...
6
votes
2answers
773 views

Proof that MAC and hash composition is insecure

Let $F$ be a secure PRF and $H$ a universal hash function. How can I exhibit a pair $(F,H)$ whose composition $$S'((k_1, k_2), m) = F(k_2, H(k_1,m))$$ is an insecure MAC (or an insecure PRF, since a ...
6
votes
1answer
1k views

Goldreich-Goldwasser-Micali Construction

The Goldreich-Goldwasser-Micali construction allows to build a (cryptographically secure) pseudo-random function from of a (cryptographically secure) pseudo-random generator. More formally, let $G: \...
6
votes
1answer
788 views

Simple application of verifiable random function?

I have been reading a little bit about verifiable random functions (e.g.). In the literature, these are described as "pseudo-random functions that provide a non-interactively verifiable proof for the ...
6
votes
1answer
433 views

Private set intersection, using a semi-trusted server

Alice has a set $S$ of words. Bob has a set $T$ of words. They want to compute the intersection $S \cap T$ of their words, with the help of a semi-trusted third party Trent. Trent runs a central ...
6
votes
2answers
525 views

Why does the CBC-MAC require PRFs?

I'm stuck on exercise 4.19 from Introduction to Modern Cryptography. Let $F$ be a keyed function that is a secure (deterministic) MAC for messages of length $n$. (Note that $F$ need not be a ...
6
votes
1answer
199 views

On CPA & KPA security of $\boxplus$-Feistel

I am interested to identify the effect of replacing $\oplus$ with $\boxplus$ on basic balanced Feistel structures over $r$-rounds. Given: $F_\boxplus[L,R]= [S,T] = [R,L \boxplus f(R)]$ where $f$ is a ...
6
votes
1answer
2k views

Can someone explain how OPRF (Oblivious pseudo-Random Function) is based on OT (Oblivious Transfer)?

Can someone explain to me how OPRF is based on OT extensions? I'm currently reading papers about private set intersection problem that uses efficient OT-based protocols based on OPRF, the link of the ...
6
votes
1answer
385 views

Homomorphic Evaluation of Pseudo Random Function

I'm looking for a special Pseudo Random Function (PRF) $F_k()$ which follows the below. For fully homomorphic encryption (FHE), $\mathit{FHE}(F_k(x)) = F_k(\mathit{FHE}(x))$. Or is there any ...
6
votes
1answer
154 views

Sponge with PRF instead of PRP

In most uses of Sponge mode of operations such as SHA3 and many of the round-2 candidates in the NIST lightweight cryptography project, the underlaying primitive is a cryptographic permutation - that ...
5
votes
2answers
957 views

Show that G is not a PRF

$\DeclareMathOperator{concat}{\|}$ I'm trying to do the following assignment: Let $F : \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^n$ be a PRF. Define function family $G : \{0,1\}^k \times \{0,1\}^{n-1} \...
5
votes
4answers
2k views

Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)

I have a question about Pseudo Random Functions. Let $f:\{0,1\}^m \times \{0,1\}^n → \{0,1\}^n$ be a secure PRF. Define $F(k,x) = f(k,x) - f(k, x-1 \bmod 2^{n}) \bmod 2^{n}$. Is $F$ is a secure PRF?...
5
votes
2answers
5k views

How to prove that a function is not pseudorandom?

I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I'm struggling with the exercies which ask for proofs, like the following one: Let G(k) be a PRG with |k| ...
5
votes
3answers
1k views

What is the purpose of Pseudorandom Function Families (PRFs)?

I'm currently in a course in Cryptography, and was wondering why pseudorandom function families exist at all. If there existed one pseudorandom function f(x), based on its definition, could that not ...
5
votes
1answer
728 views

CBC-MAC based on PRF

Why is the block cipher in the CBC-MAC taken to be a pseudo random permutation (PRP) and not a pseudo random function (PRF)? We don't need the bijective property of the PRP. So why go with it?
5
votes
2answers
230 views

Can a PRF distiguisher invoke the function's algorithm?

The definition of a function $F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ being a Pseudo Random Function Family (PRF) is that it's implementable by a P.P.T. algorithm $\mathcal F$, and there is no P.P.T....
5
votes
1answer
2k views

PBKDF2 PRF: HMAC or just hash?

I understand the way $\textrm{PBKDF2}$ can be used to 'stretch' a password/passphrase that does not provide full entropy. My question: how does one choose the PRF? A common choice is any well-known ...
5
votes
1answer
185 views

Turning PRPs in PRGs with a counter

I am following the Coursera Cryptography I course and I have the following question, I am a bit perplexed by the statement, in week 2 lecture "What are block cyphers?" that a counter-mode PRF is a ...
5
votes
1answer
382 views

Is $f(K, f(K, x))$ a pseudorandom function?

Given a PRF $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$, is $f(K, f(K, x))$ a PRF, too? My hunch is to construct a PRP similar to Feistel ciphers but with the property $f(K, f(K, x)) = ...
5
votes
1answer
2k views

TLS 1.2 PRF with HMAC-SHA256

I am implementing support for TLS 1.2 for the IBM mainframe operating system z/VSE in Assembler language, but am having difficultly getting the PRF to work. I am validating with the values described ...
5
votes
1answer
121 views

Can Trivium be used as a PRF?

The Trivium encryption algorithm has two inputs, key and IV, both of which are 80 bits long. Let's call it Trivium(key, IV) → keystream. My question is whether doing Trivium(key, input) and taking the ...
5
votes
1answer
2k views

Prove that the following MAC is insecure

I am trying to prove that the following MAC is insecure, but I don't know how to exploit the properties of the pseudorandom function $F$ involved: Gen generates a uniform $k \in \{0, 1\}^n$. To ...
5
votes
1answer
134 views

Is there any existing analysis for this construction to turn a tweakable blockcipher into a PRF?

I'm basically looking at this construction to turn a tweakable blockcipher $E_c(x)$ taking a key $k$, nonce $n$, counter $c$ (forming tweak $t = c||n$) and an input $x$ into a PRF on an arbitrary-...
5
votes
1answer
202 views

Fundamental difference between the constant, key, nonce, and counter bits in Salsa20/ChaCha20 or AES-Encrypt?

The Salsa20 core function takes a 128-bit constant, 256-bit key, 64-bit counter, and 64-bit nonce and produces a 512-bit value. Or more generically, it is a mapping from 512-bit values to 512-bit ...

1
2 3 4 5
7