Is LUKS Anti-Forensic information splitter (AFsplit) indistinguishable from random data? I want to know if AFsplit(random_data_input, stripes, digestmod=sha) output is indistinguishable from random data.

The attacker only has access to AFsplit output data.

EDIT: This question is too vague as the answer depends on the randomness hypothesis taken about random_input_data. Take care of it reading the proposed answers.

The purpose is to use this function in a deniable encryption implementation.

About AFsplit: AFsplit provides a security against forensic attacks on disk bad blocks. AFsplit splits data among several disk blocks so that if a block is put in reserved "bad block" area, it doesn't contain a complete sensitive information (particularly, a revoked key slot). LUKS uses AFsplit to store the key slots.

Note: I'm not speaking of LUKS itself that is, of course, a plain header. I just want to focus on this particular function.

Below is AFsplit Python implementation:

import sha, string, math, struct
from Crypto.Util.randpool import RandomPool
from Crypto.Cipher import XOR
def _xor(a, b):
    """Internal function to performs XOR on two strings a and b"""

    xor = XOR.new(a)
    return xor.encrypt(b)

def _diffuse(block, size, digest):
    """Internal function to diffuse information inside a buffer"""

    # Compute the number of full blocks, and the size of the leftover block
    full_blocks = int(math.floor(float(len(block)) / float(digest.digest_size)))
    padding = len(block) % digest.digest_size

    # hash the full blocks
    ret = ""
    for i in range(0, full_blocks):

        hash = digest.new()
        hash.update(struct.pack(">I", i))
        hash.update(block[i*digest.digest_size:(i+1)*digest.digest_size])
        ret += hash.digest()

    # Hash the remaining data
    if padding > 0:
        hash = digest.new()
        hash.update(struct.pack(">I", full_blocks))
        hash.update(block[full_blocks * digest.digest_size:])
        ret += hash.digest()[:padding]

    return ret

def AFSplit(data, stripes, digestmod=sha):
    """AF-Split data using digestmod.  Returned data size will be len(data) * stripes"""

    blockSize = len(data)

    rand = RandomPool()

    bufblock = "\x00" * blockSize

    ret = ""
    for i in range(0, stripes-1):

        # Get some random data
        rand.randomize()
        rand.stir()
        r = rand.get_bytes(blockSize)
        if rand.entropy < 0:
            print "Warning: RandomPool entropy dropped below 0"

        ret += r
        bufblock = _xor(r, bufblock)
        bufblock = _diffuse(bufblock, blockSize, digestmod)
        rand.add_event(bufblock)

    ret += _xor(bufblock, data)
    return ret

Is LUKS Anti-Forensic information splitter (AFsplit) indistinguishable from random data?

No.

AFSplitting is merely meant to provide diffusion, not cryptographically secure randomness.

When you check the LUKS On-Disk Format Specification (eg PDF of v1.1.1) you'll notice it states

  LUKS uses anti-forensic information splitting as specified in [Fru05b]. The underlaying diffusion function shall be SHA1 for the reference implementation, but can be changed exactly as described in the remarks above.

Even though the (broken due collision attacks) SHA-1 function is used as a diffusion function in the reference implementation, that doesn't mean the AFSplitting function does provide any more than that – diffusion.

While it definitely has a (let's just call it) random character, you should not generally rely on it to provide cryptographically secure randomness indistinguishable from random data. That's not what AFSplitting (by itself) is intended to provide. While diffusion surely adds to randomness, there's a big difference between “diffusion” and “cryptographically secure randomness indistinguishable from random data”. Both are hardly exchangeable terms.

And I'm not yet considdering practical breaks against SHA-1 which also might or might not render the answer into a clear “no”… but that's another question.

EDIT

To clarify this a bit more indeep, trying to clear up some confusion in the comments by the asker.

Let's remember the question asked

  I want to know if AFsplit(random_data_input, stripes, digestmod=sha) output is indistinguishable from random data, not knowing random_data_input.

and

  … I just want to focus on this particular function.

The question didn't ask if PBKDF2 is indistinguishable from random data and the question did not assume input to AFSplit to be indistinguishable from random data either.

Therefore, when merely focussing on the AFSplit functionality (as the question asks), one can and has to cryptanalytically assume distinguishable data inputs too. Otherwise, the input to AFSplit would have needed to be defined as “exclusively data indistinguishable from random data”, but the question doesn't limit the input to such indistinguishable data when asking what AFSplitting outputs.

In LUKS the user password is entered and processed by PBKDF2 (which provides the randomness which should be indistinguishable from random data.  The master key is then splitted by the AFsplitter into a number of stripes… via diffusion (using SHA-1 or an alternative replacement).

So, any data indistinguishable from random data needs to be produced outside the AFSplit function. If you'ld feed AFSplit distinguishable data, AFSplit won't magically turn the data you feed it into data indistinguishable from random data; it merely diffuses what you feed it. That's all you get when keeping the focus on this particular function (and the main reason for no as an answer). How the input to AFSplit should be produced in a LUKS implementation is another story, and goes well beyond the AFSplit function (which is merely a diffusion-providing piece of the LUKS cake) and therefore well beyond what was being asked – which was to focus on this particular function.

This technique allows to spread some small data all over the disk sector. The sector is partitioned in several random stripes and you need all of them to get the data.
So, yes, the sector has a random aspect.


Is this a good way extracting randomness from some physical process? Let's say the system has a hardware randomness generator, generating random numbers using a proven truly random process. The distribution of the numbers though, is unknown.

Assume the randomness source generates data blocks $P_1$, $P_2$, ..., $P_n$. There is an one-way function $f(x)$. The output data blocks are $Q_1$, $Q_2$, ..., $Q_n$. There is an initialization vector $Q_0$. The length of $P_n$ blocks, $Q_n$ blocks, $Q_0$, input and output block length of function $f(x)$ are all equal.

For each output block $Q_n$, there is:

$$
Q_n = f(P_n \oplus Q_{n-1})
$$

Questions:

Can the process above extract the randomness from the hardware source, given a proper $f(x)$ and $Q_0$?
What is the requirement for the one-way function $f(x)$ and the initialization vector $Q_0$ for this process to work properly?
Can I replace the $\oplus$ with something else without breaking the randomness? (Replacing it can allow me to relax the block length restriction.)
Can I extend this method into combining multiple randomness inputs?

If hash collisions of f don't exist then information is neither created nor destroyed by f and $f(Q_{n-1}\oplus p_n)$ has as much entropy as $Q_{n-1}\oplus p_n$ which has as much entropy as $p_n$. If (for example) $p_n$ only introduced one bit of entropy then someone with $Q_{n-1}$ and access to the same randomness source can deduce the only two possible values for the next hash.

By "extract randomness" I think what you mean is that all blocks of P should have as much entropy as there are bits in P? A good hardware random number generator should already do that. If it doesn't then bits must be destroyed to turn them into entropy. Either $P_n$ gets mapped onto a space of fewer bits or you take multiple instances of $P_n$ and compress them into one. For example you could use the central limit theorem to take several samples from your unknown distribution and generate a normal distribution. Then you can turn the normal distribution into a uniform one.

See the following application note for the controller you're using:-

AN4230 Application note: STM32 microcontrollers random number generation validation using NIST statistical test suite.

This is an extract:-

  The purpose of this application note is to provide guidelines to verify the randomness of the numbers generated by the random number generator peripheral embedded in a selection of STM32 microcontrollers. This verification is based on the National Institute of Standards and Technology (NIST) Statistical Test Suite (STS) SP 800-22rev1a (April 2010).

The nature of these devices is that they produce uniformly distributed 32 bit words, notwithstanding the previous output. The note shows the STM32 TRNG passing all of the NIST randomness tests, and this is from the datasheet:-

  The RNG passed the FIPS PUB 140-2 (2001 October 10) tests with a success ratio of 99%.

So you don't really need to do anything with the RNG output other than use it as is for TLS seeding. Entropy extraction is unnecessary as that's done on-chip. If you trust it, that is.


A hash function for sets that from a hash of a set and a subset of it doesn't reveal the hash of the remaining elements in the set I'm looking for a function to compute a hash of a set.

It needs to satisfy two properties:

If someone published a hash $h(S)$ of a set $S$ and a hash $h(S')$ of some subset $S' \subset S$ of it, I should not be able to compute the hash of $S \setminus S'$ from $h(S)$ and $h(S')$.
From the hashes $h(S_1)$ and $h(S_2)$ of two disjoint sets $S_1$ and $S_2$, I should be able to compute the hash $h(S)$ of their union $S = S_1 \cup S_2$.

Does such a hash function exist?

Here is an idea which mostly addresses what you appear to want; I'm not happy with it, however I thought I'd share it just in case.

Our 'hashes' are vectors of $n$ elements, each element being either a number between 0 and $p-1$, or the special symbol $\bot$.

The hash of a singleton element $s$ (that is, a set that consists of a single element) is computed by selecting the $n$ elements to be numbers deterministically (e.g. using the bits from SHAKE(s)), and then selecting $b$ of the $n$ indicies (again, deterministically), and setting each of those $b$ indicies to $\bot$.

And, to combine two hashes (using Ilmari's notation, to compute $c = a \otimes b$), you perform the following operation element-wise to the two hashes):

$c_i = \bot$ if $a_i = \bot$ or $b_i = \bot$

Otherwise, $c_i = a_i + b_i \bmod p$

It should be obvious that the above operator is both associative and commutative.

And, assuming $p, n, b$ are properly set, then given $a \otimes b$ and $a$, it should be highly probable that $b$ cannot be recovered (as there is likely be to some element $i$ in $a$ for which you have $a_i = \bot$ and $b_i \ne \bot$; in that case, you have no information on $b_i$, and so any of the $n$ possible values are equiprobable.

Of course, the hashes are quite large, and this noninvertability is only probable (and even that is true only if the sets $a, b$ are not too large).

Let's formalize your encoding of the sets $S$ (assumed to be the subsets of some universal set $$\Omega=\{\omega_1,\ldots,\omega_n\}\leftrightarrow (1,\ldots,1)$$ as the string
$$E(S)=(\mathbb{1}\{ w_k \in S\}: 1\leq k \leq n)$$
which has a $1$ in the $k^{th}$ position if and only if $w_k$ is an element of $S.$ So to hash a set you hash its encoding $E(S).$

Note that any good hash function should have the avalanche property; i.e., if a bit is flipped (say an element is added or removed from $S$ to obtain $S'$) the two hashes $h(E(S)),$ and $h(E(S'))$ should not be easy to determine from each other, the property you want should hold provided $n$ is large enough so that it can't be brute forced for a collision, say $n>2^{512}.$

If the universe is not so large, you may need to use some kind of salting to increase the strength of the hash function.


Why does the CBC-MAC require PRFs? I'm stuck on exercise 4.19 from Introduction to Modern Cryptography.

  Let $F$ be a keyed function that is a secure (deterministic) MAC for
  messages of length $n$. (Note that $F$ need not be a pseudorandom
  permutation.) Show that basic CBC-MAC is not necessarily a secure MAC
  (even for fixed-length messages) when instantiated with $F$.

My idea was to construct the secure MAC $F'_k = m \| F_k(m)$, which would leak information on $F_k(m_1)$.
However, that would double the size of the MAC with every step.

Is there another/better/working solution?

Why are PRFs required for the CBC-MAC domain extension?

Edit: basic CBC-MAC refers to the following construction:

The book states that basic CBC-MAC is secure for fixed length messages when instantiated with a PRF.

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 be.
But ignoring this fact for a moment, one of your observations was indeed crucial.
A MAC does in general not hide it's input message.
As you point out, if $F'$ is a secure MAC, then the MAC $F$ defined as $F_k(m) := m\Vert F'_k(m)$ is also secure.
However, if the function $F$ allows recovering its input from its output, then in the CBC-MAC construction we learn one of the intermediate values.
And that is a problem.

Let's look at the case of $\ell=2$, i.e., messages have exactly two blocks, i.e., $m=m_0\Vert m_1$.

We attack the CBC-MAC by first choosing a message $m=0^n\Vert 0^n$ and querying it to the MAC oracle.
The CBC-MAC for our query will be computed as follows:
\begin{align*}
  t_1 :=& F_k(0^n)\\
  t_2 :=& F_k(0^n\oplus t_1) = F_k(t_1)
\end{align*}
and $t_2$ is output as the tag.

Now, if $t_2$ allows us to recover the input of $F$, then this means we learn $t_1$.

We can now output the message $m^* = t_1\Vert t_2$ and the tag $t^*=t_1$ as our forgery.
We can verify that this is indeed a valid forgery by recomputing $t^* = t^*_2$:
\begin{align*}
  t^*_1 :=& F_k(m^*_1) = F_k(t_1) = t_2\\
  t^*_2 :=& F_k(m^*_2\oplus t^*_1) = F_k(t_2\oplus t_2) = F_k(0) = t_1
\end{align*}
And, given that $F$ is a secure MAC and it's output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible andf therefore our attacker is successful with all but negligible probability. (This can be generalized for an arbitrary message $m$, but I'll leave this as an exercise to the reader.)

The issue that remains is: How can we construct a length-preserving MAC such that we can reconstruct $t_1$ from $t_2$?
The construction $F_k(m) := m\Vert F'_k(m)$ clearly does not work, since it is not length preseving, but we can do something similar.

Let $F'_k : \{0,1\}^n \to \{0,1\}^{n/2}$ be a secure MAC.
Then we define $F$ as $F_k(x\Vert y) = y\Vert F'_k(x\Vert y)$ for $|x|=|y|=n/2$.
I leave proving that this remains a secure MAC as an exercise to the reader.

It remains to show how this $F$ allows us to reconstruct $t_1$ given $t_2$ in the above attack.
For this, observe the values of $t_1,t_2$ in this instantiation.
\begin{align*}
  t_1 :=& F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\
  t_2 :=& F_k(t_1) = F'_k(0^n) \Vert F'_k(t_1)
\end{align*}
I.e., given $t_2 := a\Vert b$, we can directly see that $t_1 := 0^{n/2}\Vert a$.
Therefore the attack sketched above works with this instantiation.

In general, CBC-MAC with fixed length is secure. However, in this example $F$ is "a secure (deterministic) MAC" which could mean that we can conduct the message authentication experiment MAC-forge on it and use that outcome for CBC-MAC.


In the Diffie Hellman Key exchange, why is a value of $a=\frac{p-1}{2}$ a bad choice? In Diffie Hellman key exchange, we have a large prime $p$ and non zero residue class $g \in F_p^x$ with a large order.  An $a$ and $b$ are chosen in secret, and those are used to compute $A \equiv g^a \mod p$ and $B \equiv g^b \mod p$.

Then the two communicating agree on value $g^{ab}$ via $A^b$ and $B^a$.

$a=p-1$ would be a bad choice (by Euler Fermat theorem). My question is why is the value of $a = \frac{p-1}{2}$ a bad choice?

In Diffie-Hellman besides $p$ being prime, if the factorization of $p-1$ comprises at least one big prime $k$ such that $p=2k+1$ (can be also $jk+1$, this is a safe prime). In the worst case if the factorization is composed of computable factors then we can compute $x$ using the direct product of cyclic groups (Pohlig-Hellman).

Normally, if $p$ is prime and $g$ a generator with order $p-1$ then $g^{\frac{(p-1)}{2}} \equiv p-1 \equiv -1 \pmod p$

If $g$ is a generator of the subgroup of prime order $k$, where $k$ is large enough then $g^{\frac{(p-1)}{2}} \equiv g^k \equiv 1 \pmod p$

Both congruences are deterministic as you can see.

Generally, two congruences are related by symmetry, since both have the same square root mod p:

$$g^a \equiv -(g^b) \pmod p \quad \iff b = x-d, \ d = \frac{p-1}{2}$$


Why do people criticize and mistrust the e-voting based block chain? I am planning to implement an e-voting system based on hyperledger fabric blockchain, however, I came across many criticisms from well-known security experts like Josh Benaloh and others. The problem is I couldn't find any proof that the e-voting is definitely insecure. In my opinion, I think Blockchain can be considered the best solution compared to the current voting system as it covers many security aspects.

can anybody explain to me thoroughly with tangible examples and proofs?

There's a good reason many democracies reserve mail voting to rare cases where that's the only option: it allows one's vote to be influenced by duress or bribery, because one can prove how one voted. No remote voting technology that I know has solved that issue. Ergo, physically going to a polling station with isoloirs should remain the normal voting procedure for political elections in a democracy. And this comment is right to point that some¹ usages of blockchain in electronic voting can ease vote selling.

A large fraction of voters do not understand cryptography or math, some are not even able to follow a logical argument. Even if a complex system was impossible to fraud, they would not be convinced that it is. Therefore simple systems that people understand are the best ones from the standpoint of having the people trust the outcome, which is critical to why we vote: decide who leads without a civil war.

Many electronic voting systems in use (including, in physical polling stations) fail to give a convincing argument to a rational and knowledgeable person that a vote gets counted as cast. People who know something about e-security are the hardest ones to convince because they see how an insider can rig the machine/system. I can't criticize the "e-voting system based on hyperledger fabric blockchain" of the question from that standpoint since it is not described, but ask yourself: how could an insider rig the result? And would it be that easy to make a fraud that can't be detected in a traditional voting system, where voters put a paper bulletin in an envelope at a polling station, publicly insert the envelope in a transparent box, these get locally and publicly opened and bulletins counted at the end of the day, and results of each polling station nationwide are made public, so that anyone can check this public record for accuracy when it comes to the polling station where s/he was a witness, and redo the addition towards the national outcome?

¹ Blockchain-based solutions that aim at securing the collection of results of different voting places, or prevent double voting by an individual, do not necessarily facilitate vote selling.

[...] any proof that the e-voting is definitely insecure.
[...] Blockchain can be considered the best solution compared to the current voting system as it covers many security aspects.
can anybody explain to me thoroughly with tangible examples and proofs

In cryptography, a system is considered secure:

under a set of assumptions
if formal proof exists
if an attack requires so much more effort than normal usage of the system that the attack is not only infeasible but impossible.

The proposed

e-voting system based on hyperledger fabric blockchain

is lacking so many details that no one will be able to provide proof that it is insecure. However that does not mean it is secure. Quite the contrary, typical "security assumptions" for blockchain systems include:

proof of work - this typically means, that the system is secure unless a single attacker has a substantial part of the computing power of the rest of the system. The Bitcoin blockchain is computed in a distributed network. If at any point in time any attacker ever has more computing power than the network, they can fake blocks, that will not become part of the blockchain. This makes the supposedly irreversible transactions in Bitcoin reversible (by abandoning the faked branch) and allows for fraud. This attack is even described in the whitepaper founding Bitcoin. It's not bad practice, to describe potential attacks on the system. However it is bad that the attack only requires an effort from the attacker that grows linearly with the effort put in by regular users.
Non-blockchain systems (i.e. actually effective cryptography) use exponential growth to be fast enough to be used comfortably by regular users while attackers would need all the computing power existing extrapolated to the expected end of life of the system running till the heat death of the universe to crack a single code. "Attackers not having a tad more computing power at any time" is a laughable security assumption in comparison.
trusted central authority - Bitcoin is a distributed system. Other cryptocurrencies (e.g. Ethereum) rely on a trusted central authority. However having a trusted central authority completely defeats the purpose of establishing trust via blockchain. Think about it this way: PayPal is a payment service with a trusted central authority. What benefit do cryptocurrencies add? They are slower. There's no fraud protection. Most people don't even get, what cryptocurrencies actually are.
PayPal doesn't use blockchain, because their system is simpler, faster and safer without.
non-quantum computing - Since OP tagged the question "elliptic curves", I'd like to "honourable mention" the impact of quantum computing. Since quantum computers can invert any function [citation needed] that they can compute, hash-based proof of work is likely to fail. If OP claims that his proposed system is "quantum secure", that is a strong claim that should be proven by OP, instead of asking for a proof to the contrary from people, who don't have any detail on the actual proposal. This is not just my opinion but actual practice in what's usually called an auditing process. Not passing auditing processes is also a feature of many blockchain systems as indicated by the criticism by well-known security experts.

E-voting can have some additional security assumptions

restricted access - There's a challenge to reprogram voting machines to play Doom. There's also a university professor, who takes photos of unattended voting machines. Both of this combined exemplify one of the rules of computer security: If an attacker has physical access to the system, it isn't your system anymore. Problem is, with dedicated voting machines you have to grant access to the machine to anybody, who wants to vote. Without dedicated voting machines, how do the elderly or the poor vote? How do you make sure, eventual non-dedicated machines used for voting are secure? If an attacker can change your software, they can make your software ignore the input of the user and vote for Cthulhu (why vote for the lesser evil?) instead. No amount of buzzwords (e.g. Blockchain) will change the fact that software can be changed.


In OTP you have $C=K\oplus{M}$. If the key is the same $C1=K\oplus M1$ and $C2=K\oplus M2$,  => $C1 \oplus C2$ = $K\oplus M1 \oplus K\oplus M2$ = $M1 \oplus M2$  If you have the same ciphertext, that means that the same message was encrypted. E.g. messages 4,6,7,11 have the same first 6 symbols.


How to establish if a string contains a message If you have a string S, then the string can be composed of four things:

cleartext
'random' data
encrypted data
compressed or otherwise non-encrypted, but modified, cleartext

If you want to see if the string is an encrypted message, (3), then you might construct a test for 'randomness', say the test is $T_0$. You'd then expect:

$T_0(a) \approx T_0(d)$ -- i.e. not interpreting a compression as an encryption because it is ordered
$T_0(b)$ $\not \approx$ $T_0(c)$ -- i.e. the message is detected

If the message is very well encrypted, then you'd expect:

$T_0(b) =  T_0(c)$ -- that is, the algorithm detects no patterns

Would that be correct?

I'd expect that a watermarked or steganographic image would be revealed as different from standard jpegs by a good $T_0$.

The randomness tests in 'diehard' and 'dieharder' look for specific types of pattern that would not be expected in strings of type (2). Would it not make more sense to structure a $T_0$ on known types of data, so, for example, an apparently normal image file that contained a message would stand out?

It will depend entirely on the specific encryption scheme. There is really no theoretical reason why a ciphertext should not be clearly identifiable as being a ciphertext and not a plaintext. In fact, take any encryption scheme and modify it so that the encryption algorithm works as before, only it appends to the ciphertext the string "THIS IS A CIPHERTEXT!", and modify the decryption algorithm to work as before only ignoring this string. For pretty much any reasonable encryption scheme this modified scheme will be (theoretically speaking) as secure as the original scheme.

Why is this? Because, when we evaluate the security of a scheme we assume that the adversary (i.e., the entity trying to break the scheme) knows what scheme he/she is breaking and is explicitly told what pieces of information are ciphertexts.


can half of an encrypted photo be decrypted with the key? if we have like some part of the encrypted picture,is it there any way that the picture can be decrypted. is there any specific algorithm that allows this. like can from 60 per cent of the encrypted picture, can we build it up to determone the actual picture
we also has access to the key. we know the algorithm. our purpose is to convert yhe 60 percent of cipher to image  form

OK, for clarity I'll quickly summarize your scenario:

You have the key and know the encryption algorithm.
You have 60% of the cipher text of an image encrypted under above key and algorithm.
You seek to decrypt the cipher text and reconstruct the full image.

There are two possible answers to this:

It's pretty much impossible. If the 60% are highly fragmented and you only got a bit of ciphertext every now and then, you may either suffer from desynchronization (if you don't know how large the gaps are) or you'll lose potentially even more information because you can't decrypt all the bits (highly dependent on the mode of operation in use)
You're lucky and have about 60% of the picture as a continuous block. This means that chances likely are that you can fully decrypt those 60% of the cipher text and start reconstruction of the image. How much of the image you can recover from 60%, I don't know. I suspect it depends on the details of the format and how interrelated the pixels for it are.

Not an expert, but that seems to be basically the known plain text issue.

Depending on the actual encryption mode you use, that can be problematic, but most modern crypto algorithms shouldn't allow that (AES doesn't, for example)


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

pseudorandom permutation
pseudorandom function
block cipher?

Very confused with the 3 terms and I am not good at advanced math. Can someone explain in plain word?

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 function $f_k$ which given another 256-bit string $x$ returns the xor of $k$ and $x$.  The input and output spaces need not be the same; we could imagine a family of functions $f_k$ from a 512-bit input $x$ to a 128-bit output $f_k(x)$, keyed by a 256-bit string $k$.  Here is a small function family $g_k$ with a 1-bit key, a 2-bit input, and a 3-bit output:

\begin{equation*}
\begin{array}{c|c}
x & g_0(x) \\
\hline
00 & 111 \\
01 & 000 \\
10 & 100 \\
11 & 110
\end{array}
\qquad\qquad
\begin{array}{c|c}
x & g_1(x) \\
\hline
00 & 011 \\
01 & 110 \\
10 & 100 \\
11 & 100
\end{array}
\end{equation*}

A pseudorandom function family is a family of functions—say functions from 512-bit strings to 128-bit strings, indexed by a 256-bit key—which has the following property.

Suppose I flip a coin 256 times to pick $k$—that is, I choose $k$ uniformly at random.
Suppose I also pick a function $F$ from 512-bit strings to 128-bit strings uniformly at random from all $(2^{128})^{2^{512}}$ such functions, by flipping a lot of coins—enough to fill a book with $2^{512}$ pages so that each page has a 128-bit answer on it.

(Each table above has $4 = 2^2$ rows, because the input is 2-bits long, with a total of $3 \cdot 2^2 = 12$ bits of outputs written down, because there are three bits of output for each distinct input and $2^2$ distinct inputs.  For a uniform random 512-bit-to-128-bit function, you need $2^{512}$ rows, and each row has $128$ bits of output, for a total of $128 \cdot 2^{512}$ bits just to write down one of the $(2^{128})^{2^{512}} = 2^{128 \cdot 2^{512}}$ different functions of that shape!)
I will pick one of these functions—$f_k$ or $F$, but you don't know which—and tell you what the value of the function is at any point you ask.

(Actually I don't need to fill the book up front; if I chose $F$, I can fill out the pages of the book lazily as I get queries from you.)

You can't figure out whether I gave you a member of the function family, $f_k$, or a uniform random function, $F$.

In other words, the probability distribution on functions $f_k$, when the key $k$ is chosen uniformly at random, is very close—as far as computationally bounded decision algorithms can discern—to the probability distribution on functions $F$ chosen uniformly at random from all functions.

A pseudorandom permutation family is similar, except $f_k$ and $F$ are restricted to be permutations, i.e. their input and output spaces are the same, say the set of all 256-bit strings, and they map every input to a unique output so that there is also an inverse function.  So there aren't quite as many possibilities for $F$—while there are $(2^{256})^{2^{256}}$ functions of 256-bit strings, there are only $2^{256}! \approx (2^{256}/e)^{2^{256}}$ permutations of 256-bit strings.  A block cipher is just another term for pseudorandom permutation family, for the most part.*

Here's an example of a small permutation family $\pi_k$ for comparison—again the key is 1-bit, and the inputs and outputs are 2-bit strings:

\begin{equation*}
\begin{array}{c|c}
x & \pi_0(x) \\
\hline
00 & 00 \\
01 & 11 \\
10 & 10 \\
11 & 01
\end{array}
\qquad\qquad
\begin{array}{c|c}
x & \pi_1(x) \\
\hline
00 & 01 \\
01 & 00 \\
10 & 10 \\
11 & 11
\end{array}
\end{equation*}

Note that unlike the tables for $g_k$, each output appears exactly once in each table here, so we can flip each table around to get an inverse permutation.

We can interpret the bit strings as integers in (say) big-endian binary, and write this using the alternative notation $\pi_k = (\pi_k(0) \; \pi_k(1) \; \pi_k(2) \; \pi_k(3))$ for permutations, by saying that $\pi_0 = (0 \; 3 \; 2 \; 1)$ and $\pi_1 = (1 \; 0 \; 2 \; 3)$.  Of course, for a pseudorandom permutation family like AES, the number of elements being permuted is not $2^2 = 4$ but $2^{128} = 340282366920938463463374607431768211456$, so we don't quite have enough space here to write AES down exhaustively in either notation even for a single key.

Actually it's not so much that a family of functions is or is not a pseudorandom function family, but rather we quantify your advantage as an adversary in playing that game.  Specifically, we consider a decision algorithm $A(\mathcal O)$ which takes an oracle $\mathcal O$—which might be $f_k$ for uniform random $k$, or might be a uniform random $F$—and returns a decision in $\{0,1\}$, and we consider the distance between the probability that $A(\mathcal O)$ returns $1$ given $f_k$ for uniform random $k$ and the probability that it returns $1$ given uniform random $F$, called the advantage of $A$ as a PRF distinguisher:

\begin{equation*}
  \operatorname{Adv}^{\operatorname{PRF}}_f(A)
  := \lvert\Pr[A(f_k)] - \Pr[A(F)]\rvert.
\end{equation*}

The PRP advantage is similar, but again $f_k$ and $F$ are restricted to be permutations.  If it's very hard to tell whether the oracle is answering for $f_k$ or $F$, then this distance is nearly zero.  Obviously, there is always a distinguisher with nonzero advantage: guess a key $\hat k$ at random and check whether $\mathcal O(x) = f_{\hat k}(x)$, but the advantage is very small, inversely proportional to the size of the key space.  What's more interesting is distinguishers that have much higher advantage.

We conjecture for certain functions like HMAC-SHA256 or KMAC128—based on a long track record of failure by cryptanalysts to find good distinguishers—that this distance is small no matter what the adversary $A$ is, as long as $A$ makes an imaginable number of queries.  (For example, we're not interested in an adversary that makes $2^{256}$ queries to the oracle, because nobody can do that.)

Then, when studying higher-level constructions like CBC-MAC, we set a bound on the forgery probability of the higher-level protocol in terms of a bound on the distinguishing advantage against the underlying PRF.  That way, we can study whether something like CBC-MAC is a good way to build a MAC out of a PRF separately from whether AES is a good PRF.

‘Wait, AES is a good PRF?’, you say, ‘I thought AES was supposed to be a permutation!’  Well, any PRP makes a good PRF up to the birthday bound.  Specifically, there's a theorem, sometimes called the PRF/PRP-switching lemma, that if $f_k$ is a $b$-bit permutation, then for any adversary $A$ making at most $q$ queries to the oracle, $$\operatorname{Adv}^{\operatorname{PRF}}_f(A) \leq \operatorname{Adv}^{\operatorname{PRP}}_f(A) + \binom{q}{2} 2^{-b}.$$  As long as $q \lll \sqrt{2^b} = 2^{b/2}$ so that $\binom{q}{2} = q(q - 1)/2 \lll 2^b$, the term $\binom{q}{2} 2^{-b}$ is very small.  In other words, as long as our application keeps its data volume well below the birthday bound of $2^{b/2}$ blocks, a good pseudorandom permutation family like AES is nearly as good as a pseudorandom function family.  This is, incidentally, the general reason why cryptosystems involving AES are not safe for more than a few petabytes of data under a single key—and for some of them the safe data volume limit is much lower.

* In some security analyses, it may be convenient to model a block cipher with a slightly stronger idealization than pseudorandomness: the ideal cipher model.  Pseudorandomness is a kind of logic quantifier: for uniform random $k$, $f_k$ is hard to distinguish from a uniform random permutation, and it applies to specific function families like HMAC-SHA256.  In the ideal cipher model, we study protocols where the function family itself is randomly chosen: for all distinct $k$, $f_k$ is an independent uniform random permutation.  Like the random oracle model, it is a model for how adversaries are structured, rather than a ‘property’ that a specific computable thing like SHA-256 or HMAC-SHA256 can exhibit.

Pseudorandom permutation
Confusingly, nothing really gets permuted here in the classic definition of a permutation.  It's more of a cryptographic twist on the common notion of permutation.  The actual input/output behaviour is like:-

And each input is mapped to exactly one output value. The above diagram is simplistic in that the size of the inputs and outputs can be of the order of 128 bits or $0 \to (2^{128} -1)$. This is called a bijective or injective surjective function, and AES is an example.
Pseudorandom function
The idea here is that the output is random looking.  Thus they behave as the following:-

Note the collision with 3, 4 & C. That occurs because random looking outputs collide randomly, similar to rolling pairs in dice. Output A cannot be attained due to the same collisions . But also note that these collisions are rare due to the size of the input/output domains (but not impossible depending on their actual sizes). This is called a non-injective non-surjective function. SHA-1 is an example.
Block cipher
This is simply a cipher function acting on multiple bytes at a time, rather than one. Like so, where each little square represents a byte:-

And it has to be  à la pseudorandom permutation otherwise  there would be collisions (as per above definition). That would mean that there would be multiple cipher texts matching up with a single plain text.  And that's confusing. The above example might be DES, acting on 8 bytes at a time. AES is one too, but operates on 16 bytes at a time.
The opposite would be a function called "stream cipher" operating sequentially on one byte at a time, like RC4.

Certain minor simplifications have been made and some trivial liberties taken.  This is to create a more strategic overview of the topic, and to offer a less 'mathy' answer.


Having CBC-MAC of a one block message, forge CBC-MAC of two blocks This whole question pertains to CBC-MAC.

Let's say $a$ is one cipher block long, and the attacker knows the MAC $M(a)$ of $a$, which was generated with a random key. How can the attacker forge the MAC of a two block message under the same key?

For example, if I have $M(a)$, can I forge $M(b||c)$, where $b$ and $c$ are both one block each?

If that is not possible, is it possible to forge $M(a||b)$ or $M(b||a)$?

Given just $a$ and $M(a)$, you can construct the message $a\,\|\,b$, where $b = a \oplus M(a)$, which gives the same CBC-MAC output $M(a\,\|\,b) = M(a)$ as $a$ itself.

Indeed, we can append the block $b$ to the message as many times as we like without changing the MAC value: $M(a) = M(a\,\|\,b) = M(a\,\|\,b\,\|\,b) = M(a\,\|\,b\,\|\,b\,\|\,b) = \dots$

The reason this works should be apparent by looking at the structure of CBC-MAC:

As the diagram shows, a message like $a\,\|\,b\,\|\,b\,\|\,\dots$ is processed block by block.  In the first step, we encrypt $a \oplus 0 = a$ with the block cipher, and obtain $M(a) = E_k(a)$ as the output.  If the message ended here, this would be the resulting MAC value.  However, if the message continues, the next block $b$ is XORed with the output $M(a)$ of the previous step and encrypted with the block cipher again.  If we choose $b = a \oplus M(a)$, then the input to the block cipher will be $b \oplus M(a) = a \oplus M(a) \oplus M(a) = a \oplus 0 = a$ again, and thus the output will also be $E_k(a) = M(a)$ again.

Welcome to Stackoverflow!

What you may be looking for https://en.wikipedia.org/wiki/CBC-MAC#Security_with_fixed_and_variable-length_messages


How do I explain zero knowledge proof to my 7 year old cousin? How do I explain zero knowledge proof to my 7 year old cousin?

I will use Bertie Bott's Every Flavour Beans from Harry Potter in my explanation. If your cousin has not read Harry Potter, you can refer to Jelly Beans instead.

So let's assume there are two beans which look same but one of them tastes like chocolate and the other one tastes like spinach. Your cousin claims that he can distinguish them just by looking at the beans. You don't believe him, but he doesn't want to tell you which one is which, so there is still a chance that you eat the spinach one.

Instead you hide them both behind your back and randomly choose one of them and show it to your cousin. You then put it back and choose randomly again in a way that allows you to know whether you picked the same bean or not (like swapping the beans x times). You then again show it to your cousin who will have to tell you whether it's the same bean as the one you showed before. Repeat this process until you are sure that he is indeed able to distinguish the beans (or that he's not).

You now know that your cousin is able to tell the beans apart while you still do not know which bean is the tasty one.

Finally, there are two side-channel attacks in this scenario:

He may be able to count how often you swapped the beans, so don't make it too obvious.
You could offer him one of the beans and when he refuses, it's probably the spinach one.

Peggy can tie pretty bows, like no-one else

Peggy knows how to tie very pretty bows. If you give any piece of string to Peggy, she will tie a bow for you, and give it back to you.

Everyone knows that Peggy can tie pretty bows, and they also know that the bows will look the same, every time. No matter what kind of string you give to Peggy, the bow will look the same.

But no-one knows how Peggy ties them, because that is Peggy's little secret. Only Peggy knows how to tie bows in the way that makes them look that way. And the bows are so incredibly intricate that you cannot try to untie a bow and figure out how she did it, because that would take a very long time.

One day Peggy comes to Victor and says "Hi, I am Peggy!". Victor says "Oh yes? Well if you are Peggy, then you can tie a special pretty bow for me, right?".
"Oh yes I can" says Peggy, "give me a piece of string and I will prove it to you!".

Victor gives Peggy a piece of string. Peggy takes it, turns around so that Victor cannot see what she is doing, and ties the bow. She then gives the bow to Victor.

Victor looks at the bow. First he checks that the string is the right one that he gave to Peggy (otherwise this could have been an impostor that has stolen a pretty bow that Peggy gave to someone else).

Victor says: "Can you do it again please?". Peggy says, "Sure! Give me a new string!".

Victor and Peggy does this several times, and every time Victor checks to see that the bows look exactly the same. Then Victor is happy and knows that Peggy can indeed tie this kind of bow with any string.

Hence...

Peggy knows a secret: how to tie a bow in a particular way. Victor can look at a bow and see that it was tied by Peggy, but Victor does not know how to do it themselves

What is this useful for?

If everyone — not just Peggy — knows how to tie pretty bows, but everyone ties them differently, we can make a catalogue. The catalogue says that Alice ties this type of bows, Bob ties that kind... Carol, Dave, Erin... everyone that we know is in this catalogue, along with the kind of bow they tie.

So some time later, Peggy comes back to Victor and says "Hi, I am Peggy!".

Victor looks at Peggy and says "You know what... I am really terrible with faces. But I have my catalogue of bows! Here is a piece of string. Can you please tie a bow for me?".

"Of course!" says Peggy, takes the string, turns around, and ties the special kind of bow only she knows how tie. She gives the bow to Victor.

Victor checks the bow against the catalogue and says "Oh yeah! This is the kind of bow that I know only Peggy can tie! Welcome back Peggy."


Want to generate numeric coupon codes? We want to generate coupon code series and then encrypt those coupon code in numeric only, and that must also be decipherable.

We will be sharing encrypted code as coupon code with customer.

These are the conditions:

Encrypted code must not be in series or not easily able to guess;
Encrypted code must be numeric.
Encrypted code must be having a specific number of digits (think: size/length).

Example :

We generate coupon code from 1 to 100 (needs in millions and plainCode will be either numeric or alphanumeric doesn't matter).

We want share encrypted numeric coupon code with specific digits to user.
i.e. if code is 52 then encrypted code gives us between 10000 to 99999 (if 5 digits are specified or it need to be fix number of digits)

We are also able to decrypt the same.

Note:

Above is just an example. possibilities are in millions.
Security is not a major concern. just not able to guess is matters a lot.
encrypted code must be in numeric.

Question:

Is there an established, cryptographical secure way to do this? If not, what would we need to do to handle this?

Any suggestions or ideas are more than welcome.

We have looked and FPE. Any good algo for the same recommended which return in specific number of digits. We have one which gives encrypted numbers less than specified number but we want in between specific range to maintain number of digits without 0 appending.

I have an almost identical requirement for location identifiers I use in a custom inventory system. I have a 35-bit code, which is displayed as 7 5-bit elements, which need to be human readable and unique. The method to generate the codes does not necessarily have to be format preserving, that can just be a side effect of the algorithm used.

The method I use generates a 7 character code, with each character being alphanumeric 0-9 and A-Z, omitting OIZS because they are too similar visually to 0125. Internally the algorithm is a block cipher called Bromine with 5 7-bit elements in a generalized Feistel network, which is based on the round structure of the HIGHT block cipher. The input is a numerical sequence, and the output is a pseudorandom alphanumeric sequence:

JE4HV9W
JPNJ4NE
V20MUP3
QCKCVWU
QTR7FUC
5E94W9J
4HYWH14
9W1229T
PT6JJTV
MEWTT68
91ACL19
....

Because the input sequence is numeric, there are only 10 million output combinations for the given 34.36 billion possibilities for a 35-bit value. This limits the number of ciphertexts available to reverse engineer the algorithm or determine the key used. The algorithm is simple but has enough rounds to be secure given the key size (in theory). The use environment has no requirement for this kind of security, but it allows it to be used for other applications if needed. The numeric input is a security and usability requirement, and not a limitation of the algorithm.

If used to generate coupon codes, certain input elements or bits can be fixed, and those fixed bits can define the coupon type or discount. The system would only need to keep track of used coupon codes, and decode them to determine the type and validity. Only 1/3436 codes entered randomly will decode to a valid input, and the number of coupons from valid inputs can also be limited further.

For example, your input could be structured as XXYYYYZ, where XX is the coupon type, YYYY is the value, and Z is a fixed element such as 0. Coupon 01 would be assigned to a 5% discount with only 100 allowed coupon uses before it expires. When entered into the system, it is decoded, its structural validity is determined (is numeric and Z=0), XX is determined to be a valid coupon, and YYYY is determined to have not been yet used for a given XX. If all requirements are met, the discount is given, and XXYYYY is saved for comparison with further coupons. Only 0.003% of this example format meets the required structure and only 1% of these decode to the desired coupon type.

If a longer code is required, variants of such a cipher are easily generated in other sizes. The 40-bit version extends the subwords to 8-bits, and is displayed as an 8 character code. A 42-bit version for display as 6-bit 7 character codes is created by extending the 5 subword 7-bit Feistel structure to 6 subwords, and the 48-bit version extends its subwords to 8-bits.

If I understand this correctly, you want to "encrypt" a number, turn it into a different one, and reverse the process? I think this algorithm is ok for this purpose…

Pseudocode: (for your "from number 1 to 100" example)

int i = 1
int key
int max = 100
list(of int) intList
read value for key
do until i = max
if i mod 2 = 0
intList.add(i * (i + key))
else
intList.add(round((i + _key) * i / 3))
end if
i+=1
loop

I implemented this algorithm in VB and I got some pretty random looking numbers
https://s22.postimg.org/42m3uoy01/bitmap.jpg

And you can reverse the algorithm to "decrypt" the numbers.

I got no collision (2 numbers producing the same value) but some got pretty close. Now if you were to sort the values by length (or even randomize their order) you would have a nice number of coupons that can be reversed to their initial number. Note that the smallest encrypted number doesn't equal the smallest decrypted number etc for each number.


In RSA, do I calculate d from e or e from d? In the original paper introducing RSA, it is implied that one should first choose $d$ and then calulate $e$ from $p$, $q$, and $d$. However, I have found in other places (such as the wikipedia article on RSA) that one should first calculate $e$, and only then calclulate $d$ from it.

Which of these two methods are preferred, and why?

Well, as far as the mathematics of RSA are concerned, $d$ and $e$ are symmetric; they are related by the relationship:

$$ e·d \equiv 1 \pmod{\operatorname{lcm}(p-1, q-1)}$$

So, from the perspective of making it work, it doesn't matter which you choose first.

Now, it is not sufficient that the RSA encrypts and decrypts properly, it also has to be secure.  From a security perspective, these values are not symmetric; $e$ (the encryption or verifying exponent)  is public and $d$ (the decryption or signing exponent) is private.  This means that $d$ must be a hard to guess value.  On the other hand, we couldn't care less if someone could guess $e$; we're going to tell him that value anyways.

That means that if we choose $e$ (and then compute $d$), we can choose $e$ to be a small value. This has a real advantage; it makes the public operation (public key encryption, signature verification) go much faster, without any loss of security.

In contrast, if we choose $d$ and then compute $e$, we have to select a large value for $d$ (both so that it is not guessable, and to avoid subtler attacks that can factor $n$ given an $e$ that corresponds to a small $d$), and so we end up with $d$ and $e$ both being large.  This slows down the operation without any corresponding advantage.

Because of this, common practice is to select a small $e$ (65537 is the most common value), select primes $p$ and $q$ such that $p\not\equiv 1 \pmod e$ and $q \not\equiv 1 \pmod e$ (so that $d$ exists), and then compute the corresponding $d$ value.

well I sort of came up with this method , I dont know whether most people already know this or not. For every example in my text book this method has worked

d= [ɸ(n) * (y)]+1 divided by e.
here y =  1 , 2 ...

eg p=5 , q=11 e=3  n will be 56 and ɸ(n) = 40

 d= (40 * 1) +1 / 3

    =  41/3
    = 13.66 --- but this is not an whole number

so

 d= (40 *2 )+1 /3
   =  80+1/3
   = 81/3
    = 27.

so your d must be 27!! I hope this helped . good luck  :)


Is it possible to have identical public keys for different ciphers? Is it possible (and is there any research I can read) to have 2 key pairs for different ciphers, for example RSA 1024 and some yet to be released EC (or other asymmetric cipher) than uses 1024 bit keys, that have the same public key?

There's not really a good way to answer your question other than to explain the concepts involved. The answer can be any one of "yes", "no", or "it depends".

Asymmetric encryption algorithms use public keys that have some structure. For instance, RSA public keys are a tuple of $(n,e)$, where $e$ is the exponent, and $n=pq$ for some primes $p$, $q$ unknown to all but the holder of the private key. In modern systems, $n$ will typically be on the order of 2,048 or 4,096 bits. ECC keys, on the other hand, consist of a point $(x, y)$ on an agreed-upon elliptic curve. In typical ECC schemes, each of these points will be on the order of 192, 256, or 384 bits.

Semantically there will not be colliding keys between these algorithms, because the constituent components of these keys have different meanings. On the other hand, it's technically possible (but exceedingly unlikely in practice) to create, say, a 512-bit RSA key whose $(n, e)$ is also a point $(x,y)$ on an elliptic curve used in ECC. Or, whose bit representation of $n||e$ is equal to the bit representation of a point on an elliptic curve $x||y$.

On the other hand, if two different ECC elliptic curves intersect, you could have a point $(x,y)$ that lies at that that intersection and works for both curves. One could also hypothesize the existence of a future cryptosystem that uses public keys of the form $(n,e)$ as RSA does, but isn't RSA.

However, most cryptosystems that handle public/private keys encode the type of key and additional parameters into the public key file, so it's impossible in practice to ever have a public key that will work natively for two different types of cryptosystems.

TL;DR, it's plausible that one could find colliding keys between different ECC schemes. It's not totally inconceivable to find a colliding key between RSA/ECC by either bit representation or by actual colliding $(n,e)=(x,y)$. And it's not out of the question for some new cryptosystem to reuse keys from an existing cryptosystem verbatim. But in practice, no real world software is likely to be able to use an single public key file for more than one cryptosystem.

Well, it is very rarely the case to have a collision. However it is still possible, especially if the Random Number Generator doesn't generate a good random. There is a group of researchers who are working on this problem you can check it out https://factorable.net

What they found is that

    • We found that 5.57% of TLS hosts and 9.60% of SSH hosts share public keys
         in an apparently vulnerable manner, due to either insufficient randomness
         during key generation or device default keys
    • We were able to remotely obtain the RSA private keys for 0.50% of TLS hosts
         and 0.03% of SSH hosts because their public keys shared nontrivial common
         factors due to poor randomness.
    • We were able to remotely obtain the DSA private keys for 1.03% of SSH hosts
         due to repeated signature randomness.

You may also check this article http://www.technewsworld.com/story/74436.html


Taking advantage of one-time pad key reuse? Suppose Alice wants to send encryptions (under a one-time pad) of $m_1$ and $m_2$ to Bob over a public channel.  Alice and Bob have a shared key $k$; however, both messages are the same length as the key $k$.  Since Alice is extraordinary lazy (and doesn't know about stream ciphers), she decides to just reuse the key.

Alice sends ciphertexts $c_1 = m_1 \oplus k$ and $c_2 = m_2 \oplus k$ to Bob through a public channel.  Unfortunately, Eve intercepts both of these ciphertexts and calculates $c_1 \oplus c_2 = m_1 \oplus m_2$.

  What can Eve do with $m_1 \oplus m_2$?

Intuitively, it makes sense that Alice and Bob would not want $m_1 \oplus m_2$ to fall into Eve's hands, but how exactly should Eve continue with her attack?

There is a great graphical representation (which I found on cryptosmith, but they keep changing their url structures, so I've added the graphics in here) of the possible problems that arise from reusing a one-time pad.

Let's say you have the image

and you encrypt it by using the binary one-time-pad (xor-ing on black and white)

.

You get the following extremely secure encryption

.

If you then encrypt a smiley face with the same one-time-pad,

you get another secure encryption

.

But if you have both and you xor them together

then you get the image

which, as you can qualitatively and intuitively see is very insecure.

Reusing the same key multiple times is called giving the encryption 'depth' - and it is intuitive that the more depth given, the more likely it is that information about the plaintext is contained within the encrypted text.

The process of 'peeling away' layered texts has been studied, as ir01 mentions, and those methods improve with more layers.

If you have $m_1 \oplus m_2$, you can learn about the underlying message format.

It is possible to determine patterns in the underlying plaintext and use these patterns to extract data from the ciphertext.


Post Quantum Symmetric Cryptography So I am looking for the most secure method of symmetric key cryptography for long term messaging use between two users. I have heard that most symmetric key algorithms are not absolutely compromised by quantum computers, but rather weakened.

I have read that AES 256 is in fact the weakest, followed by AES 128, and AES 192 being the strongest.

Let us imagine that today quantum computers exist with "good" capacity to break cryptography.

Is AES still the best symmetric key solution as of right now? If not which is? If so then which AES key space is the strongest?

These are many questions which remain unanswered or lack good discussion as there isn't much in regards to post quantum security concerns.

AES-256 is still considered the strongest (and is considered secure) as related key attacks are not particular to analysis with quantum computers.

Related key attacks could happen when AES is used within a construction such as a hash function, where the output of one round is used as a key for the next round.

As far as we know now, quantum computing won't have as much as an impact on most symmetric algorithms as it does on asymmetric cryptography (that usually relies on specific mathematical problems that can be solved using quantum computers).

As mentioned, the best generic attack on symmetric ciphers, Grover's attack, about halves the key strength. But you need a lot of qbits to create the attack. Of course, there may be new attacks found that are particular to a specific block cipher, but as far as we can see now, most constructs seems pretty secure against quantum computers. That means that a 256 bit key will still deliver 128 bits of security against analysis using quantum crypt-analysis.

That means that there seems little reason to double the 256 bit key strength, as 128 bits of security are considered plenty against any attack that require such kind of order of operations.

If you require 256 bits security with quantum computers (why?) you could consider Threefish-512 - an algorithm actually designed to deliver that kind of security.

Regarding using AES in the most secure way possible against quantum computers AND related key attacks (while keeping hardware compatibility with existing CPU cryptographic optimizations), I would suggest you to read https://eprint.iacr.org/2019/553 (Towards post-quantum symmetric cryptography).

At the time of the question we hadn't yet written a formal paper about it, and it is by searching the Internet for our paper that I found this question.


Hash Function Formating Question If a hash function is written:

Hash(Hello||World)

Is that equivalent to Hash(Hello) +  Hash(World) or Hash(HelloWorld) ?

Similarly, is there any difference between Hash(Hello||World) and Hash(Hello,World)?

Typically, the notation || means concatenation, which is to say Hello||World is equivalent to HelloWorld.

Is that equivalent to Hash(Hello) +  Hash(World) or Hash(HelloWorld)?

So Hash(Hello||World) is equivalent to Hash(HelloWorld).

Is there any difference between Hash(Hello||World) and Hash(Hello,World)?

This depends entirely on what Hello,World is defined to mean.

Notation does not have absolutely defined meaning - what a symbol means in one context can be different from what that symbol means in another context.

The only way to know for sure is to check the definitions of the notation from wherever you found this.

If there are no such definitions, then it is safe to assume the most common/obvious meaning for the notation. However, if the notation is non-standard, then there may not be a common and obvious meaning for it.

I think you are confusing hash functions with homomorphic encryption.
No, you cannot combine separate hash results mathematically (add, xor, etc.) and expect the same result. Any hash worth its salt will not allow that. Otherwise, it would be trivial to break the hash with lookup tables of partial results.


How can I calculate the entropy of an image? I am searching how can I calculate the entropy of a image for a Capture The Flag. I know what is the entropy theory and I tried a pair of things:

Convert the jpg image on binary image and calculate the entropy of binary text.
Viewing the images and intuiting which has greater entropy

I don't know how can I solve it. What can I do?

You don't need the probability distribution of images to calculate the information entropy of an image.  That isn't how the entropy calculation works.  For example, we can certainly calculate the entropy value of a symbol - say [@] - it would have an entropy value of 0, if we add multiple symbols...[@#], then the entropy value of two distinct bits of information would be 1.0, if we add even more [@#$] then the entropy value of the three distinct bits would be 1.58 - interestingly, if you add in redundant characters to your string, then you will reduce its entropy value, because you are not adding anything new to the string that we did not already know.

Consequently we can apply the same principle to image analyses, we do it all the time.  You would just vectorize the pixel data, read the flattened vector data into a dataframe, then do the entropy calc on the dataframe.  In my case, I just use scipy library from Python (scipy.stats.entropy).  We have analyzed many images using the technique, on average an image has an entropy somewhere between 3 and 4.  You can test this concept, by calculating the entropy of a pure white image (it should approximate zero, or be equal to zero), versus a more complicated image with graphs, people, chairs, cars, etc...(should be upwards of 4)

A fun way to cross check the validity of this, is to compare the entropy value of an "image of a string" to the entropy value "of the string bits" themselves - they won't be exactly the same (the image of a string is slightly higher (especially in languages that have multiple separated symbols within a single character bit [i.e., farsi, kanji, etc...]) - but in English they are pretty close.


How is an epsilon of 1/1000 non-negligible? Lately I've been studying cryptography and in the current course I'm taking we're reviewing statistical tests and how they can be used to determine if a pseudo-random generator is secure or not.

Essentially, one of the requirements for a Pseudo-random generator to be secure is that the probability of guessing the next bit in the string is less than 1/2 + a non-negligible epsilon (epsilon being any statistical advantage the computer has of guessing the next bit of the string due to insecurity in the PRG).

In an example the professor uses, he states that the probability of guessing the next bit of output from the PRG is 1/2 + 1/1000 (the non negligible epsilon).

How is 1/1000 non-negligible? I understand we're using computers with thousands of times faster processing power than a normal human brain, but that still means that a computer only has a 50.1% chance of guessing the correct bit. How can a computer leverage that tiny extra probability to crack a secret key?

How can a computer leverage that tiny extra probability to crack a secret key?

The answer to that depends on what type of key it is, how it's being used, etc. Certainly, the bias would make a brute-force attack easier, but you probably wouldn't need to worry about that, regardless.

Your professor, though, is trying to answer a different question. He wants to know, and wants you to think about:

  How small does the bias have to be in order to ensure that no one can leverage it to crack a secret key?

Note that this question is general: it makes absolutely no reference to what kind of key is being generated, or how it's being used. And this is how it should be: we're designing a general-purpose PRNG, so we shouldn't make assumptions about those things.

Suppose we used this PRNG to generate a 128-bit AES key. Well, assuming the bits are independent (but have the 1/1000 bias), then some math shows that the statistical distance between the result and a truly random 128-bit value is about 0.018. It follows if you used this PRNG in place of some mathematically perfect one, an attacker might be able to increase the chances of a successful attack by as much as 1.8% (but by no more than that).

Is this something you should be worried about? Well, if it's a 1.8% increased chance of someone decrypting a harmless IM conversation you had with a friend... probably not. On the other hand, if you're encrypting your bank password or a set of nuclear launch codes, a 1.8% increased chance of being compromised is probably an intolerable risk.

The 1.8% is an upperbound. We might not be able to find an attack that obtains that advantage. But by limiting the bias to something like 2^{-80}, we can safely stop worrying about the matter entirely.

The theorists would define a bias as "negligible" if it decreases "really fast" with respect to some adjustable parameter of the PRNG. This definition aims to ensure that we can always choose a value for the PRNG parameter such that (1) it's bias is quantitatively really small, e.g. 2^{-80}, but (2) the PRNG is still efficient.

Ultimately, however, you have to fix the parameter when you go and actually start  using the PRNG. At this point, you have to decide what concrete value of "negligible" you're comfortable with. This is a judgement call, but any reasonable PRNG will let you put it safely in the "we don't even have to worry about this" territory and still produce outputs as quickly as you could ask for.

Look into brute force factorization. If you can leverage a weakness in the PRNG then your factorization time is substantially diminished.


Entropy vs predictability in PRNGs If entropy is the measure of surprise, and a given PRNG has a uniform distribution, then the entropy would be high. So the Mersenne Twister(MT) has high entropy.

But the MT is also predictable. You can retrieve its past bits and predict its future bits.

What's the relationship between entropy and predictability?

entropy is the measure of surprise

That's informal, short and non-quantitative, but correct within that. In the case of a Random Number Generator, we must make that: entropy is the measure of surprise in the outputs of the RNG, for one skilled person (with arbitrarily large computing power) knowing the RNG design including any parameter (for MT: the Mersenne prime used, and a few others). That's for unknown seed (if any) assumed uniformly random but arbitrarily large computing power of the skilled person (unless otherwise stated).

The entropy considered here is a property of the generator, not that of one particular bitstring that it outputs.

Entropy further can be defined for the total output of a generator, or per output bit. In cryptography we measure the entropy in bit, so that it is 1 bit per output bit for an ideal uniform True RNG.

For any Pseudo RNG, the whole output is predictable from design, parameters and seed, hence the entropy in the whole output is limited to the entropy in what generates its seed, which is finite. And the entropy per output bit decreases to zero as the output size increase towards infinity.

  the Mersenne Twister(MT) has high entropy.

No, because it is a PRNG (see above).

  the MT is also predictable.

Yes, with enough output, and little computing power.

  What's the relationship between entropy and predictability?

If a bitstring generator has the property that it's full output is predictable from a finite length prefix (as is the case for MT), then this generator has finite total entropy (bounded by said finite length in bits for Shannon entropy in bits), and vanishingly small entropy per output bit.

The converse is false for practical definition of (un)predictable. In particular, there exist practical Cryptographically Secure PRNGs (thus of finite total entropy) that are practically unpredictable.

To make things quantitative: consider a generator $G$ of arbitrarily long bitstrings. Note $G_b$ that generator restricted to its first $b$ bits. $G_b$ is susceptible to generate $2^b$ different $b$-bit bitstrings $B$ with respective probability $p_B$ (possibly $0$ for some $B$), with $1=\sum p_B$ (the sum being over $2^b$ terms $B$). $G_b$ has Shannon entropy in bits
$$H(G_b)=\sum_{B\text{ with }p_B\ne0}p_B\,\log_2\left(\frac1{p_B}\right)$$
and its average entropy per bit is $H(G_b)/b$.

For an ideal TRNG (which output is uniformly random independent bits), and any $b$, all $b$-bit bitstrings are equiprobable with $p_B=2^{-b}$ and it comes $H(G_b)=b$.

For any PRNGs with $s$-bit seed (per any distribution), $H(G_b)\le \max(b,s)$. The entropy of the generator's whole output is $H(G)=\displaystyle\lim_{b\to\infty}H(G_b)$. That is maximal with $H(G)=s$ when all seeds generate different outputs and the seed is uniformly random.

...a given PRNG has a uniform distribution, then the entropy would be high.

In cryptography, it is common to consider the entropy of a generator as the unknown input to that generator. It would be equivalent to the seed or key for a RNG. So for a common AES-128 counter based CSPRNG, the entropy would be 128 bits. The output distribution is irrelevant where cryptographic entropy is concerned, although most RNGs in their original forms do produce uniform output. They would be difficult to use for encryption otherwise.

  So the Mersenne Twister(MT) has high entropy.

Ish.  It starts out high with an entropy of 19,937 bits for the common 32 bit implementation. However MT is invertable and the state can be discovered by looking at sufficient output.  Observing 624 output words from MT allows the internal state to be discovered. Consequently the entropy reduces by 32 bits per output word, reaching zero after 624 outputs. Any subsequent output is entirely predictable. The leftover hash lemma applies to MT outputs less than 624 words, when it would be acting as a very inefficient randomness extractor.

  What's the relationship between entropy and predictability?

In cryptography generally, entropy = unpredictability = surprisal. That   is necessary for seeding RNGs and creating keys. A cryptographer strives for unpredictable RNG sequences and unknown keys.  A CSPRNG cannot be inverted, the seed/key cannot be recovered and thus the entropy, unpredictability and surprisal of output is preserved no matter the length of said output.


Security of password hash with known prefix and appendix Assume I have a password that is exactly 32 characters long. I hash it the following way:

Prepend 1524 bytes (known to an attacker)
Append 3356 bytes (known to an attacker)
Do the checksum

It is clearly visible that only a tiny part of the plaintext is variable.

Assume the attacker stole the checksum from a DB. How difficult would it be for them to recover the password or create a collision? What checksum algorithms are more resistant against that?

Yes, I know that one cannot recover a password from a 16-bit CRC-16. Let's assume that the checksum is at least 128 bits long.

What would change if one of pads would disappear?

Except against rainbow tables, it makes no difference whether you've prepended or appended any bytes if they're known and static. Both may as well not exist.

So the scenario is reduced to "doing a checksum of" (presumably trying to hash) a 32-byte password.

There isn't a CRC-128 in common use, but if you extended the CRC algorithm to 128 bits, you'd get a completely insecure transformation. CRC was designed for simplicity and low collision probability, making it reversible. There's a paper specifically on reversing CRC - https://sar.informatik.hu-berlin.de/research/publications/SAR-PR-2006-05/SAR-PR-2006-05_.pdf - and the process can be implemented by a decent high school student.

Algorithms resistant to that - producing a true one-way transformation - are called hashing algorithms, not checksums. Popular examples of hashing algorithms include SHA-3 and SHA-2.

For passwords specifically, an even higher level of security is often called for, such as using key derivation functions (PBKDF) - bcrypt, scrypt, argon2. In addition to the quasi-randomness property that hashes have and CRC don't, PBKDF deliberately tie up additional computer resources to somewhat improve their brute-force resistance.

Let's be clear:

  A hash is just a checksum that is intended to be difficult to reverse.

If you are using an actual "checksum" algorithm then it will be simple to recover the key.

If you are using a hash then you just have hash(f(x)) which is as secure as a common-salted hash.


Generating S boxes that satisfy Coppersmith's criteria? I'd like to generate all possible 6-bit to 4-bit S-Boxes that satisfy the criteria for S-Box design given by Coppersmith, but I have a few doubts:

How many such S-Boxes are possible?
Is there any existing implementation of said boxes?
What would be the most efficient way to implement them?

Any help is appreciated, thanks!

For each of the $2^6$ possible inputs, there are $2^4$ possible outputs. Thus, there are $(2^4)^{2^6} = 2^{256}$ possible S-Boxes mapping 6 bits to 4 bits: you cannot exhaust this many possibilities.

You need to construct S-Boxes which satisfies all the criteria directly, in contrast to looking at all S-Boxes and then testing for the criteria.

You may have a look at "affine equivalence" to divide the search space (see e.g. [1]) and at DESL [2], a variant of DES which uses a unique S-Box satisfying most of the Coppersmith criteria as well as other ones [2].

[1] On the Classification of 4 Bit S-Boxes, Arithmetic of Finite Fields (2007)
[2] New Lightweight DES Variants, Fast Software Encryption (2007)

Take a look at this paper. It describes a very efficient DES S-box generator and gives an idea of how many exist. A naive implementation of enumerating all 6x4 s-boxes is infeasible.

http://www.tandfonline.com/doi/full/10.1080/01611194.2016.1169456


In end-to-end encryption, doesn't the server need to be trusted? Applications like WhatsApp use end to end encryption. WhatsApp says that only the users share a specific key and no third party can view the messages. But I do not understand how the two users agree on the shared key. It must have been transferred via WhatsApp servers. In that way, WhatsApp would know the shared key right? Please help me understand how keys are shared in end to end encryption.

End-to-end encryption over a channel with an eavesdropper, like the WhatsApp server, works by using a mathemagical spell called Diffie–Hellman key agreement.  What follows is not actually how WhatsApp works,* but explores some of the high-level ideas to concretely answer the question without getting lost in the full gory details of everything about the protocol, which defends against many more threats than what you asked about.

Alice and Bob agree on public parameters $p$ and $g$,† say $$p = 2^{2048} - 2^{1984} - 1 + 2^{64} (\lfloor2^{1918}\pi\rfloor + 124476)$$ and $g = 2$.  When Alice wants to have a conversation with Bob, she picks an integer $a$ with $0 \leq a < (p - 1)/2$ uniformly at random, computes the remainder after dividing $g^a$ by $p$,‡ written $g^a \bmod p$, and transmits $g^a \bmod p$ over the channel.  Bob does similarly: picks $b$ uniformly at random in the same range, computes $g^b \bmod p$, and transmits $g^b \bmod p$ over the channel.

By a remarkable feat of mathematics, when Alice receives $g^b \bmod p$, she can compute $(g^b \bmod p)^a \bmod p$, and it turns out to be the same as $g^{ab} \bmod p$.  Bob does the same: given $g^a \bmod p$, computes $(g^a \bmod p)^b \bmod p$, and obtains the same number as $g^{ab} \bmod p$.

Nobody has figured out the remarkable feat of mathematics that would allow someone who knows $g^a \bmod p$ and $g^b \bmod p$ but not $a$ or $b$ themselves to also compute $g^{ab} \bmod p$.

Thus can Alice and Bob share a secret, $g^{ab} \bmod p$, over a channel without revealing to an eavesdropper what the secret is.  They will then hash this into a short secret key, say the 256-bit $k = \operatorname{SHA3-256}(g^{ab} \bmod p)$, perhaps with SHA3-256, and proceed to use it for symmetric-key encryption such as AES-CTR.

But that's not all.  What if it's not just an eavesdropper, but our friend Mallory who, aside from having an annoyingly ungendered name, actively intercepts messages in transit?  Mallory could pretend to be Bob to Alice, and Alice to Bob, and do a pair of Diffie–Hellman key agreements, and establish shared secrets with Alice and Bob, and then eavesdrop on all the messages they exchange.  The WhatsApp server is in a position to do this.

To thwart this subterfuge of per-conversation shared secrets, Alice and Bob use long-term authentication in addition.  Alice generates a number $\alpha$ just like $a$, and puts $g^\alpha \pmod p$ in the telephone book, or shows it to Bob on her phone screen; Bob does likewise with $\beta$.  Thus they have a long-term shared secret $\kappa = \operatorname{SHA3-256}(g^{\alpha \beta} \pmod p)$.  Now when Alice wants to have a conversation with Bob, she does the per-conversation protocol—but instead of transmitting just $g^a \bmod p$, she transmits $(g^a \bmod p, \operatorname{KMAC256}_\kappa(g^a \bmod p))$.

When Bob receives a candidate message $(A, t)$, he first checks whether $t = \operatorname{KMAC256}_\kappa(A)$ before processing it.  If not, he drops the message on the floor and ignores it.  Only Alice and Bob can compute the function $\operatorname{KMAC256}_\kappa$, because only Alice and Bob know the secret $\kappa$.

Next, instead of just encrypting their actual conversation with $k = \operatorname{SHA3-256}(g^{ab} \bmod p)$ using AES-CTR, they encrypt and authenticate their conversation using AES-GCM.  The WhatsApp server can flip bits in messages encrypted using AES-CTR without either Alice or Bob being any the wiser even though only Alice and Bob know the secret key, but without knowing the secret key, the WhatsApp server cannot change anything in messages encrypted and authenticated using AES-GCM without Alice and Bob noticing.

What if Alice and Bob can't exchange $g^\alpha \bmod p$ and $g^\beta \bmod p$ on their phone screens because they've never actually met in person?  They have to consult the telephone book—which WhatsApp publishes.  When Alice consults WhatsApp for Bob's long-term public identity key $g^\beta \bmod p$, WhatsApp could spoof it and lie about it, and if Alice ever later checks Bob's phone screen she will detect the subterfuge because it won't match the key that the WhatsApp server handed out.

On the other hand, if WhatsApp does not spoof Bob's long-term public identity in the telephone book, then Alice will remember it in her personal address book.  If the WhatsApp server ever tries to impersonate Bob when Alice tries to start a conversation, Alice will detect that.  This model of authentication is sometimes called TOFU, or trust on first use.  You will also find it in the ssh protocol.

There's a catch: Sometimes Bob's identity key changes, like when he gets a new phone.  What should Alice do in that case?  In Signal, the app won't send any new messages on behalf of Alice; it will notify her that something is amiss and ask her what to do.  In WhatsApp, by default,§ the app will automatically retry with the Bob's new identity key, in an attempt to reduce usability hurdles for users who don't understand this, which led to an enormous kerfuffle about mainstream media reporting of the choice, which somehow dwarfed a much worse vulnerability in the app leaking the text of what you were typing if it looked like a URL.

In the end, since WhatsApp—part of Facebook—provides the software and doesn't let you scrutinize it, they certainly have the power to read and impersonate your messages, which they probably think very earnestly they won't ever abuse.  That's better than letting everyone on the internet route between Alice and Bob, like the stalker who is sitting a few tables down at the coffee shop on the same wifi network as Alice, which is why it was so harmful for the Guardian to report breathlessly in a back door in WhatsApp the way it did.

Even if your phone spoke TLS to the WhatsApp servers with a pinned certificate, it's still easier to engineer audit trails for malicious changes to the telephone book than it is to engineer audit trails for eavesdropping by the WhatsApp servers—whether by a technical attacker exploiting a software vulnerability, by a LOVEINT disgruntled employee, or by a court-ordered wiretap.

So, can third parties read your WhatsApp messages?  No, not likely, and it would take an active attack by WhatsApp itself—similar to the kind that Apple refused to do for the FBI—for them to read your messages.

* WhatsApp claims to use the Signal protocol (technical documentation).

† Technical details: $p$ is a safe prime, meaning it is a prime of the form $p = 2q + 1$ where $q$ is also prime.  $g$ is a quadratic residue modulo $p$, and thus has order $q$, meaning there are $q$ distinct possible remainders of $g^x$ when divied by $p$ for any integer $x$.  The powers of $g$ modulo $p$ form a subgroup of the multiplicative group of integers $(\mathbb Z/p\mathbb Z)^\times$.  None of this is important for you to understand how to share secrets over a public channel, but I provide the keywords for you to follow if you want to study further.

‡ Alice does not actually compute, e.g., 2^13805771959684693407656077397889219317288456747119690312451189306384849479687628613222950288427889322679415500741971589068616989911210949597114445259398229588157002772876797268276100622563299377498600497546320786879884333079126581727906347769889606788799518360227168951984468071470187490408276074397578464837282521956615118563389889631151319459158126320262667606793413409480951816493115818911703426164912115254095626026747790743791560327229116656590818054138360168383331595495242709153295834514181328053967320381842712608527965926684083141420258332671624779764031721576291538707703835661166957458717002972300906725181, and then divide the result by $p$; instead she uses a modular exponentiation algorithm so that it is possible to get an answer before the universe burns itself out.

§ Some of this is configurable: conscientious users who must use WhatsApp, like a journalist whose only contact with a source is WhatsApp, should study WhatsApp's privacy and security options.

What you really need is to make sure your public key and the other partys is actually transmitted correctly. The only way to make this sure is to hand over the public key personally and physically on a device you trust, preferrably analog . The technology clearly exists (as in I could do it technologically speaking if I wanted to) to adaptively in transit over the open internet switch public keys for fake ones to allow for MITM attacks, if you just manage to bribe the right people.

And once you become a parent you will be very susceptible to bribes. Also most of the worlds voting population are parents, so good luck in changing any of that within the frames of democracy.


How to make a hypothesis test for a simple statistical test for a certain RNG? I'm self-studying about hypothesis test in the context of RNGs.  I'm building a hypothesis test from scratch.  I'm taking the simplest statistical test I can think of: how many $1$s are there in the sequence sample?  My null hypothesis is that the RNG is uniform, so I expect the average number of $1$s to be close to $n/2$, where $n$ is the size of the sample.

I believe (or I guess) the sample averages should follow a normal distribution.  To implement the hypothesis test, I will have to know the variance, though.

What should I do here?  Should I look at a good RNG and come up with a variance relative to my simple statistical test?  This makes sense to me.  A good RNG will likely present averages close to $n/2$, specially if $n$ is large.  I could then empirically determine the variance this way.

Is there anything wrong with this construction?  Can you advise?  My main interest is not in testing real world RNGs.  My main interest is in knowing how to do hypothesis test, but I'm looking for an example in this precise context.

The number of one bits in a sequence of iid Bernoulli trials won't be normal: it will be binomial.  But you have the right intuition that, as the number of bits grows, the binomial distribution converges to a normal distribution—specifically, for fixed $p$, as $n \to \infty$, $$\operatorname{Binom}(n, p) \to \mathcal N\bigl(np, np(1 - p)\bigr),$$ or, more precisely and with less abuse of notation, if $X_n \sim \operatorname{Binom}(n, p)$, then $(X_n - np)/\sqrt{np(1 - p)} \to Z$ where $Z \sim \mathcal N(0, 1)$ is a standard normal.  This is a standard theorem of probability theory, the de Moivre–Laplace theorem; see, e.g., Feller, Vol. I, Ch. VII, ‘The Normal Approximation to the Binomial Distribution’, for an introduction.

That said, once you have decided on your test statistic and cutoff for a prescribed false alarm rate (‘statistical significance’), your job is not done: you should also have alternative hypotheses for the bugs you might have in your software, or physical defects you might have in your hardware.  For instance, will you detect deterministic alternating 0/1 bits?

The hypothesis test is valuable only insofar as it distinguishes plausible nonuniform distributions from uniform ones.  After all, if all you want is a hypothesis test with statistical significance 0.05 like any good little psychology journal, you could ignore the data altogether, roll a d20, and raise an alarm if you rolled a 1.

If you're talking about a pseudorandom generator, which is a deterministic function of a key, then your hypothesis test should be designed with knowledge of the function.
If you're talking about a hardware entropy source, which is a physical process, then your hypothesis test should be designed with knowledge of the physics.

If you just count bits and apply a test for goodness-of-fit in terms of the ratio of zeros to ones with significance level 0.05, and stop there, you've only made an entertaining way to implement a d20 in software.

Surprisingly, you've picked a toughie even though it is meant to be the simplest of the randomness tests.  The easiest technique is the feely touchy approach in the ent test (explained here). You simply count them up and get a mean.  The average of the means should be exactly 0.5 in the long run. See what you get and how you feel about it...

A longer technique is to say  a bit generator is a coin tossing machine.  You can then go to Wikipedia and look at Checking whether a coin is fair. You end up with a beta probability density function morphing into factorials, such as:-

for getting 7 heads and 3 tails( read ones and zeros). That's all a lot more complex, but there is a worked example that will guide you to a numerical probability.

Another version is the official NIST Frequency (Monobits) Test of NIST 800-22, A Statistical Test Suite for
Random and Pseudorandom
Number Generators for
Cryptographic Applications, Sections 2.1 & 3.1. They have both theory and a toy example.

It's not common to use $\sigma^2$ in randomness testing per se.  Knowing that (for samples) $\sigma^2= 400 $ (one of my TRNGs) is more useful for entropy source health testing than general RNG verification. If you do get through to a p probability, it's typical to consider the hypothesis threshold as 0.01. Or NIST does any way.


Uses of digital signature in asymmetric cryptography May I know what could be some advantages and disadvantages of doing the below in an asymmetric crypto process. What could be some of its primary and common uses?

Produce a digital signature on the plaintext, encrypt both plaintext and digital signature, and then produce another digital signature on the ciphertext

The outer signature protects the ciphertext against change. If the signature is verified before decryption then the signature can for instance protect the ciphertext against padding oracle attacks, both on the asymmetric encryption as well as the symmetric encryption that is commonly within a hybrid cryptosystem.

The encryption of the plaintext and inner signature of course offers confidentiality of the message (see the last section why the signature itself also needs to be encrypted).

The inner signature protects the integrity of the message after decryption. Obviously the outer signature (over the ciphertext) cannot be used on the plaintext message.

So you would either have to store the ciphertext (which means you'd have to decrypt the message with your private key each time to view the verified contents) or you would loose the ability to verify the plaintext message.

However, if you sign the plaintext message as well then you can still verify the message using the sender's public key even after decryption.

Note that encrypting the inner signature prevents an attacker of retrieving information about the plaintext. If it was directly available then the attacker could verify hashes over possible plaintext using the public key of the sender.

For instance, an attacker could verify that the message is "Yes" or "No" by guessing either message and then verifying the signature.

This falls into the anti-pattern "Mac-Then-Encrypt" but you are adding "Encrypt-then-Mac" to the output of first anti-pattern.  It's tough to say but since you are encapsulating the first anti-pattern within the EtM pattern you could be good.
But error conditions are multiple in this case:
 1. What happens when the outer MAC is found to be incorrect
 2. What happens when the inner MAC is found to be incorrect
 3. The time it takes to give someone a result of error in #1 and #2 above

You could potentially do it correctly but it all comes down to the implementation.  My recommendation is use standard authenticated encryption with associated data (AEAD) methods but again I'm not a cryptographer: https://en.wikipedia.org/wiki/Authenticated_encryption


Pseudorandom functions: how are functions stored? I am wondering about the setup for testing if a function family is pseudorandom. We step into a room, and query the black box with $x$, which yields $f(x)$, etc... We don't know if $f$ is a random function, or if it comes from some preset function family $F$. In the latter case, what assumptions are made about the functions in $F$? Is it enough for each $f$ in $F$ to be listed as a table in the black box, so that $f: \{0,1\}^n \to \{0,1\}^n$ is listed as a table with $2^n$ entries? What if $f$ is described by some function of a polynomial with coefficients that are exponential in $n$? What are the restrictions on the functions in the function family $F$, if any?

For the definition of pseudorandomness, the family $F$ of functions can be any set of functions at all. But typically we take it to be a set where each function can be described by a rather short key/seed, and where one can efficiently compute the function output given the input (and the key). This is because we want the family $F$ to represent functions that we can randomly choose from and use in real life.

For example, $F$ could be the set of functions AES$_k$, taken over all 128-bit strings $k$ (where AES$_k$ denotes the AES block cipher with key $k$).  Notice that there are "only" $2^{128}$ functions in this family, which is much less than the number of functions mapping 128 bits to 128 bits (which is $(2^{128})^{2^{128}}$).

Pseudorandom functions just have to produce 'random' values, there are no special restrictions on the functions.

There are tests to measure the quality of random functions. These tests will try to detect if the outputs of a function are somehow correlated or biased.

A well-known test battery are the Diehard Tests from George Marsaglia. Or you have more recent tests here.

PS: Often random functions will just generate a random sequence based on an initial seed value; you don't have to pass a parameter $x$ each time you call the function. While such random functions do exist, the box in your description somehow reminds me of a hash function (or a random oracle).


DES Bruteforce attack and false positive keys I have read that a bruteforce attack (regardless on which block cipher is used) can lead to a false positive if key space is greater than blocks space.
It is pretty clear to me that is due the pigeons hole principle (if I have more keys than available blocks, sooner or later I will use two different keys for the same mapping).

My question is, how can DES exhibit such behavior if the key space is about $2^{56}$ and block space is $2^{64}$.

What I am expecting from those premises is that given a plaintext and all possible keys, not all possible ciphertexts will be addressed.

My question is, how can DES exhibit such behaviour if the key space is about $2^{56}$ and block space is $2^{64}$

Let us assume that the attacker has a single plaintext/ciphertext pair, that is, two eight byte values $P, C$ with $C = \text{DES}_k(P)$, where $k$ is the correct unknown key.

Then, let us consider the values $\text{DES}_{k'}(P)$; there $k'$ ranges over the $2^{56}-1$ possible incorrect keys.  If we model DES with the incorrect key as a random permutation, then what we get is a list of $2^{56}-1$ random 8 byte values, each one of which has a $2^{-64}$ probability of just happening to be $C$.

Hence, the expected number of times the value $C$ appears on that list is $(2^{56}-1)2^{-64} \approx 2^{-8}$ (and the probability that the value $C$ appears at least once on the list is a tad smaller).

Hence, there does indeed exist a nontrivial probability that a brute force search would find two keys; the correct key $k$, and another key $k'$ that just happens to map $P$ to $C$.

Of course, in practice, we never really get only one plaintext block and one ciphertext block; we generally get additional ciphertext blocks that, at the very least, attempt to decrypt, and see if they make sense; that'll allow us to distinguish the correct key from any incorrect ones.

The answer is hidden in the internal structure of DES. the Heart of DES is S-box. All internal DES operations are one-to-one mapping, except S-box which in turn, do many-to-one mapping from input to output, because it has 6-bits input and 4-bits output. that means different inputs will lead to the same output. this way some of the sub keys will generate same output for the same data (of course, I am talking for one internal Round). The average number of these subkeys is (2^48 / 2^32 = 2^16 subkeys. calculated from the input/output size of the S-BOXs). But, I still haven't a clear estimation for the number of false positive Main keys. Any ideas?


Difference between encrypting something and hashing something What is the difference between encrypting something and hashing something?  in what situations would I want one or the other?

(I am new to cryptography, so hopefully I wouldn't say anything wrong. The following I hope should help give an idea of differences).

In general you always have a plaintext or something that you want to keep secret. This might be a message or a file or a password.

Encrypting: encryption transforms the plaintext into something that cannot be understood - something that doesn't have any meaning. Something unintelligible. You encrypt the message/plaintext by using an algorithm and a key. The output (the ciphertext) always depends on the key. The essential thing about encryption is that you can always recover the plaintext (if you know the key/password), and given a key/password you have only one plaintext. So you can think of encryption/decryption as a way to move back and forward between you plaintext and your cipher text (using a key).
Uses: Encryption is good if you say have a message to send to someone. You encrypt the message with a key and the recipient decrypts with the same (or maybe even a different) key to get back the original message.

Hashing: hashing turns something (usually a key or a password) into a (usually fixed length) string of characters. For example your hashing algorithm might always produce a string that is 8 bytes long. As with encryption you transform something intelligible into something unintelligible. One might call the product of the hashing the hash codes of the hash sums. One difference is that hashing two different messages might produce the same hash values. So you cannot decrypt something that you have hashed. But even though you can't decrypt a hashed value, it is (or it should) in general hard to make two messages that have the same hash value. Another difference is that hashing doesn't require a key.
Uses: One use of hashing is if you want to send someone a file. But you are afraid that someone else might intercept the file and change it. So a way that the recipient can make sure that it is the right file is if you post the hash value publicly. That way the recipient can compute the hash value of the file received and check that it matches the hash value.

In short Encryption help protect the data confidentiality, while hashing protect the data intigrity