Questions tagged [pseudo-random-permutation]

A Pseudo-Random Permutation (PRP) is a function that cannot be distinguished (with practical effort) from a permutation selected at random with uniform probability from the family of all permutations on the function's domain.

Filter by
Sorted by
Tagged with
3 votes
3 answers
1k views

Why is SHA-2 considered an ARX construction when it also uses non-ARX operations?

SHA-2 makes use of non-ARX non-linear operators such as the Choice and Majority functions: \begin{align} \mathsf{Ch}(E,F,G) &= (E \wedge F) \oplus (\neg E \wedge G)\\ \mathsf{Ma}(A, B, C) &= (...
LightTunnelEnd's user avatar
0 votes
0 answers
76 views

Full-Block Cipher Feedback Mode as a complete AEAD with a free MAC?

Full-State Keyed Sponge (aka Donkey Sponge) appears to cross over into block cipher mode territory such as Full Block Cipher Feedback Mode: Full State Keyed Sponge (FKS) construction: FKS has been ...
LightTunnelEnd's user avatar
1 vote
0 answers
120 views

Can a Full-State Keyed Sponge be used as AEAD by using XEX?

Full-State Keyed Sponge (aka Donkey Sponge) is when a message is absorbed into the full state of the sponge. Such an approach to MAC construction is considered secure. 1 However for an AEAD or a ...
LightTunnelEnd's user avatar
3 votes
2 answers
288 views

Are sponges inherently inefficient when compared to other constructions?

A sponge has by definition 'wasted' operations (the part of the state which always remains private but goes through all the ops of the permutation). In return for that waste you get a MAC at the end - ...
LightTunnelEnd's user avatar
4 votes
1 answer
115 views

How is the Full-State Keyed duplex useful?

In the Full-State Keyed duplex (sponge construction AEAD), plaintext is absorbed into the entire state of the sponge permutation but only a portion of the output can be used else the scheme breaks (...
LightTunnelEnd's user avatar
1 vote
2 answers
81 views

Given $i$ keyed-$PRP$ labels $\ell_{i,x}$ from a $2^{256} \times 2^{256}$ Sudoku (Latin-square), how difficult is it for an adversary to solve?

There's a keyed-permutation I'm playing with, $\ell_{i,x} = \pi_i(x_i)$, which is a bijection $X \leftrightarrow X$, where $|X| = 2^{256}$, and whose evaluations on plaintext inputs $x_i$ perfectly ...
aiootp's user avatar
  • 785
0 votes
1 answer
53 views

Regarding: Pseudorandomness, Pseudorandomgenerators and Padding

Hey there guys and gals, so I am right now studying topics regarding pseudorandomness. I was wondering why, for example with CBC-MAC oder a regular CBC blockcipher, we use padding instead of a PRG. ...
LePetit's user avatar
  • 15
1 vote
0 answers
103 views

Can a one-way permutation be used to stretch a pseudorandom generator?

Consider a secure PRG $G:\{0,1\}^\lambda \to \{0,1\}^n$ and a one-way permutation $f:\{0,1\}^{n-\lambda} \to \{0,1\}^{n-\lambda}$. I'm wondering if the following construction $G': \{0,1\}^\lambda \to \...
Vishnu Iyer's user avatar
1 vote
1 answer
72 views

Can the last n bitcoin blocks (including transactions) be reliable enough to be used as a seed for a PRNG or an input to a crypto hash-function?

Suggested by u/HolgerBier on reddit Is it unpredictable enough or too difficult to manipulate (as in more than a few hundred million USD) to have a sequence of blocks?
TheReal_Skywalker's user avatar
1 vote
0 answers
51 views

What are some ways to produce a pre-determined sequence of a large number of dice rolls? [closed]

What are some ways to produce a pre-determined sequence of a large number of dice rolls (on the order of 100-1000 times) using biased dice or a biased human roller given the constraints that multiple ...
TheReal_Skywalker's user avatar
2 votes
1 answer
70 views

Conceal time-based GUIDs with an affine-cipher?

I'd like to create a custom type of sortable GUID by concatenating an 8-byte nanosecond timestamp, 6 random bytes, a 1-byte node number, and a 1-byte counter. But, such a precise timestamp can be used ...
aiootp's user avatar
  • 785
1 vote
0 answers
55 views

Effcient collision attack for the Davies-Meyer compression function [closed]

We have a block cipher $E:\{0,1\}^{128}\times\{0,1\}^{128}\rightarrow\{0,1\}^{128}$. We know that the PRP advantage of E is Adv$_E^{PRP}=t/2^{128}$ where $t$ is the time needed by the algorithm to get ...
RudeusGreyrat's user avatar
3 votes
1 answer
791 views

Is there a 32 bit block cipher that is also a permutation over all 4bn elements?

Purpose: I'd like to shuffle a file system's blocks without loosing space so I thought if I formatted the disk to have exactly 2^32=4bn sectors, then a secure cipher with 32 bit wide data blocks could ...
yacrc's user avatar
  • 33
1 vote
0 answers
57 views

DES next round key

I don't understand which DES key is used in the next round of Feistel construction. As you can see below, we use our original key that has been inserted in permuted choice 1, where we got 56 bits, ...
joxavy's user avatar
  • 11
1 vote
1 answer
113 views

Derive independent values using block cipher

Suppose having an arbitrary $GF(2^n)$ element $x$. Its distribution is unknown. The task is to derive two $GF(2^n)$ elements $y$ and $z$, that have uniform distribution and are independent from each ...
Georgy Firsov's user avatar
0 votes
2 answers
145 views

Are Block Ciphers Pseudorandom functions? [duplicate]

I am reading this page on wikipedia on Key derivation function here where it states: In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys ...
Finlay Weber's user avatar
1 vote
1 answer
67 views

An unconditional proof of a PRP by restricting adversary run time

I am a Ph.D. student studying CS theory, I made this account for this question. Recently, I seem to have obtained a proof of existence of a PRP (which is unconditional in the sense that it does not ...
Eccentric3523's user avatar
0 votes
1 answer
136 views

Is this pseudo random function any good and/or original? [closed]

I designed this pseudo-random function algorithm that takes a uint64 and returns a uint64. I'd like to know if it is any good ...
Andrew Tomazos's user avatar
1 vote
1 answer
141 views

Even-Mansour Cipher: Efficient algorithms for sampling a random permutation

My understanding of the Even-Mansour cipher is the following: We draw a random permutation $P$ from the set of all permutation $P: \{0,1\}^n \rightarrow \{0,1\}^n$. This permutation is public. We ...
cryptobeginner's user avatar
1 vote
0 answers
53 views

Generalizing randomized permutation functions

The paper on the "SNEIKEN and SNEIKHA" AE and HASH sponge-based algorithms, respectively, presents a 512-bit permutation function "SNEIK512" that, unlike other permutations (ie: ...
cookiecipher's user avatar
2 votes
2 answers
347 views

Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?

In Katz's Introduction to Modern Cryptography, Chapter 7 Practical Constructions of Symmetric-Key Primitives In previous chapters we have demonstrated how secure encryption schemes and message ...
Tim's user avatar
  • 151
0 votes
0 answers
95 views

Pseudorandom permutations

So I am trying to solve some exercises about pseudorandom permutations. Assume that keyed-permuation $E_k(x)$ is a pseudorandom permutation, where $|x|=|k|=n$. Using $E_k(x)$, we construct an ...
pepsilon's user avatar
2 votes
1 answer
84 views

Any way to find $g,P$ for max cycle size in Blum–Micali with $x_{i+1} = g^{x_i} \mod P $ and $x_0 = g$?

For some $g$ and prime $P$ the sequence $$x_{i+1} = g^{x_i} \mod P $$ $$ x_0 = g$$ can contain all numbers from $1$ to $P-1$ and with this it is a pseudo-random permutation of those numbers (EDIT: ...
J. Doe's user avatar
  • 573
4 votes
1 answer
454 views

The different bounds of PRP/PRF switching lemma

The PRP/PRF switching lemma is usually denoted as follows: I understand the proof of this version of the bound $\frac{q(q-1)}{2^{n+1}}$ and the game-playing technique behind it. However, I came ...
Max1z's user avatar
  • 145
3 votes
1 answer
151 views

Questions regarding the pseudorandom function construction of Banerjee, Peikert, and Rosen

I am trying to understand the following pseudorandom function constructed by Banerjee, Peikert, and Rosen in this paper, assuming the hardness of LWE. Consider the following LWE/LWR based pseudorandom ...
BlackHat18's user avatar
2 votes
1 answer
977 views

Nexor, an encryption algorithm that promises unlimited key sizes: Is it safe?

My intention is not to make spam here, but I came across this project in Github: https://github.com/andrewhodel/nexor It's an algorithm called Nexor, it promises encryption with unlimited key sizes. ...
phantomcraft's user avatar
5 votes
1 answer
270 views

What is the best way to pseudonymise IP addresses while retaining the ability to identify those that share a subnet?

Background: I'm developing an app that is based around registered users voting on stuff, and I want to create a heuristic that involves IP addresses as one way to flag accounts for further ...
Inkling's user avatar
  • 161
1 vote
2 answers
142 views

Is there any fundamental difference between the block cipher operations encryption and decryption?

Is there any fundamental reason to designate one direction of a block cipher as "encryption" and the other "decryption"? Or are these arbitrary choices? Or perhaps practical ...
eddydee123's user avatar
9 votes
3 answers
1k views

Any advantage to a block cipher which is not efficiently invertible?

The classic definition of a PRP includes efficient invertibility. Given that many modern cipher modes (CTR-based e.g. GCM) use only the forward direction of the block cipher, it seems that the ...
eddydee123's user avatar
2 votes
0 answers
74 views

Examples of one-way pseudo-random permutation?

One-way functions have many candidates such as integer factorization. I am interested in combinatorial one way permutations. Specifically, I am interested in known one-way pseudo-random permutations (...
Mohammad Al-Turkistany's user avatar
2 votes
3 answers
800 views

How are the keys used in cryptography generated?

It seems there are keys everywhere in cryptography. From things like HMAC to encryption (both asymmetric and symmetric). The bit I do not totally understand now is how are cryptographic keys generated?...
Finlay Weber's user avatar
1 vote
1 answer
134 views

How to generate a random string in Python for a mission-critical application

I'm trying to figure something out, but it is difficult for me. I need to generate a fully random string in Python. My current function is attached below. I just want to know whether this is secure ...
LimesBytefend's user avatar
1 vote
0 answers
126 views

Formal security arguments for 3 round feistal network using PRF

There is a proof sketch in Introduction to modern cryptography that a three-round feistel network using pseudorandom round functions is a secure pseudorandom permutation PRP Πk against probabilistic ...
Chulbuli's user avatar
1 vote
0 answers
157 views

Four round Feistel network using pseudo random round function [closed]

I am solving a four-round Feistel network using pseudo-random round function is a strong pseudo-random function for security against adversaries, but I don't understand that how to solve I know 3 ...
Mary's user avatar
  • 11
0 votes
1 answer
205 views

How does this generate a permutation?

In the process of trying to answer this question, I ended up getting stuck. I found a paper which seems to solve their issue: its authors define a process which yields a pseudorandom permutation ...
JamesTheAwesomeDude's user avatar
8 votes
4 answers
252 views

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $...
Ritesh Singh's user avatar
2 votes
1 answer
181 views

Test the randomness of a random permutations, that was generated without Fisher-Yates?

Overview of the problem Before this gets immediately flagged as duplicate, I'm not interested in testing the Fisher-Yates shuffle for randomness, since this can simply be done by testing the ...
camel-cdr's user avatar
  • 123
5 votes
3 answers
368 views

How to combine $n$ 'less random' bits to generate one 'more random' bit?

Suppose we have a random number generator badrand() generating 1 with probability $0.9$ and 0...
Ritesh Singh's user avatar
5 votes
1 answer
215 views

Can a block cipher with fixed point permutations be a good PRP?

Let $E:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a good PRP and consider blockcipher $\widetilde{E}$ defined as follows $$\widetilde{E}(K,X) = \begin{cases}K & \text{if } X=K \\ E(K,K ) & \...
Yunus Karakaya's user avatar
0 votes
1 answer
71 views

Generator of one-way functions

Please pardon my question if it seems silly, but I am very keen on knowing: in applied cryptography, there is such a thing as a one-way function, which given an input would generate an output that is ...
jimmytann's user avatar
  • 177
2 votes
0 answers
93 views

Fisher Yates on "faulted" random number generator cryptanalysis

For the sake of curiosity and fun, i have implemented a C# program that operate as deck dealer on 40 cards deck (following the Fisher Yates shuffeling algorithm https://en.wikipedia.org/wiki/Fisher%E2%...
Skary's user avatar
  • 361
13 votes
1 answer
2k views

Formally, what is AES?

AES is supposed to be a symmetric key block cipher. The theoretical counterpart to this is a pseudorandom permutation. I'd like to say that AES is a PRP (well, supposedly at least), but that doesn't ...
extremeaxe5's user avatar
3 votes
2 answers
2k views

Why I can't permutate an email and get away with it?

I can understand why a simple substitution cipher can be broken easily using English letter frequencies, and even English digrams like th can be used. Also a ...
KMG's user avatar
  • 403
3 votes
2 answers
940 views

What is the difference between a permutation and a shuffle (transposition cipher)

A non-cryptographic definition of a permutation is "2a: the act or process of changing the lineal order of an ordered set of objects. 2b: an ordered arrangement of a set of objects The Wikipedia ...
SAI Peregrinus's user avatar
1 vote
0 answers
117 views

Impossibility of recovering the key of a keyed pseudorandom permutation

I'm currently working on some cryptography homework, but I'm stuck on this particular question. Let $F$ be a pseudorandom permutation with identical key length and block length (both equal to the ...
Peiffap's user avatar
  • 111
3 votes
1 answer
4k views

Two Round Feistel network

While reading on block ciphers and DES I read that two-round Feistel network is not a secure PRP? Is there any easy to understand proof to explain the intuition behind this statement. I did search ...
Alex's user avatar
  • 321
1 vote
0 answers
93 views

Is there a universal construction for Davies-Meyer hash functions?

My understanding is that there exists no strong pseudorandom permutation for which the Davies-Meyer construction is known to yield a provably collision-resistant hash function. Were I mean provably ...
Keshav Srinivasan's user avatar
1 vote
1 answer
266 views

Security of block cipher PRP(k⊕m)⊕k

Let $\mathcal S=\{0,1\}^n$ be the set of bitstrinsg of $n$ bits (for security parameter $n$). Let $P$ be a public Pseudo-Random Permutation of $\mathcal S$, efficiently computable in both directions. ...
fgrieu's user avatar
  • 138k
3 votes
1 answer
118 views

Is there any block cipher which is also a pseudo-random-permutation over the key

As block ciphers are defined as a pseudo-random-permutation over the data (keyed with the key), I was wondering, if there are also constructions for which key and data can be switched and the cipher ...
DasArchive's user avatar
0 votes
1 answer
88 views

Shuffling: Purpose and formal definition

To my understanding, shuffling means simply to permute the elements in vector $\mathbf{v}$ pseudorandomly, using a PRP $\pi (\mathrm{seed},\mathbf{v})$. A secure PRP should yield a permutation ...
Daniel B's user avatar
  • 347