How to perform frequency analysis of a substitution cipher using a Base64 alphabet Let's imagine a cipher that works like the following:

Plaintext is encoded to Base64.
The characters in the encoded plaintext are substituted with a randomly shuffled character set(A-z, 0-9, -, _, =).  The shuffled alphabet is, in essence, the key.

Not particularly complex or even secure.  But...

What if I wanted to do frequency analysis?

For example, "RUNFORYOURLIFE" when encoded in Base64 is:

UlVORk9SWU9VUkxJRkU=

When the character set is shuffled, the final cryptext can look something like this:

xv24DYG9qxG2xYg6DYxf

The key being:

yhAc5bTOWeYvBXCpVuoMJLdg8P1jHN3ZIsi67SrK4E_D9-x2qRQmnlkwUaFt0G=zf

Which is a shuffled version of:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_=

Let's also assume that the character set in subsequent messages is in the same order(ie the key is re-used).

Since the bytes are basically split up resulting in different character units that may or may not correspond, is frequency analysis still feasible?  Does encoding plaintext this way before encryption add any form of security?

My question mostly pertains to longer messages, as my example may be too short for any sort of real analysis.

I'll assume that the plaintext consists entirely of capital ASCII letters as in the example. This implies the high 3 bits of each byte of plaintext are 010.

It is useful to visualize how 3 consecutive bytes of plaintext map to 4 consecutive Base64 characters.

1. Frequency analysis of the last character of 4-char blocks in ciphertext

We see there is a straight mapping from the last of every three characters in the plaintext to the last of every four characters in the Base64 encoding (notice that the characters in Base64 codes the 5 lower bits of the character in the plaintext, on the right of the above picture, which are characteristic of the letter). It follows that we can perform single-letter frequency analysis on the ciphertext restricted to the last character of every block of four characters. If among the characters kept the last one is different from all the others, it likely represents = in Base64; all the other characters kept should be among 26 characters (else the assumption made above is disproved). The mapping, ordered by decreasing expected letter frequency in English plaintext (according to this source) is:

Plaintext          Plaintext          Plaintext          Plaintext
 | Base64           | Base64           | Base64           | Base64
 |  | Frequency     |  | Frequency     |  | Frequency     |  | Frequency
 E  F  0.12702      H  I  0.06094      W  X  0.02360      K  L  0.00772
 T  U  0.09056      R  S  0.05987      F  G  0.02228      J  K  0.00153
 A  B  0.08167      D  E  0.04253      G  H  0.02015      X  Y  0.00150
 O  P  0.07507      L  M  0.04025      Y  Z  0.01974      Q  R  0.00095
 I  J  0.06966      C  D  0.02782      P  Q  0.01929      Z  a  0.00074
 N  O  0.06749      U  V  0.02758      B  C  0.01492
 S  T  0.06327      M  N  0.02406      V  W  0.00978

and with a kilobytes of ciphertext, it is likely that the most frequent character in the fraction of the ciphertext kept corresponds to E in the plaintext, thus F in the Base64.

2. Frequency analysis of the first character of 4-char blocks in ciphertext

There is a function from the first of every three characters in the plaintext to the first of every four characters in the Base64 encoding; we can perform a variant of single-letter frequency analysis on the ciphertext restricted to the first character of every block of four characters. The characters kept should be among 7. Expected frequency is

Plaintext  Base64  Frequency
  DEFG       R      0.21198 = 0.04253 + 0.12702 + 0.02228 + 0.02015
  LMNO       T      0.20687 = 0.04025 + 0.02406 + 0.06749 + 0.07507
  TUVW       V      0.15152 = 0.09056 + 0.02758 + 0.00978 + 0.02360
  PQRS       U      0.14338 = 0.01929 + 0.00095 + 0.05987 + 0.06327
  HIJK       S      0.13985 = 0.06094 + 0.06966 + 0.00153 + 0.00772
   ABC       Q      0.12441 =           0.08167 + 0.01492 + 0.02782
  XYZ        W      0.02198 = 0.00150 + 0.01974 + 0.00074

It happens that the set of Base64 characters in the second method is a subset of the set for the first; this allows cross-checking the guesses.

3. Frequency analysis of the third character of 4-char blocks in ciphertext

There is a function from the second of every three characters in the plaintext to the third of every four characters in the Base64 encoding; we can perform a variant of single-letter frequency analysis on the ciphertext restricted to the third character of every block of four characters. The characters kept should be among 16 (except perhaps the last, which may map to = in the Base64 character set). Expected frequency is

Plaintext                               Plaintext
 | Base64                                | Base64
 |  | Frequency                          |  | Frequency
EU  V  0.15460 = 0.12702 + 0.02758      HX  h  0.06244 = 0.06094 + 0.0015
DT  R  0.13309 = 0.04253 + 0.09056      GW  d  0.04375 = 0.02015 + 0.0236
CS  N  0.09109 = 0.02782 + 0.06327       L  x  0.04025
IY  l  0.08940 = 0.06966 + 0.01974      FV  Z  0.03206 = 0.02228 + 0.00978
AQ  F  0.08262 = 0.08167 + 0.00095       M  1  0.02406
 O  9  0.07507                           P  B  0.01929
BR  J  0.07479 = 0.01492 + 0.05987       K  t  0.00772
 N  5  0.06749                          JZ  p  0.00227 = 0.00153 + 0.00074

Several of the characters in the Base64 character set for this third method also occur in the first two methods; this allows cross-checking the guesses.

Frequency analysis of bigrams

We can also consider bigrams in plaintext occurring in the last character of a block of three, and the first character of the next block; and how they map to bigrams in Base64 occurring in the last character of a block of four, and the character following. We can compute the common bigrams obtained in the ciphertext by keeping (as first character of bigram) the last character of a block of four, and (as other character of bigram) the next character; and compare to common bigrams in English (adding frequencies of up to 4 bigrams as we did in the second method).

This also works for bigrams in plaintext occurring in the last two characters of a block of three, mapping to bigrams in Base64 occurring in the last two characters of a block of four; again well be comparing to the frequencies of common bigrams in English (adding frequencies of up to 2 bigrams as we did in the third method).

Common/guessable trigrams in plaintext to finish the analysis

The above will allows recovering the mapping to ciphertext of no more than 36 out of 65 characters used in Base64. For the others, we should guess some aligned blocks of three characters in the plaintext based on what we already know and common English words, transcode these blocks of three plaintext characters to four Base64 characters, see if there is a contradiction with the established mapping of Base64 to ciphertext, and if not cautiously apply the new guesses.

Automated cryptanalysis

As rightly pointed in that other answer, heuristic algorithms can handle the search automatically. Still, I guess that the first three techniques (which can be adapted to different plaintext alphabets, e.g. with space, lowercase..) will greatly simplify the heuristic.


How to decrypt using public key? Can anyone decrypt ciphertext using a public key? I always thought we can only decrypt using a private key. In that case, what does this line in the RLPx documentation mean?

Receiver receives the initiator handshake and decrypts it with its own public key.

Is the author talking about verifying signatures?

That's actually a typo, you'd use your private key, not your public key, to establish the secret used for ECIES. File a bug report on the documentation!


Compute statistical distance between two distributions over tuples Let $X$ denote one distribution. Let $f,g, \text{ and } h$ denote three functions. If we have the results: $g(X)$ is within a negligible statistical distance of $h(X)$. Is it possible to prove

$$(f(X),g(X)) \text{ is within negligible statistical distance of } (f(X),h(X))$$

I was struggling with this problem for a long time.
Any hints are welcomed.

No, you cannot prove that, since it is not generally true. Consider the following counter example.
Let $X$ be a distribution over $\{0,1\}$ with $$\Pr_{b\gets X}[b=0] = \Pr_{b\gets X}[b=1]=\frac{1}{2}.$$
Let $f,g,h : \{0,1\} \to \{0,1\}$ be defined as $$f : b \mapsto b,\quad g : b \mapsto b, \quad \text{and} \quad h : b \mapsto b\oplus 1.$$
The statistical distance between the distributions $g(X)$ and $h(X)$ is zero and thereby negligible.
\begin{align}&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\Pr_{b'\gets X}[g(b')=b] - \Pr_{b'\gets X}[h(b')=b]\right|\\
=&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\Pr_{b'\gets X}[b'=b] - \Pr_{b'\gets X}[b'\oplus 1=b]\right|\\
=&\frac{1}{2} \sum_{b\in \{0,1\}} \left|\frac{1}{2} - \frac{1}{2}\right| = 0
\end{align}
However, the support of the two distributions $$(f(X),g(X)) \in \{(0,0),(1,1)\}\quad \text{and} \quad (f(X),h(X)) \in \{(0,1),(1,0)\}$$ are completely disjoint and their statistical distance is thus $1$ which is non-negligible.


Should an AES byte key generated with OpenSSL be converted to hex? I am generating a key & iv with Ruby's OpenSSL wrapper for an AES CBC 256 setup:

cipher = OpenSSL::Cipher::Cipher.new('aes-256-cbc')
key = cipher.random_key
iv = cipher.random_iv

I am then storing the generated key / iv in blob columns in the database. When trying to display the key or iv it looks something similar to this:

×>×=ñ±8i·ÊahJ[  }öúÇ{xÎÝ¿

My question is:

should the key & iv which seem to be random bytes be converted to hex with an SHA function before using and storing into the DB?

Is it safer this way for storage / use or can they be used just as they are generated in byte form?

UPDATE:

Looks like I was mistaken on my terminology and use of SHA.

Revised question: Is a random byte key from OpenSSL just as random and secure if I convert it to hex via unpack('H*')

Any help is appreciated.

Thanks!

This is an answer to your revised question, although it doesn't seem to make any more sense:

Hex is just another way to represent your data. It is neither more nor less secure than the binary representation or any other representation. Its all about convenience when dealing with this numbers.

As humans we tend to operate with data encoded in the decimal system. Computers on the other hand operate with binary data. However, the problem with binary data is that it tends to get quite long and error prone when you as a human have to deal with it. It is much more easy for us to remember or copy 46 rather than 0b101110.

The hex representation is a a good compromise, because:

A single character encodes four bits, therefore making it shorter than the appropriate binary representation.
It is quite easy for humans to handle. Basically everyone is used to 0-9 and A-F.
Is is really easy to convert data from binary into hex and vice versa.
It can be represented in ASCII without any problems. Random binary data on the other hand looks like complete gibberish and gets messy because of different encodings and such.

Yet, at the end of the day it is all representing the same information.


Why is Multiplicative group used in RSA or Euler's theorem but not additive? I am on the verge to understanding RSA, but suddenly a question popped into mind. When we are calculating $U(N)$ i.e $U(PQ)$, we are taking invertible elements that are co-prime to $N$. For example, $U(5\times2)$ becomes $\{1,3,7,9\}$. We are ultimately never using the inverses in $U(N)$ in either key generation or encryption. But just the order of $U(N)$ is what we need. We are using invertible elements in the order of $U(N)$ as a part of key generation, And that part I understand why, but the never using the invertible elements within $U(N)$ itself. So thereby the question, Why we don't use additive groups? Is it a security thing?
PS, I don't know much about additive groups, just the multiplicative group as it's a part of RSA and I am studying RSA. Thanks :)

Why we don't use additive groups? Is it a security thing?

Yes, it's a security consideration. If we used the additive group $(\Bbb Z_N,+)$ rather than $(\Bbb Z_N^*,*)$  for RSA, public encryption would go $M\mapsto C=e\,M\bmod N$ rather than $M\mapsto C=M^e\bmod N$. Problem is, decryption would be trivial since anyone with the public key $(N,e)$ could compute $d=e^{-1}\bmod N$ (e.g. using the extended Euclidean algorithm) and then decrypt as $S\mapsto M=d\,S\bmod N$, without knowing the factorization of $N$.

This is related to the order of $(\Bbb Z_N,+)$ being $N$ part of the public key $(N,e)$, when the order of $(\Bbb Z_N^*,*)$ is $\Phi(N)$, which is not easily obtained from the public key.


How to assess the strength of the avalanche effect for AES? Within the scope of a study project I'm looking for an approach to assess the quality of AES encryption in practice. To do so, I modified the OpenSSL source code to be able to log metrics while encrypting thousands of blocks to obtain a representative result.

The first criteria for assessment is to check for the Avalanche criteria:

During (AES) encryption rounds I copy the current block to be encrypted (let's call it $I_o$), flip one bit (let's call it $I_c$) and encrypt it as well, so the same operation is applied (before roundkey is modified, shifting etc.).
This results in the blocks $C_o$ and $C_c$, which I check for their Hamming Distance ($\operatorname{HD}$).
AES seems to do a good job, for each byte the $\operatorname{HD}(C_o, C_c)$ is continuously ~ 4 bit.

At this point I'm struggling with two questions:

Does it matter WHICH bit I'm  flipping? Is it legit to always flip the MSB f.e. or should it be a random position?
The presence of the Avalanche effect implies for an attacker to have a 50/50 chance to predict the input ($I$) state of one bit for each round.
So the benefit of applying several rounds (in my case $b/k=128$ bit -> 10 rounds) is to reduce the probability for an attacker to predict a bit's original (plain) state to $0.5^{10}$?

Thanks for any inspiration! :)

Does it matter WHICH bit I'm flipping? Is it legit to always flip the MSB f.e. or should it be a random position?

If you see the cipher design as a black box then certainly yes. It could well be that the design would be more secure for certain positions than the other. This would indicate a (local) weakness.

Note that the Hamming distance is just one method of testing (pseudo) randomness.

  The presence of the Avalanche effect implies for an attacker to have a 50/50 chance to predict the input (I) state of one bit for each round. So the benefit of applying several rounds (in my case b/k=128 bit -> 10 rounds) is to reduce the probability for an attacker to predict a bit's original (plain) state to 0,5^10?

No. Each bit has two states. This means that one state is correct and one state is incorrect. If you can "predict" the state with a chance of 0.5 then you're perfectly secure.

Guessing a bit right with a chance lower than 0.5 actually doesn't make sense at all. It means you guess wrong with a high probability. In that case you just have to invert the bit to get a higher result (of $1 - P$ where $P$ is the probability).

The additional rounds are needed to protect against other attacks than simply performing black box testing. AES has been "broken" up to 7, 8 or 9 rounds for 128, 192 and 256 bits respectively.


one time pad regarding If I had two ciphertexts

$$c_1 = m_1 \oplus y_1 \text{ and } c_2 = m_2 \oplus y_2$$

will it be possible to obtain

$$z_1= (m_1 \lor m_2) \oplus y_1 \oplus y_2 \text{ and } z_2= (m_1 \land m_2) \oplus y_1 \oplus y_2$$

from $c_1$ and $c_2$ without revealing $m_1$, $m_2$, $y_1$ and $y_3$?

No, because then you could calculate $z_1 \oplus z_2 = (m_1 \land m_2) \oplus (m_1 \lor m_2) = m_1 \oplus m_2$.

In practice, you can only find $m_1 \oplus m_2$ if both $m_1$ and $m_2$ are encrypted with the same OTP (i.e., $(m_1 \oplus y_1) \oplus (m_2 \oplus y_1) = m_1 \oplus m_2$).

So without any knowledge of $m_1$, $m_2$, $y_1$ or $y_2$, there is no way of magically eliminating both of the OTP key streams $y_1$ and $y_2$.


Camellia Key Schedule Camellia is widely used, an international standard now. Its key schedule seems to be too simple compared to other famous ciphers like Twofish and CAST-256. What are the prerequisites for the key schedule, and does Camellia's key schedule have them?

This question and answer covers the requirements of a key schedule.

I could not find a simpler description of Camellia then this rfc

The following excerpt outlines the key schedule. Addressing only the 128 bit cipher for simplicity:

128-bit key K:
KL = K;    KR = 0;
...

  The 128-bit variables KA and KB are generated from KL and KR as
     follows.  Note that KB is used only if the length of the secret key
     is 192 or 256 bits.  D1 and D2 are 64-bit temporary variables.  F-
     function is described in Section 2.4.

   D1 = (KL ^ KR) >> 64;
   D2 = (KL ^ KR) & MASK64;
   D2 = D2 ^ F(D1, Sigma1);
   D1 = D1 ^ F(D2, Sigma2);
   D1 = D1 ^ (KL >> 64);
   D2 = D2 ^ (KL & MASK64);
   D2 = D2 ^ F(D1, Sigma3);
   D1 = D1 ^ F(D2, Sigma4);
   KA = (D1 << 64) | D2;
   ...

  The 64-bit constants Sigma1, Sigma2, ..., Sigma6 are used as "keys"
     in the F-function.  These constant values are, in hexadecimal
     notation, as follows.

Sigma1 = 0xA09E667F3BCC908B;
Sigma2 = 0xB67AE8584CAA73B2;
Sigma3 = 0xC6EF372FE94F82BE;
Sigma4 = 0x54FF53A5F1D36F1C;
Sigma5 = 0x10E527FADE682D1D;
Sigma6 = 0xB05688C2B3E6C1FD;

  64-bit subkeys are generated by rotating KL, KR, KA, and KB and
     taking the left- or right-half of them.

It appears the first part of the key schedule is a Feistel network as well: The right half is combine via XOR with F(left half, key), using a constant (SigmaN) for each of the keys. Then this process continues alternated, and some key additions are applied.

Actual round subkeys are generated via simple rotations of the result of the above. So recovery of one subkeys bits provides partial knowledge of the bits of other round subkeys.

This would appear to classify as a type "1B" key schedule, according to the classification system presented in this paper.

The strongest key schedule classification is "2B". For more details on the classification and what exactly it indicates, consult the paper linked at the top of this answer.


"Weak" implementation of AES-CTR? Assume an instantiation of AES-CTR like in the following picture:

Some details on the input-values for keystream generation:

COUNT: a 32-bit value associated with the transmission mode
IV#1: a 5-bit value that can be assumed constant for a specified transmission
IV#2: a 1-bit value indicating the direction of the transmission
incr: a 64-bit value initialized to 0 and then incremented per standard $\bmod 2^{64}$ increment function.
cipher key: refers to ciphering key which is obviously not known

Assume that all those input values are not difficult to identify/guess as they are required to establish correct transmission and synchronization between the two communicating parties (e.g., direction, radio info, etc). We also assume that no pairs of ciphering keys and input values ($COUNT||IV\#1||IV\#2||0^{26}||incr$) are used. Is this a weak AES-CTR implementation, assuming one can obtain pairs of keystreams/input-values?

I guess we can say this implementation is malleable as any AES-CTR without authentication steps. Any other weaknesses?

If the implementation ensures that no (COUNT, IV#1, IV#2) tuple can ever be used more than once, and if no tuple is ever used to generate more than 264+4 bytes of keystream output, then this scheme is as secure as any instantiation of AES-CTR can be.  Of course, as CTR is not an authenticated encryption mode, it will still be malleable unless combined with a MAC.

Conversely, if an attacker can cause two plaintexts to be encrypted with the same COUNT, IV#1 and IV#2 values, then they can easily obtain the bitwise XOR of the plaintexts, which may be sufficient to at least partially recover the plaintexts themselves.  In particular, if an attacker can cause a plaintext of their choosing (or at least known to them) to be encrypted with a chosen COUNT, IV#1 and IV#2, then they can fully decrypt any other plaintext (of equal or lower length) encrypted with those same values.

Your question does not contain enough information to let us tell which of these two scenarios applies, and so we cannot say whether this specific AES-CTR instantation is secure (in the usual IND-CPA sense one would expect of CTR mode) or not.

That said, the short length of IV#1 certainly raises some concern.  You have not described exactly what constitutes a single "transmission" in this protocol, but whatever it is, there can be only 32 of them in this scheme before you'd need to rekey (assuming that nothing prevents two transmissions from using the same COUNT values).  That seems like it might be a problem.


Does the timing of cycle-walking pose a threat? Cycle-walking is a technique for format-preserving encryption that involves repeating an encryption process until the result is inside a desired range.

For example, given an input P, a range R, and an encryption function E.

C := E(P)
Is C in R?
  yes?
    Output C and quit
  no?
    C := E(C)
    Try again

My question is, does the variable timing of this pose a threat? It isn't constant time, but the time is dependant on E(P), which in theory shouldn't be a problem.

Your intuition is correct: the timing channel in cycle walking does not affect the pseudorandom permutation (PRP) security of a format-preserving encryption scheme built using cycle walking.

More precisely, it is possible to prove that any FPE scheme which meets PRP security in the standard sense also meets a stronger notion of PRP security in which the time taken to encrypt a point is given to the adversary. Intuitively, this is because the distribution of cycle lengths for a random permutation can be simulated given only the size of the domain. See section 9 of the original FPE paper.


How do you implement a cipher as one lookup table? I am reading up on whitebox cryptography and have trouble understanding how are ciphers implemented as one lookup table?

Assuming my plaintext is just 4 bits so the size of my lookup table should be $2^4$, what does such a lookup table look like?

Specifically, this is the slide I am looking at, I found it on Google.

For a fixed key, a (block) cipher is a reversible transformation of a plaintext set to ciphertext set. Usually (and in the slide) these sets are identical, and consist of all the exactly $n$-bit strings. This set has $2^n$ elements, and is often noted $\{0,1\}^n$.
Note: in this notation $\{0,1\}$ designates the set with the two elements $0$ and $1$, and as usual raising a set to the $n$ means we are considering the set of all $n$-tuples with each element in the base set.

One possible implementation of a that transformation is a table $T$ of the cipher's output for each of its input. This table has one entry for each input, thus $2^n$ entries. Each entry is an $n$-bit string, thus uses $n$ bits. The table thus uses $2^n\cdot n$ bits.

To use the cipher defined by way of the table, one converts the $n$-bit input to an integer $j$ with $0\le j<2^n$, fetches the table at index $j$ that is $T[j]$, obtains an $n$-bit value, and that's the cipher's output.

Addition per comment: if the adversary possesses a box (of whatever color) implementing that transformation, we must assume the $n$-bit inputs and outputs, and their correspondence, are observed when the box is used. That might not be a total disaster if the adversary can't economically reproduce the box, and/or enumerating all input/outputs is impossible (e.g. requires too much time/energy, or exhausts a usage counter).


Malleability attacks against encryption without authentication Suppose there is a message that is encrypted with AES-128-CBC.  The message is as follows, new lines are used to delimit the 16 byte boundary for each block:

Wire funds from:
Alice to Bob in
 the amount of $
1

Because this message is encrypted using CBC mode,  any modification of the first block of cipher text would propagate throughout the message.   However, the amount of the fund transfer falls in the last block.  I am under the assumption that an attacker can use the property of Malleability to alter the last block and produce a valid amount that is greater than \$1 in far fewer than $2^{128}$ operations.

Is this a correct assumption?  Is there a name for this attack or do you know of a real world example?

My instinct is that if you just need one byte of the 16 byte block to be of a specific value then it would only require $2^8$ operations because the other 120 bits of the plain text could be any value. For example lets say we wanted the last block of cipher text to decrypt to 9\0 (where \0 denotes a single null byte, and the message would be interpreted as \$9), then it would take only $2^{16}$ operations to find this cipher text block.

Is there something I am missing?

First of all, you stated:

  Because this message is encrypted using CBC mode, any modification of
  the first block of cipher text would propagate throughout the message.

Actually, that's not true.  Here's the CBC mode operation in the decryption direction:

(Public domain image from Wikimedia Commons.)

If you examine the process closely, you will see that a specific plaintext block depends only on two ciphertext blocks (or a ciphertext block and the IV for the very first plaintext block).

So, if you modify a ciphertext block $N$ (say, flip one of the bits), then the resulting plaintext will have block $N$ garbled (because the modified block goes through the decryption, and unless we picked a ciphertext block which we already knew the decryption of, the result will be unpredictable).  In addition, block $N+1$ will have the corresponding bits modified (in our example, the same bit will be flipped).  And, there will be no other changes; all other plaintext blocks will be exactly what they were in the original message.

So, how can we use this observation?  Well, if block $N$ is the one we want to affect, and we don't mind if block $N-1$ decrypts to something unpredictable, the obvious approach is to modify block $N-1$ of the ciphertext.  If we guess that the real plaintext is $A$ (which corresponds to \$1), and we want it to read $B$ (which corresponds to (\$1000000), then we exclusive or $A \oplus B$ into ciphertext block $N-1$; this will cause the last ciphertext block to read exactly as we want it to.


Why should I use Authenticated Encryption instead of just encryption? There are various different modes of operation for block cipher use, some of which provide "encryption" and some of which provide authenticated encryption.

Why should I use an authenticated encryption mode rather than just an encryption mode?

This question does not aim to discuss different modes of authenticated encryption vrs encryption modes (although a good answer might choose to): its aim is to justify why/when AE is better than 'plain' encryption.

The crucial difference between plain encryption and authenticated encryption (AE) is that AE additionally provides authenticity, while plain encryption provides only confidentiality. Let's investigate in detail these two notions.
In the further text, we assume $K$ to be a secret key, which is known to authorized parties, but unknown to attackers.
Goals
Confidentiality (privacy) means that an attacker can not get any information about the plaintext $P$ from the ciphertext $E_K(P)$ except, possibly, for the length. In other words, the ciphertext looks like a random string for those who does not know $K$, even if they have some control over the plaintext. All the folklore encryption methods, from one-time pad to Enigma, provide confidentiality (under some assumptions) and only it.
Data authenticity (integrity) means that an authorized party (receiver), who possesses $K$, can check if the received data $D$ is genuine, i.e. it has been constructed only by a sender who knows $K$. The data can be cleartext or ciphertext, and there is a subtle difference what is authentic in each case: if the ciphertext is authenticated, then we know that the key owner authorized the ciphertext, but not necessarily plaintext. A traditional way to achieve authenticity is to use Message Authentication Code (MAC):
$$
H_K(D) = T,
$$
where $T$ is called tag.
In the world of public-key cryptography, the same goal is achieved with digital signatures.
What you need
A user is usually able to decide which of these properties he is looking for. For instance, if he knows that an attacker can not modify data, he may not need to authenticate it. However, if he needs both, there are secure as well as insecure ways to combine the schemes of two types. For example, a naive approach to use the same key $K$ in both schemes is dangerously insecure for most instantiations. Hence a combined scheme is recommended.
Authenticated encryption
Authenticated encryption (AE) provides confidentiality and data authenticity simultaneously. An AE scheme is usually more complicated than confidentiality-only or authenticity-only schemes. However, it is easier to use, because it usually needs only a single key, and is more robust, because there is less freedom for the user to do something wrong (see also a more elaborative answer).
As a separate feature, an authenticated encryption scheme may authenticate, but not encrypt, a part of its input, which is called associated data. For example, we may wish to encrypt the contents of an Internet packet, but we have to leave its header unencrypted but still bound to the internal data.
Security
We have not specified yet what we mean by a secure scheme. Apparently, there are several security notions, and the user has to choose among them according to the capabilities he expects from an adversary.
For confidentiality-only modes of operation the most popular security notion deals with chosen-plaintext attacks. Let $E$ be an encryption scheme. We assume that the adversary not only knows some plaintexts $P$, but is also able to choose some of them for the encryption (this is quite a practical situation). Hence, we allow the adversary to choose any plaintext for the encryption, and many times in a row. What we still require from a secure scheme is that it outputs randomly looking ciphertexts in each case:
$$
E_K(P_1),E_K(P_2),\ldots, E_K(P_n) \sim RandomString(|P_1|+|P_2|+\cdots+|P_n|)
$$
The adversary can not distinguish the whole set of ciphertexts he obtains from an output of true random bit generator of the same length, even if the adversary repeats his plaintexts. The latter requirement implies that the scheme must be non-deterministic, and indeed, the confidentiality-only modes that satisfy these requirements are either probabilistic or nonce-based.
I note that there are folklore security notions that relate the security of the scheme with the ability to recover the key $K$ itself. This was relevant when the key could be used elsewhere, but this is far less common now, and the security notion described above is prevalent.
The security of authenticity modes is defined in a different way. Let $H_K$ be such scheme with the secret key $K$. We require that if the adversary chooses any data $D$ that has not been authenticated yet, then his chances to guess tag $T$ such that
$$
H_K(D) = T
$$
are negligible. If he submits the pair $(D,T)$ to a verifier, he will get the answer $\perp$ (error).
Note that we have not talked about chosen-ciphertext attacks on confidentiality-only modes. These are attacks when the adversary is also able to send his own ciphertexts for decryption. While this setting also appears in practice (even though less often than chosen-plaintext attacks), the confidentiality-only schemes can not resist such attacks. To establish this sort of security, the user must turn again to the authenticated encryption.
Security of authenticated encryption schemes is defined in two parts. First, similarly to confidentiality-only modes, the adversary must be unable to distinguish the ciphertexts from random strings. Secondly, whatever fake (not created on $K$) ciphertext she sends for decryption, she is likely to get $\perp$ in response.
Therefore, the authenticated encryption modes provides you also security against chosen-ciphertext attacks if it is needed.
How it works
There are numerous integrated authenticated encryption schemes: CCM, GCM, OCB, EAX, etc, where mechanisms that establish confidentiality and authenticity are tightly coupled. The design of these schemes is far beyond the topic. However, there is a simple composed scheme, well-known as Encrypt-then-MAC, that works as follows. Let $K_1,K_2$ be secret keys, $P$ be the plaintext, $E$ be some encryption mode, and $H$ be some MAC. Then the scheme
$$
\Pi_{K_1,K_2}: M\rightarrow E_{K_1}(M) ||  H_{K_2}(E_{K_1}(M))
$$
is a secure authenticated encryption scheme if $E$ is a secure confidentiality mode and $H$ is a secure authenticity mode.
Additional features of authenticated encryption schemes
Besides providing both confidentiality and authenticity, authenticated encryption schemes may have a number of additional features. No scheme has them all, hence the best choice is determined by user's settings.

Security level. A scheme guarantees confidentiality and data authenticity only up to some bound on the amount of encrypted data or decryption requests. This bound is typically much lower than the key space, and for AES-based modes does not usually exceed $2^{64}$.

Parallelism If a lot of resources are available, one may desire to run the encryption, decryption, or verification in parallel. The modes that use  chaining (like the ones derived from the CBC encryption or the sponge construction) are difficult to parallelize.

Online encryption. We say that a scheme is online, if it allows to encrypt immediately when the data is available, without the knowledge of its length.

Use of patents. One of the most interesting AE schemes, the OCB mode, is patented, and is less frequently used and analyzed because of this property. It is often desirable that the scheme is patent-free.

Tag update. Most of the schemes, with a few exceptions like GCM, require to recompute almost entire ciphertext if a small portion of plaintext is modified. If the ciphertext can be updated quickly, it would allow much faster processing of large amounts of encrypted data, e.g., hard-drive encryption.

Use of nonces or random IVs. Nonces and random IVs lead to distinct security models, which are often incompatible (schemes might be secure with nonces, but not with random IVs of the same length, or vice versa). While the nonce uniqueness might be harder to ensure, the random IVs need a separate random-number generation mechanism and leads to the ciphertext expansion.

Variable key, nonce, or tag length. All the three parameters are usually restricted by the application that uses an AE scheme. In turn, AE schemes  have their own, sometimes incompatible restrictions. The more variability the scheme has, the more applications it suits.

Processing of associated data. All the modern schemes allow for the authentication of associated data, which is not encrypted. Some of them, however, can not preprocess AD before the plaintext is over, which might be a penalty on the performance.

Additional reading
The technical report by Rogaway is a comprehensive survey of confidentiality-only modes, MACs, and some authenticated-encryption modes. It also contains all formal details about security notions.


Security of traditional ORAMs if write accesses are revealed I was reading about path ORAM, and I have few questions

I was wondering if an adversary knows all write accesses will be performed and has a view of the tree of which path being accessed. Can he infer anything about the system?

The adversary will not be able to distinguish between that access pattern and any other with the same volume and timing.


Proof of Disclosure? Is there such a thing? Let's say I have a document. I want to give you a copy, and then I want to prove that I gave you a copy. Ie, I want some kind of digitally signed receipt from you. If you're dishonest, you may receive the document and then refuse to give me a receipt. I would like some sort of cryptographic protocol that provides some sort of "simultaneous swap" - I give you a document, you give me the receipt. Does anything like this exist?

PS. I'm happy to do the research myself, but I have no idea what terms to google for. "Proof of disclosure" definitely isn't the right search term.

You could probably achieve this with a distributed ledger (e.g. a blockchain). If you were to have an image taken of your document recipient holding the document, otherwise you would take the document back immediately or nullifying its effect (e.g. revoke a digital signature on the document that would've been useful for the recipient), and hash that image, and place that onto said ledger, you would have proof that you disclosed information to the recipient. The importance is that due to distribution, the record is redundant, immutable, and most importantly, irrefutable. This method could also be used as a proof of chronology.

One example of this is Bitcoinproof, a method of hashing image data into a Bitcoin address, and sending either a small transaction or no bitcoins to that address. By doing so, the transaction can be mined into a block, becoming a permanent record that can be verified using an image.

Finding the image hash as a Bitcoin address (SHA-256, RIPEMD-160, and base58check), which will have likely only 1 transaction to it, with a timestamp that cannot change, i.e. a proof of chronology. This can also be used as a proof of disclosure, as you mentioned.

That is, unless you're exceptionally good at Photoshopping an image of your recipient into holding your document.

And it might fail, if you lose the photo, or if the network becomes less popular.

Also, this wouldn't be good for private information. You would be using a public ledger, so in the event the receiver disputes your claim, you would have to reveal the information to the public in order to prove this. This means that the document is only good for gaining one time access to a system, through a digital signature.


Can ECB mode really leak some characters? In an Ars Technica article about Adobe's use of 3DES in ECB mode, there's a paragraph

  The passwords, according to password expert Steve "Sc00bz" Thomas, are encrypted in a mode known as ECB. That was a poor choice on
      the part of Adobe engineers, because ECB often leaks information about the passwords, such as their last few characters and some of
      their lengths. In certain cases, for example, passwords that end in e will generate an encrypted string that ends in
      n2auThm2+Q==; those that are nine or 17 characters long will sometimes end in mfZq5OGbb5.

Is it really the case?

The article mentions that 3-DES was used to encrypt these passwords in ECB mode. DES has a 64-bit/8-byte block.

So let's say you use ECB to encrypt a nine byte password. The first 8-bytes are encrypted using ECB. So far so good.

But what happens when we come to the ninth byte? Well we're now in a new block but only the first byte is populated with any data. The rest are zeros (assuming no padding is used).

This means that there are only 256 possible encryptions of the second block for all nine byte passwords. With a large enough database, it will be relatively easy to guess what these encryptions are. If you had a dictionary of common nine character passwords, a mere frequency analysis of the last character of the password and a comparison to the frequency of the second ECB blocks would be enough!

So yes, the paragraph is correct. It's a significant hole in the scheme they used.


Question about HMAC with SHA1 I would like to make sure I understood HMAC. Wikipedia declares it like:

$$\operatorname{HMAC}(K,m)=H((K\oplus\text{opad})||H((K\oplus\text{ipad})||m))$$

If I want to use HMAC-SHA1, am I correct to say that:

Let's say I take key length of 16 bytes. Does it mean that according to Wikipedia I must pad the key with zeros from right up to 512 bits? (block length of SHA1)
$\text{opad}$ must be a 512 bit value, like: 0x5c...5c (512 bits)?
$\text{ipad}$ similarly: 0x36...36 (512 bits long)?
What to do with $m$ if its length is not 512 bits?
What is the recommended length of actual key and what is the recommended way to generate it?
Is it bad idea to implement HMAC myself, if I have implementation of SHA1?

let's say I take key length of 16 bytes. Does it mean that according to wiki I must pad the key with zeros from right up to 512 bits? (block length of SHA1)

Yes.

  opad must be a 512 bit value, like: 0x5c5c5c…5c5c....5c (512 bits)?

Yes.

  ipad similarly: 0x363636…3636 (512 bits long)

Yes.

  what to do with m if its length is not 512 bits?

This should not be relevant for the HMAC implementation itself, since the hash function is the cryptographic primitive responsible for effectively processing the message (of arbitrary length).

  what is the recommended length of actual key? and recommendation for key generation?

Before using it, HMAC will pad the provided key material with 0's until it reaches the block size. The size (and the quality!) of this key material depends on how much security your implementation is targeting. Note that RFC2104 "strongly discourages" the usage of keys of shorter length than the hash output (see comment from otus), which for SHA-1 would be 160 bits. As SEJPM mentioned in his comment to the question, the key can be either generated at random or pre-shared/derived from a common secret (see Diffie-Hellman).

  is it bad idea to implement HMAC myself, if I have implementation of SHA1?

It might be a good exercise if you want to get familiar with cryptography implementation details. However if you need an HMAC implementation in the scope of a project for example, you may prefer to use an extensively tested and validated implementation (e.g., open source cryptography libraries).


Private and Public Keys I have a very basic understanding of encryption and the encapsulation process, but for the life of me I can't grasp how public keys and private keys work, how they're made, and how they're exchanged. Can anyone break it down to a basic level, or point me in the direction of material that explains it Barney style. Thanks in advance.

How they work

Public and private keys work as follows. Every party who wants to communicate with others generates a private key which they keep secret. From that private key, they derive a public key, which they publish for anyone to see.

For example, if we have three agents, Alice, Bob, and Charlie, they will all have a secret key S_A, S_B, and S_C and a public key each, P_A, P_B, and P_C.

If Alice wishes to encrypt a message to Bob, she uses Bob's public key for encrypting the message. To decrypt the message encrypted with his public key, Bob must use his respective secret key.

How they are made

You don't need to understand how public and private keys are made to understand how to use public-key cryptography. It is only necessary to understand the following basic concept: While there is a one-to-one correspondence between a public and a secret key, it is computationally easy to go from the private key to the public key, while it is computationally hard to go from the public key to the private key.

Such problems form the basis of asymmetric cryptography and are abundant in computer science. For example, the factoring problem has this asymmetry. If I give you two prime numbers p and q (the private key), you can readily evaluate their product n = pq (the public key). However, if I give you the public key and I tell you it's the product of two large primes, it is hard for you to find these two primes even though there's only one unique solution. The factoring problem is in fact used in the RSA cryptosystem. Other problems that have this asymmetric property are problems on lattices and the discrete logarithm problem in finite groups.

How they are exchanged

Exchanging public keys is easy. Public keys can simply be published, as they are not secret. For example, they can be published on a newspaper, spoken over the phone, sent on an email, or uploaded to public key servers.

How does asymmetric encryption work?

This is a more complicated question that you don't need to understand to move on and use public-key cryptography. The math is somewhat convoluted. It is also specific to various cryptosystems. The easiest to understand is the RSA cryptosystem. To understand it, you need to study some basic algorithms and facts such as the Fundamental theorem of arithmetic, the Extended Euclidean Algorithm, the Miller-Rabin primality test, Fermat's Little Theorem and its extension Euler's theorem. Following this knowledge, Wikipedia's explanation of RSA can be understood without much effort.


What does it mean : "Canonical representative of Sbox is 0123468A5BCF79DE"? and How can we calculate this representative for Sbox? In paper :Cryptographic Analysis of All 4 × 4-Bit S-Boxes Saarinen has classified $4 \times 4$ S-Boxes and defined Canonical representative for each class of S-Boxes.

What does "Canonical representative of S-Box is 0123468A5BCF79DE" mean? And,
How can I calculate it for an individual S-Box?

Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set $\{0,1\}^4$ of 4-bit bitstrings.  These bitstrings can be viewed as the binary representations of the integers from $0$ to $15$, which in turn are naturally represented by hexadecimal digits.  Thus, we can also regard a 4×4 bit S-box as a permutation of the hexadecimal digits 0123456789ABCDEF.

A common compact way of representing a permutation of a finite naturally ordered set (such as the hex digits listed above) is to list the results of applying the permutation to each element of the set in order.  Thus, for example, the string 0123468A5BCF79DE represents the permutation:

0123456789ABCDEF
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
0123468A5BCF79DE

(See e.g. this answer for examples.)  While the article you've linked does not seem to actually define this notation, I'm all but certain that this is what they mean.

The story doesn't end here, though.  The article you've linked does not discuss individual S-boxes, but equivalence classes of them.  One type of equivalence is defined at the beginning of section 3 (formatting original, [editorial notes] mine):

  Definition 5. Let $M_i$ and $M_o$ be two [4×4] invertible matrices and $c_i$ and $c_o$ two [4-element] vectors [over $\mathbb F_2$]. The S-Box $S'$ defined by two affine transformations $$S'(x) = M_oS(M_i(x ⊕ c_i)) ⊕ c_o$$ belongs to the linear equivalence set of $S$; $S' ∈ \mathrm{LE}(S)$.

Later, in definition 7, the author also defines a narrower notion of equivalence of S-boxes, called "permutation equivalence" (PE), which is the same as the linear equivalence defined above, except that the 4×4 binary matrices $M_i$ and $M_o$ are further required to be permutation matrices.  (Note that these matrices represent permutations of the four bits in a 4-bit input/output bitstring, not permutations of the entire set of such 4-bit strings!)

The reason for considering these equivalence classes of S-boxes, instead of each S-box individually, is of course that any two S-boxes that only differ by a permutation of their input or output bits (and/or XORing those inputs and outputs with some constant bitstrings) have essentially the same cryptographic strength against attacks that don't care about such details, such as all those considered in the paper.

Anyway, to be able to usefully discuss these equivalence classes of S-boxes, we need to have some way to name them.  One obvious way to do that, which the author of the paper indeed uses, is to somehow pick one specific "canonical" S-box out of each equivalence class to represent it.  But which one?  The author describes their choice in definition 6:

  Definition 6. The canonical representative of an equivalence class [of S-boxes] is the member [whose compact representation as a list of hex digits] is first in lexicographic ordering.

For example, the S-boxes 0123468A5BCF79DE and 5BCF79DE0123468A are permutation equivalent as defined in the paper, since one can be obtained from the other by XORing the input with the 4-bit vector $1000$ (8 in hex) before applying the S-box.  But the string 0123468A5BCF79DE sorts before 5BCF79DE0123468A in lexicographic order (since 0 < 5), and indeed (assuming the author made no silly mistake) also before all other members of its equivalence class, making it the canonical representative of that class.

As for how to calculate the canonical representative of a particular equivalence class of S-boxes, given one member of the class, I believe the simplest (and possibly the only) way to do that is by brute force: just apply all possible input and output bit permutations (or invertible bit matrices, for linear equivalence) $M_i$ and $M_o$ and XOR masks $c_i$ and $c_o$ to the S-box to generate all members of the equivalence class, calculate the hex digit string representation of each of them, and find the one that comes first in lexicographic order.


RSA-KEM construction "Create a random key for CCPA2 scheme, encrypt m, send it along with a
  PK encryption of the symmetric key. "

Say in the process, the KDF is HMAC, then:

get a random key (128-bit)
C1 = encrypt the message "Hello World" using AES
C2 = is a tuple of E_pk(random_key), and HMAC(random_key, random_key2)

then send C1 || C2?

I have a feeling this is the wrong interpretation. Somewhere doesn't smell right. Or is this good enough?

What you are proposing is bad.

RSA-KEM uses RSA encryption without padding, but not in the way you are proposing. See the second part of its Wikipedia Page

The problem with your construction is that if you encrypt a short message (i.e. AES key) with RSA without padding, then it might get decrypted through e-rooth calculation or through Coppersmith.
It actually depends on the message size and on your public key, for example if your public key is $e=3$ then you just need to compute $(E_{pk}(random\_key))^{(1/3)}$ to get the decrypted text.

In order to properly use RSA-KEM you first need to generate a random message $m: 1 < m < N$

Then derive your AES from it: $key=KDF(m)$

And finally encrypt your message with $key$ and send it along $E_{pk}(m)$.

Note that there are variants:

You can derive, with the same KDF call another key, used to MAC your (encrypted) message.
Or as specified in RFC 5990 with the KDF you generate a KEK (Key Encryption Key) which is then used to wrap the actual AES key used for the message encryption. This has the benefit to allow KEM to be used with an already encrypted message.


Is it safe to use the same key for different variants of the HMAC-SHA algorithm? I need to apply HMAC-SHA hashes in my application. Depending on the context I'll use either HMAC-SHA512, HMAC-SHA256 or HMAC-SHA1.

Is it safe to use the same key for all of these algorithms, or do I need to use a different key for each hash type? I plan to make the key 128 bytes which I understand is long enough for all of them.

So, the answer to your question is that while it is recommended that you never reuse keys for different algorithms, it is quite unlikely that different hashes in HMAC would interact badly.

However, that does not mean what you are planning is the way to go. It makes little sense to change the strength of the authentication based on the length of the message, unless the message length directly correlates with the security level you expect. And even if that is something you want, there is no real advantage to using different HMAC hashes.

Instead, you should pick either SHA-256 or SHA-512 and use only that hash for HMAC. You can truncate the authentication tag to the desired length, which can vary with message length. However, you must make sure an attacker cannot simply use a shorter tag in all situations. And it is not really required, since even a 64-bit tag is usually considered sufficient. So you should likely just pick one length you are comfortable with.

Oh, and a 128-byte key is overkill. 256 bits is sufficient.


Is the security of MAC function is based on HASH function It is widely known, generally, that a MAC is a HASH with key. I just want to ensure that my understanding is correct to avoid base further assumptions on wrong conception. So, if I used MAC that uses strong key but weak HASH such as MD-5. Does this means my MAC does not provide security and can be forged?

It is widely known, generally, that a MAC is a HASH with key.

Nope; there are plenty of perfectly good MACs that, if you know the key, aren't very good hashes at all.  Examples of this would include CMAC and GMAC; in both cases, if you know the key, it's easy to generate an image that MACs to a specific value.

However, lets assume that you're talking about HMAC specifically (which is a specific type of MAC based on a hash function).

  So, if I used MAC that uses strong key but weak HASH such as MD5. Does this means my MAC does not provide security and can be forged?

Depends on how weak the MAC is.  With MD5, we can easily generate collisions (that is, pairs of images that hash to the same value), however that's not useful in attacking HMAC-MD5 (assuming the attacker doesn't know the key; if he does, he can use that knowledge to create two values that HMAC-MD5 to the same tag).  In fact, there's no known attack against HMAC-MD5 that's more effective than "brute force search of the key".

Please don't use this advice as an excuse to use HMAC-MD5, however.

On the other hand, a sufficiently weak hash (e.g. MD4) does give you a weak HMAC; and so the answer to your question is "yes, a weak hash can give you a weak HMAC"; the hash just has to be weaker than what we know MD5 to be...


Is the 'Padding Oracle attack' deterministic? I'm thinking about the example of Padding Oracle attack in CBC mode with PKCS7 padding given in Wikipedia.

It says about the guess of the last byte in the plain text:

  In the worst case, they need to make 255 attempts to find the right
  value of z_1 (one guess for every possible byte).

But what will happen if the last but one byte of P2 happens to be 0x02. In this case it is obvious that we may have two possible values of z_1 which will result in correct padding: the first one will cause the last byte to be equal to 0x01 (valid padding) and the second one will cause the last byte to be equal to 0x02 (again a valid padding).

So is it guaranteed that the attacker will decrypt the message. Or the attacker may decrypt the message with high probability?

EDIT: How the attacker may distinguish between these sample plain text blocks (PT2) with different length of the padding:

... ... ... 68 02 02
... ... ... 68 02 01

The first plain text is with length 14 and 2 bytes padding.
The second plain text is with length 15, last byte but one is 2 and padding 1.

Another edit:

By following the advice in the accepted answer I managed to quickly build an app which demonstrates a successful padding oracle attack. Available here.

These should both be valid paddings:

... ... ... 68 02 02
... ... ... 68 02 01

But if this ambiguity comes up, we can distinguish between the two by  modifying the second-to-last byte in some way. After flipping, say, the highest four bits:

... ... ... 68 f2 02
... ... ... 68 f2 01

Only the second one is a valid padding.


A query on Learning with errors(LWE) problem In generating an LWE sample, we do

$s\xleftarrow{$}\mathbb{Z}_q^{n}, A \xleftarrow{$}\mathbb{Z}_q^{n \times m}~$and  $e\xleftarrow{$}\mathbb{{\chi}^{m}}$

Then we compute $b^T$ = $s^TA$ + $e^T$ and the sample $(A,b)$ $\approx$ truly random sample.

Now suppose we have a fixed matrix (not random and public) $A \in\mathbb{Z}_q^{n \times m}$. We choose $R\xleftarrow{$}\mathbb{Z}_q^{n \times m}$ and compute $A' = A + R$ and the generate the LWE sample as $(A',b')$.

Will the LWE assumption still hold? If it doesn't hold, then is there a way to mask matrix $A$?

It is easy to reduce this problem to LWE, since adding any element to a uniformly random value gives a uniformly random distribution.

For example, here, $(A',b')$ is distributed the same as if $A'$ was drawn uniformly randomly, and $R$ set as $A'-A$. You're now in the setting of the LWE assumption and can replace $b'$ by a uniformly random value without anybody (PPT) noticing it. With more details:

$$R\gets\mathbb{Z}_q^{n\times m}, A' := A + R, b'^t := s^t A'+ e^t, e\gets \chi^m,$$

is distributed identically to:

$$A'\gets\mathbb{Z}_q^{n\times m}, R := A' - A, b'^t := s^t A' + e^t, e\gets \chi^m,$$

which is computationally indistinguishable from:

$$A'\gets\mathbb{Z}_q^{n\times m}, R := A' - A, b' \gets \mathbb{Z}_q^{m}.$$

You can then switch back to normal generation of $A'$: the previous distribution is identical to:

$$R\gets\mathbb{Z}_q^{n\times m}, A' := A + R, b' \gets \mathbb{Z}_q^{m}.$$

Edit: added more details to clarify the answer.


How can a client privately query a subset of a database? I am trying to build a solution for the following problem and I think it is relevant to crypto:

Party A has a set of indexes M, such as a group of people's ID; Party B has information of a larger group of people, and we name the set of this group as N. Let's assume M is a subset of N. Party B agrees to provide information of people whoever requested by A for a business purpose. Although party A wants to have all the information of M from B, it does not want to reveal any ID in M to Party B during the process.

Does anyone know if this is possible?

Thanks.

You're looking for PIR, Private Information Retrieval or OT, Oblivious Transfer and possibly also PSI, Private Set Intersection.

PIR enables a client to query a server for the $i$-th entry of a database without the server learning the query. However, the client may learn values for other indices too.

OT is a stronger PIR without this leak.

PSI enables a client to find the intersection of their secret set and the server's secret set. You might want to do PSI before PIR to filter out non-members before trying to look them up, to reduce communication costs. Possibly of interest RePSI, Reactive PSI reduces the ability for a malicious client to enumerate the server's set.

A much weaker alternative may be of interest too. If the database is large, but reasonably partitioned and the client is willing to reveal which region they are querying, then you can use k-anonymity.

Ex. Have I Been Pwned's password lookup works by taking the first 5 hex characters of the hash of your password to identify the partition of the large password hash database. Then, you filter the smaller but still large partition down to your exact hash/key and read its value.

Although the server does not learn the user's password, related queries can uniquely identify the user if they have multiple compromised passwords tied to a common username or email address. I.e. There may be only one user whose two password hashes start with "12345" and "abcde".

If the client searches for the information on "Bobby Smith" and "Carol Smith" and these two people exist in separate partitions, then the server may link the two queries to recover your query. Even if all queries are independent without any relation, k-anonymity still reveals the tiny subset of the large database, the client is interested in.


Using High Level Probability Theory (eg Markov Chain Mixing) in Cryptography/Cryptanalysis I'm currently doing a PhD in probability theory, specifically (discrete space) Markov chains and their mixing properties. As well as my current main project, I'm looking to have a side project, eg to work on if I want a (temporary) change from my main project. What I'm doing is fairly applied in the sense that we have certain graphs and we're looking at mixing on them; it's fully rigorous though.

While it's not hugely related to Markov mixing, I'm also very interested in cryptography/cryptanalysis. I expect cryptanalysis is more related to my kind of probability theory, but I could be wrong. I'd like to be able to apply similar principles of my main project (Markov chains, in particular mixing) to this.

I'm interested in using high level probability theory. By this, I don't mean only having to know about discrete distrubutions and conditional probabilities, but more -- for example, material in the Aldous/Fill book. By this I mean that it would be a probability project on (/applied to) cryptography/cryptanalysis.

In a related field, I'd also be interested in similar applications to coding theory, eg codes that error-correct with high probability. I know coding theory is based on basic probability, but again I'd be looking for more than just having to know some basic rules.

After some searching it doesn't appear that anything like this has been done. It might be a nice opportunity to do develop some new tools. After all, Tim Gowers got his field medal for combining combinatorics and functional analysis. Not suggesting I'm on Tim Gowers' level, of course! Bollobas successfully used probabilistic methods to show lots of stuff about graphs (again, no claim to be on his level!). This could include things such as developing algorithms via Markov chains and proving fast (polynomial) mixing. I'd be happy to learn new things -- maybe some machine learning techniques would be helpful? -- in order to do this. But I would like it to be probability at heart.

Now, it might be that there isn't literature on this topic because the tools I want to use just aren't applicable in this situation, or it might just be that people haven't done it it. People have different interests, and maybe this is a less common crossover. Let's hope for the latter!

So I'm wondering if anyone has experience of, or knows about, any such questions or areas of research? I've looked at various literature, but maybe someone of a more cryptographical/cryptanalytical background would know of some such problems.

I'd certainly appreciate any comments. This is a cross-post from Maths Overflow (see here).

Note the highly related question "Current mathematics theory used in cryptography/coding theory". In this, however, there is no mention of probabilistic tools being used there; it's mostly number theoretic or algebraic. Note that there is the tag "probabilistic encryption".

I think you're being too dismissive and thinking of this as a "side project".

The challenge is representing the action of the cryptographic mappings such as the key schedule and the round functions which result in a pseudorandom permutation that can only sample a vanishingly small subset (a fraction $$\frac{2^k}{(2^n)!}$$ for keylength $k$ block length $n$, which are usually the same, but not necessarily) of all permutations in $S_{2^n}$.

The key is random, but the subkeys are not, they are directly derived from the key, so you have $k$ bit maximum key entropy used typically for $kr$ total subkeys bits.

More importantly, you need a worst-case approach while to my understanding the mixing time convergence to uniform is more of an average case criterion.

Are you aware of work by Lai-Massey-Murphy, Luby Rackoff. You can start by tracking the references to those.

And poly time mixing may tell you hundreds of rounds are enough on average but you'll want to use sublinear number of rounds.

This answer focused on block ciphers alone.


How is ElGamal not secure under chosen ciphertext attack, but semantically secure in some cases? I know that you can create a ciphertext c' using c and then find the corresponding m' for c' which you can use to find m for c. So, doesn't this mean that it is not semantically secure? But I also read that it is semantically secure when it meets the DDH assumption. Is there some terminology I'm misunderstanding because that seems contradictory to me.

Finding the corresponding $m'$ using $c'$ is a chosen cipher text attack. It's possible for a scheme to be semantically secure under certain types of attacks (perhaps something weaker like chosen-plaintext attack), but be broken under heavier attacks (like the chosen ciphertext attack you talk about).


Why doesn't this replay attack work on ECDSA? I've just started working with elliptic curves and ECSDA in particular, so my understanding of the underlying math isn't great.  The thing I'm currently stuck on is trying to understand why replay attacks don't work on ECSDA.

For this scenario, the public key, $Q = x \centerdot G$, where $x$ is the private key and $G$ is the generator of size $n$.  Additionally, $H(m)$ is the hash of message $m$ and $k$ is a random number in $[1,n-1]$.  The signature $(r,s)$ would then be defined as

$\begin{eqnarray*}
r &=& (kG)_x \mod n\\
s &=& k^{-1}(H(m) + rx) \mod \ n
\end{eqnarray*}$

Now, in this hypothetical attack, the attacker sees $(r,s)$ along with message $m_1$ and wants to send message $m_2$ on the next transmission via replay attack.  If my math is correct, and it most assuredly isn't, he could achieve this by keeping the original $r$ and deriving the following:

($mod\ n$ omitted for tidiness)

$\begin{eqnarray}
s_1 &=& k^{-1}(H(m_1) + rx)\\
 &=& k^{-1}(H(m_1)) + xk^{-1}(kG)_x\\
 &=& k^{-1}(H(m_1)) + (xG)_x\\
 &=& k^{-1}(H(m_1)) + Q_x\\
k^{-1}(H(m_1)) &=& s_1 - Q_x\\
...\\
s_2 &=& k^{-1}(H(m_2)) + Q_x\\
s_2 &=& (k^{-1}H(m_2))(H(m_1)H(m_1)^{-1}) + Q_x\\
s_2 &=& (k^{-1}H(m_1))(H(m_2)H(m_1)^{-1}) + Q_x\\
s_2 &=& (s_1 - Q_x)(H(m_2)H(m_1)^{-1}) + Q_x
\end{eqnarray}$

$(r, s2)$ is now a valid signature for $m_2$.  But that's way too easy to be realistic, so where's the error?  The only thing I can think of is if $xk^{-1}(kG)_x \neq (xG)_x$, but it seems like it would need to for the authentication steps to cancel correctly.

If this were a valid attack, then the receiver would need to counter it by logging $r$ to ensure that it's never reused, and I've never heard anyone suggesting doing that.

You got tripped up by the fact that there are two different group operations in play here, and they don't play nice with each other.  This is implicit in the notation, and it's easy to get tripped up, because the notation expresses both operations in the same way -- but they are not the same.  This is arguably a pitfall in the notation: the assumption is that the reader will be careful to keep track of which operation is which and not get tripped up, but as you have seen, it is easy to lose track and be led astray.

When we write $kG$, we are referring to a group operation in the elliptic curve.  $kG$ is short-hand for $G+G+G+\dots +G$, where here $+$ represents the elliptic curve point-addition operation (it takes two points on the curve and "adds" them, returning another point on the curve).

When we write $rx$, we are referring to a group addition for the integers modulo $n$.  It is short-hand for multiplying the two integers $r$ and $x$ and reducing the result modulo $n$.  Note that this operation acts, not on two elliptic curve points, but rather on two integers modulo $n$.  It is a totally different operation.

With that understanding, here's where you went wrong.  You wanted to write something like $k^{-1} r = k^{-1} (kG) = (k^{-1} k)G=G$.  However, that derivation is simply wrong, because it mixes up the two different kind of operations.  $kG$ is an elliptic curve operation, so the result is a point.  Actually, $r$ is not $kG$; it is an integer given by the x-coordinate of $kG$.  This is essential, because when we write $k^{-1} r$ (or $k^{-1} (kG)_x$), we are multiplying two integers using the group operation for integers -- not the elliptic curve group operation.

Even if you adjusted the derivation to $k^{-1} r = k^{-1} (kG)_x = (k^{-1} k)G=G$, it would still be wrong, because of the difference between the elliptic curve point $H$ and its x-coordinate $H_x$; the former is a point on the curve, while the latter is an integer.  Different addition/multiplication operations apply to these two different kind of mathematical objects, and they don't cancel each other out.

In fact, in some sense the security of ECDSA relies upon the fact that these two different kinds of operations don't cancel each other and don't play nice with each other.  So buried in your question is an insight about elliptic curve cryptography that is pretty fundamental to the whole concept.


Which risks are associated with deriving multiple keys from the same DH secret Z? NIST recommends Krawczyk's HMAC-based key derivation function (HKDF) in SP-800-56C (PDF). HKDF shall e.g. be used to create keys from shared secrets after Diffie Hellman key establishment.

NIST states in the same doc:

  Each call to the randomness extraction step requires a
  freshly computed shared secret $Z$, and this shared secret
  shall be zeroized immediately following its use in the
  extraction process.

Why is it not recommended to derive multiple keys from the same $Z$, e.g. why not derive a key for data encryption and a key for authentication from the same $Z$ using different info strings? If I still do it, what weaknesses might the derived keys be facing? Is it simply bad practice (without deep explanation) to do so since the derived keys obviously are related? Krawczyk seems to think that multiple derivations from the secret are expected use (see section 3.2 in RFC 5869, my interpretation).

Does salting the HKDF with a good random salt change my risks when deriving multiple keys from a single $Z$?

It depends on how you use HKDF to derive multiple keys.

Background: HKDF consists of two stages: first HKDF-Extract computes an intermediate value from the randomness source; then HKDF-Expand can be used to generate one or more session keys from the intermediate value.

The right way is to use HKDF-Extract once, and then call HKDF-Expand multiple times, with multiple different info strings.  In other words, to derive two session keys, you'd call HKDF-Extract once and HKDF-Expand twice.  If you do that, then this is a perfectly good practice -- it is exactly what HKDF was designed for.

The wrong way is to call the entire HKDF process twice, with two different salts.  Some implementations of HKDF might not separate out the two stages, and just combine them; if you used that, and performed the entire process twice (using HKDF-Extract twice and HKDF-Expand twice), then this is not the intended way to use HKDF.

Everything is fine if you use the "right" way, so for the rest of this question I assume you were asking about the "wrong" way.  There are two answers about whether this is a good idea: the "engineering" answer, and the "principled" answer.

The engineering answer is that, in practice, if you generate two keys using two different info strings, I suspect you'd probably get away with it without problems.  If we model the hash as a random oracle (admittedly a very strong "assumption"), then I suspect it might be possible to demonstrate that what you propose is OK.  Disclaimers: I haven't analyzed this, and I'm certainly not going to give you any guarantees -- if you do what you propose, cryptographers will wag their finger and say "tsk, tsk", and rightly so.  I suspect you'd probably get away with it (it's not the worst sin you could make), but if something does go wrong, cryptographers aren't going to take the blame -- it's all on you.

The more principled answer is that if you do what you propose, you are misusing the HKDF primitive.  The HKDF is only intended to be applied to a single $Z$ once.  It is intended to turn an unguessable value into something that looks uniformly random.  It has been analyzed for that use.  It was not designed to derive multiple keys from the same $Z$: it hasn't been analyzed for that kind of use case, since that's not what it was designed for.  So, you're throwing away the benefits you could get from the public analysis of HKDF if you use it in a way that it wasn't designed for.

Consequently, given that it is so easy to use HKDF the right way, you should probably do that.


Can Winternitz be easily converted to a many-time encryption scheme? The Winternitz scheme is typically cited as being an OTS scheme. Can it also be used as a one-time encryption scheme?

If it can be used as a one-time encryption scheme, then is it possible to easily convert it into a many-time encryption scheme that uses either a single key or different keys that may be generated in some deterministic way from a single key i.e. only a single key needs to be stored and cyphertexts provide some sort of IV to allow the appropriate key for that cyphertext to be generated and decrypted?

Can it also be used as a one-time encryption scheme?

You cannot build asymmetric encryption from just hash functions. There is an impossibility proof for that. So for asymmetric encryption the answer is no. See Merkle Puzzles are Optimal - Boaz Barak, Mohammad Mahmoody-Ghidary for the proof.

For symmetric encryption, you can simply use the hash function directly to build encryption, no need to bother with Winternitz.

But you could use quantum-key-exchange together with hash based signatures to achieve something similar to asymmetric encryption.

Concerning many-time signatures

It's straight forward to build stateful many-time signatures from one-time signatures. Just create as many one time keys you need, compute a hash tree over their public keys and public its root. The hash tree allows you to efficiently prove what the nths public key is and proceed with the one-time signature form there.

But if you don't want to keep track of which one-time signatures you already used, you need a stateless many-time signature. It is possible to build stateless hash signatures, but it's a bit trickier. SPHINCS is a recent example.


On what basis is padding chosen in OpenSSL? I am using CAPI Engine in OpenSSL and I did some test. When I use TLS 1.0 or 1.1, during handshake and RSA signing, PKCS padding is chosen. When I use TLS 1.2, RSA signing uses PSS padding.

What affects the choice among paddings?
How client knows what padding was used?
When is padding assigned to RSA structure?

Q: I am using CAPI Engine in OpenSSL and I did some test. When I use TLS 1.0 or 1.1, during handshake and RSA signing, PKCS padding is chosen. When I use TLS 1.2, RSA signing uses PSS padding.

Funny, a quick lookup of TLS 1.2 contains the following:

Note that there are certificates that use algorithms and/or algorithm
combinations that cannot be currently used with TLS.  For example, a
certificate with RSASSA-PSS signature key (id-RSASSA-PSS OID in
SubjectPublicKeyInfo) cannot be used because TLS defines no
corresponding signature algorithm.

As I didn't find any RFC's that counteract this, it seems impossible that TLS 1.2 uses PSS for authentication at all.
Now, on the other hand TLS 1.3 specifies that you should use PSS, which is not that surprising as TLS 1.3 very deliberately uses up to date cryptography at the cost of backwards compatibility. The TLS 1.3 specification does specify in section 4.2.3 that a 1.3-capable implementation negotiating 1.2 must support PSS signatures. If the peer supports 1.3, there should be no good reason not to negotiate 1.3 though, and if it only supports 1.2 it should not allow PSS, as there is no way to indicate that padding format1.
1 Choosing the padding algorithm can be performed by guessing the signature format, but PKCS#1 explicitly requires you to define the configuration beforehand, rather than looking into the signature format itself, as that may leave you prone to downgrading attacks on the signature algorithm itself.

For TLS 1.0 a very specific structure with both SHA-1 and MD5 is used. This standard predates SHA-2 and therefore it uses a more secure construct using two hashes that are separately pretty insecure. It also may use RSA encryption using PKCS#1 v1.5 padding as PKCS#1 v2.0 hadn't been introduced either. I don't see any changes for TLS 1.1 for RSA signing / encryption. Note that TLS 1.1 and 1.2 were mainly incremental updates of TLS 1.0 rather than the significant rewrite that TLS 1.3 is.
So basically, the use of RSA padding in TLS is directly tied to the standard itself. OpenSSL will try and follow that standard.

It might be that if you have a certificate that identifies the public key algorithm as PSS, see here. In that case an implementation may decide to go with that single choice, even though it is prohibited by the TLS 1.2 standard - I guess the correct response would be to throw an error unless the connection is downgraded from TLS 1.3.


Is there confirmation blocks in Proof-of-Stake Blockchain? When I'm reading literature about proof-of-stake blockchain, I found that it seems there is no concept about confirmation blocks (which is used to confirm a posted transaction is indeed honestly generated and in bitcoin we need 6 confirmation blocks that is enough). However, my question is that why we don't need confirmation blocks in Proof-of-Stake blockchain like Proof-of-Work blockchain?

For a proof-of-work blockchain, say Bitcoin, the confirmation length is 6, just to make sure any adversary doesn't create any additional blocks and make a new fork that's longer. That's possible because all you need is more computation, and no proof of identity.

However, in proof-of-stake blockchain protocols, you often need to provide a new block with some kind of proof that you are eligible to propose the new block. This instantly creates a confirmed block because for a particular slot, another party cannot create a valid block and proof later in time.

Take a look at the Algorand protocol for more details.


The sensitivity in differential privacy with deep learning In differentially private deep learning, the sensitivity is determined by clipping gradient norm (see Abadi et al.'s paper). In this paper, when the clipping gradient norm is $C$, the sensitivity is $C$. Why is the sensitivity $C$? I think the sensitivity should be $2C$.

This is because they're using a definition of adjacency where you only consider two pairs of inputs adjacent when one record has been added or removed, instead of arbitrarily changed.

(…) each training  dataset is a set of image-label pairs; we  say that two of these sets are adjacent if they differ in a single entry, that is, if one image-label pair is present in one set and absent in the other.
   Definition 1.  A randomized mechanism $\mathcal M: \mathcal D\to\mathcal R$ with domain $\mathcal D$ and range $\mathcal R$ satisfies $(\epsilon,\delta)$-differential privacy if for any two adjacent inputs $d,d'\in\mathcal D$ and for any subset of outputs $S\subseteq\mathcal R$ it holds that
$$\Pr[\mathcal M(d)\in S]≤e^\epsilon\Pr[\mathcal M(d')\in S]+\delta.$$

Since each record contributes a value in $[-C,C]$ to the gradient, removing or adding a record will change the total by $C$. It would be $2C$ if the definition included "arbitrarily changing a record".


Is the DES F-function injective for a given subkey? Is it possible for two different half-block inputs to the DES F-function, with the same round subkey, to produce the same output?

That is, if we feed two different half-block inputs $b_1$ and $b_2$ through the expansion stage, XOR them with a constant subkey $K$, and then pass the expanded and XORed inputs through the S-boxes, is it possible for the outputs $o_1 = F(b_1, K)$ and $o_2 = F(b_2,K)$ to be equal?

Yes, it can; within the DES round function, two different 'right side' inputs can, after the sboxes, come up with the same value to xor into the 'left side'.

This was a deliberate decision by the DES designers, who thought that this was an important property.  I don't know their reasoning about why they thought it was important.


What happens if the first input block is identical to the key in DES? In Data Encryption Standard (DES),
M is the input message and K is the key of 64 bits size.
M is divided into n 64 sized blocks (B1,B2,B3...Bn).

DES encrypts the block, or decrypts it if it is used in the other direction.

DES is a block cipher and therefore a keyed permutation. The key is used to choose the permutation. In this permutation every value of the input is mapped to a pseudo-random output value of the same size. However, how the permutation is chosen is quite different from performing the permutation. Because of that it is unlikely that there are any mathematical properties exposed when encrypting the same data as the key.

From the practical side: before the DES key is used the 56 (not 64) bits undergo a subkey derivation to derive a separate (but related) key for each round. Already at this stage the key won't be equal to the input bits anyway. If DES had weaknesses in such a way that this kind of input would expose the key then it would be considered broken - and despite the key size and existence of other weak keys, it isn't.

That all said, encrypting the key is not considered very useful. Sure you can encrypt it, but you'd need to know the key to decrypt it again. If you already know the information then there is little need to do so. You could possibly use it to confirm a good key guess, but in that case CBC-MAC over a random block of data would arguably be better. It would also scale to other key sizes than the block size, for one. Moreover, it would not treat the key as plaintext data.


Is a small size block cipher usable? Consider a block cipher with a key of size 128 bits but a small block size, say 32 bits.  Is this kind of block cipher secure?

I would like to know to what extent I can use a small block cipher, like a 32 bit block cipher. What are the constraints so that the use is acceptable in a real life application.

For instance, if we use a one-time key, that is, to encrypt only one message. Besides, the message could be small.

Suppose that when we want so send one file, we perform a key agreement so that we use the key for one message. This scenario is not efficient, but the CPA find-then-guess game is not adequate in this case.

Such a block cipher would be completely unusable in any of the standard modes of operation, presuming you want at least IND-CPA security. Say, for instance, that you are using it in CTR mode. A chosen plain text adversary looking at a cipher text consisting of only two blocks (i.e. 2 times 32 bits), would have a non-negligible probability (higher than $2^{-32}$) of guessing if the cipher text is produced by your block cipher in CTR mode, or a random function.

This matters in so far that a block cipher in CTR mode is only secure up to the bound where the block cipher might still be modeled as a PRF, as defined in the security proof. If you are able to distinguish the block cipher from a PRF, CTR mode is no longer IND-CPA secure. This applies to all other standard modes as well.

If one of the CTR mode cipher texts is 16 GB, you will have revealed the entire code book, and the adversary will not need the key.

If you have a hard time seeing this, consider a 2-bit block cipher in CTR mode that has produced the ciphertext stream 3-1-0. If Eve has tricked us into encrypting 0 three times, then the next CTR value must be 2 with probability 100%. Real plaintexts are nearly that predictable, so exhaustion of the ciphertext space is a practical limit. 32 bits is just too tight.

Edit:
Please also note that it would be a mistake to assume that failure to meet IND-CPA security, would only be relevant in scenarios where the exact CPA game can be played out. Suppose, for instance, that you encrypt only a single message (in CTR mode) with each key, and that this message is $l$ bits long. If $l \le 32$ you are safe, but if it is longer, you are not. Suppose $l=64$. In such case the plain text $m$ might be divided into two blocks $m=m_0|m_1$ and the cipher text $c$ into two blocks $c=c_0|c_1$. Now, the attacker might immediately deduce that $m_1\ne m_0\oplus c_0 \oplus c_1$ (because $m_i \oplus c_i = E_k(i)$ and $E_k(0) \ne E_k(1)$) and has learned $32/{2^{32}}=2^{-27}$ bits of information about $m$. The more that is known of patterns in $m$ and the greater the length $l$, the more information about $m$ might be deduced even in a cipher text only attack.


Encoding numbers that can be decoded mentally? I have a lot of objects, all of which need a particular number tagged on them so I can quickly tell the customer accordingly. But the problem is that the customer should not know what these numbers say (I write how much I buy the object for).

Is there any way I can encode them so that i can quickly decode and understand what the words mean?

I wouldn't try and do this mentally. Whatever you come up with will be insecure, slow and error prone.

Here's what I would do:

Each box would have a QR-code on it that you print and attach to the item.
You then scan the item with your phone.
Your phone has 128-bit key saved to it that is unique to that device.
The phone decrypts the QR code and displays the associated data inside the QR code.

The bigger QR-codes can store enough data that you can actually do the crypto properly with the proper IVs and authentication tags. AES in GCM mode would be my suggestion.

This solution has the advantage that it's very quick to decode the message on the boxes, the underlying scheme is secure, and QR-codes have automatic error correction capabilities, so they can resist damage.

This has to be better than trying to do it in your head.


irreducible Polynomial in a Cipher If we change the irreducible polynomial of the AES to someother irreducible or primitive polynomial, what effect will it have in security?

Yes, we can change the irreducible polynomial of AES to another irreducible polynomial. In doing so we have to implement a change of basis or change the polynomial for the S-Box, this may effect the security. Moreover research had been done on how to enhance the security of AES by changing the irreducible polynomial. See this paper for detailed discussion.

Hope this helps.


How does the polynomial modulus work in the Fan-Vercauteren scheme? I'm reading this introductory blog on the Fan-Vercauteren
 scheme and there are a few things I don't understand about polynomial moduli. The author uses practical examples:

  Because we are considering remainders with respect to $x^{16}+1$, we only have to consider polynomials with powers from $x^0$ to $x^{15}$. Any larger powers will be reduced by division by the polynomial modulus. This can also be understood by considering that $x^{16}\equiv −1(\mathrm{mod} \ x^{16}+1)$, meaning that $x^{16}$ can be replaced by -1 to reduce the larger powers of x into the range 0 to 15.

I don't understand the third sentence at all, $x^{16} \equiv -1$?

Further down the tutorial, there is a practical example of polynomial multiplication followed by a division by polynomial modulus:

  When we multiply two powers of x, say $2x^{14}$ and $x^4$, we add their exponents - making $2x^{18}$. One might assume that finding the remainder of this polynomial with respect to the polynomial modulus might involve just rotating the exponent back through 0 at $x^{16}$, to give $2x^{2}$, like it does for the integer coefficients shown above. This would be the case if the polynomial modulus was just $x^{16}$. However, our polynomial modulus is $x^{16}+1$ - as mentioned above, the extra plus one factor introduces a sign change which helps further scramble the result of the multiplication.

How does this extra plus one factor introduce a sign change?

and finally:

  ...multiplication of a term $2x^{14}$ by $x^4$ modulo $x^{16}+1$ takes this term (represented by the red dot above), rotates it forward 4 powers around the torus, and then reflects the value across the 0 point, making $22x^2$ (or $−2x^2$ if we consider numbers from -12 to 11 rather than 0 to 23).

$2x^{18}$ modulo $x^{16}+1 = 22x^2$, how?

You have to pay attention to the fact that two moduli are used: a polynomial modulus $x^n + 1$ and an integer modulus $t$ (in that example, $n = 16$ and $t = 24$).

In practice, it means that not only the degree is limited but also the coefficients: they always lie in $\mathbb{Z}_t$, which is traditionally represented as the set $[0, t-1] \cap \mathbb{Z}$, but in lattice-related texts, it is usually represented as $[-t/2, t/2)  \cap \mathbb{Z}$.

So, for the first point, it is easy if you think that for any polynomial $p(x)$, reducing it modulo itself results in a zero, i.e., $p(x) \equiv 0 \pmod{ p(x)}$, because the division $p(x) / p(x)$ is $1$ with remainder $0$. Hence, taking $p(x) = x^n+1$ gives us

$$x^n+1 = 0 \pmod{x^n+1} \Rightarrow x^n = -1  \pmod{x^n+1}.$$

Now, if you use the properties of modular multiplication, you will see that when you reduce a polynomial modulo $x^n +1$, you will actually replace the powers $x^n$ by $-1$, $x^{n+1}$ by $-x$, $x^{n+2}$ by $-x^2$, etc.

Thus, for instance, $2x^{14} \cdot x^4 = 2x^{18} = 2x^2 \cdot x^{16}$. But since $x^{16} = -1$ because of the modular reduction, we have

$$2x^{14} \cdot x^4 = -2x^2 \pmod{x^{16}+1}.$$

Until this point, only the polynomial reduction was done, but we also need to compute each coefficient modulo $t = 24$. Since $-2 = 22 \mod 24$ we get

$$2x^{14} \cdot x^4 = 22x^2 \pmod{x^{16}+1, t}.$$

Notice that if we use the representation of $\mathbb{Z}_t$ that includes negative numbers, then $-2$ equals itself modulo $t$ and the result is still $-2x^2$, as it is said in the last parenthesis of your question.


Comprehension question on a signature protocol based on the RSA assumption We have the following two-party protocol between Alice and Bob. Alice sends messages $m_1, m_2, \ldots \in_R \mathbb{Z}_n^*$ to Bob and Bob signs these values by calculating $v_1, v_2, \ldots \in_R \mathbb{Z}_n^*$ and
$a_1 = \left( G \cdot H^{-v_1} \cdot K^{-m_1} \right)^{1/x}\ \bmod\ n$

$a_2 = \left( G \cdot H^{-v_2} \cdot K^{-m_2} \right)^{1/x}\ \bmod\ n$

...

$x$ is a prime and all values are public. Only $1/x$ is known by Bob because Bob knows the factorization of $n$. It is $a_i, G, H, K \in \mathbb{Z}_n^*$

Is is possible that...

(1) Alice can get $(1/x)$ or the factorization of $n$ by sending lots of messages $m_1, m_2, \ldots$ to Bob and analyse the pairs $(a_i, v_i, m_i)$?

(2) Alice can contruct her own pair $(a_i, v_i, m_i)$ without knowing the factorization of $n$.

I have found this algorithm in a paper and they choose $x$ randomly for each signing process. I ask myself, if it is really necessary to choose $x$ randomly, because finding a big prime number is relatively time-consuming. $v_i$ is under the control of Bob so the signed part between the brackets is always different. Is this enough or should the exponent $1/x$ also be different?

Assuming that $x$ is odd, then the answer is no for number (1); to the best of our knowledge, the attacker would not be able to either compute (1/x) or factor N, even with a huge number of sets $(a_i, v_i, m_i)$, even if he got to select the $m_i$ (and even the $v_i$) values.

This follows directly from the fact that no one knows how to factor an RSA number $n$ given an oracle that computes $F(z) = z^{1/x} \bmod n$ for odd $x$.

On the other hand, we have a definite yes for number (2); if an attacker gets two distinct valid triplet $(a_1, v_1, m_2)$, $(a_2, v_2, m_3)$, that is, with:

$a_1 = \left( G \cdot H^{-v_1} \cdot K^{-m_1} \right)^{1/x}\ \bmod\ n$

$a_2 = \left( G \cdot H^{-v_2} \cdot K^{-m_2} \right)^{1/x}\ \bmod\ n$

Then it is possible that he can construct a third triplet $(a_1^2 \cdot a_2^{-1}, 2v_1-v_2, 2m_1 - m_2)$; this will be a valid set as long as $2v_1-v_2$ and $2m_1-m_2$ are both in range; that will happen nontrivially often.  Note that the attacker can compute $a_1^2 \cdot a_2^{-1}$ using $\bmod n$ arithmetic; he can't compute $2v_1-v_2$ using $\bmod \phi(n)$ arithmetic; he has to use standard subtraction, and hope the value is in range, where "in range" means "a value that the verifier will not reject as silly".

As for the expense of finding new prime values $x$ every iteration, the obvious question is "why do they need to be prime?".  The only requirement that RSA places on $x$ is that it be relatively prime to both $p-1$ and $q-1$, where $p$ and $q$ are the prime factors of $n$. An easy way to handle this is during RSA key generation, you select $p$ and $q$ such that $p-1$ and $q-1$ have no small prime factors other than 2.  If you ensure that neither $p-1$ nor $q-1$ have any odd factors less than $2^{k}$, and you select odd values of $x$ less than $2^{k}$, then that value of $x$ will always work, even if it is composite.  On the other hand, perhaps there is something that this protocol needs besides "RSA works"; the paper discussing this protocol might mention any such concern.


Can ECDH be used for authentication? Is it safe to use ECDH for challenge-response authentication, with server key being ephemeral?

The goal is that server does not store sensitive data (hashes) and allow clients to use additional security if needed (for example generate and store their key in a smartcard and skip key derivation).

Client derives private key from the password, using a strong hash algorithm (similar to bitcoin address generators using passwords)
Server generates a key and sends its (ephemeral) public key and a challenge string
Client must reply with the challenge, encrypted with the shared key
Server checks if decrypting response yields the challenge

Assumptions

A secure channel is already established
Server has the client's public key stored

Here’s a link that shows how to implement ECDH with long term public keys and ephemeral shared keys. You could just add this authentication after the TLS handshake as it’s own layer. Think about the openID protocol.  You can publish the keys at a well-known-endpoint,  it’s not necessary to wrap them in a certificate.


How do substution-permutation networks work? I understand what's going on in higher level. But i don't understand what's really going on in page 3 and 4 of this slide.

Specifically,

How S0 and S1 is used? What goes in what goes out?
How exactly  key bits determine
which s-box is to be
used at each position? Position refers to what?
is the function "f" in page 4 exactly the same SP network in page 3?
why split plain text into left L and right R?
why XOR L with R after applying "f"?
why rotate after  applying last "f"?
why XOR is used? why not some other bitwise operation?

preceding slides for reference

1) and 2) Either S0, or S1 is used for each 4-bit long part of block depending on key bits. 16 S-boxes are used in each round (because you split 64-bit-long block into 16 parts of length 4) of the Lucifer cipher, so each round needs a 2 byte long subkey.

Example:

16 starting bits of the key (the first subkey):

0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 (2 bytes together)

S-boxes used in the first round:

S0 S0 S1 S0 S1 S1 S1 S1 S0 S0 S1 S0 S1 S0 S0 S1 (4 bit input/output each, 64 bits together)

3) No, not necessarily. Feistel's scheme is a general solution based on any S-box and any permutation P. The Lucifer SP is just one example of a possible SP. Feistel's scheme can be used with non-invertible function F, too. You don't need to use SP, although it is the most common choice.

4) and 5) Because this is how Feistel designed his scheme... He wanted to develop a hard-wired device he could safely use for both encryption and decryption and which would have all the great features provided by SP network (avalanche effect, non-linearity,...). You cannot use the same device for both encryption and decryption with basic SP network decribed on page 3 of your slides.

Why did he decide to rotate L and R after each round? If there is no rotation, R stays untouched - not very good for an encryption scheme, right?

6) Your slides are a little bit confusing, I think this picture illustrates Feistel's scheme better:

As you can see, if you place all XORs on the left and uses the right part always as an input of F, you rotate L and R after each round except the final one. Why not? Because the final rotation does not depend on key, so it would provide no extra security.

7) Because it is fast to compute XOR by our hardware and because the result depends equally on both input bits. If you used AND and the result was 1, you would know the input was 1 independently on the key, which is not what you really want, right? The same problem with OR and 0 result.

Linear cryptanalysis (based on comments):

Let's have a block cipher, output of which can be represented as a system of linear equations:

C1 = a11P1 XOR a12P2 XOR ... XOR a1nPn XOR b11K1 XOR ... XOR b1kKk

C2 = a21P1 XOR a22P2 XOR ... XOR a2nPn XOR b21K1 XOR ... XOR b2kKk

...

Cn = an1P1 XOR an2P2 XOR ... XOR annPn XOR bn1K1 XOR ... XOR bnkKk

where Ci stands for the i-th bit of the ciphertext, Pj is the j-th bit of plaintext, Kp is the p-th bit of the secret key and coefficients aij and bij are some wellknown 0/1 constants defined by the design of the cipher.

If you had enough plaintext-ciphertext pairs known for the same key, you could solve the equation system and find the key value. That would be a problem, right? That is why modern ciphers are never linear - you cannot write their output as a system of linear equations of input bits and key bits as above.

S-boxes in SP networks are always chosen not to be linear and even more, it must be difficult to approximate them by linear equations, otherwise the whole SP network would be vulnerable to linear cryptanalysis.

If you chose S-boxes of your SP network wisely, the whole network will be non-linear (therefore safe against linear cryptanalysis) and so will be Feistel's scheme based on this SP network.

However, this is just a basic intro. The linear cryptanalysis is very interesting and very complex topic and you should find some more detailed source of information in case you are interested.

Feel free to ask.