A pseudo-random function is an efficiently-computable function which emulates a random oracle.

learn more… | top users | synonyms (1)

-2
votes
1answer
19 views

pseudo-random-function

please, can you help me about this question... Design a blockcipher E : {0, 1}k × {0, 1}128 → {0, 1}128 that is secure (up to a large number of queries) against non-adaptive adversaries, but is ...
1
vote
1answer
45 views

how to prove sequence y uphold golomb's third axiom

given $\{ x_k \}$ is a m-seq of order $n$, we define $\{ y_k \}$ to be a $m$ digits number: $$ y_i=x_ix_{i+1}...x_{i+m-1} $$ for every integer $n \ge m \ge 1$ how can I show that $\{ y_k \}$ upholds ...
2
votes
1answer
74 views

How can I generate cryptographic-quality 1/f noise, aka “pink noise”?

Can anyone suggest how I'd generate cryptographic quality 1/f noise: aka 'pink noise', where the PSD follows 1/f. I'd be happy to derive the pink noise from white noise (e.g. /dev/urandom), but I ...
2
votes
1answer
68 views

Are the following schemes based on a pseudo-random permutation secure?

I am currently working on the following task: Let F be a pseudorandom permutation. Consider the encryption scheme for the message space $\{0, 1\}^n$ defined as follows: $Gen(1^n)$ chooses ...
1
vote
1answer
44 views

Prove that a function is not PRF

Let $G$ $PRG$ and $G'(s)$ equal to the first $n$-bits of $G(s)$, where $|s| = n$. Show that $F_k(x) = G'(k) ⊕ x$ is not a $PRF$. My attempt: Lets assume a $k$ and 2 messages $x_1$ and $x_2$. So, for $...
1
vote
1answer
37 views

Prove that a function is PRF

Let $F : K×K \rightarrow \{0,1\}^{128}$ be $PRF$ function. Is $F'$ $PRF$ ? $ F'(x) = \begin{cases} 0^{128} & \quad \text{if } x = 0\\ F_k(x) & \quad otherwise \end{cases} ...
4
votes
1answer
85 views

How to prove a function is pseudorandom function?

I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I am using a function having $F_{k}$ = $A_{k}(B_{k}(r,m),r)$, the random number is generated using the ...
4
votes
1answer
197 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 ...
9
votes
1answer
186 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\...
2
votes
2answers
188 views

Cryptanalysis of Marvin32 compared to SipHash

So I am curious about the security analysis of Marvin32, the randomized hash algorithm used in .NET (to prevent hash-table DoS). I found the source code here: ...
4
votes
1answer
72 views

Statistical tests for PRNG that generates a sequence which is not binary

Is there a pratical application to PRNG that generates a sequence which is not a binary one? A ternary, quaternary sequence, for instance. If so, how can we test this? Is there any alternative test ...
4
votes
1answer
55 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 ...
0
votes
0answers
34 views

TLS 1.2 PRF Cipher Suite Specification

I am upgrading our assembler SSL/TLS implementation to support TLS 1.2 and am reviewing RFC5246 specification for TLS 1.2. It states that the PRF is now part of the cipher suite specification but ...
1
vote
2answers
82 views

Is a PRF applied to a secure MAC also a secure MAC?

Suppose I apply a PRF to a secure MAC. Do I still have a secure MAC?
-1
votes
1answer
49 views

Collision-Resistance Hash Function PRF

I am trying to solve the following question with an example/proof. The question is from Introduction to Modern Cryptography by Katz and Lindell. Any help would be appreciated.
2
votes
1answer
95 views

Could use an explanation of the notation for an oracle adversary

In the definition below, what exactly does it mean for the adversary (not even sure that's the correct term?) to equal one? $$ \underset{K}{Pr} \left [A^{F_k(\cdot)} = 1 \right ] $$ Source (Page 22/...
0
votes
1answer
48 views

PRNG that takes input a $n$-bit string and gives output a $2n$-bit string?

Recently, I'm reading one paper of Boneh and Zhandry. They have mentioned a pseudo random number generator that takes input a $n$-bit string and gives a $2n$-bit string as output. They just used it as ...
0
votes
1answer
98 views

Combining multiple PRGs together

Got some theoretical questions about PRGs to solve (given by lecturer for self-learning, no score involved). Tried to find on the internet but couldn't figure out how to solve them, so I will mention ...
6
votes
1answer
96 views

Is IPsec IND-CCA secure provided the used block cipher is a pseudorandom function?

I am trying to solve the question whether "IPsec is IND-CCA secure provided the used block cipher is a pseudorandom function" (with IPsec using a variant of Encrypt-then-MAC) As a resource I am given ...
2
votes
1answer
154 views

Is F' a pseudorandom function when F is composed with G, a pseudorandom generator?

If $F$ is a pseudorandom function, is $F'$ also a pseudorandom function in the following: $$ F'_k(x)=F_k(G(x)) \space \space \text, $$ where $G$ is $a$ pseudorandom generator? Also, does the other ...
1
vote
0answers
35 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 ...
5
votes
0answers
47 views

Best differential characteristic for this PRF

Consider the following construction of a PRF $F: \{0,1\}^{128} \times \{0,1\}^{64} \to \{0,1\}^{64}$ on 64-bit messages and 128-bit keys. Define $f:\{0,1\}^3 \to \{0,1\}$ by $$f(c,x,y) = \begin{...
1
vote
1answer
80 views

Determine whether a given function is a pseudorandom generator/function

I am trying to solve the following three tasks (for exam practice, not as a homework): Define $𝐺 : \{0,1\}^* \rightarrow \{0,1\}^*$ by $G(x_1,...,x_n) = 𝑥_1 \oplus 𝑥_2,𝑥_1,⋅⋅⋅,x_n.$ Prove that ...
2
votes
1answer
60 views

Why is $Mac_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$ not a secure MAC?

I am preparing for an exam and trying to solve the following question I found on the internet: Let $F_k$ be a pseudorandom function. Show that the following MAC for messages of length $2n$ is ...
2
votes
1answer
64 views

Distinguishing two sets of pseudorandom values when their keys differ by one

Suppose we use a pseudorandom function $PRF$ and a random key $k$ to generate a set of pseudorandom values: $\forall i, 1\leq i \leq n: w_i=PRF(k,i)$ Now, consider instead of picking a fresh key, ...
1
vote
0answers
64 views

Is $E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ PRF?

$E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ and F is PRF which maps $\left \{0,1 \right \}^n \times \left \{0,1 \right \}^n $ to $\left \{0,1 \right \}^n$. Let two messages $m_{0} = 0^l $ and $m_{1} ...
0
votes
0answers
27 views

NIST SP800-108 KDF modes comparison

According to NIST SP800-108, there are three modes that can build KDF from PRF: counter mode, feedback mode and double-pipeline iteration mode. Assume that the same PRF and input distribution are used,...
4
votes
0answers
166 views

How to 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 ...
0
votes
0answers
85 views

Proof that this is not a secure pseudorandom function

$p$ is a large prime number. Consider the following function $F:\mathbb Z^*_p \times \mathbb D\rightarrow\mathbb Z^*_p$ where $\mathbb D=2,....,p-1$. $F_k(x)=x^k \bmod p$ Proof that it's not ...
1
vote
1answer
50 views

Is this a secure keyed hashing construction?

I need a PRF for use with PBKDF2, however, the only thing I have is the AES block cipher primitive. I'm attempting to derive a keyed hash function from the block cipher. The design is based on the ...
3
votes
1answer
566 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|...
2
votes
2answers
92 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 ...
2
votes
2answers
177 views

Given a pseudorandom function F, is $(F_k(r) \; | \; F_k(r + 1))$ also a PRF?

Given: F is a pseudorandom function, G is a pseudorandom generator with $l(n) = n+1$. The following schemes should be classified as being insecure, IND-COA secure, IND-CPA secure. To encrypt $m \in \...
2
votes
2answers
120 views

Given PRNG $G(s)$, why is $G(s) || G(s+1)$ not a PRNG?

I have given a pseudorandom Generator $G(s)$, $|s|=n$ whose expansion $l(n)$ is $>2n$. I also know that $G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor})$ is a pseudorandom generator. Now ...
3
votes
1answer
97 views

Can Pseudorandom values be used as secure keys?

I want to derive $n$ keys from a master key. I pick a master key $mk$ and use pseudo-random function (PRF) to generate $n$ pseudo-random values, $v_i=PRF(mk,i)$ where $1\leq i \leq n$. Next, I use ...
2
votes
1answer
123 views

Key Derivation Function (KDF): Can a key derived from KDF be considered as a secure key?

Consider a case where we have a master key MS that is used in pseudo-random function to generate a set of pseudo-random values. Then we use key derivation function to derive a key from each of pseudo-...
3
votes
2answers
177 views

secure PRF or not

I am new in Cryptography and I saw this question in a note I solved it but I'm not sure about my answers. Let $F : \{0, 1\}^n × \{0, 1\}^n→ \{0, 1\}^n$ be a secure PRF (i.e. a PRF where the key ...
0
votes
1answer
38 views

Key derivation function in theory & practice

I am implementing a cryptographic protocol and I'd like to generate a set of seeds using a seed for a pseudo-random function. The reason is that I can pass on only one seed and it can be used to ...
1
vote
1answer
54 views

Help with pseudorandom functions

I started a new lecture this year about crypto and I've had a few problems in the first few weeks with the exercises we got. I would appreciate a "guide" on how to solve problems like the following ...
2
votes
0answers
71 views

If a PRG is constructed by iterating a PRF, is it backtracking-resistant?

Say we construct a pseudo-random number generator from a pseudo-random function $f$ (using some constant key $k$ and some initial value $v_0$). We do this by feeding the output block of the PRF back ...
0
votes
1answer
73 views

If PRF is non invertible, why does Ctr-mode work?

I am currently taking Dan Boneh's Cryptography I course online. I have just finished the segment discussing the Cipher Block Chaining and Counter-Mode. I am having difficulty understanding why Ctr-...
2
votes
2answers
96 views

Is pseudorandom function also a one-way function?

Can I assume this? Specifically, I want to know if the following two cases are valid. Suppose $prf_k(m)=c$ One-wayness: Only given $c$, we cannot reveal $m$. Without key $k$, even given $m$, cannot ...
1
vote
1answer
54 views

PRF that can be distinguished after $k$ queries?

In adaptive attacks, if we design poorly, adversary can modify his queries and break the given pseudo random function (that is being able to distinguish it from uniform randomness). Is there a poor ...
0
votes
0answers
41 views

Existence of a random function under constraints

Let $F_1$ and $F_2$ be two random functions taking as input $N$ bits and returning $N$ bits. Let $C_1$ and $C_2$ two constants of $N$ bits. Is there a random function $P$ taking as input $2N$ bits and ...
2
votes
0answers
115 views

Pseudorandom Functions with different input and output lengths

I am working on a problem found in my Cryptography textbook that goes as follows: Let F be a pseudorandom function such that for $k \in \{0,1\}^n$, function $F_k$ maps $l_{in}(n)$-inputs to $l_{...
1
vote
1answer
37 views

Deriving a Set of Seeds from a Seed

I need a set of seeds $S=\{s_1,..., s_n\}$, for pseudo-random function where seed $s_i$ is used to generate a set of pseudo-random values. Obviously I need to be able to regenerate the sets of pseudo-...
2
votes
1answer
40 views

Data Switching and Information Leakage

Hypothesis: Let $z,a$ be uniformly random elements of a field $\mathbb{F}_p$ where $p$ is a large prime number. Also, let $(-z)$ be additive inverse of $z$. I have a fixed secret value $x$. I mask ...
2
votes
1answer
64 views

Modified version of a CPA-secure encryption scheme

The following encryption scheme: choose a random string $r \leftarrow \{0,1\}^n$ and compute the ciphertext $c= \thinspace <c_0, c_1>= \thinspace <r, F_k(r) \oplus m>$, assuming $F$ a PRF; ...
2
votes
1answer
83 views

Crypto-period for keys used in PRF

I am wondering about the crypto-period for keys used in pseudo-random functions. For example, let's say I am using HMAC-SHA256 with a secret key $K$. After how many computes do I have to update $K$?
6
votes
1answer
2k 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 ...