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.
171
questions
4
votes
0
answers
53
views
Repeated tweak in tweakable block cipher
I am reading the proof for the Tweakable Authenticated Encryption in the paper Tweakable Block Ciphers. They stated that if the tweak is not repeated, the output of each tweakable random permutation ...
- 41
1
vote
1
answer
59
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?
1
vote
0
answers
49
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 ...
2
votes
1
answer
63
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 ...
- 53
1
vote
0
answers
52
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 ...
3
votes
1
answer
731
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 ...
- 33
1
vote
0
answers
51
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, ...
- 11
1
vote
1
answer
105
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 ...
- 208
0
votes
2
answers
127
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 ...
- 484
1
vote
1
answer
62
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 ...
0
votes
1
answer
131
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 ...
- 637
1
vote
1
answer
96
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 ...
- 347
1
vote
0
answers
48
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: ...
- 195
2
votes
2
answers
259
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 ...
- 151
0
votes
0
answers
75
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 ...
- 1
2
votes
1
answer
80
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: ...
- 557
4
votes
1
answer
337
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 ...
- 125
2
votes
1
answer
123
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 ...
- 347
2
votes
1
answer
976
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.
...
- 867
5
votes
1
answer
203
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 ...
- 161
1
vote
2
answers
133
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 ...
- 147
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 ...
- 147
2
votes
0
answers
70
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 (...
2
votes
3
answers
484
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?...
- 484
0
votes
0
answers
73
views
Are there any block ciphers (like AES) which are (or can be) commutative under composition for different keys?
Let $BC$ be a block cipher with similar security as AES (in ECB mode).
This $BC$ is applied to a message $m$ of same bit size. The result is a cipher $c$.
e.g.;
$$BC(key_A,m) = c_A$$
$$BC(key_B,m) = ...
- 557
1
vote
1
answer
119
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 ...
1
vote
0
answers
106
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 ...
- 11
1
vote
0
answers
146
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 ...
- 11
0
votes
1
answer
177
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 ...
8
votes
4
answers
225
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 $...
- 319
1
vote
1
answer
148
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 ...
- 113
5
votes
3
answers
334
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...
- 319
5
votes
1
answer
204
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 ) & \...
- 276
0
votes
1
answer
65
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 ...
- 177
2
votes
0
answers
89
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%...
- 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 ...
- 249
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 ...
- 403
3
votes
2
answers
732
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 ...
- 5,536
1
vote
0
answers
110
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 ...
- 111
3
votes
1
answer
3k
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 ...
- 321
1
vote
0
answers
83
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 ...
1
vote
1
answer
238
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.
...
- 134k
3
votes
1
answer
108
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 ...
- 71
0
votes
1
answer
86
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 ...
- 337
1
vote
2
answers
529
views
Is there a Pseudo Random Permutation Generator that can output all values of the length of N
Is there a pseudo random permutation generator that produces all permutation of any bit length of the plaintext (this may not be clear, please let me know and I will explain). It must be fast, and ...
4
votes
2
answers
456
views
What makes AES look like an ideal cipher?
There are 2128! permutations on 128-bit inputs. AES supports a maximum key length of 256 bits, therefore offers at most 2256 permutations. The total number of 128-bit permutations is much larger than ...
- 699
0
votes
0
answers
107
views
Is it possible to compute permutations of a sequence of bytes by using exactly one pseudo-random number?
Suppose I have a certain sequence of bytes, for example 0102F4829hex, and I can pick from a pseudo-random number generator exactly one number.
Is it possible, by using exactly one pseudo-random number ...
- 139
7
votes
2
answers
508
views
How random are permutations generated from Feistel networks with a small number of rounds?
I wrote a toy pseudo-random permutation out of a Feistel network using blake2b. However, looking at the distribution of permutations for small n = 6, it's clearly not uniform unless many rounds are ...
- 245
3
votes
0
answers
104
views
Provably secure way of expanding permutations
Gimli is a 384-bit permutation that makes use of an internal 96-bit permutation which works on columns. Every 4 rounds starting from the 1st a "small swap" is performed and every 4 rounds ...
- 143
1
vote
0
answers
91
views
Implementing MAC with PRF family $f$, why do we need $f_k$ to be invertible?
As per the title, say we have $\text{MAC}(k,m) = (m,f_k(m))$ where $f$ is a PRF family and every function $f_k$ is PRP, where $f_k(m)$ and $f_k^{-1}(m)$ are efficiently computable. I proved that this ...
- 11