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.
177
questions
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) &= (...
- 169
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 ...
- 169
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 ...
- 169
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 - ...
- 169
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 (...
- 169
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 ...
- 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. ...
- 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 \...
- 11
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?
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 ...
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 ...
- 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 ...
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 ...
- 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, ...
- 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 ...
- 223
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 ...
- 484
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 ...
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 ...
- 637
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 ...
- 347
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: ...
- 307
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 ...
- 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 ...
- 1
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: ...
- 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 ...
- 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 ...
- 357
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.
...
- 877
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 ...
- 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 ...
- 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
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 (...
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?...
- 484
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 ...
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 ...
- 11
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 ...
- 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 ...
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 $...
- 319
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 ...
- 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...
- 319
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 ) & \...
- 276
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 ...
- 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%...
- 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
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 ...
- 5,786
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 ...
- 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 ...
- 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 ...
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.
...
- 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 ...
- 71
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 ...
- 347