Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
46 votes
Accepted

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

You asked for the practical impact, so the answer is that for \$120 I could probably have your entire password database done by tomorrow. Here is your program, or something similar to it: ...
ymbirtt's user avatar
  • 678
26 votes

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

From what you have described, it sounds like your system works as follows: Consult the system clock to find a 32-bit seed $s$. Use System.Random to generate a ...
Squeamish Ossifrage's user avatar
21 votes

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

The main fundamental issue with this approach, as with approaches that attempt to base cryptography on NP-completeness, is that the hardness you refer to is worst case hardness, and not average case ...
Yehuda Lindell's user avatar
18 votes

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

The official documentation for System.Random explicitly says it should not be used for generating passwords. It’s predictable, and seeded only from the system clock. This means System.Random has at ...
rmalayter's user avatar
  • 2,297
16 votes
Accepted

Relationship between PRF/KDF/MAC?

A key derivation function (KDF) takes in some secret keying material, which may or may not be uniformly distributed, and where the adversary may also have some auxiliary information about the keying ...
hakoja's user avatar
  • 2,725
16 votes
Accepted

Is 512 bits a more secure hashing than 256 bits?

When there is no known weakness in the hash function we talk about their generic1 resistances Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. E.g., consider ...
kelalaka's user avatar
  • 48.7k
15 votes
Accepted

Does IND-CPA imply PRF?

If there exists an IND-CPA symmetric encryption scheme (where the key is shorter than the total length of the messages, i.e., the scheme is not the OTP), then there are one-way functions. A sequence ...
Geoffroy Couteau's user avatar
15 votes
Accepted

Is constant-time compare really required for AEAD ciphers?

Let the vulnerable comparison compare byte-by-byte and break out of the loop after the first mismatch. If we neglect noise, this leaks how many bytes (prefix) of the MAC are correct via timing. Then ...
CodesInChaos's user avatar
  • 24.9k
15 votes

Does Grover's algorithm really threaten symmetric security proofs?

Yes, but also no. Grover's algorithm is actually quadratically faster than classical algorithms. However there are a few catches. Quantum computers are slow and expensive. This means that in the near ...
Oscar Smith's user avatar
13 votes
Accepted

The difference between MACs vs. HMACs vs. PRFs

A PRF or pseudorandom function family is a family of functions $F_k\colon \{0,1\}^n \to \{0,1\}^m$ such that if $k$ is uniformly distributed, then $F_k$ appears to be uniformly distributed among all ...
Squeamish Ossifrage's user avatar
13 votes
Accepted

Does Grover's algorithm really threaten symmetric security proofs?

Despite the classical security proof, Grover's algorithm threatens symmetric key cryptography. The main reason is that classical security proof assumes that the adversary makes classical queries to ...
Hhan's user avatar
  • 438
12 votes
Accepted

Show that G is not a PRF

If the adversary takes $x, y \in \{0, 1\}^n$ such that $(0 \parallel x) = (y \parallel 1)$ then $$G_K(x) = F_K(0 \parallel x) \parallel F_K(x \parallel 1)$$ $$G_K(y) = F_K(0 \parallel y) \parallel ...
aventurin's user avatar
  • 543
12 votes
Accepted

Is a secure deterministic MAC always a PRF?

Your intuition is not right. The fact that no forger can obtain new valid message/tag pairs doesn't say anything about the "shape" of the MAC. For instance, if $\Pi$ is a secure MAC, then the MAC ...
Daniel's user avatar
  • 3,972
12 votes
Accepted

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

You won't be able to find a reduction since you need somehow to XOR $k$ with the output you would get from oracle queries to the PRF, and you can't do this. In fact, the answer is that this is not ...
Yehuda Lindell's user avatar
11 votes

What is the difference between PRF and a Random Oracle?

$\newcommand{\str}[1]{\{0,1\}^{#1}}$ Roughly speaking, a pseudo-random function is to a random oracle what computational encryption scheme is to one-time pad -- the former is a computational analogue ...
ckamath's user avatar
  • 5,258
11 votes

Does Grover's algorithm really threaten symmetric security proofs?

Does Grover's algorithm really threaten symmetric cryptography? Lov K. Grover's algorithm reduces the key search into $\mathcal{O}(\sqrt{2^n})$ instead of the $\mathcal{O}(2^n)$. What is generally ...
kelalaka's user avatar
  • 48.7k
10 votes

Truncating the output of AES-128

What you describe is exactly using AES-CTR to encrypt a 32-bit or 64-bit message. So, yes.
Squeamish Ossifrage's user avatar
9 votes

How to calculate entropy of a random number?

In a cryptographic sense this is not really possible. The entropy of the numbers is determined by the way they have been chosen. From only a list of numbers, say $(1, 2, 3, 4)$, we cannot just ...
dusk's user avatar
  • 1,175
9 votes
Accepted

Why does the CBC-MAC require PRFs?

The question as posed (in the book) is a bit weird, mainly because it does not state that $F$ is required to be length preserving, however for the CBC-MAC construction to make sense it clearly has to ...
Maeher's user avatar
  • 6,852
9 votes

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

Do you really need a KDF when you have a PRF? Maybe. The security contract of a PRF requires that the key be a uniform random bit string. If you have a DH secret or a diceware phrase, then what you ...
Squeamish Ossifrage's user avatar
9 votes

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

Some time ago (more than 5 years, I think) in a local forum one guy gave a "cryptographic challenge" to the community. He gave an encrypted string and a small piece of code that produced it. The goal ...
Vilx-'s user avatar
  • 1,095
9 votes

Is 512 bits a more secure hashing than 256 bits?

A n-bit hash can be brute forced $O(2^n)$ operations. If you run the numbers, you find that a 256-bit hash is completely immune to brute force attacks. $2^{256}$ is so large that it would literally ...
Cort Ammon's user avatar
  • 3,261
9 votes

What is the sponge construction in simple terms?

I find that the following image from Wikipedia, though perhaps a bit too technical for your purposes, is still helpful with a little explanation: Essentially, a function $f$ is used repeatedly in two ...
thesquaregroot's user avatar
8 votes

Statistical Tests for Pseudorandom Functions

Nobody uses generic statistical tests to verify correctness of encryption algorithms. To verify correctness of an implementation, engineers write proofs of correctness for their code, tr running it ...
Squeamish Ossifrage's user avatar
8 votes

What is the difference between pseudorandom permutation/pseudorandom function/block cipher?

All three are families of functions. For example, $f_k(x) = k \oplus x$, where $\oplus$ is xor and $k$ and $x$ are 256-bit strings, is a family of functions; for any 256-bit string $k$, there is a ...
Squeamish Ossifrage's user avatar
8 votes
Accepted

LWE and pseudorandom functions

You can. There is a certain caveat that should be mentioned here --- the LWE problems hardness is controlled (in part) by the size of the modulus $q$. Two important parameter regimes are $q$ being ...
Mark Schultz-Wu's user avatar
  • 13.3k
8 votes

Does Grover's algorithm really threaten symmetric security proofs?

I'm going to answer the question in your headline and then go forward. No. Grover's algorithm is a canard and you ought to stop worrying about it. The major reason for this is that Grover reduces the ...
Jon Callas's user avatar
  • 2,304
7 votes

What is difference between PRG, PRF, and PRP

In case there's still some confusion, I'll try giving a stab at it. Anyone correct me if I'm wrong! I believe a Pseudo Random Function tries to simulate a random function. Since a random function is ...
Timal Peramune's user avatar
7 votes

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

The general approach for proving that something is not a PRF is to come up with a distinguisher for it. A general approach for proving that a construction $F'$ from a PRF $F$ is also pseudo-random is ...
Jon Deaton's user avatar
7 votes

Are there any industry standards for PRFs?

HMAC is the standard way to construct a PRF from a hash function. FIPS PUB 198-1 - The Keyed-Hash Message Authentication Code (HMAC) (NIST standard) RFC-2104 HMAC: Keyed-Hashing for Message ...
CodesInChaos's user avatar
  • 24.9k

Only top scored, non community-wiki answers of a minimum length are eligible