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

learn more… | top users | synonyms (1)

9
votes
1answer
182 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 ...
2
votes
2answers
175 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: ...
1
vote
1answer
56 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 ...
4
votes
1answer
67 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
49 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
23 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 ...
0
votes
2answers
78 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
44 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
94 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 ...
1
vote
1answer
32 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 ...
0
votes
1answer
44 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 ...
1
vote
0answers
31 views

Generating cryptographic-quality 1/f 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 ...
0
votes
1answer
96 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
95 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
33 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
45 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) = ...
1
vote
1answer
73 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 ...
1
vote
1answer
55 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
23 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 ...
4
votes
0answers
158 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
83 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 ...
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
531 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 ...
2
votes
2answers
86 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
175 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
115 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
110 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 ...
3
votes
2answers
173 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
35 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
53 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
70 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
69 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 ...
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
52 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
109 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 ...
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 ...
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
63 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 ...
6
votes
3answers
2k views

Estimating bits of entropy

Best ways to estimate average bits of entropy in a byte stream. I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy. What ...
1
vote
1answer
99 views

The encryption scheme is secure?

I have a scheme and I don't know that this scheme is semantic security or not. Secret keys $\{s_1,s_2, x_1,x_2\}$ and public parameter $p$ (large prime number). Encryption E(m): $C_1 = s_1m + x_1k ...
3
votes
2answers
119 views

Does CTR mode yield a PRF?

Can the keystream generated by CTR mode be considered a pseudo-random function? I give more information. Assume $f$ is a PRF. We define a function which takes 2 inputs, the desired length, and an ...
4
votes
2answers
98 views

A periodic PRNG based on hash function?

I need a PRNG which provides 128 bytes numbers. Let's say that given a symmetric key $K$ and an internal state $s$ I use the PRF HMAC-SHA512 this way: The output is PRNG($K, s$) = ...
1
vote
1answer
54 views

Random Function size

I am new to cryptography. I have question regarding the size of the set of random functions. I found the text from "Introduction to modern cryptography" by Katz and Lindell, in another thread which ...