Proving statistically hiding for a simple commitment scheme in the ROM It is well known that one can construct a simple commitment scheme in the random oracle model (ROM) by setting
$\mathsf{Commit}(m;r) = H(r||m)$, where $m \in \{0,1\}^k$, $r \in \{0,1\}^{2k}$ and $H: \{0,1\}^* \to \{0,1\}^k$ is modelled as a Random Oracle.
My question is: How can I formally prove that this scheme is statistically hiding?
Intuitively, the RO is "compressing" and therefore there will be enough random strings $r, r'$ such that a challange commitment $c$ in the hiding experiment can have preimages of the form $r||m_0$ or $r'||m_1$ with similar high probability, so even an unbounded adversary has negligible advantage in the experiment. But that is merely an intuition and not a formal proof. I would be really thankful for some advice on how to prove the statement.
(Additionally I'm wondering if random strings $r$ of length $2k$ are enough to achieve statistically hiding. Maybe one can see in the proof that we need a longer random string.)

Statistical hiding for a commitment is not about the distribution of inputs associated with a given commitment output, but rather the distribution of commitment outputs associated with a given pair of messages.
What you need to show is that for any two fixed messages, the total variation distance between the two distributions of outputs is small. Now, the statistical distance is a metric and so the triangle inequality applies. A good choice for the third distribution is the uniform distribution on $2^k$ outputs. The random oracle model means that the total variation of the distribution of outputs for a fixed message has small total variation distance from uniform and so by the triangle inequality, the distribution of outputs for two fixed, distinct messages has small total variation distance.


Number of LWE samples in NewHope This is regarding the number post-quantum key exchange protocol New-Hope (https://eprint.iacr.org/2015/1092.pdf). In the paper, we can see that the number of samples generated by the protocol is $2n$ where $n$ is $1024$, the rank of matrix $a$. Once in server side $b\leftarrow as+e$ and once in client side $u\leftarrow as'+e'$. But the authors in the paper (page 18 appendix B) says that the number of samples in each instantiation of the protocol is $5n$.

I can't understand why. Also, as far as I know the LWE samples are related when the matrix $a$ and the secret $s$ remains same. But, in the protocol the secret changes $s$ and $s'$.

Can someone please explain this?
Thank you in advance.

They're actually sampling $5n$ elements from $\Psi_{16}$. Perhaps Protocol 2 on page 5 shows this most clearly, where $\textbf{s}, \textbf{e} \stackrel{\$}{\leftarrow} \Psi_{16}^n$ and $\textbf{s}', \textbf{e}', \textbf{e}'' \stackrel{\$}{\leftarrow} \Psi_{16}^n$ are sampled (on line 3 on Alice' side, and line 1 on Bob's).

This probably also answers part of your follow-up question, but for completeness: the values $\textbf{s}$ and $\textbf{s}'$ are sampled independently by Alice and Bob, and are thus not at all related. The final shared secret is neither $\textbf{s}$ nor $\textbf{s}'$, but the reconciled $v$.


Affine cipher : Why it is required to have GCD(a, m) equals to 1 In the Affine cipher, the key $k = (a, b)$ should have the following property, i.e. GCD of $a$ and the modulus should be 1:

  $\gcd (a, m) = 1$, where $m$ is the set of possible moduli

My question is, why it is required that $a$ should have the above property? What is the significance of this? And why is $b$ excluded from this condition?

OK, to understand this issue, let's first recap how the affine cipher is defined:

$$c=a\cdot x+b\bmod m$$

Note that the following holds: $a\cdot x+b=c\iff a\cdot x=c-b$, where you would calculate $-b$ as $m-b$ which is $>0$ because $m>b$ because otherwise you could reduce $b\bmod m$ further.

Ok, so on our way to decryption we now only need to get $x$ out of $a\cdot x=c'\bmod m$ (with $c'=c-b\bmod m$).

Now if $d=\gcd(a,m)>1$ then this equation has either $0$ or $d$ solutions, neither being what you want from a decyption function (no plaintext recovery or uncertain plaintext recovery).

So this is why we make the restriction $\gcd(a,m)=1$, which will ensure that there is exactly one integer solution to $a\cdot x=c'\bmod m$ with $0\leq x<m$.

If you want illustration of the lack of solutions, have a look at the modular multiplication table of for example 15. You will note for example that there is no $x$ such that $6\cdot x=5\bmod 15$ however, there are three $x$ such that $6\cdot x=3\bmod 15$ and note that $\gcd(15,6)=3>1$.


Information theoretic message authentication code (MAC) Let's $\ a,b\ $ be two (pseudo)random independent values, and $m$ be a message, where $a,b,m \in \mathtt{F}_p$, where $p$ is a large prime number.

Question 1: Is $\ am+b\ $ an information theoretic MAC?

if yes

Question 2: Is there any paper/textbook uses it?

Just collecting some of the comments, if you make sure that $a$ and $b$ are chosen uniformly at random with $a \neq 0 \mod p$, then the given function is a information-theoretic MAC, basically because it satisfies the following property:

  If $h_k(m) = am + b$ with $k= (a,b)$ and $\tau$ is the codomain of $h_k$, then for all $m\neq m'$ and $t,t'\in\tau$ we have
  $$\operatorname{Pr}[h_k(m) = t \ \wedge\ h_k(m') = t'] = \frac{1}{|\tau|^2}$$
  (probability taken over random choice of $k$)

When a function satisfy this property we say it is a strongly universal function, and the main result is that such a function is a $1/|\tau| -$secure MAC, that is, the advantage of an attacker is at most $1/|\tau|$ (notice we can not ask for this advantage to be zero because any adversary can always try to guess a valid tag).


How can frequency analysis be applied to modern ciphers? I am building a computer program that deciphers Caesar, Vigenere and monoalphabetic substitution ciphers. All of those are susceptible to frequency analysis. However, it does not seem to be real-world applicable considering the complexity of the modern-day ciphers. Where else can frequency analysis be applied in the modern day to make my project real-world applicable?

The only suggestion I have been given is an application to the Bitcoin encryption algorithm. I am not sure if this would be a viable option. Is it?

Classical ciphers operate on letters. If we consider the frequency attack on classical ciphers it considers the frequency of the letters. Modern ciphers, if we consider only block ciphers, operates on blocks - 64, 128, or more bit blocks. Let see how you can perform a frequency attack on modern ciphers to infer some data.

Example attack on Databases:

Let assume that a sensor network has deployed in a rural area to observe animals by researchers. When an animal's tag is detected, the nodes stores this information on a database table; here for simplicity only the type of the animal and date and time encrypted in ECB mode;

|  TYPE  | D&Time|
|-----------------
| 0x443  | 0x7FE |
| 0x122  | 0x1E0 |
| 0x443  | 0x651 |
| 0x443  | 0x6AA |
| 0x084  | 0x09C |
| 0x112  | 0xC9F |
| 0x443  | 0x18D |
| 0x112  | 0x76B |

Now, assume that the poachers cannot extract the encryption key from the nodes but they can read the information. What can they learn from this data?

In ECB mode $E_k(x) = E_k(y)$ iff $x=y$ and this can leak information. This mode is used for equality and count queries on encrypted databases, see the CryptDB paper by Popa et.al. An attacker can calualte the frequency of the ciphertext and infer information from them.

By the Kerckhoffs's principle, we assume that they know everything but the key. The poachers also know the region, so they know how frequently a deer or a wolf appears around this sensor node. Assuming that mostly deer than wolf then bears appears in this region.

If we look at the ciphertext frequencies the 0x443 appears most. So they deduce it actually represents a deer. And similarly 0x122 is a bear data.

Long story short result:  Frequency analysis can break deterministic encryption. If you have pre-knowledge on the frequency of the data you can infer information without decryption. So a ninth-century attack of Arab philosopher and mathematician al-Kindi still lives.

The attack Naveed et.al is performed using electronic medical records. Some of the data is also publicly available like the frequency of the illnesses, drug sales, etc. So their experimental result shows that an alarming amount of sensitive information can be recovered

Mitigation: Don't use ECB mode. Then, you cannot have simple equality queries on the encrypted data. The CryptDB designed to execute queries of TPC-C ot measure the capability and performance.

The future may reside using equality under the FHE, however, it may not easily solve all of the problems.

Some further readings on modern frequency analysis;

Inference Attacks on Property-Preserving Encrypted Databases, by Naveed et. al. Applied frequency attack on electronic medical records.
On the Difficulty of Securing Web Applications using CryptDB, by Akın and Sunar, example how to infer the data form Hospital records.
Access pattern disclosure on searchable encryption: ramification, attack
and mitigation by Saiful Islam et. al.


Encryption wth expiry date Is there a way to encrypt a file with expiry date?

I want to share a file which can be decrypted using a key until certain date. After that date, the recipient should not be able to decrypt the file.

Let divide the problem into two cases;

The file encrypted and stored on the cloud for access.
For this case, to decrypt the file people will need the key. So, if the expiry date is not passed you will transmit the key. They will download and decrypted. From this point, they will not need your key and encrypted file. Nothing can prevent them to take a copy of it. They can use screen capture softwares etc., if this is prohibited in hardware, they can take photos. If no want accessed the file you can delete the file from the cloud. Actually, you will never be sure that a copy was taken. So, in the future when your encryption scheme is broken the file will be accessible.

The file encrypted and not stored on accessible storage for the third party.
You can safely delete the file and the keys.

As point of view, there can be some solutions depend on the environment that this system applied. If the user is in a very strict environment where the cameras or similar devices are prohibited and the computers are highly secured as no input-output ports etc. However, all these are nothing to do with Cryptography.


Pohlig Hellman and small subgroup attacks While studying Curve25519 I read about the small subgroup attack in chapter 3. So far i know, that you need a point with a small subgroup to do such an attack. Curve25519 has a basepoint with prime order, therefore it is resistent. My question is: How does such a small subgroup attack work? Can you give me an example?
Now I'm a bit confused, too. I know the Pohling Hellman attack. You can use this attack, when the order of the field of the elliptic curve is not prime ( you can use it with a prime field, too, but it is not useful ). How it works: Be $E$ an elliptic curve over $F_p$. Be $p = f_1 \cdot f_2 \cdot ... \cdot f_n$ the factorization. Be $xP = Q$ the discrete logarithm. Now you can use the Chinese remainder theorem to solve the following system of equations: $x \cdot (p/f_1)P = (p/f_1)Q$, $x \cdot (p/f_2)P = (p/f_2)Q$, ... , $x \cdot (p/f_n)P = (p/f_n)Q$. So this can be used to calculate the private key by just knowing the public key. My question: I think those two attacks are related. But I don't understand how. Can you explain this to me?

The Pohlig-Hellman algorithm reduces the discrete logarithm from a group of composite order to subgroups of prime order. For instance, with an elliptic curve and a point $P$ whose order is a composite integer $q = p_1 \cdot p_2$, and we want to find $k$ such that $Q = [k]P$ for a given point $Q$. Then, since $[p_2]P$ is a point of order $p_1$. Let
$$
Q_2 = [p_2] Q,\quad \text{and} \quad P_2 = [p_2]P,
$$
and now we have $Q_2 = [k\bmod p_1] P_2$. Generic discrete logarithm algorithms can then be used to get to obtain $k\bmod p_1$.
With $Q_1 = [p_1]Q$ and $P_1 = [p_1]P$, we obtain $k\bmod p_2$ and the Chinese Remainder Theorem can be used to get $k$. Then, the security depends mainly on the largest prime in the decomposition of $q$. That's why points whose order $q$ is a large prime is chosen.
In the small subgroup attack, the idea is to make the computation happens with a point of small order instead of a point whose order is a large prime. Typically, standardized curves in cryptography have order $q\cdot h$ where $q$ is a large prime and $h$ is generally small. The principle is the attacker, instead of sending a point of order $q$, sends a point $P$ of order $h$ (for example in a Diffie-Hellman key-exchange). Then the computation with a secret value $k$ will be $Q = [k]P$, but since $P$ has order $h$, there is at most $h$ possible values for $Q$.
In a Diffie-Hellman key-exchange, it works like this: the attacker sends $P$ of small order to Alice instead of its valid public point. Alice computes $Q = [k]P$ thinking that the point $Q$ is the shared secret, from which she derives a symmetric key to encrypt the communication. Since there is only a few possible values for $Q$, there are only a few possible keys. The attacker tries them one by one until the decryption is correct. When this is the case, he learns $k \bmod h$.

You can use this attack, when the order of the field of the elliptic curve is not prime ( you can use it with a prime field, too, but it is not useful ). How it works: Be $E$ an elliptic curve over $F_p$. Be $p = f_1 \cdot f_2 \cdot \ldots \cdot f_n$ the factorization.

For clarification, in cryptography an elliptic curve is defined over a finite field, and a finite field has an order that is either a prime $p$ or a power of a prime $p^\ell$. This value is not the order of the curve. The order of the curve is very close to it, but is generally different.


Why are the Davies-Meyer and Miyaguchi-Preneel constructions secure? The Davies-Meyer compression function $h(H, m) = E_m(H) \oplus H$ is said to be secure.  So too is the Miyaguchi-Preneel compression function $h(H, m) = E_m(H) \oplus m \oplus H$.  Why are these secure?  How do we know that they are secure?

(Here $E$ is a block cipher with $n$-bit key and $n$-bit plaintext; $E_k(x)$ denotes encryption of plaintext $x$ under key $k$.  This question is based upon one originally asked by yanglifu90.)

The detailed technical analysis is given in the following research paper:

Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV.   John Black, Philip Rogaway, Tom Shrimpton.  CRYPTO 2002.

They show that Davies-Meyer and Miyaguchi-Preneel are secure, assuming the block ciphers can be modelled as "ideal ciphers" (that have no regularities or patterns beyond that implicit in the very definition of a block cipher).

In a nutshell, an ideal cipher assumes that, for each key $k$, the function $E_k(\cdot)$ can be treated as a totally random permutation on the set of all $2^n$ possible texts, and these permutations for different keys $k$ are independent.

In other words, you can think of an "ideal cipher" as a black box where you send it a key $k$ and a plaintext $x$ and it responds with a ciphertext $c$.  It behaves in a very special way.  When you feed it a key $k$ and plaintext $x$, it picks a totally random ciphertext $c$ uniformly at random and gives you $c$, subject only to the following two consistency restrictions:

if you've previously queried the black box on the same key $k$ and the same plaintext $x$, then it will respond the same way it previously did, and
if you've previously queried the black box on the same key $k$ and a different plaintext $x'$ (where $x'\ne x$) and got back the response $y'$, then this time the black box won't respond with $y'$ again (it'll respond with some $y$ such that $y \ne y'$)--in short, it'll never give the same response to two different queries with the same key but different plaintexts.

That gives the flavor of the model, but it's not quite sufficient, because it only models encryption, but not decryption.  In actuality, we model this with two black boxes: one that emulates $E_k(\cdot)$, and one that emulates $E_k^{-1}(\cdot)$.  It's a bit tricky to describe how they work, but it goes like this:

If you query $E_k(x)$ and you've previously queried the $E_\cdot(\cdot)$ black box with the same key $k$ and the same input $x$, then it  will respond with the same value it previously did;
If you query $E_k^{-1}(x)$ and you've previously queried the $E_\cdot^{-1}(\cdot)$ black box with the same key $k$ and the same input $x$, then it  will respond with the same value it previously did;
If you query $E_k(x)$ and there was some prior query to the $E_\cdot^{-1}(\cdot)$ black box with key $k$ and some input $y$ and it responded with the output $x$, then this query will respond with $y$;
If you query $E_k^{-1}(x)$ and there was some prior query to the $E_\cdot(\cdot)$ black box with key $k$ and some input $x$ and it responded with the output $y$, then this query will respond with $x$;
If you query $E_k(x)$ and none of the above conditions hold, then the box will randomly pick a value $y$ that is different from the responses from all prior responses to queries of the form $E_k(x')$ (i.e., same key but different input) and that is different from all the inputs $y$ that were submitted to the $E_\cdot^{-1}(\cdot)$ box with key $k$.
If you query $E_k^{-1}(y)$ and none of the above conditions hold, then do something similar.

That's the definition of an ideal cipher.  It turns out that this is equivalent to picking $2^{n'}$ different, independent random permutations on $2^n$ texts (one permutation per key).

It is possible to use various mathematical techniques to prove that if you apply the Davies-Meyer or Miyaguchi-Preneel construction to an ideal cipher, the result will be a secure compression function.  Therefore, if our block cipher acts like an ideal cipher, then we can expect that Davies-Meyer and Miyaguchi-Preneel ought to be secure.

That's the basic idea.  You'll need to read the research literature to get the full details.


Given a 128-trit state space, is a 3-symbol block cellular automaton secure against preimage attacks? The following implementation, here for illustration:

void hash(int* bits, int bitsLen, int* out, int outLen){
  const int tt[9] = {1,2,0,0,0,1,1,2,2};
  int st[128], i, k, j, x, y, a, b;     // state st holds 128 trits
  for (i=0; i<128; ++i)                 // initial state setup
    st[i] = i%3;                        //
  for (k=0; k < bitsLen + outLen; ++k){ // for each input and output bit
    for (j=0; j<32; ++j){               // 32 times for each input and output bit
      if (k < bitsLen)                  // if processing an input bit..
        st[0] = bits[k];                // enter that input bit in state
      for (i=j%2; i<128; i+=2){         // for each pair of trits in state
        x = (i+0)%128;                  // index of first trit
        y = (i+1)%128;                  // index of second trit
        a = st[x];                      // get these current trits values
        b = st[y];                      //
        st[x] = tt[a*3+b];              // update these trits per table tt
        st[y] = tt[b*3+a];              //
      };                                //
    };                                  //
    if (k >= bitsLen)                   // building an output bit
      out[k-bitsLen] = (st[0] + st[1] + st[2] + st[3]) % 2;
  };
}

uses a 3-symbol block cellular automata, with transition rules encoded as the 3x3 table defined by tt and using a 128-trit (about 202 bits) state space, to materialize an one-way function. It employs k interactions, where each interaction advances the automata by 32 steps, inserting one of the input bits on the first cell of the automata at each step. Under those conditions, is this function secure against preimage attacks? Here is a test run.

Note: code commented and trimmed for clarity, without changing the output. See previous link or this for the original.

This is a not an answer, as I do not touch preimage resistance; it is comments (now removed) made into something hopefully correct, including a description per cryptographic conventions.

The proposed code implements a minimalist hash function with an internal state st of 128 trits, parameterizable message and output size (inLen 16 bits and outLen 256 bits in the illustration). At the core is a simple state transformation, iterated for 32 rounds per input and output bit, potentially changing each state trit.

At each of such round, 64 times, two state trits are selected per a simple schedule (giving potentially full diffusion after 2 rounds), and replaced according to the following transformation (an alternate expression of constant table tt and st[x] = tt[a*3+b]; st[y] = tt[b*3+a]; ):

input   output
 0 0     1 1
 0 1     2 0
 0 2     0 1
 1 0     0 2
 1 1     0 0
 1 2     1 2
 2 0     1 0
 2 1     2 1
 2 2     2 2

This transformation is reversible, therefore the 64 transformations in a round for (i=j%2; i<128; i+=2){..} are entropy-preserving.

Each input bit is injected by replacing a trit at each round, by st[0] = bits[k];. Thus each round processing an input bit looses some amount of state entropy, but not nearly as much as if the above transformation was not reversible.

The output is formed (still with 32 rounds per bit, and no input injected) by a formula combining 4 trits. Under the natural assumption that the state is about unbiased, the output is noticeably biased: a bit is set with odds $40/81<49.4\%$. That would be fixable by mixing much more trits to produce the output. Note: because there is no entropy loss during output production, it is likely that with 256 output bits, almost all the state entropy after input processing makes it to the output, which is good.

This hash can be viewed as a traditional iterated hash function à la Merkle-Damgård or sponge, with 1 bit per message block (compensating the less than complete diffusion per round), no length-strengthening (replaced by iterations in the output production, which also gives the variable-size output), and the unusual characteristic of having sizable state entropy loss per 1-bit message block processed. The later is slightly frightening compared to using an entropy-preserving message injection like st[0] = (st[0]+bits[k])%3;, but I do not immediately see that it opens to a devastating attack (nor have proof that this entropy loss is not in fact a strength); studying this seems interesting in its own regard.


Open source implementations of Symmetric Searchable Encryption and Order Preserving Encryption Are there open source implementations of SSE and OPE?
Can anyone please point to sample codes, if available.

EDIT

If cryptDB is not an option, what other options are available?
(Indeed, these schemes are weak — which is why cryptDB proposes onion layers for encryption.)

cryptdb has these implementations inside it . But their licensing is not Open sources as in GPL etc . They say its available for research purposes !

I have implemented Symmetric Searchable Encryption in Java, its LGPL


A "one time pad" can be thought of a Vigenere cipher with A "One Time Pad" can be thought of a Vigenere cipher with...

An infinitely long key
A secure symmetric key
Multiple ciphertext alphabets
A columnar transposition

I had this question come up today in one of my mid-terms and to be honest it caught me off guard a little, I chose (2) but I'm having doubts and now thinking its (3). I'm pretty sure i'll get a quick response to this because its quite a basic question, this is from an initial test on intro to cryptography and I felt I did pretty well on the rest of the test but this is bugging me.

I know one time pad can have infinite period and can be truly unbreakable but that doesn't mean it has an infinitely long key! (does it). (4) is surely a null consideration which leads me to think its (2) or (3)!

(1) is the correct answer.  The Vengiere cipher phrase is a distractor.  Basically all alphabets are in the cipher.

Note that the key does not need to be infinite, merely the same length as the plaintext and random.  So in that regard, all of the answers are incorrect... But (1) is the "best" answer as it is the answer with the most entropy or randomness, which is the point of a one-time pad. You cannot draw any conclusions about entropy from the other answers.


Key derivation for AES-GCM using HKDF? I have a system comprising N >1000 nodes.  At each node I would like to use HKDF to derive a unique 256-bit key, Kn (for the nth node), from a pre-shared master key, K0, and a locally-generated random bit string, Rn.

Kn would then be used to apply AES-GCM to UDP packets that the nth node sends to other nodes and the receiving nodes would independently derive the necessary Kn using K0 and Rn, which would be included in the packet header and protected as “additional data” by the AES-GCM MAC.

The HKDF implementation takes the following parameters…

Hash type: SHA256, SHA384, SHA512, BLAKE2B
Input key of arbitrary length (presumably K0)
“Additional Info” of arbitrary length (optional, but presumably Rn)
Salt of arbitrary length (optional)

My questions are:

What would be a good choice for the hash type?
What is a sufficient length for K0?
What is a sufficient length for Rn?
What is the purpose / benefit / need of the optional Salt?  Is it okay to omit assuming it can't be sent in the clear or pre-shared?
Any other general flaws / issues / recommendations w.r.t. this approach?

Thanks.

What would be a good choice for the hash type?

Whatever works best for you. As long as the hash is considered secure, the difference comes down to performance.  SHA-256 and SHA-512 are both traditional and safe choices recommended e.g. by NIST.  You can't really go wrong with either of those.  Which one is faster depends on your hardware.  (SHA-384 is basically just tweaked and truncated SHA-512; there's little point in using it unless you're implementing some standard that requires it.)

  What is a sufficient length for K0?

The master key needs to be long enough to resist brute force guessing attacks.  128 bits is probably enough; 256 bits certainly is.

  What is a sufficient length for Rn?

You should use Rn as the salt in HKDF-Extract, to detive a distinct PRK for each node.  For that purpose it just needs to be (almost certainly) unique for each node.

If you can assign the values deterministically, even 10 bits would be just enough for 1000 nodes.l, and 16 bits wouldbe plenty.  If every node chooses a random ID, you'll want something like 2×16 + 32 = 64 bits to guarantee a $< 2^{-33}$ (i.e. less than one in eight billion) chance of a collision for up to $2^{16}$ nodes.  (But be careful to seed your RNGs well!)

Also, if your nodes already have some unique ID each, you can just use those, however long they might be.

  What is the purpose / benefit / need of the optional Salt?  Is it okay to omit assuming it can't be sent in the clear or pre-shared?

The purpose of the salt is key diversification.  In your case, as noted above, you should use Rn as the salt to ensure that each node gets its own PRK.

The purpose of the info parameter to HKDF-Extract is to let you derive multiple (pseudo-)independent keys from the same PRK.  If you only need one key per node, you may omit it.


Cryptanalysing Affine cipher I am trying to cryptanalyse a cipher–text encrypted by Affine cipher.

The encryption formula is: $c = f(x) = (ax+b)\bmod m$, where $a$ and $b$ are unknown constants; $x$ is a plain-text symbol, and $c$ the corresponding cipher-text symbol, both in range $[0\dots m-1]$; $m=26$ is known.

This is what I got so far:

$x=4\implies c=17$

$x=19\implies c=10$

That means that letter 4 has been encrypted into 17 (numbers are according to alphabetical order of letters in English language). Same applies to the line below.
Now goes the following calculations:

$15a\equiv-7\equiv19\pmod{26}$

$a\equiv19/15\pmod{26}$

$a=3$ [because $15\cdot3=45$ and $45\equiv19\pmod{26}$]

$b=5$

I don’t get the logic which leads to obtaining $b$ value. Any help, please?

Once you know (you didn't question that) that $a = 3$, then knowing 4 goes to 17, using $f(x) = 3x + b$, we just substitute $x = 4$ to get $3 * 4 + b = 12  + b = 17 \mod 26$, where we can easily see that $b= 5$ does the job.


Perfect zero knowledge for the Schnorr protocol? Can somebody explain (or point to a reference) why the Schnorr protocol cannot be proved zero knowledge?

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$).

Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it to the prover. The prover computes $z = r + ue$ and sends it to the verifier. The verifier checks that $g^z = a y^e$.

Remember, (informally) a protocol is zero knowledge if for any verifier $V^*$ there exists a simulator that can create conversations with the same distribution as conversations between the honest prover and $V^*$.

Proof sketch: Our simulator chooses $z$ uniformly at random and guesses what challenge $V^*$ will issue. Based on the guess $e$, it computes its initial message $a$ as $g^z y^{-e}$. If $V^*$ chooses $e$ as its challenge, the simulator has the correct response and has created a challenge with the correct distribution. It is a fairly easy exercise to prove that it succeeds with probability $1/2$, when $V^*$ is restricted to respond with $0$ or $1$.

So Schnorr is zero knowledge when the challenge space is small (so that we can guess the challenge with significant probability), but Schnorr is also not very useful when the challenge space is small, since you need to run the protocol many times to be sure that the prover really knows the secret.

When the challenge space is large, the above simulator fails. I can't remember a proof that there cannot be a different simulator that succeeds, but no such simulator is known. Which means that while we cannot say that Schnorr is zero knowledge. On the other hand, as far as I know, we cannot say that it is not zero knowledge.

There are alternative notions of zero knowledge, e.g. honest verifier zero knowledge. We can prove that Schnorr satisfies these notions even when the challenge set is large, and for many applications this is sufficient. E.g. in the random oracle model, we can get non-interactive zero knowledge via the Fiat-Shamir heuristic. There are also constructions for converting honest verifier zero knowledge to zero knowledge.


Safety of nested hashes Assume that you use this function: SHA-256(key_1 + SHA-256(key_2 + SHA-256(key_3 + special_key))). First, second and third keys are long random strings of 64 bytes. A special key is a short string (from 5 to 12 bytes).
Also, assume that an attacker has:

the special key;
16 bytes from the beginning of the function result.

How realistic is it for an attacker to obtain the keys 1, 2 and 3? Is there any vulnerability, except brute force? And if the attacker has multiple pairs of key/result string?

This is similar to HMAC-SHA-256 with 64-byte key, except that

HMAC-SHA-256 has two SHA-256 layers where there is three;
HMAC derives its two key_j from a single one (using XOR with constants) rather than using independent keys;
HMAC potentially reveals its whole 32-byte output, rather than part of it;
HMAC's security model  includes the adversary choosing the messages (that is, values of special_key) for which it obtains input; and seeking something weaker than key recovery (ability to distinguish the function from random).

It follows this is at least as strong as HMAC-SHA-256 is: with a strong theoretical argument even for relatively weak hypothesis on SHA-256 (the generic proof of HMAC applies), and unbroken.

Key leak by some side channels might still be an issue for a particular implementation, though.


Entity authentication protocol by encryption I'm not a cryptography expert, so excuse me if the question seems very trivial.

I need to know if this protocol is secure against a MiTM attacks and ensure a safe entity authentication method.

We have Alice and Bob that share the same key $K$.
Alice needs to be sure that Bob is really Bob.
In order to achive this Alice generates a random number $N$ and sends it to Bob.
Bob receives this message from Alice, computes $C=ENC_K(N,ID_{B})$ and then sends to Alice $C$.
Upon that Alice received $C$ performs $DEC_K(C)$ extracts the nonce, named $N'$ and checks if $N'$ = $N$.

Is it correct?

UPDATE:
I've found this paper:

  M. Bellare, R. Canetti, and H. Krawczyk, “A modular approach to the
  design and analysis of authentication and key exchange protocols”,
  Proceedings of the 30th Annual Symposium on the Theory of Computing,
  ACM, 1998.

Where in section 3.2 is described an authentication technique using encryption and MAC algorithms. Now, I need to know, since the paper is quite old, if this scheme could be considered secure yet. Furthermore, how can I make it secure against a Reset Attack (if it is possible) ?

In general, no, this is not safe, and in the cases where it is safe it's wasteful.

The safe (but wasteful) cases are those where you're already using an Authenticated Encryption with Associated Data (AEAD) scheme or applying a Message Authentication Code (MAC) over the ciphertext. It's wasteful since those both have their own authentication systems, but safe since it prevents a MITM from modifying the ciphertext in transit.

Without authentication the MITM can simply modify data in the ciphertext beyond the start of $N$, ie anything in $ID_{B}$. This won't affect $N$ at all in any of the commonly used modes (either a direct stream cipher or a block cipher in CTR or CBC mode). There are some caveats to my statement, eg if $N$ is not a multiple of the underlying block size in CBC or CTR mode then data out to the next multiple of the block size needs to be preserved by the attacker, but since you didn't specify anything about the cipher used for encryption I'll go with the most general case.


Practical attack on an impractical implementation of Rijndael (AES?) My understanding of the cryptanalysis of AES, is based on what I've read on Wikipedia and my intuition, I have nothing but self-taught education on the subject.

So I want you to imagine: I have only TWO blocks of 128-bit cipher text.

The input was 256bits, we did not use any padding, we also ignored IVs and Salts, when implementing our "demonstration of Rijndael". Finally and most importantly, the two blocks of cipher text, are different by just one bit (in an arbitrary space), however: When presented with the two 128-bit blocks (and just a 128-bit key, both in same), we can come under two conditions:

Condition one:
We know none of the weaknesses and similar plain-texts in these two blocks, I just mentioned, how easily could we discover it?

Condition two:
We know everything I just mentioned above, apart from which bit is flipped and what the two plain texts and the key (let's keep it simple and make the key, only 128 bits). Can we discover much here? How do we go about it?

I said in the title, this is about "practical attacks", I don't know if even with all these conditions knowingly been met, there is much we can do, however since we've used Rijndael, so grossly incorrectly, I assume we're on our way to be able to deduce some information... In which of either, both or none, does an "attacker" learn anything about these two blocks, they weren't told?

What you're describing is a ciphertext-only attack on AES.
No, there's no (known) ciphertext-only attack on AES.

  Condition one: We know none of the weaknesses and similar plain-texts
  in these two blocks, I just mentioned, how easily could we discover
  it?

By the lack of an transmitted IV, an attacker can learn whether the two messages are equal and that no IV was used. He can't learn anything else about the relationship of the plain texts without actually brute-forcing the key.

  Condition two: We know everything I just mentioned above, apart from which bit is flipped and what the two plain texts and the key
  (let's keep it simple and make the key, only 128 bits). Can we
  discover much here? How do we go about it?

You can't learn anything about the plain texts you didn't already know without brute-forcing the key.

  ...since we've used Rijndael, so grossly incorrectly...

We have indeed, yes, however more advanced defensive measures (i.e. use of authenticated encryption and IVs) mainly protects you from more advanced attack scenarios, where the attacker can actually decrypt and encrypt arbitrary data under the challenged key to distinguish unknown plain texts.
The scenario you give however is even safe when using ECB mode, which are you doing. ECB mode is safe as long as all plain texts (under a given key) are different, your messages are different so they are secure. The only thing you can tell by observing ECB encrypted data is whether one block equals the other.


What do you call one time pad where pseudo-random numbers are used? What is the encryption method called when pseudo-random numbers are used instead of true random numbers?

Synchronous stream cipher, or just stream cipher.

  In a synchronous stream cipher a stream of pseudo-random digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext (to encrypt) or the ciphertext (to decrypt). In the most common form, binary digits are used (bits), and the keystream is combined with the plaintext using the exclusive or operation (XOR). This is termed a binary additive stream cipher."

http://en.wikipedia.org/wiki/Stream_cipher#Synchronous_stream_ciphers


Does Shamir's Sharing Scheme make sense if k=2 and n=2? Given that I have a secret which I want to split into 2 parts (n=2) and require 2 parts to restore it (k=2), does it still make sense to use Shamir's Scheme or would a trivial scheme with XOR (generate a random string, same long as the secret, XOR those, random string and the XOR result become shares) be just as secure? Are there any benefits in using Shamir's Scheme in such case?

In general, what would be the recommended sharing scheme for this use case?

Except for the extensibility (being able to latter add a third user), the trivial scheme with XOR works just as well as Shamir; the trivial scheme retains the following properties:

The length of each share is still as long as the original secret (in fact, you don't need to bother assigning share identifiers, which you have to with Shamir's scheme)
It is information theoretically secure.


Why is SHA-3 a Sponge function? A sponge function is supposed to be able to generate an arbitrary length of output. Yet, SHA3 (Bouncycastle) constrains me to choose an output length between 224, 256, 384, and 512. Evidently, these are not arbitrary lengths. How then is SHA3 a sponge function?

Is there a specific way to generate "arbitrary length" using bouncy castle implementation?

Here is my code:

     SHA3.DigestSHA3 digestSHA3 = new SHA3.DigestSHA3(320);
     byte[] digest = digestSHA3.digest(bip39Seed);

What am I missing?

My uneducated guess is that the standardized version of Keccak is different from the original one that was submitted to NIST. If this is the case, how can I get to the version that allows me to specify arbitrary lengths?

… SHA3 (Bouncycastle) constrains me …

Bouncycastle offers the NIST approved, fixed, and standardized output lengths of the keccak sponge function.

See, when talking about SHA-3, you're talking about those NIST standards. This was built upon the proposed and accepted keccak sponge function.

NIST standardized SHA-3 to those lengths (which libs like Bouncycastle cover) to match up with the SHA-2 output standard perfectly, so that SHA-3 can be used as an immediate drop-in replacement in case SHA-2 (let's just say) "goes down" one day.

Yet… just because NIST created/fixed those standard output lengths it doesn't mean that the underlying sponge function couldn't be used to create other output lengths.

In the end, the only thing you are missing is the fact that many programming libraries (including Bouncycastle) focus on providing functionality that adheres to standards, not custom functionality.

  … is there a specific way to generate "arbitrary length" using bouncy castle implementation …

Well yes, if you look at the BC lightweight API you’ll discover the option to use SHAKE128 and SHAKE256 – which does exactly that. (hint: SHAKEDigest class)

If you think the SHAKE128/256 functions don’t fit your needs (they actually should), that's where programming comes in. If you want something special (read: non-standard), you'll have to grab the core sponge functionality and create your own corresponding functionality you think you need. Libraries like Bouncycastle will hardly be of much use here.

But it's not as if there aren't projects and sourcecode pieces out there on the web that already offer what you are looking for. Simply use your favorite search engine to find them for whatever programming language you deem suitable and fitting your needs.

  … standardized version of Keccak is different from the original one that was submitted to NIST …

Yes, you are also correct related to SHA-3 and Keccak being different. They are both sponge functions… but SHA-3 was built upon Keccak, with a small tweak introduced by NIST. This small difference within the sponge functionalities of SHA-3 and Keccak makes them produce different outputs for the same output length.

Practically, both are considered cryptographically secure. So, when wanting arbitrary length of output, you'll have to decide what sponge function you want to use. Looking at Gimli, I'ld like to note that there are other sponge functions out there which are suitable for cryptographic purposes too. Depending on what exactly you need or expect, you have diverse choices.


Are there flaws in (cryptographic) science/engineering/software/research due to pseudo random generators? I am trying to see if there were any incidents in the past where using PRNG or not actual random scheme leaded to wrong conclusion in research.

For example, a lot of fields today use simulations to predict natural science results and I was wondering what are the best practices and if there were any flaws due to bad randomness in the past.

For security purposes it's clear that one has to use encrypt lib random function, but for science or simulation of physical systems I am not sure it's the case. My guts say it should be the same, but I am not sure how to justify it.

Are there flaws in (cryptographic) science/engineering/software/research due to pseudo random generators?

There are a few examples:

RANDU is probably the quintessential example of a bad pseudorandom generator. It consisted of the sequence $x_{i+1} = 65539\cdot x_i \bmod{2^{31}}$, which is always odd and whose sequential triples are highly correlated. It was implemented by IBM in its software, and so it was used all over the place. It has been suggested that research results relying on RANDU are not reliable, but I could not track down any concrete example of this.
Another interesting example is that of 1992 Ferrenberg et al., in which a pseudorandom number generator that passed the statistical tests common of the time, but nevertheless resulted in incorrect results in a real Monte Carlo Ising-Model simulation. The generator in question was R250, a very simple generalized feedback shift register.

There are most likely many other examples incorrect results that simply haven't been checked or reproduced.


User-specified PBKDF2 password, salt, and iterations limits For a decentralized login where a user is left to select the password, salt, and iterations, what minimums for each should be enforced?

In other words, because none are ever stored by the implementation, can standard login authentication guidelines also with a 4-digit PIN be enforced to produce theoretically uncrackable combinations where the login username & password are substituted for the PBKDF2 password & salt or vice versa, and the PIN is the number of iterations no less than 1,000?

Specifically, this PBKDF2 scheme is merely a tool for the user to generate 32-byte signing keys from user memory rather than by storage.  Any conforming key is of course accepted by the overall implementation, but for those that use the tool properly, I'd like to help save them from themselves.

If the standard username/password rules should not be implemented, why, and what minimums, by any measure such as length or quantity and/or variety of special characters, should be placed upon the PBKDF2 password/salt combination?

In other words, because none are ever stored by the implementation, can standard login authentication guidelines also with a 4-digit PIN be enforced to produce theoretically uncrackable combinations where the login username & password are substituted for the PBKDF2 password & salt or vice versa, and the PIN is the number of iterations no less than 1,000?

I see no good reason to make the iteration count configurable, at least within just 1000-9999. Attackers can check all the hashes with the different iteration counts in similar time as only the 9999 one, if they know know the hash and salt.

If you leave the iteration count configurable, it would need to have a significantly larger range of allowed values before it had much of an effect on how an attacker should try to look for a matching password. I.e. several orders of magnitude. That would mean someone willing to wait, say ten seconds every login (tens of millions of iterations) would get some extra buffer.

The standard specifies which of the parameters is meant to be the password (the one used as HMAC key) and which the salt, and while using them in the opposite order may not be insecure, that's what you should use to be safe. I.e. the secret password/passphrase as the PBKDF2 password and the (possibly public) username as the salt.

  If the standard username/password rules should not be implemented, why, and what minimums, by any measure such as length or quantity and/or variety of special characters, should be placed upon the PBKDF2 password/salt combination?

Well, pretty much no heuristics can stop a user using a poor passwords like "pa$$w0rd". However, the purpose of KDFs like PBKDF2 is to make the cost of cracking a password higher for an attacker. You can basically subtract ~10 bits from desired attack complexity due to your 1000 iterations.

For example, NIST recommends 80 bits for most secure passwords. You might get away with 70 for a comparable strength. That would mean 12 random base 64 characters (~numbers and upper and lower case letters), but a user-chosen 12 character password would probably have much lower entropy, even if it contained lower-, uppercase and numbers.

As an aside: if you want to guide users to choose good passwords, I would rather not set any limits (especially maximum length or minimum character set) and point users towards something like Diceware or password managers.


Is it safe to use RSA multiple times Assuming I have multiple symmetric keys on specific machine(more than 10000 probably),
can I use the same rsa key to encrypt all of those keys?
I'm a bit concerned from a situation where multiple encrypted keys will have similar pattern
and will leak data about the original ones

You shouldn't be concerned if you use PKCS#1 v2 encryption padding - the OAEP.
OAEP, the Optimal Asymmetric Encryption Padding guarantees that even the slightest difference in raw plaintext (in your case, your symmetric keys) will result in huge difference in padded plaintext.


concerning collision-resistant hash function Let H, H' be collision-resistant hash functions. Which of the following functions H'' is NOT
necessarily collision-resistant?

1) H''(x) = H(H'(x))

2) H''(x) = H(x)||H'(x), where || denotes concatenation.

3) H''(x) = H(x)||0...0, where || denotes concatenation.

4) H''(x) = H(x) xor H'(x)

My conclusion is the following:

1. H(H'(x)) is the collision resistant as H(x) is collision resistant thus it will return the output as collision resistant.

2. In this there is concatenation of two collision resistant functions thus the output will also be collision resistant.

3. It is also collision resistant as this is just concatenation of collision resistant and 0.'s thus it will also be collision resistant.

4. As H''(x) is the XOR operation thus there could be chances that result of both of them would be same due to which it will always return 0.

Thus it may not be collision resistant.

I appreciate if experts correct me if i am wrong.

When given the question "here's a hash function $H''$ based on a collision resistant hash functions $H, H'$; is $H''$ also necessarily collision resistant?', there are two general ways to answer the question:

We can show how, given a collision in $H''$, we can deduce a collision in either $H$ of $H'$.  That is, if we were given two values $x \ne y$ with $H''(x) = H''(y)$, could we then immediately give two values $z \ne w$ with $H(z) = H(w)$ or $H'(z) = H'(w)$?  If we can, then we can conclude that $H''$ is collision resistant (because if it weren't, that is, if we could find a collision, we'd also find a collision in $H$ or $H'$, and we assumed we weren't able to do that.
We can demonstrate a pair of collision resistant functions $H, H'$ (possibly quite artificial ones, but you won't need that here) that, with the construction, make finding a collision in $H''$ easy.  This would show that $H''$ needn't necessarily be collision resistant.

It turns out that, for all four examples you gave, demonstrating either 1 (for an answer "yes") or 2 (for an answer "no") is quite straight-forward.

Your homework is to figure out the details...


Is there FHE (fully homomorphic encrpytion) for string/text processing? I had a quick look at FHE libraries like SEAL, HeLib, and Palisade and they deal with addition or multiplication of encrypted data.

Is there a FHE that deals with string? If no, is that because it is computationally expensive or there is a better/simpler way to work with text/string-based encryption?

Example of string-based processing here, would be to check if a string is an email address and maybe return 1 if Gmail and 2 if Hotmail

Any clarification is very much appreciated.

All encryption methods deal with bit or numbers not strings. You can convert your strings into bits and numbers to process. As I understood from your question you are looking for detection of mail provider on the FHE encrypted data.

One way to this is by encoding your data. You can separate the e-mail as the user_name and domain then encrypt and use integer comparison circuit to check. You can find the circuit in this answer

Of course, you can compare without encoding, however, this circuit will be much complicated and slower.

update for implementation

There can be pitfalls on the implementation design. For example, if you only send the encrypted values of the domain names like gmail and hotmail
you may leak information to the server with the size of the ciphertext. To mitigate the problem, first, determine the maximum possible length of all possible domain, then encode the domain names with leading zeros. After that you can call the comparator circuit $\mathcal{C}$; $$\mathcal{C}(c_1,c_2,p_k^{[1]})$$

where $c_1 = enc_{p_k}(\operatorname{encode}(p_1))$ and $c_2 = enc_{p_k}(\operatorname{encode}(p_2))$ with your public key, $p_k$

Once the server returns you the FHE result bit $r$, either decrypt with your secret key $s_k$,

$$cpm(p_1, p_2) = Dec_{s_k}(r)$$
$$cmp(p_1, p_2) = Dec_{s_k}(\mathcal{C}(c_1,c_2,p_k))$$

or use it with some other circuit that you want to calculate.

Note 1: Your data need not be on your site. You can supply the server with the cloud data.

Note 2: If your data encrypted with AES, and deployed into the cloud, you can still compute the comparison circuit, this time the operation is a bit more complex. You need to run an AES decryption FHE circuit so that after the circuit finishes, you don't have plain plaintext around but the FHE encrypted plaintexts. Now, you can call the $\mathcal{C}$ but this time you may need to compare all e-mail.

[1] : Your public key may be required to during computation by the server, like encryption of zero or one. Therefore, you sent it into your circuit.


How to select elements randomly from a multiplicative group Zn* I am working on a problem in which I have two large safe primes say p and q randomly selected each of 512 bits. I have generated these safe primes using OpenSSL library.Now,

  n = pq

What will be Zn* called? Is it a group under multiplication modulo n and same as (Z/nZ)*? But I have read that (Zn,⋅), integers modulo n under multiplication, is a group if and only if n is prime?
In this link

What all comprises the elements of this group if at all this is a group? And is there way to select its elements randomly using a code in C/C++ using some library like Openssl.

Thanks and Regards.

$(\mathbb Z_n,+,\cdot)$ and $(\mathbb Z/n\mathbb Z,+,\cdot)$ both denote the ring of integers under addition and multiplication modulo $n$, per perhaps different but in the end equivalent constructions. This set has $n$ elements.

$\mathbb Z_n^*$ and $(\mathbb Z/n\mathbb Z)^*$ both denote the subset of elements of said set which have an inverse under multiplication modulo $n$ (or equivalently, which Greatest Common Divisor with $n$ is 1). It forms a group under multiplication modulo $n$.

The ring $(\mathbb Z_n,+,\cdot)$ is a field if and only if $n$ is prime, in which case $\mathbb Z_n^*$ is simply $\mathbb Z_n-\{0\}$.

By definition, $x$ in $\mathbb Z_n$ belongs to $\mathbb Z_n^*$ if and only if $x$ has a multiplicative inverse $y$ , that is such that $x\,y\equiv1\pmod n$ (or equivalently, if and only if $\gcd(x,n)=1$ ). When $n=p\,q$ with $p$ and $q$ primes, this is if and only if $x$ is such that $x\ne0\pmod p$ and $x\ne0\pmod q$ . The set $\mathbb Z_n^*$ has $\varphi(n)$ elements, where $\varphi$ is Euler's totient function. If $p\ne q$ , then $\mathbb Z_n^*$ is the set of the $\varphi(n)=(p-1)(q-1)$ elements of $\mathbb Z_n$ that are divisible by neither $p$ nor $q$ . If $p=q$ , then $\mathbb Z_n^*$ is the set of the $\varphi(n)=p(p-1)$ elements of $\mathbb Z_n$ that are not divisible by $p$ .

We can obtain a uniformly random element of $\mathbb Z_n^*$ in several ways:

Heuristically: generate a uniformly random integer $x$ in $\mathbb Z_n$ (that is a uniformly random integer in $[0,n)$ ) until $x$ is divisible by neither $p$ nor $q$ (which if almost certain in practice if $p$ and $q$ are large). We can equivalently test if $\gcd(x,n)=1$ using the Euclidean or Binary GCD algorithm, with the advantage that we do not need the factorization of $n$. Also, we can as well generate $x$ in $[1,n)$ before testing it, since we'd eliminate $x=0$ anyway.
Constructively: generate a uniformly random integer $u$ in $[1,p)$ , and

if $q\ne p$ generate a uniformly random integer $v$ in $[1,q)$ , and form $x$ in $[0,n)$ with $x\equiv u\pmod p$ and $y\equiv v\pmod q$ by the Chinese Remainder Theorem; for example, as $x=(q^{-1}(u-v)\bmod p)q+v$.
if $q=p$ generate a uniformly random integer $m$ in $[0,p)$ , and form $x=m\,p+u$.


Checking the share membership in secret sharing schemes I was thinking of this since yesterday. Imagine, a secret is split into its respective shares (using any secret sharing scheme) with threshold $t$ and total $n$.  Can we find out given any random string if it is a valid share of the secret ?

Of course without brute force approach, i.e splitting the secret into its shares and matching the string with each of its member to find out if its legitimate member.

Is it possible at all ? for any secret sharing mechanism ? So to summarize, given a string $s_i$ ,a secret string $secret$ and any configuration parameters needed (say $t,n$ values etc) to share secret.

Can we identify if $s_i$ is valid $secret$ without brute force approach described above ?

Just to be specific we are talking about information theoretically secure secret sharing, e.g. Shamir sharing. Lets say a secret $secret$ is shared in $n$ shares $S = \{s_1, \ldots, s_n\}$. Assume further party $P_i$ is given share $s_i$. If I understand your question correctly, you are asking if we give $P_i$ some share $r \ne s_i$ is there anyway for $P_i$ to decide if $r \in S$?

If that is the question, I think the answer is, "no", since it would contradict the properties of secret sharing.

Here is my argument: Assume we give $P_i$ some help. We give her $t - 2$ shares from $S\backslash \{s_i, r\}$. Now $P_i$ has $t - 1$ shares of $secret$. Now $P_i$ can take $r$ and in total have $t$ shares (possibly with one share not being correct). This is enough to reconstruct some secret $secret'$. If and only if $r \in S$ we have "secret' = secret". So if $P_i$ could tell if $r \in S$, then $P_i$ would know whether or not $secret' = secret$. However, this contradict the property of secret sharing that $t - 1$ shares gives no information on the secret.

In fact since this is information theoretic security even a brute force attack will make no difference.


Secret sharing - no dealer, modifiable, verifiable I need to find a secret sharing scheme with these properties:

The scheme is set up by all participants, ie no single entity called the dealer

The parameters of secret sharing need to be modifiable, eg enrollment, disenrollment, change of access structure, ...

Need to be verifiable, ie participants could check whether their shares are consistent with others.

Is this scheme could be available at all !?
A brief description is helpful.

The "simple" answer to your question is that all of the above can be achieved using secure multiparty computation (see this review article on Secure Multiparty Computation for a more detailed overview). The best way to abstract this is to define an "ideal functionality" $F$ which is run by a trusted third party, receiving inputs from the parties and providing outputs. The theory of MPC then tells us that any such functionality can be securely computed by the parties interacting. (There are details of early abort, fairness, etc. However, I believe that this is orthogonal to what is in the question.)
According to the above, we can define each of the required features as an ideal functionality:

For setting up the sharing without a dealer, one has to assume that they are generating a sharing of some random value (otherwise what are they sharing). Assuming that they wish to share a random $s\in\mathbb{F}$ according to some access structure $\cal Q$, the ideal functionality can be defined to receive the description of the field and the access structure from all parties. Then, assuming they are all the same, it samples a random $s\leftarrow\mathbb{F}$, locally computes the secret sharing according to $\cal Q$, and sends each party its share.
The parameters can all be changed by defining an ideal functionality that receives the shares from all parties (or at least a quorum) and the new parameters. The trusted party then reconstructs the secret $s$, generates a new secret sharing according to the new parameters, and sends each party its new share.
Verifiability follows automatically from the fact that if the MPC protocol is secure against malicious adversaries, then it is guaranteed that all outputs are correct.

Having said this, one issue that may arise is that parties may send incorrect shares to the trusted party for the second item. This can be solved by either assuming that the threshold is strictly less than the number of parties participating. This suffices since if the secret sharing is Shamir, for example, then all shares must lie on the same polynomial, and any incorrect value is detected. However, if you wish to prevent an abort, then you need enough redundancy (e.g., if $t<n/3$ then you will always have enough honest shares to "correct" any corrupt ones). Another, more general, way of ensuring that nothing is changed is to have all parties hold commitments of all shares, or the like, and the trusted party verifies that all inputs used are unchanged.
Having said all of the above, what one often wants is something more complex. First, not all parties may participate in all phases. Second, you want to find an efficient MPC protocol that deals with the above. In general, this is all possible. However, exactly specifying how to do it is beyond the scope of this answer, and depends very much on exactly what setting you are in. The best source to understand more specifically about this would be the book Secure Multiparty Computation and Secret Sharing. However, there are many techniques that are relevant that can be found in the MPC literature.


Generating AES-256 Private Key from user string So I wish to encrypt a string using AES-256 and want to provide the user to specify the password for unlocking the string. I plan to use sha-256 to hash to users entered password and use this as the key. Is this secure? and is their a better way of doing this?

Edit: it would be nice if people left a comment about why they down-voted it.

Using a key derived from a password hash means someone could brute force this using either a known list of passwords or dictionary.

Since SHA-256 is quite fast, it's very easy to do with a moderate amount of computational power.

To better protect the key from such an attack, it is suggested to use a password derived from a key derivation function.

Some examples of these include: PBKDF2, scrypt and argon2.


Homomorphic encryption based on XOR Consider the values $a$ and $b$ are encrypted as $c_1=(a \oplus D)$ and $c_2=(b \oplus D)$.

My question is: can we derive $b+a$ from any combination of $c_1$ and $c_2$?

Note:

I admit that the $D$ should have not been used for both $a$ and $b$. For now assume we can use it.
Basically I define the values ($a$ and $b$) in $Z_p$, accordingly the result in $Z_p$.

Based on the additional details in the comments, it seems like your question is: given $c_1=a\oplus d$ and $c_2=b\oplus d$, can we get $(a+b)\oplus d$. Where $a,b,d\in\mathbb{Z}_p$, $+$ is addition modulo $p$, and $\oplus$ is a bitwise XOR of the values, then taken modulo $p$.

Or put another way, is there an operation $\boxplus$, such that $(a\oplus d)\boxplus (b\oplus d)\equiv (a+b)\oplus d\bmod{p}$?

Hopefully I've understood the problem correctly.

The answer is no, except in the trivial case of $p=2$, or more generally (if $p$ is not necessarily a prime) when $p=2^q$ for some prime $q$. That is because in these two cases, in the finite field $\mathbb{Z}_p$, $\oplus$ and $+$ are traditionally the same operation (note that by $+$ I am not talking about integer addition modulo $p$, I am referring to addition in the finite field). Or put another way $+$ is defined as bitwise xor in these fields.

In the case where $p\neq 2$ and $p\neq 2^q$ for some prime $q$, the bitwise XOR destroys all algebraic structure necessary for there to be an operation $\boxplus$. Now, what you can do is use $+$ instead of $\oplus$. Then you have $(a+d) + (b+d) = (a+b) + (d+d)$ and to decrypt, subtract $(d+d)$. If doing this, you should use different $d$ values for each message. In other words $(a+d_1) + (b+d_2) = (a+b) + (d_1+d_2)$ and to decrypt, subtract $(d_1+d_2)$. The $d_i$ values must be randomly chosen.

Full disclosure: My answer is based on intuition. It might be hard to prove that $\boxplus$ does not exist, but it seems very unlikely that it does. Basically we need associativity between $\oplus$ and $\boxplus$ (i.e., $(a\oplus b)\boxplus c = a \oplus (b\boxplus c)$ and $\boxplus$ must be commutative ($a\boxplus b = b\boxplus a$). There are lots of candidates for commutativity, but I can't think of any for that type of associativity.


How can i calculate prime of Elliptic Curve? In many articles i have found directly the calculation of prime elliptic curve. How can i calculate this prime $p$ ? For example if I consider NIST P-256, $ p = 2^{256}-2^{224}+2^{192}+2^{96}-1$. Why ? Is there a formula ? Thanks for your support.

This prime $p$ corresponds to the size on the base field $\mathbb F_p$ on which is defined the elliptic curve. It has not been computed, it has been chosen. It is chosen to satisfy a few properties, like, of course, being prime, but also being large enough (here, 256 bits), and allowing fast computations modulo $p$.
Maybe when you say "prime elliptic curve", you mean elliptic curves with a prime number of points? The number of points is not the prime $p$, and is computed using the Schoof-Elkies-Atkin algorithm.


In CPA, how does one-message security implies multi-message security? I am learning modern cryptography and recently we reached the CPA mechanism.
In CPA game setting, A sends two messages to C and then C randomly chooses one message and encrypts it and sent the encrypted text back to A, then A will determine which one of the two messages is chosen by C.
However, if A sends two identical messages, say 'm', to C, A would definitely know the encrypted 'm' by the returned text of C. Then, for the second time, A can send a 'm' and any other message to C, then, if the returned text of C is the same as that of the returned text when inputting 'm', the message chosen by C is 'm', otherwise is that any other message. And this enables A to have a probability of 1 to guess the chosen message of C.
So, it seems that one-message security doesn't imply multi-message security, even in the one-message security scheme, if the two sent messages from A are the same, A still has a probability of 1 to guess the chosen one of C.
Could anyone help me in understanding this?
Thank you for the answering!

For the CPA game, we play the following experiment

Generate a key $k$ with the security parameter $n$
The adversary $\mathcal{A}$ is given the $n$, Oracle access to the encryption oracle $Enc_k(\cdot)$
$\mathcal{A}$ outputs two messages $m_1$ and $m_2$ of the same length ( here, there is no restriction about $m_0 \neq m_1$)
A random bit is chosen $b \overset{R}\leftarrow \{0,1\}$ the the ciphertext $c = Enc_k(m_b)$ is computed and trasnmitted to $\mathcal{A}$. This is called the challange ciphertext.
$\mathcal{A}$ access to the encryption oracle $Enc_k(\cdot)$ ( even before  submitting)
And, finally, $\mathcal{A}$ submits $b'$ as their candidate
The output of the experiment is defined to be $1$ if $b' = b$ and $0$ otherwise. If the output is $1$, we also say that $\mathcal{A}$ succeeds.

Then we can make the definition of $Ind\text{-}CPA$ as;
An encryption scheme is  $Ind\text{-}CPA$ if for all probabilistic polynomial-time adversaries  $\mathcal{A}$ the advantage is negligible $negl(n)$
Notes:

The negligible is depends on the security parameter $n$
There is no restriction for submitting the same messages. The adversary must find the correct $b$.
If you send two identical messages there is no advantage since the adversary will not learn anything.
CPA security requires randomized encryption. Deterministic encryption like ECB mode cannot have CPA security.
The experiment also requires a good random number generator.
In public-key cryptography, the encryption oracle  $Enc_k(\cdot)$ is free. One can access all the time they have, consider encrypting with RSA's public key.
The key is fixed during the experiment (Step 1)

However, if A sends two identical messages, say 'm', to C, A would definitely know the encrypted 'm' by the returned text of C. Then, for the second time, A can send a 'm' and any other message to C, then, if the returned text of C is the same as that of the returned text when inputting 'm', the message chosen by C is 'm', otherwise is that any other message. And this enables A to have a probability of 1 to guess the chosen message of C.

You know the $m$ but which $b'$ will you submit to win the game?
For the second time the encryption of the $m$ will change since the CPA game requires randomized encryption, in other terms any CPA-secure encryption scheme must be probabilistic. In which, random coins tossed in order to ensure that two encryption of the same message is different.


Effect of ESSIV when used with XTS I looked everywhere on the web and I did find a lot of information about full disk encryption, but nothing really answered my question.

When formatting a partition to use LUKS, the two most common ciphers are

aes-xts-plain64
aes-cbc-essiv:sha256.

Now I know that ESSIV is simply a way to prevent the watermarking attacks possible against CBC. Still, a cipher like "aes-xts-essiv:sha256" is accepted by cryptsetup, and it is the setting I have been using on my laptop for quite a while.

My question is then, why are people not using ESSIV with XTS instead of plain IVs? Every bit of entropy in the encryption procedure should make the result more resistant, right? Is doing this actually harmful to the security of the data, or does it just use slightly more processing power?

Because XTS already solves the problem ESSIV is designed to solve.

Disk encryption modes are meant for retaining some security despite the lack of space for a unique IV. They do this by making use of the sector number so that at least multiple copies of the same data stored in different places end up looking different. That is not sufficient for good general purpose security, but the best that can be done transparently in full disk encryption.

With XTS the sector number is used as a tweak so that every sector is encrypted with an effectively independent FPE transformation. With ESSIV each sector is encrypted with an effectively independent key. Using both would have no additional advantage: different sectors are already encrypted differently with XTS alone and using both would not change the fact that on rewriting the single sector is encrypted deterministically.

Another, more heuristic way to look at it is that using the information (sector number) again does not "add entropy".


LFSR Output Sampling for Berlekamp-Massey Looking at the use of Linear Feedback Shift Registers in cryptographic algorithms, I have learned that the Berlekamp-Massey algorithm can be used to find the (shortest) LFSR that generates a given sequence.

But I am not sure if I have really understood things correctly.

Since an LFSR function always returns a copy of its (current) state, one only has to collect enough outputs to be able to construct an LFSR that produces the same binary sequence like the attacked LFSR produces. In a sense this could be interpreted as "collect enough samples/output" to be able to create a function that allows to reconstruct the same binary sequence. (Hope that's correct so far?)

Now, what I am unsure about:

correct LFSR output sampling for Berlekamp-Massey

To be able to successfully apply the Berlekamp-Massey algorithm, does it matter if the collected samples/output are collected "in sequence", or is it enough to do "random sampling"?

Differently asked (to ensure you get what I'm trying to ask), which one of the following is correct:

Start by fetching a random output and continue collecting several follow-up outputs until enough outputs/samples have been collected. (what I called "in sequence")
Skipping/missing a few outputs during sampling does not represent a problem, because it does not have to be a series of follow-up outputs; as long as the total number of collected random samples/outputs suffices. (what I called "random sampling")

expected info to be able to calculate the minimum number of needed samples

I've seen some formulas which seemed to point at the calculation, but I do not yet understand them well enough to deduct an answer to the following: Can the minimum number of to-be-collected samples be deducted from a single LFSR sample/output, or would one need more than a single sample/output to calculate the the minimum number of to-be-collected samples/outputs (which would be needed to successfully apply the Berlekamp-Massey algorithm)?

Please don't misinterpret my questions. I'm "doing my research" and I have been reading a whole slew of academic papers that I found in relation to Berlekamp-Massey, but that doesn't mean I'm confident in the fact that I am interpreting those papers correctly. Also, search engines aren't always the best place to find good references. If you know about a specific paper that I should definitely be reading (in relation to Berlekamp-Massey and related LFSR attacks/breaks), I would be grateful if you'ld point me to it.

Berlekamp-Massey is designed for the situation where you have observed $2n$ consecutive output bits from a $n$-bit LFSR.  It doesn't work if the observed bits are scattered randomly, at random non-contiguous offsets in the stream.

Information-theoretically, a minimum of $2n$ bits of output are needed to reconstruct the LFSR.  Intuitively, this is because there are $2n$ bits of unknowns: the unknown $n$-bit state of the LFSR, and the unknown $n$ bits on the taps (the feedback polynomial).  Therefore, Berlekamp-Massey exactly meets the known lower bounds, in the case where you get to observe consecutive output bits.

Of course, you could also have used linear algebra to solve for these $2n$ unknowns, but Berlekamp-Massey is faster than solving a system of linear equations ($O(n^2)$ instead of $O(n^3)$, or something like that).

The number of observations you need depends only on the size of the LFSR, not on the output bits.  If you do know the size of the LFSR, you don't need to see any output bits to predict how much output will be needed.  If you don't know the size of the LFSR, seeing a few output bits doesn't help you predict the size of the LFSR and doesn't help you  predict how much output will be needed.

One cool thing about Berlekamp-Massey, though, is that you don't need to know in advance what the size of the LFSR is (what $n$ is).  You can just start running Berlekamp-Massey on the output stream, and it will generate candidates for the LFSR initial-state and feedback polynomial.  After each bit of output, it will update its candidate.  Once you've observed $2n$ bits of output, you are guaranteed that its candidate is correct.  If you don't know what $n$ is, you can take each candidate and test it against the next few output bits; this will let you recognize when Berlekamp-Massey has finally found the right candidate, i.e., when you've observed enough output stream (it'll let you recognize when you've hit the $2n$ limit, even though you don't know $n$ a priori).


Calculate shared key having A public Key and B private Key (Diffie Hellman) I cannot understand how this works.

$\text{A}_\text{public} = g^a \bmod p$

$\text{B}_\text{private} = \text{B}$

$\text{g} = p$

I also have $p$, I need to get the shared key, that I know both $\text{A}$ and $\text{B}$ get exactly the same value. Im not understanding how can I get the shared key that $\text{B}$ generated only having those variables I wrote above.

Also I know that the shared key is $\text{g}^\text{ab} \bmod p$, how can I get that $\text{b}$ value?

$\text{B}_\text{private}$ is $\text{b}$ and $\text{B}_\text{public}$ is $\text{g}^\text{b} \bmod p$.

So $\text{B}$ can compute $(\text{A}_\text{public})^b \bmod p = \text{g}^{\text{ab}} \bmod p$


Skein or Keccak stream cipher construction I am wondering if using Skein or the Keccak hash algorithm in this construction (as a stream cipher) is secure:

$H$ = Keccak or Skein hash with a 256 bit output
$K$ = The main 256 bit random key, pre-shared between sender and receiver
$K_M$ = A secondary 256 bit random key for creating the MAC, pre-shared between sender and receiver
$IV$ = A per message 256 bit random initialization vector, sent in the clear with the ciphertext and MAC
$i$ = counter starting at 0 for each message which increments by 1 every 256 bit block
$K_i$ = 256 bit block of the generated key for encrypting the corresponding 256 bit block of the plaintext $P_i$
$P_i$ = 256 bit block of the plaintext. The final plaintext block would be padded to the right with 0 bits, thus the
final concatenated plaintext is a multiple of 256 bits and disguises the true plaintext length.
$C_i$ = 256 bit block of ciphertext
$|$ = concatenation
⊕ = XOR

Encryption:

$K_i$ = $H$($K$ | $IV$ | $i$)
$C_i$ = $K_i$ ⊕ $P_i$

MAC:

$H$($K_M$ | $IV$ | $C_i$ ... $C_n$)

I hope I explained that clearly.

My other question:

Is there a particular attack on using the same key for encryption and MAC?

I am wondering if using Skein or the Keccak hash algorithm in this construction (as a stream cipher) is secure:

In the case of Skein and Keccak it should be secure. However, both of those have defined their own cipher modes which you should IMO prefer. (For speed and compatibility, if not security.)

The Skein one is defined in section 4.10 of the paper. It uses the underlying primitive directly rather than hashing the key and nonce.
For Keccak the web site links to a separate paper on an authenticated encryption mode. It uses the sponge to squeeze a larger number of output bits, like the SHAKE modes of the hash function.

Alternatively, in the case of Keccak/SHA-3 you may want to use one of the SHAKE extendable output functions, which produce an arbitrarily long output stream. They may also be faster than repeated calls to the hash function.

  Is there a particular attack on using the same key for encryption and MAC?

You should make sure the MAC invocation can never match an encryption one. I.e. it is not possible for $K|IV|C$ to match any $K|IV|i$. Easiest would probably be to add a string to make them differ, like $H(K|\text{'E'}|IV|i)$ and $H(K|\text{'A'}|IV|C)$.

In that case the MAC and encryption are independent, and a known or chosen plaintext attack cannot leak any extra MAC values.

Generically, your construction is not necessarily secure. First a hash function doesn't have to be a secure MAC when you prepend the key. Second, a stream cipher must be a PRF, which is a stronger condition than unforgeability for a MAC.

For example, you could define a stupid MAC like: $MAC_k(m)||MAC_k(m)$ and it would be just as strong a MAC as the original, but would make a lousy stream cipher.

(In practice most MACs do seem to also claim to be PRF.)


How to divide 2 coordinates on elliptic curve? On the elliptic curves, there is no divide function, and I need divide coordinates - X/Y, o I need not divide but make (X minus or multiply to "modified" Y). How to modify Y?

An elliptic curve as used in cryptography is a finite group, constructed on top a finite field. A pair of elements of the field that obey the curve equation form the Cartesian coordinates of a point of the elliptic curve group (and vice versa for all points of the elliptic curve group, except the neutral / point at infinity, often noted $\infty$).
In the field we can add; subtract; multiply; and divide, except by 0. The result is an element of the field.
In the elliptic curve group we can add and subtract. The result is an element of the elliptic curve group. One such addition involves several operations in the field (with the exception of addition of the neutral).
There is no multiplication in the elliptic curve group: we can't meaningfully multiply two points of an elliptic curve group. We can however define multiplication of an integer $k$ and a point $U$ of an elliptic curve group, by using repeated addition:
$$k\times U\,\underset{\text{def}}=\;\begin{cases}\infty&\text{if }k=0\\((k-1)\times U)+U&\text{if }k>0\\(-k)\times(-U)&\text{if }k<0\end{cases}$$
It follows $1\times U=U$, and $2\times U=U+U$.

On the elliptic curves, there is no divide function.

That's an oversimplification. We can meaningfully define division of two points of an elliptic curve. $U/V$ can be the lowest non-negative integer $k$ such that $U=k\times V$, when there exists such an integer. For many elliptic curves of cryptographic interest, that operation is defined except when $V=\infty$; but is not efficiently computable for random $U$ or $V$ (that's the very basis of the security of cryptography on that elliptic curve).

How to divide 2 coordinates on elliptic curve?

That's just a division in the field, independent of an elliptic curve. How to perform the operation depends on the field.
A common field is $\Bbb F_p$, that is arithmetic modulo a prime $p$. In this field, we can compute $x/y$ (for $y\ne0$):

as $x\cdot\left(y^{p-2}\right)$, computed modulo $p$. In Python, that's x*pow(y,p-2,p)%p.
or, more efficiently, as $x\cdot a$, computed modulo $p$, where $a$ is the modular inverse of $y$ computed using the extended Euclidean algorithm. The integer $a$ (and the integer $b$, that we do not need) is found by solving for unknowns $a$, $b$ and givens $y$, $p$ the Bézout identity $a\cdot y+b\cdot p=1$. In Python starting with version 3.8, that's x*pow(y,-1,p)%p.


Are the following functions pseudorandom? Given a PRF $F $, such that for each $k \in \{0,1\} \ ^ n$ , $F_k:\{0,1\} \ ^ n \to \{0,1\} \ ^ n$ , is the function defined by $W_{k_1,k_2}(x) = F_{F_{k_1(0 \ ^n )}}(x) || F_{k_2}(x)$ also a PRF?

I'm almost sure the answer is yes.
I'm trying to assume $W$ is not a PRF and conclude that $F$ isn't either but I dont see how.

Let F be as in (1). Now $H_k(x) = F_k(x) || F_{F_{k}(1 \ ^ n)}(F_{F_{k}(1 \ ^ n)}(F_{k}(x)))$.
I think $H$ is not a PRF.
The polynomial distinguisher I thought about is the following:

$D$ on input $1 \ ^ n$ and orcal asses $O$ , asks for $O(1 ^ n)$ and writes $O(1 ^ n) = \alpha || \beta$ for $\alpha,\beta \in \{0,1\} \ ^ n$.
Now $D$ checks if $\beta = F_{\alpha}(F_{\alpha}(\alpha))$. if yes, outputs 1 otherwise outputs 0.

If $O=H_k$ then $D$ outputs $1$ so $Pr(D \ ^ {H_k()}(1 \ ^ n)=1 ) =1$.
If $O=h$ for a truly random functon then $D$ outputs 1 iff $F_{\alpha}(F_{\alpha}(\alpha)) = \alpha$ for $\alpha$ which is a random number in $\{0,1\} \ ^ n$.

I want to say that $Pr(F_{\alpha}(F_{\alpha}(\alpha)) = \alpha) = v(n)$ for a negl. func. and this will conclude the proof but i can't find a way to prove it. someone can help?

Thanks for the help.

Okay, so now that we've agreed that generalized pseudorandom functions can be of variable length :-D, I'll slightly rephrase your question to meet the definitions I'm working with, and then prove (1).

Given a pseudorandom function $F = \{F_{n}\}_{n \in \mathbb{N}}$, such that for each $k \in \{0,1\}^n$ , $F_k:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, is the function defined by $W_{k_1,k_2}(x) = F_{F_{k_1(0 \ ^n )}}(x) || F_{k_2}(x)$ a generalizable pseudorandom function?

Assume by contradiction that $W$ is not a generalizable pseudorandom function,
then there exists a probabilistic polynomial time (PPT) oracle machine $M'$ and a
polynomial $p(\cdot)$ such that for infinitely many $n$'s,

$$\big|\text{Pr}[M'^{W_{k_1,k_2}}(1^{n}) = 1] - \text{Pr}[M'^{H'_{n}}(1^{n}) = 1]\big| > \frac{1}{p(n)}$$

where $k_1,k_2 \xleftarrow{\$} \{0,1\}^n$ and $H' = \{H'_n\}_{n \in \mathbb{N}}$ with $H'_n$ uniformly distributed over the set of all functions mapping $n$-bit strings to $2n$-bit strings.

We will use $M'$ to construct a PPT oracle machine $M$ to distinguish $F_k$, where $k \xleftarrow{\$} \{0,1\}^n$, from $H = \{H_n\}_{n \in \mathbb N}$, where $H_n$ is uniformly distributed over the set of all functions mapping $n$-bit strings to $n$-bit strings. On input $1^n$, $M$ first queries it's oracle $\mathcal{O}$ with the string $0^n$ and records the result as $k' \leftarrow \mathcal{O}(0^n)$. $M$ then uniformly selects $k'' \xleftarrow{\$} \{0,1\}^n$. Next $M$ runs $M'(1^n)$ and serves as its oracle, returning $F_{k'}(x)||F_{k''}(x)$ whenever $M$ queries with input $x \in \{0,1\}^n$. Whatever output $M'$ returns to $M$, $M$ outputs itself.

If $\mathcal{O} = F_k$, then

$$\text{Pr}[M^{F_k}(1^n) = 1] = \text{Pr}[M'^{F_{k'}||F_{k''}}(1^{n}) = 1] = \text{Pr}[M'^{W_{k_1,k_2}}(1^{n}) = 1]$$

since how we chose $k'$ makes our experiment identical from the point of view of $M'$ to when it's interacting with the oracle $W_{k_1,k_2}$. If $\mathcal{O} = H_n$ we have $\text{Pr}[M^{H_n}(1^n) = 1] = \text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^n) = 1]$. Now, $M'$ is a black box, and was not "designed" to distinguish $W_{k_1,k_2}$ from $F_{H_n(0^n)}||F_{k''}$. That said, we can intuitively see that $F_{H_n(0^n)}||F_{k''}$ should not be distinguishable from $H'_n$ because of our assumption that $F$ is a pseudorandom function. We will now formalize that notion.

Assume that there exists a polynomial $q(\cdot)$ such that for infinitely many $n$'s

$$\big|\text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^{n}) = 1] - \text{Pr}[M'^{H'_n}(1^{n}) = 1]\big| > \frac{1}{q(n)}$$

We can then use $M'$ to construct a PPT oracle machine $M''$ to distinguish $F_k$ from $H_n$. We denote the oracle of $M''$ by $\mathcal{O}'$. On input $1^n$, $M''$ selects $k''' \xleftarrow{\$} \{0,1\}^n$ and runs $M'(1^n)$, acting as its oracle by returning $\mathcal{O}'(x)||F_{k'''}(x)$ for any query $x \in \{0,1\}^n$ that $M'$ makes.

If $\mathcal{O}' = F_k$, then

$$\text{Pr}[M''^{F_k}(1^n) = 1] = \text{Pr}[M'^{F_k||F_{k'''}}(1^n) = 1] = \text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^n) = 1]$$

where the last equality follows because $k$ was chosen uniformly at random and $H_n(0^n)$ is a uniformly distributed random variable over the outputs on input $0^n$ of every function mapping $n$ bits to $n$ bits, and $k'''$ and $k''$ were both chosen uniformly at random. In the case $\mathcal{O} = H_n$ we have $\text{Pr}[M''^{H_n}(1^n) = 1] = \text{Pr}[M'^{H_n||F_{k'''}}(1^n) = 1]$. We must now go just one layer deeper before deriving a direct contradiction, and prove by contradiction that $M'$ cannot $H_n||F_{k'''}$ and $H'_n$.

Assume that there exists a polynomial $r(\cdot)$ such that for infinitely many $n$'s

$$\big|\text{Pr}[M'^{H_n||F_{k'''}}(1^{n}) = 1] - \text{Pr}[M'^{H'_n}(1^{n}) = 1]\big| > \frac{1}{r(n)}$$

Since the first $n$ bits of the output of the two oracles should be uniformly distributed, they cannot provide any useful information to $M'$ to make its decision*. Then $M'$ must be able to distinguish $F_{k'''}$ from the second half of $H'_n$ with more than negligible probability. Since this is equivalent to distinguishing $F_k$ from $H_n$, it contradicts our claim that $F$ is a pseudorandom function.

Now we unfold the argument. Since $M'$ cannot distinguish $H_n||F_{k'''}$ and $H'_n$ with more than negligible probability, this contradicts our assumption that $M'$ can distinguish $F_{H_n(0^n)}||F_{k''}$ from $H'_n$ with more than negligible probability. If that assumption is wrong, then $M$ distinguishes $F_k$ from $H_n$ with only negligible difference in probability from that the which $M'$ distinguishes between $W_{k_1,k_2}$ and $H'_n$. By our hypothesis, this is non-negligible, but because we assume $F$ to be a pseudorandom function, no such $M'$ can exist. Therefore, we conclude that $W$ is a generalizable pseudorandom function.

* You could prove this more rigorously by remembering that polynomial-time unpredicability and pseudorandomness imply each other. Then show that you can replace $M'$ with a PPT oracle machine $M'''$ that never reads less than $n+1$ bits of its input (or more than $2n-1$) before guessing a bit, and that the probability that $M'''$ guesses correctly is no less than $M'$.


Explanation of the Fiat-Shamir heuristic The Wikipedia page on the topic (http://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) is completely useless as it only explains what it is and not how it works. I looked at the original paper by Fiat and Shamir, but it only contains a single construction. In other words, the so called heuristic must be an idea extracted from that specific construction.

Could anyone provide a more detailed explanation of how it works and also why the interactive proof system must be public-coin?

The initial idea of Fiat and Shamir was to eliminate the interaction in public coin protocols (note that public coin means that the random choices of the verifier are made public) and was used to convert three move public coin identification scheme into conceptually simple signature schemes (it has later been proven by Pointcheval and Stern that under the random oracle model such signature schemes provide existential unforgeability under chosen message attacks).

If you apply the Fiat-Shamir heuristic to interactive zero-knowledge proofs you

firstly collapse the protocol rounds which all the small challenge space of $\{0,1\}$ into one round using a larger challenge space (e.g., $\mathbb{Z_p}$, where the size of the message space controls the soundness error) at the cost of only being honest-verifier zero-knowledge, and
secondly you do not longer let the verifier sample the challenge (public coins), but compute the challenge as output of a hash function with input the previous protocol messages. The hash function is modelled as a random oracle (outputs random strings that are not distinguishable from truly random strings), which models the unpredictability of the verifier.

Why public coin? Because it is inherent to the Fiat-Shamir transformation, which basically exchanges the public coins of the original protocol with public coins obtained from the hash function.


Efficient way to confirm identity I am working on a multiplayer game.

I have a central server which handles all data transmission and coordinates all games. Clients which involved in a single session send requests to do actions to the server, those actions are checked and the consequences are pushed to all clients.

I am looking for a way for the server to confirm whether the request came from authorised client (a specific player).

I originally planned to use RSA, but it's too computationally expensive, and is an overkill since I don't need really need request data encrypted.

What should I do/use for this purpose?

Traditionally, one would just use an implementation of DTLS and some form of challenge-response player authentication.


Hide Randomness in Ciphertext Ciphertext has the property to appear random. As a matter of fact, randomness is the first test, an encryption algorithm must pass. However, there are various setups, which monitor the incoming/ outgoing traffic and can easily identify Random Bits (ciphetext). Is there any technique/ research paper in literature which can disguise the randomness of ciphertext, making it less susceptible to identification? In other words, can a system be designed to introduced undetectable form of encryption?

Note:- I am fully aware of steganography, but I want to explore the chances of hiding randomness in the domain of Encryption.

You can compute an $f(g(m))$ in which $g(m)$ is your encryption method and $f$ is a meaningful mapping function. As an example of $f$ I can mention a dictionary codebook mapping.
For example if your output is 11101000 you can see it as 1110 and 1000 then map 1110 to "apple" and 1000 to "grape". Your codebook here must consist of all inputs of 4 bits and the name of fruits as output.
In the receiver side, you must clearly first compute $f^{-1}$ and convert the name of fruits to predefined codes and then decrypt it.


Which compound algorithms would weaken cipher, not strengthen it? OK, in school, some of the lecturers always say "if you compound the crypto, it may make the cipher weaker".

So, which combinations of algorithms would do this? Why? Can anyone show the mathematical proof?

For example, would RSAk1(AESk2[AESk3[x]]) make the encrypted x weaker? Assuming all keys used are different and randomly generated using a SecureRandom function.

Moving my reply from the comments into a proper answer. The general case of double-encrypting is formally explained by Yehuda Lindell in this answer on crypto.SE. Summing up:

Same Algorithm, same key: It may or may not be secure, depending on the properties of the cipher. It is definitely not always secure, but may be secure for practical cases.
Same Algorithm, different keys: Secure, because otherwise people who do not know the key could break the encryption by encrypting with a different key, which would be... strange, and not very logical.
Different Algorithms, different keys: Secure, for the same reason. Otherwise, sending PGP-encrypted eMails over a TLS connection would be unsafe, which would be ridiculous.
Different Algorithms, same keys: Insecure. Never reuse keys for different encryption algorithms (even when not double-encrypting). For example: If you are using the same RSA keys to sign and encrypt, and the adversary can get you to sign a value for them, it can use you to decrypt data, because signature = encryption with the private key = decryption of data encrypted with the public key.

Summing things up: "Don't double encrypt" is a pretty general hint that definitely doesn't always apply, but it serves as a good baseline to avoid critical mistakes. The more nuanced version is "Don't reuse keys for different algorithms, and to be sure, don't double-encrypt with the same key and algorithm, either, it may hurt you".


Encrypting twice with same key gives back plain text I read in the answer here that when encrypting twice the plain text with same key could result in plain text as shown below

$encrypt_{key}((encrypt_{key}(plain)) = plain $

Which block-cipher algorithms are they? What is this property called in general? Is it considered weak?

Edit 1 : the question is about block ciphers, not block cipher modes of operation
Edit 2 : added more clarity to the question through an equation

These block ciphers are called involutional ciphers, after the (mathematical) involution property of a function. This article shows a cryptographic analysis of two of them: Khazad and Anubis.

Neither Khazad nor Anubis  seem to be broken at the time of writing, basically they use the same internal structure for normal block ciphers, replacing the inner components with involutional ones.


In modular calculations such as this, the divisor (in your case 26) must be at least the size of your character code space. Your code space is 46 characters, so that is not going to work.

Any output of the modular calculation will be less than the divisor, so you will never get 83 for x mod 26, it is not going to happen. For a 46 character code space, 46 is the appropriate divisor.

Also the code space for your message characters is inconsistent, 06 codes to both "6" and "R". 92 will also code the same as 00 mod 46, so your code book values will never work. They must all be unique mod 46.

You have even more problems with your key and ciphertext. There was no modular calculation in generating your ciphertext, or all values would be less than 26. I also have no idea how you got 83+48=105, and 48 is once again outside the code space.