Key sizes for discrete logarithm based methods I have a question regarding the key generation process of methods that are based on the discrete logarithm problem.
This site gives some good insights, but I don't fully grasp it I think: http://www.keylength.com/

For example I know that till lately one should have used 1024 bit group modulus and a 160 bit long secret key and that picking the secret key size is always roughly double the security level (hence here 80 bit security) one wants to achieve.

My question is: How does the groups modulus size relate to the security level? Does the group generator always have to be the same size as the group modulus?

The best known estimates are still the two that can be found in RFC 3526. Both estimates (with regard to the modulus size) are based on the estimated number of operations required to compute discrete logarithms using number field sieve based methods. The reason the estimates differ, is because of the second estimate does not account for memory/time trade offs that would require arguably unrealistic amounts of storage space.

   +--------+----------+---------------------+---------------------+
   | Group  | Modulus  | Strength Estimate 1 | Strength Estimate 2 |
   |        |          +----------+----------+----------+----------+
   |        |          |          | exponent |          | exponent |
   |        |          | in bits  | size     | in bits  | size     |
   +--------+----------+----------+----------+----------+----------+
   |   5    | 1536-bit |       90 |     180- |      120 |     240- |
   |  14    | 2048-bit |      110 |     220- |      160 |     320- |
   |  15    | 3072-bit |      130 |     260- |      210 |     420- |
   |  16    | 4096-bit |      150 |     300- |      240 |     480- |
   |  17    | 6144-bit |      170 |     340- |      270 |     540- |
   |  18    | 8192-bit |      190 |     380- |      310 |     620- |
   +--------+----------+---------------------+---------------------+

These estimates do not account for post-quantum cryptography. Arguably, it is not entirely improbable that we will see major break-troughs in quantum cryptography, rendering these estimates moot, long before the difference between estimated 128 bit strength and 256 bit strength will become relevant for most practical purposes. Then again, there might of course be applications that generate a lot of traffic and has to bump the estimated security strength, to guarantee that the advantage of an attacker stays well below $2^{-128}$ even in a shorter term.


Understanding Feldman's VSS with a simple example I'm trying to understand Feldman's VSS Scheme. The basic idea of that scheme is that one uses Shamir secret sharing to share a secret and commitments of the coefficients of the polynomial to allow the other party to verify that the share they received is valid. I implemented it in code following the wikipedia page, but my verification function doesn't work. Here is a simple example of the failure:

We will work in the field $\mathbb{Z}_{11}$ with generator $g=3$. Let $f(x)=5+3x+8x^2$ be our Shamir polynomial. Thus $f(1)=5$. So let $s_1=5$ be the share that party $p_1$ gets.

The dealer also must commit to the coefficients. So the commitments are $3^5=1, 3^3=5, 3^8=5$. (These are computed as $g^c$ for each coefficient $c$ of the polynomial).

For verification that $s_1$ is correct, we compute $g^{s_1}=3^5=1$ and compare this to $1*5*5=3$ (the exponents are all $1$ since $i=1$, otherwise this step is done as $k^{i^j}$ where $k$ is the commitment, $j$ is the index of the commitment). Since $1\neq3$, the verification fails. But why? It should pass assuming I have done things correctly.

Update
So working the math a little in more detail:
$g^{s_1}=1$ and $g^5 g^{3^{1^1}} g^{8^{1^2}}= g^{5+3^{1^1}+8^{1^2}}= g^{5+3\cdot 1^1 + 8\cdot 1^2} = g^{16} = g^6 = 3$ and $1\neq 3$.

Note that the exponent is $f(1)$. Wikipedia offers a small hint:

  (Typically, one takes a subgroup of $\mathbb{Z}_q^*$, where $q$ is a prime such that $q$ divides $p-1$.

Is my problem that I am not working in such a subgroup? If so, why does it not work in general for $\mathbb{Z}_p$ (Wikipedia only says that typically one works in this subgroup)? Is there a standard way to set up such a subgroup?

It has to do with which modulus you use.  You did all your arithmetic modulo 11.  However, when using Feldman's VSS, you gotta use two different moduli (using each one in the appropriate spot).  In your example, you shouldn't do all arithmetic modulo 11.  Instead, you should be doing some arithmetic modulo 11, and some arithmetic modulo 5 (the order of $g$ in this case).  If you do that, everything will work out.

In general, you need to pick primes $p,q$ such that $q | p-1$.  Then, some arithmetic is done modulo $p$, and some arithmetic is done modulo $q$.  In particular:

The polynomial $f(x)$ is treated modulo $q$, so when you compute the shares, you need do arithmetic modulo $q$.
The commitments and all computations with the commitments are treated modulo $p$, so when you verify that you got the correct share, you work modulo $p$.

The reason we do it this way is that when doing a computation like $3^{15}$ (modulo $11$), we can reduce the base modulo 11, but we have to reduce the exponent modulo 10.  Roughly speaking, commitments are in the base, whereas the value of the polynomial (the shares; the coefficient of the polynomial) are in the exponent -- so you gotta use different moduli for these two different kinds of values.

We can modify your example to take this into account. We could take $p=11$, $q=5$, and generator $g=3$ of the subgroup of order $q$ of $(\mathbb{Z}/p\mathbb{Z})^*$.  However, you can no longer have the polynomial $f(x)=5+3x+8x^2$: the polynomial is interpreted modulo $q$, so all coefficients have to be in the range $0..4$.  This means we'll need to change things a little bit.

So, here's a corrected example.  You could use the polynomial $f(x)=0+3x+3x^2$.  Since $f(1)=1$, you'll get the share $s_1=1$.  The commitments are $3^0=1$, $3^3=5$, and $3^3=5$.

For verification of the correctness of the share, we first compute $3^{s_1}=3^1=3$.  Next, we compute the check value $1 \times 5^1 \times 5^{1^2} = 3$.  You can see that $3^{s_1}$ is equal to the check value, so everything verifies, and the share is correct.


Conditional $k,n$ secret sharing I would like to know if there is a way to place a condition on $k$-out-of-$n$ secret sharing such that out of $k$ participants who can pool their shares to reconstruct a secret, one of them should always be a particular user say $P_1$. In other words, say we share a secret $S$ with $n$ users $P_1,P_2,\dots, P_n$. The participants will be able to re-construct the secret $S$  iff { $P_1$ + at least $(k-1)$ other users from $\{P_2,\dots,P_n\}$ } pool their shares. If $P_1$ is not there, the other $(n-1)$ users cannot reconstruct the secret.

This can be trivially achieved by sharing twice.
First share your secret $S$ using a $2$-out-of-$2$ secret sharing scheme into $S_1$ and $S_2$. (E.g. choose $S_1$ at random and set $S_2:=S\oplus S_1$.)

In the next step you now share $S_2$ using a $(k-1)$-out-of-$(n-1)$ secret sharing scheme into $S_{2,1},\dots,S_{2,n-1}$.

Give $S_1$ to $P_1$ and $S_{2,i}$ to $P_{i+1}$ for $1\leq i <n$.

The secrecy of the $2$-out-of-$2$ secret sharing scheme guarantees that both shares $S_1$,$S_2$ are required. $S_1$ is only known to $P_1$, and $S_2$ can only be recovered by at least $k-1$ of the other parties collaborating.


Does blinding protect again fault injection attack against RSA with CRT I know that blinding can be used as a countermeasure against side-channel timing attacks on RSA-CRT:
RSA Timing Attack and Prevention through blinding
My question is: can blinding also be used as a countermeasure against differential fault injection attacks on RSA with CRT as described by BellCoRe (see: https://hal.archives-ouvertes.fr/hal-00939473/document and here: https://www.limited-entropy.com/crypto-series-dfa/)

In the original Bellcore attack, the attacker needs to obtain a valid signature and a signature where the computation of one of the coefficients is faulty. The exact nature of the fault does not matter, as long as it affects one of the exponentiations. Therefore it doesn't matter how the coefficients are calculated: blinding has no impact on this attack.
In any case, a cheap defense against single-fault Bellcore-style attacks against RSA is to perform the public-key operation after the private-key operation and compare against the input to the private-key operation.
Blinding may help with more advanced variants involving multiple faults. If the attack requires the faults to happen in a specific way, blinding might cause the result to be unusable for the attacker. I'm not familiar with the literature on those variants.


Earliest citation for truth density I am searching for a citation of a formula that calculates the proportion of true (1) outcomes in the corresponding truth table of a boolean function. Searching a little bit in the Cryptography literature, I found that the hamming weight of a boolean function is defined as the number of $1$'s, so it is close to the metric I am referring to. I have also seen this metric/property mentioned as 'truth density' in Wolfram, see an example.
Has anybody used this formula in a paper before ~2000-2010s? (a recent paper that defines it as bias is this one). Or maybe provide a proper (older) publication to cite for the hamming weight?

The truth density $p$ is arguably the same concept as the bulge to 0 $b$ of a Boolean function as $b=1-2p\iff p=(1-b)/2$. The bulge leads to cleaner formulae in many cases though. The language of bulges was common at Bletchley Park. Do you count the General Report on TUNNY as a 1945 or a 2015 publication?


On keyword for generators of composite moduli The link says $n$ has a primitive root if and only if $n$ is of certain form ($n=ap^k$ where $a=1$ or $a=2$ if $p$ is an odd prime or else $a=1$ and $k\leq2$ holds).

In particular $n=pq$ or $n=pqr$ where $p,q,r$ are not all equal primes are disallowed.

Yet in here discrete logarithms modulo such $n=pq$ or $n=pqr$ forms are defined and used (by this I mean there is a $g$ that generates $\phi(n)$ elements and this is used as generator).

Since generator $g$ cannot be primitive root what is the keyword for $g$ for these $n=pq$ or $n=pqr$ forms?

I tried this in mathematica with no use. How to search for these generators in mathematica?

The link says $n$ has a primitive root if and only if $n$ is of certain form, either $n = ap^k$ where $a \in \{1, 2\}$, $p$ is an odd prime or $n \in \{2, 4\}$

This is true.

  In particular $n = pq$ or $n = prq$ where $n, q, r$ are not all equal primes are disallowed.

Other than the minor nit that $n=pq$ where $p=2$, $q$ is an odd prime does have primitive roots, the obvious question is "what do you mean is disallowed?"

A primitive root is a value $g$ where $g^k \bmod n$ can take on all values in $Z^*_n$; what the statement says is that such a $g$ will exist if $n$ is of the form listed, and no such $g$ will exist if it's not.

  Yet in here discrete logarithms modulo such $n=pq$ or $n=pqr$ forms are defined and used.

Well, yes, the problem "given $g, h$, does there exist a $k$ such that $g^k \equiv h \pmod n$ (and if it does exist, what is its value)" is well-formed, even if $n$ is not of the listed form.  Now, as there isn't a primitive root, there's no value $g$ for which such a $k$ will exist for every $h$ relatively prime to $n$; however that doesn't make this an invalid question.

  Since generator $g$ cannot be primitive root what is the keyword for $g$ for these forms?

Well, I can't think of any better term than "generator".  Any value $g$ relatively prime to $n$ will generate some subgroup; the only distinction between "primitive roots" and "everything else" is that primitive roots generate the entire group.  I suppose you might insist on a value $g$ which generates as large of a subgroup as possible (which would be, for the forms you listed, of size $\text{lcm}(p-1,q-1)$ or $\text{lcm}(p-1,q-1,r-1)$), however I haven't heard of specific terminology given to elements that generate subgroups of that size.


How does BB84 fare against an attacker who can entangle qubits? Consider the following attack on the BB84 quantum key exchange protocol (as far as I can tell, it should work similarly for E91):

After Alice sends her key bits encoded in qubits with randomly chosen bases, Eve intercepts them without making a measurement.

She uses her quantum computer, prepares it in a |0⟩ state and, for each bit, does a CNOT with her own qubits as targets and Alice's bits as controls, thus entangling them.

Then, she sends Alice's bits on to Bob, who measures them.
This projects them into an eigenstate of Bob's chosen base.
It also projects Eve's qubits into the same states.

After Bob and Alice have publically announced their bases, Eve measures her qubits in the same bases that Bob chose, getting the same result.

This way, she will not learn which bits Alice sent, but she will learn which bits Bob received, which is enough.
She will also not be detected when Alice and Bob compare part of their keys, because she makes her measurements only after Bob makes his.

Does this attack (theoretically) work?
If not, what's the problem?
If it does, why is BB84 considered (theoretically) secure?

After some consideration of Lukas' comment, it seems I haven't thought this through.
In fact, Eve will only entangle Bob's qubit with hers if Alice chooses the diagonal basis.
However when Bob also measures the diagonal basis, a quick calculation shows he randomly measures 0 or one, with probability 1/2 each.
So even though Eve learns which bits Bob measured, she will also introduce a 25% error chance as if she had measured them, and she will be detected.


substract points on secp256k - result as moved to N-1 I must perform calculate of substract two points:
Let $G$ be the generator point and;
$P_1 =[1]G = (x_1,y_1)$
$P_2 = [2]G = (x_2,y_2)$,
When I will subtract $P_1 - P_2$ -> I will move Point to N-1 with negative $y_1$ of $P_1$
second:
Let $G$ be the generator point and;
$P_5 =[5]G = (x_1,y_1)$
$P_2 = [2]G = (x_2,y_2)$,
$P_3 = [3]G = (x_3,y_3)$,
When I will subtract $P_2 - P_5$ -> I will take result $P_3$ with  negative $y_3$ of $P_3$
it looks like $P_2 - P_5$  it "similiar" to integer 2 minus integer 5 = we get minus 3 - and in this example -3 it is N-3 .
How to check that substract points cross the order of curve n? without checking  y is negative?
how to check that substract point is crossed by Point of Infinity and order of the curve?
Ps. N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
order of curve -> maximum points.

How to check that substract points cross the order of curve n?

You cant'; or at least, we hope you can't.
If you could, you could use that method to compute discrete logs.
Here is one approach; suppose you had a method that, given the points $[a]G$ and $[b]G$, would return you $[a-b]G$ and also informed you whether it "crossed the order of curve n", that is, if $a < b$.  Then, what you could do, given the point $[x]G$, you could use this method on the points $[x]G$ and $[\lfloor n/2 \rfloor]G$; that method would tell you if $x < \lfloor n/2 \rfloor$.  If it turned out (for example) if $x$ happened to be larger, you could repeat this with $[x]G$ and $[\lfloor 3n/5 \rfloor]G$; and continue to do binary searching until you have recovered the value of $x$.
That means that you've just recovered the discrete log of $xG$ with only circa $\log_2(n)$ calls to your method; we certainly hope that we can't do that.
BTW: why do you care if "the points cross the order of curve n"?


Does anyone know of any programmes that can find a function from a known input and output? The outputs I'm getting are only 2x the length of the input strings so any kind of brute force programme would be fine. Thanks.

Recovering an arbitrary function $f:M \rightarrow N$ from samples $x_i, f(x_i)$ is clearly impossible without additional information unless the given $x_i$ cover $M$ or unless $N$ is of size one, since an arbitrary continuation can be chosen on the remaining inputs. By the same token, it is trivial to find some function that reproduces the input-output behaviour of $f$ (for instance one may just pick a function that takes inputs outside the given values to some constant output in the codomain of the function).

Finding the simplest or most efficient function that reproduces some given input-output behaviour is believed to be difficult in general, even when a full description of the target function is given to the adversary and even when domain and codomain are fairly small. For instance, the paper Partitions in the S-Box of Streebog and Kuznyechik by Leo Perrin basically showed a surprisingly efficient way to implement the S-box of the Russian encryption algorithm Kuznyechik (and the Russian hash function Streebog) as well as the techniques used to obtain this representation and won the best paper award at FSE 2019. The S-box in question is a function that takes an 8-bit value to another 8-bit value and is completely public. Hence, even for functions that small, recovering an efficient function representation from the value table will not be easy in the general case.


AES S-box calculation I am trying to design the s-box for AES. Quoting from Wikipedia, the algorithm for applying affine transformation in AES s-box calculation is

Let s (an 8-bit unsigned variable) be the input number.
Let result be 0.
For 5 times:
   XOR result with s.
   Rotate s one bit to the left.

My question is why the multiplication is done this way? Why only 5 steps?

This is first half of the calculation presented on the Wiki page.

Notice that every bit of the result is actually a XOR of just five bits:

Now we slightly modify the algorithm you wrote to create five numbers by rotating the original number to the left and only then XOR them together:

As you can see the result is exactly the same.


Birthday attack on AES-CCM with 32-bit Authentication Tag I would like to use AES-CCM with a very small Authentication Tag length of 32 bits. Thus, I have a question about the vulnerability to birthday attacks.

How vulnerable is CCM to birthday attacks?
Jonsson explains that the adversary does not gain more than negligibly from making multiple forgery attempts if the tag length is considerably larger than $\frac{k_b}{2}$.

Theorem: $\mathcal{Adv} \leq \frac{q_{dec}}{2^{\tau}} + \frac{\sigma^2}{2^n}$, where $q_{dec}$ bounds the total number of decryption queries that the adversary asks and $\sigma$ bounds the total number of blockcipher calls that the mode would make on the adversary’s sequence of queries, both to encrypt all the encryption queries and to decrypt all the decryption ones [explanation from Rogaway].

Since AES is used, $k_b$ should be 128 and the theorem wouldn't hold on a 32-bit authentication tag size. Does that mean that a birthday attack would work after $2^{16}$ attempts? Does this apply to blocks or messages (since blocks are mentioned here)? It would make quite a difference if it's the amount of blocks the function is called or the amount of messages:
$2^{16} \times 128\text{-bit block} = 1\text{MB}$
Thus, there'd be a collision after 1MB of data?

Or do I misunderstand Jonsson's theorem? On the other side, Rogaway applies Jonsson's theorem on 32-bit tags and explains that if a forgery that can perform 10,000 attempts until the key will be retired and the total amount of plaintext or ciphertext that the adversary attempts to encrypt or decrypt corresponds to $2^{50}$ blocks, then the adversary’s probability of forging will be at most $\frac{10000}{2^{32}} + 2^{-28} \approx \frac{10000}{2^{32}} < 0.000003$
Again, he works with $2^{50}$ blocks. Does that mean that the birthday bound describes the amount of messages instead of the blocks?

In short: How many messages can I securely send in CCM with a 32-bit authentication tag and after how many INVALIDs should the key be retired? Is Jonsson's Theorem applicable on 32-bit tags?

Please note: This answer is entirely based on the theorem the OP stated.

Notation:

$\tau$: length of the tag, in bits, this is 32 in your case
$\sigma$: the number of encrypted / decrypted blocks
$n$: the block size of the cipher, in bits, this is 128 for AES
$q_{dec}$: the allowed number of decryption queries
$\text{Adv}$: the probability that an attacker wins "the game" and thus breaks the associated security definition

Formula: $$\text{Adv}<\frac{q_{dec}}{2^\tau}+\frac{\sigma^2}{2^n}$$

First, for $q_{dec}$: You should really set this value as low as you can tolerate it to be without giving (too many) false positives, ideally this would be $1$.

The next step is to chose the upper probability you're willing to tolerate for an attacker breaking your scheme. Ideally, you'd want to set this as low as possible, for example FIPS 140-2 specifies that no random attempt should have a chance better than $\frac{1}{10^6}$ of succeeding (at wrongly authenticating the user) and it also specifies that an attacker may not have a chance greater than $\frac{1}{10^5}$ of succeeding within one minute when being alone with a cryptographic module. Also note that the chance of an attacker succeeding at least once after $k$ tries with probability $\text{Adv}$ is $1-(1-\text{Adv})^k$, so you may want to do the math and keep the value reasonably low for a given time-period and try-count an adversary has.

Now, after you figured out how much advantage you're willing to give to the attacker and how many decryption queries you're willing to accept, you can finally go ahead and use the above equation to find the maximal number of block cipher calls allowed for the scheme. This should be $$\sigma<2^{48}\cdot\sqrt{2^{32}\cdot\text{Adv} - q_{dec}}$$


Optimizing SHA-256 implementation for fixed input prefix Is it possible to optimize/precalculate some results in SHA-256 if the input starts with fixed values? My input is always 1111||message. Can I precalculate the 1111 in SHA-256 to save some cycles?

You can't completely precalculate 1111, however, you can completely precalculate messages that have a length multiple of 512. The reason is simple, SHA-256 uses 512-bit message block per compression, i.e. the compression function of SHA-256 uses 512-bit message inputs and 256-bit previous hash values.
$$C:\{0,1\}^{256}\times \{0,1\}^{512} \to \{0,1\}^{256}$$
and
$$H_i= C(H_{i-1},m_i)$$ where each $m_i$ has 512-bit lenght and $H_0$ is the IV.

per comment below

To be honest, my input is 32-Byte ones || 32-Byte X || 32-Byte Y, what exactly do I have to precalculate with X is not constant?

32-Byte makes 256 bits, therefore you cannot completely precalculate one compression. However, still, you can pre-compute some rounds of the compression function it that helps;
The SHA-256 uses a block cipher with 64 rounds and each round uses the message as a key and you can calculate 8 rounds of the next compression call. The key $W_i$ for round $i$ is formed by the message words $M_t$ of the block is formed by;
$$W_i = \begin{cases}M_t^{(i)} & 0 \leq t \leq 15 \\
\sigma_0^{256} W_{t-2} + W_{t-7} + \sigma_1^{256}W_{t-15} + W_{t-16} &
16 \leq t \leq 63
\end{cases}$$
With the 32-byte you can precalculate only 8 rounds of the compression function. The Y has no such options since at the beginning of the rounds the previous hash value from the previous compression function is needed.

using $11..11$ as a full block:
There is one way, though not effective, one can calculate $H'=C(H_0,11..11)$. This will require padding. Now you can use this $H'$ as the $IV$ for the $\operatorname{SHA256'}$; That is
$$H_i= C(H_{i-1},m_i)$$ where each $m_i$ has 512-bit lenght and $H_0$ is the $H'$ then your real message becomes as
$$11..11 \mathbin\| padding_1 \mathbin\| X \mathbin\| Y \mathbin\| padding_2$$


What is the strength and attack vectors of this simple scheme? Let's say that Alice wants to communicate some secret value $S$ to Bob through a public channel in a way that other people don't know what the value was.

To do this, Alice publishes that secret value to the public channel, along with $N-1$ other values, making a list $L$ which has $N$ items in it.

Before this communication, Alice and Bob agreed that the value Alice wanted to communicate to Bob would be $L_M$ where $M \in [0,N)$.

How secure is this scheme?  What attack vectors could be used on it? Also, does this technique have a name?

Some thoughts of my own:

The security of the scheme seems to relate to the size of $N$.  Larger $N$ values seem more secure.
It seems like if you didn't choose the other values of the list carefully, that it could be seen statistically that "one data point doesn't fit with the others" which could make the actual value cared about stick out more obviously.
One idea to make the value fit in completely could be that if the secret value $S$ could be represented in $B$ bits, that maybe the list $L$ could be a random shuffle of all values $[0,2^B)$, but if someone knew that, they could know that the number was probably on the higher side of the values so this may be too naive.
Agreeing on $M$ in advance has the usual key generation / key sharing / key storing problems and attack vectors.  I'm not interested in that part of the problem.

Short answer: Sorry, no, unfortunately your concept is neither a secure, practical nor efficient crypto scheme.

Slightly longer answer: To illustrate the impractically of your scheme, let's assume you are sending a completely random bit string $S$ of length $B$. In such case, in order to preserve perfect secrecy, you will at least have to send a list $L$ containing all possible values $[0..2^B)$ in random order, except for $S$ which is fixed at position $M$, where $M$ is the secret key you share with the recipient.

Now, if $M$ is selected completely at random from all possible values, it will also be a random element from $[0..2^B)$ and consequently be exactly as long, and contain as much entropy as, the message $S$ you want to sent.

The cipher text $L$ on the other hand, will be exponentially longer than the plain text message $S$. This is bad, because it means that your effort of sending the message securely, will be exactly as great as the effort you want your adversary to suffer trying to brute force guessing the key or the plain text.

Furthermore, if the plain text $S$ is not completely random, securely executing your scheme gets more complicated, but the conclusion doesn't change. If you maximize security, your effort of encoding and sending the plain text will be no less than the effort you want your adversary to suffer trying to break your scheme.


Are there use cases where a signature itself needs to be signed? I'm writing some code to digitally sign certain files (JSON, if you must know), and I'm trying to understand the use cases, not being a crypto guy myself.

I understand there are use cases where several parties all need to sign the same content, e.g. the two parties who enter a contract sign it to indicate their approval.

But are there use cases where B signs not just the content (of the contract, or whatever), but the concatenation of content plus the previously-created signature by A of the content?

Update: given this discussion, I created a proposal that I believe covers the case in case you are interested: http://upon2020.com/blog/2014/03/digital-signatures-on-json-payloads-lets-call-it-jsonsig/

In a nutshell there are two main uses cases for signing an existing signature:

validation: the signature of another person (ex: a superior) is
required to give effect to a primary signature. The second signature
covers the content, the first signature and potentially additional
data added by the second signer.
witness / notary: a second person signs only the first signature, to
vouch that the person applying the first signature is indeed the right one.
Contrary to the previous case, the content is not covered by the second signature, because the second signer does not commit to it.


What does $\langle A, B\rangle$ mean? I'm reading about CL-PKC and in Al-Riyami's FullIndent, I find some notations I must be sure to understand, to well explain it in my report.

  This algorithm takes paramsand $A$'s secret value $x_A$ as input and
  constructs $A$'s public Key $P_A$ like this :

  $$P_A = \langle X_A, Y_A\rangle$$

  With $X_A=x_A P$ and $Y_A = x_A P_0 = x_a s P$

Does $\langle A, B\rangle$ mean the concatenation of $A$ and $B$ ? If yes, why not using the || operator ?

From context, it appears $\langle A,B \rangle$ simply denotes (some value unambiguously encoding) the pair of values $A$ and $B$.

In general, when discussing high-level protocols, no specific encoding for such pairs (or more complex tuples of values) is specified.  It is simply assumed that we can unambiguously store and transmit such structured data somehow, but the specific manner in which this is done is considered an implementation detail.

Of course, an interoperability standard may indeed need to specify such an encoding, especially if such data structures are to be processed by cryptographic primitives that are defined as operating on (bit or byte) strings, with the expectation that independent evaluations of the primitive on the same structure should yield the same canonical output.  Some standard encoding schemes include e.g. csexps or the various ASN.1 encodings, although it's also common for specific interoperability standards to specify their own custom encoding schemes.

Note that, even if $A$ and $B$ are both strings, the pair $\langle A,B \rangle$ can not generally be unambiguously encoded merely by concatenating $A$ and $B$ together, since concatenation may introduce ambiguity when the length of the strings being concatenated is not fixed.  For a simple example, $10 \,||\, 1 = 101 = 1 \,||\, 01$.  That said, if the length of either $A$ or $B$ (or both) is fixed, then $A \,||\, B$ can indeed be a valid unambiguous encoding of $\langle A,B \rangle$.


Best attack on double DES followed by XOR with third key What is the best attack here?

  $E_k(m)=DES_{k1}(DES_{k2}(m)) \oplus k3$

I cannot think of how to attack this using exactly the same resources as the classic meet-in-the-middle attack against double-DES, but there is a way to solve it with similar computational and memory resources (i.e. with about $2^{57}$ time and memory), but using $2^{56}$ chosen plaintexts and $2^{56}$ (adaptive) chosen ciphertexts.

First, notice that if we ask for the encryption of $m$, xor the ciphertext with a known constant $T$, and then ask for the decryption of $E_k(m) \oplus T$, the following equality holds:
$$E_k^{-1}(E_k(m) \oplus T) = DES_{k2}^{-1}(DES_{k1}^{-1}(DES_{k1}(DES_{k2}(m)) \oplus k3 \oplus T \oplus k3))$$
$$= DES_{k2}^{-1}(DES_{k1}^{-1}(DES_{k1}(DES_{k2}(m)) \oplus T))$$
So we don't have to worry about the third key, and now we only need to figure out how to conduct a MitM attack against that construction using four applications of DES and two keys.  We are going to do this in an inside-out fashion.

Step one: pick any 64-bit value, $A$, and for all $2^{56}$ possible candidate values of $k2$ (which I will denote $k2^*$), do the following:

compute $B = DES_{k2^*}^{-1}(A)$,
request $C = E_k(B)$,
request $D = E_k^{-1}(C \oplus T)$.
compute $F = DES_{k2^*}(D)$.

Store all $2^{56}$ values of $F$ in a hash table, along with the $k2^*$ candidate values associated with each.

Step two: For all $2^{56}$ possible candidate values of $k1$ (denoted $k1^*$), do the following:

compute $G = DES_{k1^*}^{-1}(DES_{k1^*}(A) \oplus T)$,
check if there is any $F$ such that $F = G$.

Any such collision will 'suggest' that $k1 = k1^*$ and $k2 = k2^*$ (the stored $k2^*$ candidate value for $F$), a suggestion that can be easily tested in the following manner:

If you know $m$, $m'$, and $E_k(m)$ and $E_k(m')$, then compute $DES_{k1^*}(DES_{k2^*}(m)) \oplus DES_{k1^*}(DES_{k2^*}(m'))$ and check if that equals $E_k(m) \oplus E_k(m')$.  If so, then you almost certainly have the right keys.  From there, $k3$ is trivially deducible.


What is the probability of finding 4 equal bytes? Is it $2^{-32}$ or $2^{-24}$ as one byte is assumed to take a given value and the remaining 3 bytes should have the same value?

There are $2^8$ one-byte (technically, one-octet) patterns. That implies there are $2^8$ four-octet strings where all four octets are identical out of $2^{32}$ possible patterns. $\frac{2^8}{2^{32}}=2^{-24}$


Secure offline treasure hunt Say I would like to create an app that would allow users to organize treasure hunts for their parties. The host of the party would create a list of GPS coordinates for each hiding spot and distribute the list to the guests. At the treasure hunt, guests would then use the app – offline – to get alerts when they are close to a hiding spot, record how long they took to find each treasure, etc.

Given the above setup, a moderately tech-savvy user will just look at the list of GPS coordinates and spoil the hunt. To what degree can this be avoided? In this example, obfuscation would probably be sufficient, but I am interested in the general case.

I’ve considered distributing the list in this form: HASH(QUANTIZE(latitude) || QUANTIZE(longitude)) with the quantization level set to allow the app to give hints at the appropriate distance, but I’m not sure if this could be tweaked to still be difficult to attack.

Is this a know problem? Are there any standard techniques or approaches that
can be (practically) applied to it? I'd also appreciate pointers to related questions/papers.

There's no cryptographic way to keep users from faking their location without trusted hardware. There's also no good way to keep users from running multiple copies of whatever algorithm verifies a location guess in parallel, again without trusted hardware.

The best that can be done for an offline system is to make the is_coordinate_close() function expensive to compute. Still a user can then either bring a powerful portable computer or connect to remote computing capacity to brute force the data set you provide. Additionally, increasing the cost of the function increases the power consumption of your app.

There are two options that get rid of this tradeoff:

cryptographic secrets at the locations (EG:QR codes)
DRM capable hardware (Phone as trusted third party)


Elliptic curve ed25519 vs ed448 - Differences Other than key size, What are some differences between the Elliptic curve ed25519 and ed448?

Edwards25519 is the twisted Edwards curve $$-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$$ over the prime field $\mathbb F_p$ where $p = 2^{255} - 19$.  The coefficient $d = -121665/121666$ was chosen to so that this curve is birationally equivalent to the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, called Curve25519, whose coefficient 486662 was chosen to be the smallest integer in absolute value satisfying the security criteria[1].  The group of $\mathbb F_p$-rational points has composite order $8 p_1$ for a 253-bit prime $p_1$, and its twist has composite order $4 p_2$ for a 253-bit prime $p_2$.  Edwards25519 is designed to make the cost of a discrete log computation cost at least about $2^{128}$ bit operations to break the first of any number of targets.

Edwards448, also known as Ed448-Goldilocks, is the twisted Edwards curve $$-x^2 + y^2 = 1 - 39081 x^2 y^2$$ over the prime field $\mathbb F_p$ where $p = 2^{448} - 2^{224} - 1$.  The coefficient $d = -39081$ was chosen to be the smallest integer in absolute value satisfying the same security criteria as edwards25519, together with the additional constraint that the order of the group of $\mathbb F_p$-rational points have order below $p$, namely $4 p_1$ for a 446-bit prime $p_1$.  There is also a birationally equivalent Montgomery curve $y^2 = x^3 + 156326 x^2 + x$ derived from edwards448, called Curve448.  Edwards448 is designed to make the cost of a discrete log computation cost about $2^{224}$ bit operations to break the first of any number of targets.  Of course, since $2^{128}$ bit operations is already infeasible, edwards448 is really a hedge against modest cryptanalytic advances.

Ed25519 is specifically an instance of the EdDSA signature scheme[2][3] with edwards25519 as the curve, SHA-512 as the hash function, an optional context identifier for compatibility, etc.; likewise Ed448 is an instance of EdDSA with edwards448 as the curve, SHAKE256 as the hash function, an obligatory domain identifier, etc.  See RFC 8032 for the details of EdDSA instantiation, and RFC 7748 for the curve definitions.

The only major substantive differences are in security level and performance:

Security level: Edwards25519 aims for a ‘128-bit security level’, and edwards448 aims for a ‘224-bit “Spinal Tap-grade” security level’—not actually a meaningful difference in the real world unless there is a modest cryptanalytic advance in computing elliptic curve discrete logs.
Key size: Edwards448 points and scalars are 1.75x the size of edwards25519 points and scalars.
Fixed-base scalar multiplication: Edwards448 costs about 1.5x what edwards25519 costs.
Variable-base scalar multiplication: Edwards448 costs about 5x what edwards25519 costs.

(See SUPERCOP dh and sign for details.)

Edwards25519 has $p \equiv 1 \pmod 4$ while edwards448 has $p \equiv 3 \pmod 4$, so there are some differences in protocols beyond DH and signing, but not really substantive: for encoding points indistinguishably from uniform random strings, edwards25519 supports only Elligator 2, while edwards448 supports Elligator 1 and Elligator 2[4], but I don't know of any advantages to Elligator 1; both support a prime-order group encoding that avoids pitfalls with cofactors[5], with a couple of different software implementations, Ristretto  and libdecaf.  Both curves are designed for traditional discrete log applications and pass the SafeCurves criteria; neither curve is pairing-friendly.

In brief, the two curves were designed with essentially the same qualitative security criteria and differ only on quantitative security level and performance.


How Paillier cryptosystem can be used practically to encrypt and decrypt big messages "m"? I want to use the Paillier cryptosystem for encryption and decryption purposes in my research work. But i haven't found a way to encrypt big input messages;
As i want to encrypt the message i,e m :

m = 0xa56f89d6aa234776b22347293429ff074928ab3749cc2837c492b874ebfaba78364ba0912efe862f628347982478b

Key Gen:

p =887, q = 907 , n =804509 ,n² = 647234731081;
g = n+1 = 804510;
λ = LCM(p-1,q-1) = 401358;
μ = L(g^λ mod n²)^(-1) mod n = 637146

Encryption:

Let random r = 1987
 c = ((g^m) * (r^n)) (mod n^2)

How can calculate g^m for such big input m?

If encrypted, then how can decryption work for big messages i,e m?

The Paillier cryptosystem allows to encrypt integers modulo $n$. Therefore, if $m$ is bigger than $n$, encrypting it will lose most of the message - only $m \bmod n$ is retrieved through decryption.

To encrypt a message bigger than $n$, you must break it into blocks, which you encrypt separately. You can for example write $m$ in base $n$, as $m = \sum_i m_i n^{i}$, and encrypt the $m_i$'s separately with Paillier.

Also, regarding how to calculate $g^m \bmod n^2$: note that $g = n+1$, hence

$g^m = (1+n)^m = 1 + n\cdot m \bmod n^2$

(if you develop $(1+n)^m$, you get $1 + nm + n^2\cdot \mathsf{something}$, and the $\mathsf{something}$ disappears modulo $n^2$).


Maximum number of possible keys for a fixed-length password? I'm reviewing some information and possibilities regarding key space size following a unique password requirement, as it were.

This particular requirement is a fixed-length password of 12 characters, with exactly 1 capital letter, and exactly 1 digit.

My understanding is that, let's say we have 26 letters, then we'd take 26^{(number of characters)} so for a 10 character password, your possible key combos is in the neighborhood of 141,167,095,653,376.

If you included all upper case and lower case, that'd be 52^{(number of characters)}, so on and so forth--the question I'm stumped on is how that changes if you have exactly 1 of a UC and exactly 1 of a digit, if it does at all.

A password space with $n$ lower case letters, 1 upper case letters and one digit in any order is of size: $26^{n+1}*10*(n+2)*(n+1)$

The choice of the letters the times the choice of the digit times location of digit times location of the uppercase letter.


Non partial homomorphic encryption It seems that AES is non homomorphic. I am seeking a public key non homomorphic encryption that has been proved to be such or at least is accepted as non homomorphic. The internet search leads to those that are homomorphic. Any lead?

mikeazo has the answer in a comment:

  RSA with proper padding

So, use RSA (or actually any trap door one way function) with proper padding. For instance: OAEP padding. These are designed to achieve indistinguishability, which has also been mentioned in the comments. The padding which uses a hash internally kills all homomorphic properties of the cipher.


RSA encryption with private key and decryption with a public key When using the RSA cryptosystem, does it still work if you instead encrypt with the private key and decrypt with the public key? What about in the case of using RSA for sender authentication?

Mathematically it work just fine. "Encrypt" with the private key, "decrypt" with the public key. Typically, however, we say sign with the private key and verify with the public key.

As stated in the comments, it isn't just a straight forward signing of the message $m$. Typically a hash function and padding is involved. Also, often one has a separate key pair for signing.

As you can see, there are a number of caveats, but in general you are correct, it is used for sender authentication.


How does PUF hardware help in software activation? I have read that one of the PUF's application is software licensing, but do not know how. I have been reading different articles and forums (such as here), but still not clear for me.

One vague point for me is that PUF is a hardware and I do not think that vendors provide a separate hardware rather than maybe just a CD including the software.

I also want to know what is the functionality of PUF in this application? Key generator (like explained here)? or chip ID (like explained here - minute 16)? I found a protocol explained in here, but it is not very clear if PUF can act as product key, hardware ID, or activation number.

I was wondering if some one can explain it to me or give me some references.

You're right about hardware activation devices for desktop applications.  Dangling dongles outa your printer port is quite legacy.  New applications tend to use some form of on-line activation system. You see this in games  and Windows.

But it is becoming more common in the embedded world, where it can act as product key, hardware ID, or activation number.  Consider the most fundamental behaviour of a PUF. It allows a  challenge–response protocol to generate a non clone-able set of values, each usually (but not necessarily)  one bit wide, with some degree of repeat ability.  Using fuzzy extraction, secure sketches, error correction and compression, a single number can be produced with very good reliability.  The PUF (oscillator based) with multiple challenge-response pairs would live within an FPGA like so:-

And that's it: a set of bits.  Use the set as you will.  It could very well simply be the (uncloneable) device ID.  PUFKY is a design for a random 128 bit cryptographic key extracted from ring oscillators.  Intel have   Stratix FPGAs/SoCs that incorporate on-board SRAM PUFs for protection against counterfeiting, cloning or reverse engineering. It can also be the key for cryptographic communications from the chip. You can see where the PUF fits into the Stratix:-

Circling back to software activation, a PUF is the evolved in-built "dongle" of yesteryear protecting modern software.  It's just that the 'software' these days can be intellectual property like IP cores, gate/block configurations, digital signal processing algorithms etc. and communications data within and around embedded devices.


Recommended Shake256 digest size for KMAC based HKDF On the wiki page for HKDF, in the Python Implementation, there is a hash_length variable for the sha256 digest length, used in the hmac in the hmac_sha256 function.

However, if I wanted to replace the hmac with a kmac, I would have to change the hmac(...) into kmac(...), where the underlying hash algorithm is the shake256 algorithm (XOF) - with variable output length.

So my question is what is the recommended length to set the shake256 digest size to when incorporating it into a KMAC based HKDF?

HKDF already has expansion on top of the MAC that it is based on. What would be the point of using a XOF for that? Why not use the XOF directly or define a different KDF? Because having two different methods for expanding the output seems troublesome to me.

If you're going to use HKDF then use one of the normal SHA-3 / HMAC functions with it. Sure, that's less than optimal, but commonly that's not a huge issue for deriving a limited amount of key material anyway.

Any form of HKDF that redefines the PRF used to derive the key material will not be compatible with anything out there. That's true regardless of the XOF and KMAC standardization.


What makes the Discrete Logarithm Problem hard? I am missing a crucial piece of the maths behind the DLP, and I'm hoping someone can give me a really dumbed down answer..

If  $h=g^x \bmod p$  and we're working in the group $Z^*_p$, why can I not find $x$ in linear time given I have $h, g, p$, and $Z^*_p$? I have at most $\operatorname{ord}(Z^*_p)$ iterations to run through?

I can't see what aspect of the maths I'm obviously misunderstanding. Is it not linear to calculate $g^x \bmod p$ for some $x$? That's my only guess.

It is true that you have in the worst case $\operatorname{ord}(Z^*_p)$ values to test. However, the complexity of a problem is actually measured according to the size of the input of the problem in computer representation which is binary.
Here the inputs to our problem are h and p. These two are integers both of size $log_2(p)$ at most in computer binary representation. And the algorithm would take $\operatorname{ord}(Z^*_p) = p$ iterations. However, $p = 2^{log_2(p)}$, so we can clearly see that the number of iterations required is actually exponential to the size of our input of the problem. Which is why the discret logarithm problem is hard.
When you usually see complexities of the form $O(n)$ or $O(log(n))$, we actually assume that the size of our problem is $n$ in computer representation, without explicitely saying it.


What is the proper way to generate a fixed length key from a variable length password? The password is entered by the user and the key is processed locally. Neither the password nor the key will be stored, only used and forgotten (but hopefully not by the user). Is SHA256 by itself strong enough for this purpose? Do I really need a salt in this case?

I've looked around Google and other StackExchange questions, but they all assume the password and/or key will be stored. In any other case it probably would be stored, though my case calls for using it and forgetting it.

Using simply a hash function is not strong enough, even if the key is not stored. We the users tend to choose very crappy passwords, such as "1234" or "password". If you only use a hash function for generating the key, then there are a lot of chances that the generated keys are SHA256("1234") or SHA256("password"). That is, this method is very vulnerable to brute-force attacks. An attacker could simply hash common passwords, similarly to a dictionary attack.

It is also possible to perform brute-force attacks on established key derivation methods, such as PBKDF2 and scrypt, but the probability of success is extremely small. These methods are specifically designed for this, for example by using a salt value (in order to prevent dictionary attacks) and a lot of iterations of the hash function (in order to slow brute-force attacks).


Is this symmetric key MAC-then-encrypt auth token methodology secure? NOTE: This question originally conflated a "digital signature" and a "MAC", which I've since learned are not the same thing. Any references (in the answer or any comments) to a "signature" should be read as a "MAC".

I'm experimenting with auth tokens and I'm trying to wrap my mind around the best method.

Goals

Upon successful login, a token is created containing the users accountID, a nonce, and an expiry. The token is then passed back to the client to be used for the next request.
The client passes the token back to the server with each request to identify the origin (accountID) of any given request.
The token contains a nonce that's changed with each request.
A MAC is created from the plaintext value to ensure it's not been tampered with.
The plaintext value of the token (including the MAC) is then encrypted to ensure it's securely obscured.
The client is never privy to the macKey or the encryptionKey. The client is not intended to ever have access to the plaintext contents of the token.

Current Method

///process.env.TOKEN_ENCRYPTION_PASSWORD = '13sd4089f-268c-483d-9e82-jk3c1b47c77a';
///process.env.TOKEN_MAC_KEY = '1fde05f4-268c-483d-9e82-85fc1b42321';

/// Successful login by user ...

var token = {
    nonce : 'SOME-UUID-GOES-HERE',
    accountID : 'account-12345',
    expires : 1234567890
};

token.mac = crypto.createHmac('sha512', TOKEN_MAC_KEY)
                  .update(JSON.stringify(token))
                  .digest('base64');

var encryptedToken = cryptoJS.AES.encrypt(JSON.stringify(token), TOKEN_ENCRYPTION_PASSWORD).toString();

response.send({
    message : 'Created, MAC'd, and encrypted an auth token.',
    authToken : encryptedToken
});

Questions

Is it secure, in this case, to employ a MAC-then-encrypt method? I've read several opinions on this and walked away more confused than when I started.
I've read that cbc-mode should be used when employing a MAC-then-encrypt method. Is this the default mode for CryptoJS.AES.encrypt()?
CryptoJS.AES seems pretty generic. Is this defaulting to AES256? Or is that something that I need to explicitly declare in my code?
When passing a string to CryptoJS.AES.encrypt() I've read that it automagically generates a key and and iv 'behind the scenes'. Would it be more secure to generate my own key and iv, or should I just let CryptoJS handle that?
Is there more security to be had by employing a MAC-encrypt-MAC method, or is that just adding complexity to my app logic?

Is it secure, in this case, to employ a sign-then-encrypt method? I've read several opinions on this and walked away more confused than when I started.

First of all, given that your sample code is using HMAC, not digital signatures, I assume you mean MAC-then-encrypt.

The generally safe way to combine a MAC and encryption is encrypt-then-MAC: first encrypt the message, then compute a MAC on the ciphertext (including the IV and any associated data you may have!).  When decrypting, first verify the MAC, and only then try to decrypt the message.

Encrypt-then-MAC is safe because it guarantees that the MAC and the cipher each only need to do their own job: when encrypting, the MAC only receives input that has already been encrypted, so it cannot accidentally leak information about the plaintext; when decrypting, the cipher only receives input that has already been authenticated by the MAC, so it doesn't need to worry about securely handling forged or modified messages.

However, MAC-then-encrypt (or even MAC-and-encrypt) can be safe if the MAC and the cipher are chosen appropriately.  In particular, a sufficient condition for the security of MAC-then-encrypt is that the cipher mode must be length-preserving — that is, the ciphertext (not counting the IV) must be exactly as long as the input plaintext.

The CFB, OFB and CTR modes are all length-preserving, but CBC is not (unless combined with a modification known as "ciphertext stealing").  In particular, because normal CBC mode requires messages to be padded to an integer number of cipher blocks, it is often vulnerable to padding oracle attacks unless protected with a MAC applied after encryption (and thus verified before decryption).  Thus, you should not use CBC mode with MAC-then-encrypt.

  I've read that cbc-mode should be used when employing a sign-then-encrypt method. Is this the default mode for CryptoJS.AES.encrypt()?

That's hard to say, and may depend on which version of CryptoJS you're using.  This page says the default is OFB mode.  This page (for CryptoJS v3) says it's CFB.  Both of those appear to be unofficial third-party sources, but I haven't been able to find any comprehensive official documentation for this library.  Apparently it's "still a bit sparse." :(

In any case, as noted above, you should not use CBC mode with MAC-then-encrypt.  If you want to use CBC, apply the MAC after encryption.

  CryptoJS.AES seems pretty generic. Is this defaulting to AES256? Or is that something that I need to explicitly declare in my code?

See previous answer.  According to the linked Google Groups post (which may or may not be reliable, of course), the library can handle AES-128, AES-192 or AES-256, presumably depending on the size of the key you pass in.  If you pass in just a password, I have no idea which AES variant it'll choose.

(I'd also like to take this opportunity to reiterate my dislike of poorly documented crypto libraries.  It doesn't matter how well your library is coded, if nobody can tell what it's supposed to be doing and how to use it correctly and safely.)

  When passing a string to CryptoJS.AES.encrypt() I've read that it automagically generates a key and and iv 'behind the scenes'. Would it be more secure to generate my own key and iv, or should I just let CryptoJS handle that?

It looks like if you pass the encrypt() method a plain string as the key, it assumes that this string is a user-supplied password, and applies a password-based key derivation function like PBKDF2 on it.  Such functions are deliberately designed to be slow, in order to resist brute-force password cracking.  Thus, whenever possible, it's more efficient to call the key derivation function only once yourself, and to store the raw AES and/or HMAC key that it outputs.

You almost certainly don't have any reason to supply your own IV; any decent crypto library should be able to generate perfectly good random IVs for you.

  Is there more security to be had by employing a sign-encrypt-sign method, or is that just adding complexity to my app logic?

In general, there's no point in doing MAC-encrypt-MAC instead of plain encrypt-then-MAC.  That said, it shouldn't hurt either (beyond wasting a few CPU cycles, and increasing your ciphertext length a little), and it might protect you against some implementation mistakes (like forgetting to include the IV in the outer MAC input).

However, what you really should do, if at all possible, is use an integrated authenticated encryption mode like SIV (my current personal favorite) or GCM (or even the new GCM-SIV mode that combines them).  Those encryption modes come with message authentication built in, and take care of combining the encryption and the authentication safely and correctly.

(For actual digital signatures, sign-encrypt-sign might sometimes be useful, since the double signing protects against some attacks where e.g. the attacker takes a valid encrypt-then-signed message, strips off the signature and substitutes their own, or where a malicious recipient decrypts a signed-then-encrypted message and resends it to someone else, keeping the original signature.  In most cases, however, there are more effective ways to avoid such attacks.  See e.g. this earlier question for more details.)


Why I can't permutate an email and get away with it? I can understand why a simple substitution cipher can be broken easily using English letter frequencies, and even English digrams like th can be used. Also a complete random substitution will have a key length of $26!$ which can be done (around $2^{88}$, maybe NSA).
But what about emails? According to Google, emails have an average word count of 400 words. So I guess letter count will be at the very very least 800 letters. Brute forcing $800!$ (assuming a completely random permutation function) is not possible.
I also guess English letter frequencies can't be used as these frequencies apply to all English words and these letters can be used to construct different words. But still, it's not secure to use only permutations for encryption.
So why is that? How to get around brute-forcing $800!$ permutations?

I can understand why a simple substitution cipher can be broken easily due to English letter frequencies can be used and even English diagrams like th can be used, also a complete random substitution will have a key length of 26! which can be done(around 2^88 maybe NSA)

The first part is correct. A thousand years old Frequency analyses can break this very easily. Many times this is given as homework on the Introduction to Cryptography courses. Note that this may require longer text in some languages or in some contexts (Gabel's Novel without e). In real-life both are assumed to be known since the attackers know you.
Trying all permutations is not the correct way since it can lead to many false positives and a long process to go.

but what about emails according to google emails have an average word count of 400 words so I guess letters count will be at very very least 800 letters. Brute forcing 800! (assuming complete random permutation function) is not possible. I also guess English letter frequencies can't be used as these frequencies apply to all English words and these letters can be used to construct different words. But still, it's not secure to use only permutations for encryption so why is that, How to get around brute-forcing 800!.

I think you mixed about how the permutation cipher works. Or you are referring you generate a larger permutation like the permutation of two characters instead of one where you will have $26^2$ elements to permute in the standard English letter. That will contain $26^2! = 676!$. And it has 1622 decimal digits, try here, or around 5386 bits. This is still applicable to diagram-based frequency attacks therefore insecure.
Now, what about the key size? How do you exchange this key? It is not practical since you need to send an array of size $676*2^{10}$.
A cryptosystem besides being secure needs to be practicable, and this is not practicable. The common wisdom is using the substitution/permutation (confusion/diffusion) to achieve a computationally secure cipher like AES and be practical.

The kind of permutation I mean is we have 800 letters so 800 positions are possible. The first letter will go into one of 800 positions the second letter goes into 799 positions and so total =800!. From your answer, I guess this approach is completely safe (if letters length is large), but not practical right?

That is a positional permutation that only scrambles the letters. It is not as secure as one may think of since all characters are there. It may take time to place them correctly. The e-mails have some known beginning and ending and that will help to find the permutation. And keep in mind that that is not even secure under the Known-Plaintext Attack. The key size still is the issue.


If you iterate a cryptographic permutation long enough will you map the input to itself? Given a cryptographic permutation $\{0,1\}^n \rightarrow \{0,1\}^n$ does it follow that after some number of iterations you must eventually map the input to itself?

Any permutation $f$ (cryptographic or not) on a finite set $X$ satisfies $f^n=id$ for some $n>0$.

To see this, note that there's only finitely many functions from $X$ to itself. Hence $f,f^2,f^3,\dots$ aren't all distinct, so $f^k=f^l$ for some $k$ and $l$ with $l<k$. Now $$id=f^{-l}f^l=f^{-l}f^k=f^{k-l}$$ so we can set $n=k-l$.


What "Tag Length" should be used for the EAX MAC? Since EAX is very flexible with regard to the length of the calculated MAC (what they call "tag" is the MAC value right?), and the EAX paper as well as other documentations carefully avoid suggesting any value for the length of the MAC, is there anything to take into consideration before setting for a value?

Is the length just "proportional" with collision resistance or are there also other more subtle consequences depending on the MAC length?

While the EAX mode permits truncating the tag to any length $\tau$ between 0 and $n$ bits, where $n$ is the block size of the underlying block cipher, this should only be taken as a statement that truncating the tag in EAX mode does not introduce any security issues beyond the obvious (an attacker only needs $2^\tau$ attempts to froge a $\tau$-bit tag by brute force).  Still, in the absence of a particular space or bandwidth constraint that would require a shorter tag, I see no reason not to use a full-length tag ($\tau = n$).

(I suspect the main reason for introducing a variable tag length into EAX was because CCM had one; see the table in figure 4 of the EAX paper you cited.  EAX was designed as a replacement for CCM, and so one of the main design goals was to be able to do anything CCM did, only better.  If EAX had been specified with a fixed tag length, someone might have cited that "missing feature" as a reason to use CCM over EAX.)


Web Crypto API - deriveKey vs. deriveBits? I have some questions about deriveKey and deriveBits for web crypto API.

I am confused about the state of these APIs. I do understand deriveKey generates a native key object whereas deriveBits just generates a byte array. However, when I look at Mozilla documentation https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto it doesn't even include deriveBits() in the API list. Is this one of those features that are "experimental" and may be dropped in the future? Or is this some political gesture?
What makes this even more confusing is how Safari doesn't even implement deriveKey() for PBKDF2 at all, whereas they did recently implement deriveBits() for PBKDF2 https://webkit.org/blog/7790/update-on-web-cryptography/ Does this mean I have to give up on using deriveKey() and use deriveBits() in order to support all platforms?
Assuming that #2 is true, I'm thinking of

using deriveBits() to first generate a bytearray
and then feed it into importKey() to generate a symmetric AES key
and use this process as an alternative to using the deriveKey() API. Is this the way to go?

It sounds like deriveKey is just a composition of deriveBits and importKey.  There is no cryptographic difference between ‘generating an AES256-CTR key’ and ‘generating 256 bits uniformly at random’—this is at most an API distinction.  Support for one or the other is inconsistent, apparently, even though they both appear in the W3C recommendation.  How to get around this in practice in a web application is a question for a forum on JavaScript coding, not crypto.se, however.


How to supply the GCM authentication tag to the OpenSSL command line tools? I'm using AES-256-GCM for authenticated encryption. In order to decrypt, the ruby OpenSSL library requires an auth_tag parameter (in addition to the key and iv). This, according to the ruby docs, is because authenticated encryption is only supported with associated data (AEAD).

How can I use this auth_tag to decrypt? The node.js crypto library doesn't have an option for it, so I'm trying to use the openssl command line tool. However, looking at the docs, even that doesn't have an option for supplying the authetication tag.

Here's a NodeJS AES-GCM module. Or alternatively, you can use the OpenSSL library to write your own GCM decryption code, here's a quick tutorial.

The OpenSSL utility has historically not supported GCM encryption/decryption via command line parameters, likely due to the auth tag issue. I don't think that anything has changed since then, so you may want to take another approach.


Cipher Block chaining but with encrypting the plain text first then xor with IV I have just learned about the CBC mode of operation and that it gives the cipher by xoring the plaintext m0 with random IV and then encrypt it with random key and I found out that the CBC is not CPA-secure if the IV can be predictable.

I'm considering a new mode like what if CBC work by encrypting the plain text and then xored with the IV is it still CPA secure? and is still the IV can be predictable over CPA attack?

$C_0 = IV \oplus E(P_0)$ and $C_i = C_{i-1} \oplus E(P_i)$ for $i>0$

My guessing is that it is not secure because im not encrypting the IV im only xoring it with the E(m), an attacker can do a CPA attack on the E(m) and then xor it with the IV that he has guessed it  and then can compare it with the Cipher and guessed the key.

It is a really bad idea to have $$C_i = C_{i-1} \oplus E(P_i).$$ The ciphertext leaks a deterministic function of each plaintext block, as  $$C_i \oplus C_{i-1}  =E(P_i).$$ Now an eavesdropper can easily tell whether $P_i = P_j$ by checking whether $$C_{i-1} \oplus C_i = C_{j-1} \oplus C_j.$$


Why does DESX break if one removed post whitening? DESX uses whitening to strengthen against brute force attacks. What is an attack one could use to recover DESX's pre-whitening key with only two known ciphertext/plaintext pairs, given that the attacker can successfully disable the post-whitening step?

So far I have come up with this:

The attacker could use an active fault injection attack to reduce DESX to return the results after round 1, effectively skipping rounds 2 to 16.
Starting from the two ciphertexts, the attacker could then find all inputs to the s-boxes to recover all s-box input candidates.
Starting from the two plaintexts, the attacker can find E(whiteningKey) xor roundKey combinations that produce the same s-box input candidates.

My problem now is this: The attacker has no way other than brute force to separate the whitening key from the round key in the equation above. Given the fact that brute force takes on average 2^55 attempts, this would be incredibly slow without special FPGA hardware.

The goal of DESX is to improve the security above the 56-bit level offered by DES. So an attack that's merely as expensive as brute-forcing the DES key is an attack, even if it's still rather expensive.

Define $E_{K,W}^\prime(P) = E_{K}(P\oplus W)$ and $D^\prime$ as its inverse. Then we can relate the two known pairs $(K_1,P_1)$ and $(K_2,P_2)$:

$$\begin{eqnarray}
P_1\oplus P_2 &=& D^\prime(C_1)\oplus D^\prime(C_2)
             \\ &=& (D_K(C_1)\oplus W)\oplus (D_K(C_2)\oplus W)
             \\ &=& D_K(C_1) \oplus D_K(C_2)
\end{eqnarray} $$

Since $P_1\oplus P_2 = D_K(C_1) \oplus D_K(C_2)$ only involves $K$ and not $W$ we can simply brute-force that 56-bit key, ignoring $W$, showing that using only pre-whitening does not improve security compared to plain DES. A similar argument can be applied to post-whitening. Note that this attack does not rely on the particular structure of DES (except having a key short enough to brute-force) and can be applied to any other blockcipher.


Two-timing a one-time pad Is a one-time pad still breakable on a depth of 2+ if the plaintext is completely random?

I'm assuming this idea is wrong, mostly because it occurred to me, but let me walk you through my logic so you can concisely correct me:

A one-time pad is unbreakable on a depth of 1 because a comprehensive
brute-force attack will yield numerous reasonable plaintexts.
Upon a depth of 2 or more (e.g., the same pad used with multiple
plaintext messages) it becomes breakable:

Brute-forcing message $A$ may result in (say) 10 plaintexts
Brute-forcing message $B_n$ may result in 10 plaintexts each
The key that commonly results in valid plaintexts is probably the one-time pad used.

If the plaintext is completely random, then this attack won't work, as there is no way to discriminate between "plaintext output" and incorrect outputs.

I was thinking of ways to pass encryption keys and IVs - which, if properly generated, should be very random data - between two systems.  Let's presume they have a trusted channel by which they can exchange the one-time pad, but wish to use an untrusted channel for exchanging more voluminous data.  They can use symmetric encryption to protect data across the untrusted channel if they have away to agree upon the keys used for the symmetric encryption.  If a one-time pad could be used to securely exchange symmetric keys across that untrusted channel, then the sparse use of the trusted channel (exchanging the one-time password) could enable encryption across the untrusted channel.

Would this, instead of a one-time pad, be a shared secret? A key derivation function?

Some "please don't beat me up" caveats:

Yes, I realize this sounds like I'm breaking the "never invent a new cryptosystem" rule, and I realize the importance of that rule.  Rather, I'm using this as a gedankenexperiment to understand encryption better, and/or as a way of identifying an existing model that describes what I'm suggesting.
Yes, I realize SSL is the appropriate model for what I'm suggesting - the certificate exchange and handshaking is the "trusted channel", enabling symmetric encryption of the general data over the "untrusted channel".  I have reason to contemplate lighter-weight solutions.

I humbly appreciate any edification you can give me.

The scheme as you describe it in itself may be secure in some (especially) theoretical environment.
However, I don't suggest to use it, because any attempt to use of values passed between the peers can possibly undermine the security of the scheme as can e.g. insecure RNGs.

I have expressed a few concerns below.

I'm bit concerned about calling the scheme OTP anything, because this this is not OTP. A comment from daniel already mentioned when this practice is secure:

As long as you have after each use, n+1 unknowns on n equations, that's the preshared value plus each key value, seems hard to break (or impossible). Another thing is if it's advisable to use such a protocol for other reasons.

This was in the question:

  I was thinking of ways to pass encryption keys and IVs - which, if properly generated, should be very random data - between two systems.

What do you do with these keys and IVs? Consider they are for instance, used to encrypt data. Also suppose the adversary gets hands on ciphertext and (partial) plaintext processed with these encryption keys (unknown to adversary) and IVs:

The block cipher modes of operation (generally) do not protect IV from disclosure. This is because IV should be value unpredictable by the attacker before it is used. It may be, however, possible for attacker to determine the used IV afterwards; occasionally even pretty easily.
The adversary can use computational attacks the keys instead of information theoretic attacks (like against OTP. This may not be great deal, as for many algorithms keys are pretty hard to break).

Example of foul play

I decided to write an example of foul play, based on my understanding of the scenario written. It is not illustrated very clearly in the question what are the possible uses of communicated values, but this explanation tries to capitalize my point that using the exchanged values easily causes security issues. It is possible the example as-is does not apply here.

Assume that the Key+IV secured with multi time pad is used to do AES-CBC. Also assume that each Key+IV is "secured" with the same pad. The attacker can alter data messages sent (known as $M_i$ below).

We get for first keys and IVs (assuming this scheme uses "XOR" operation), A is multiply used pad:

$M_1 = A \oplus (Key_{1} || IV_{1})$
$M_2 = A \oplus (Key_{2} || IV_{2})$

The attacker may affect contents of $Key_{1}$ and $Key_{2}$. It may be possible to e.g. set keys and IVs to be the same for two different uses. (By replacing $M_2$ with $M_1$.)

Some other concerns

  Let's presume they have a trusted channel by which they can exchange the one-time pad, but wish to use an untrusted channel for exchanging more voluminous data.

How much faster your untrusted channel is than trusted channel, i.e. how many times you intent to reuse "OTP"?

Where do you get the "plaintext stream" containing passwords and IVs? It is common that random number generators do not provide completely i.i.d. as is required by the scheme you describe.

If you have "OTP" that is kept scret and you use it multiple times to pass secret, this actually becomes some sort of secret sharing scheme. You should examine them to understand how to use them correctly.


What are the capabilities of passive and active adversaries? I have trouble understanding what exactly the capabilities of passive and active adversaries are on paper and in the real world.

It depends on the situation. In crypto, we tend to think of a passive adversary (Eve) as someone who can listen to all communications sent between two parties (Alice and Bob).  So, you create a security goal based on the "power" of your adversary. If all that Eve is doing is listening in on communications, Alice and Bob need to ensure that Eve cannot understand whatever she reads. In the real world, this is a very real threat. For example, suppose we are both sitting in a cafe with public WiFi. If I control the network or actively sniff for packets (something like Wireshark), I can read all of your communications with the website you are talking to/browsing. So, the natural goal is to prevent me from understanding what you are communicating. The natural answer is strong encryption.
An important question is,  "how strong is strong enough?" The answer is complicated and has given way to several varying degrees of strength. Most security models are described as a game between you and the adversary. One such model is chosen plain-text attack.  That is, suppose the adversary Eve is given oracle access to a black box decryption algorithm. That is, she can ask for the encryption of $m_1,...,m_k$ for some reasonable number of $k$ to get cipher texts $c_1,...,c_k.$. The adversary then picks two messages $m_0^*,m_1^*$ and is given the encryption of one of the two messages chosen uniformly at random $c_b$ where $b\in\{0,1\}$. If the adversary can correctly guess if $b=0$ or $b=1$ with greater than $1/2$ probability, then the adversary wins.
Now suppose Eve is allowed to change messages in transit. That is, suppose you are logging on to the Bank of America, and you ow me \$100. If I am Mallory (the name given to an active adversary), I can flip some bits of the message in transit and hope that my changes make the amount larger. Or worse, I could throw out your message and inject my own! Now you went from paying me \$100 to \$1000. We, of course, want to prevent this.
This is where message authentication codes come into play. We want to be able to "sign" our messages so that others can be sure that they came from us and not from Mallory. In practice, if I see you sending messages, you want this signature which is a part of the message (commonly called a tag for symmetric algorithms) to be what is called existentially unforgeable. That is, even if you intercept a bunch of my messages, and see a bunch of tags, you will never be able to produce a valid message and tag pair. The model is normally described as an adversary unable to distinguish between an algorithm that rejects every single message and tag combo and one that actually uses the message authentication code. Combining these two protocols, in the theoretical world, you get authenticated encryption where you are sure that not only is it Alice's message, but even Mallory cannot read it. If Mallory tries to alter it, the message will be rejected.
In practice, many things can go wrong. Just because I write a theoretically secure cipher on a blackboard does not mean there is nothing an adversary can do! Software engineers are famous for shooting themselves in the foot, and there is always an issue of backward comparability. You could write entire books on how difficult it is to implement crypto. That is because our models pretend computers are back boxes--it turns out that they are not.  There are documented attacks on just about every cipher you can think of that make use of sounds computers make, the time it takes to execute, and power consumed by the computer. You can also perform protocol downgrade attacks that force victims to use broken crypto (basically every attack on TLS that has been written about in the last few years uses this sort of attack). The short answer for this is modeling real worlds attacks is an extremely daunting task.


Given ciphertexts C1, C2 of different messages P1 and P2; how can we prove that both C1 and C2 were encrypted using public keys of the same pair? I vaguely recall reading about a scheme that accomplished this but am not able to figure out which one it was. For the sake of brevity I'm gonna omit any nonces.
Let's say we have an asymmetric keypair: (Kpub, Kpriv)
An observer is provided:
C1 = E(Kpub, P1)
P1 is known. It can verified that by performing E(Kpub, P1) the result is indeed C1.
The observer is then provided:
C2 = E(Kpub, P2)
P2 is not known to the observer, but they are provided a proof that they can use to verify that C1 and C2 are indeed ciphertexts that can be decrypted by the same private key (or in other words; were obtained by encrypting using the same public key).
I think ElGamal and NIZK were part of the proof but I'm not sure. Any ideas?

Chaum-Pedersen protocol tweaked with Sigma AND composition should do.
The high level intuition: using Chaum-Pedersen protocol for DH-triple, one can prove knowledge of secret witness $\alpha$ in the following relation in (honest verifier) zero-knowledge:
$$
\mathcal{R}:=\left\{((x, y, z), \alpha)\in\mathbb{G}^3\times\mathbb{Z}_q: \quad y=g^\alpha \land z=x^\alpha\right\}
$$
where $(x,y,z)$ is the statement ("claiming that they are a DH-triple")
Recall the following ElGamal encryption scheme:

Now let $y$ be your public key and $\alpha$ your secret exponent (secret key), let $x$ be the first part of the ElGamal ciphertext above (namely $v$ in the screenshot), and naturally $z = y^\alpha = g^{\alpha\cdot\beta}$ is the shared secret and let it be the $w$ in the ElGamal encryption process.
With Chaum-Pedersen Sigmal protocol above, we can prove knowledge of a secret key that produce a ciphertext for a certain message.
Finally composing two Sigmal protocols, one for each (message, ciphertext) tuple, using AND-proof construction, the verifier could easily verify that the two ciphertexts are encrypted under the same key as the two statements shared the same $y$. $\blacksquare$


How does Random Oracle and Standard Model differ? I am new to Crypto field. Many papers are boasting of not using Random Oracle model. Instead, those prove security in Standard Model. I am surprised how do these models differ. Can anyone please clarify me? Does using Hash function mean that the paper makes use of Random Oracle?

The random oracle model is a heuristic that assumes the existence of a truly random function to which all parties involved in a protocol, good and bad alike, have access. Since in reality no such function exists, random oracles are instantiated with hash functions and one heuristically assumes that a hash function behaves good enough to be a replacement for random oracles. Random oracles are nice as they allow to prove protocols secure while they are still practically efficient.

Since there are theoretical results showing that there are protocols that are secure in the random oracle model but trivially insecure whenever the random oracle is instantiated with any hash function, standard model constructs, i.e., constructs that do not rely on random oracles, are nicer from a theoretical perspective. Standard model means that the protocols only rely on standard cryptographic assumptions (DDH, CDH...) in their proofs.

No, using hash functions does not mean that you are in the random oracle model - only if you model them as random oracles. If you rely for instance on the collision resistance of a hash function, you can be still in the standard model.


Random Bytes in TLS Handshake During the TLS handshake, there are random bytes sent from the server to the client and random bytes sent from the client to the server.

Since these bytes are sent in clear text, what is the relevance of them being random? I thought randomness was mostly about lowering the likelihood that these numbers could be guessed. If they are passed around in clear text; whats the importance of the randomness?

Also, what exactly are these random bytes used for?

Since these bytes are sent in clear text, what is the relevance of
  them being random?

They are a guarantee that the other party with whom you wish to communicate is actually interactively there and you're not just seeing a recorded session that is being replayed to you, potentially impersonating somebody else.
The randomness helps in this to prevent attackers from simulating a bunch of sessions beforehand and then picking the the relevant one for you.

  Also, what exactly are these random bytes used for?

Their actual usage is limited to being additional input to the key based key derivation function that transforms the pre-master secret into the master secret (section 8.1 RFC 5246).


Are there any symmetric Partial Homomorphic Encryption Schemes? Note that I am asking specifically for Partial Homomorphic Encryption (PHE) schemes and not Somewhat Homomorphic Encryption (SHE) schemes. I believe there are several SHE schemes that are symmetric but I am not familiar with any PHE schemes that are symmetric.

It depends on what you mean by "symmetric". As mentioned in the comments, you could use an asymmetric scheme and let $\mathsf{k} = (\mathsf{sk},\mathsf{pk})$. This seems unsatisfying though.

If you want symmetric to exclude this definition, a natural way to restate your question is "Are there any partially homomorphic encryption schemes in Minicrypt", in the sense that you can build them from solely the existence of a one-way function. I'm unsure of the answer in this situation, but there's some evidence against it being true.

For motivation, an easy way to construct a somewhat homomorphic encryption scheme is from $\mathsf{LWE}$.
This states that:
$$(A, As + e)\approx_c (A, u)$$
for $A$ and $e$ distributed correctly.
Standard LWE encryption schemes then use $As+e$ as a "blind", and then apply the one-time pad.
This design pattern of "Use a pseudo-random function to construct a "blind", then use the one-time pad" is fairly common. What gives LWE its homomorphic property is that the pseudo-random function $(A, As+e)$ is somewhat homomorphic.

So, a naturally way to try to answer your question would be starting with some one-way function / pseudo-random function that is partially homomorphic. A recent result showed that taking various minicrypt primitives and adding an additional partial homomorphic property is sufficient for many Cryptomania primitives (and therefore already takes you out of Minicrypt). This of course doesn't answer your question in the negative, but it does rule out a natural class of approaches to designing such a scheme while staying within Minicrypt.


set of integers modulo an integer q in lattice Some literature about lattices set $\mathbb{Z}_{q}$ in $[-\frac{q}{2}, \frac{q}{2})\cap \mathbb{Z}$ but not $[0,q-1]$ such as "lattice signatures without trapdoors" and "lattice based  blind signatures", I don't know the reason. Thank you for explain the reason for me if you know it.

Well, these lattice schemes need to define a 'small vector' $\epsilon$ in such a way that the multiplication of two small vector elements $\epsilon_0 \times \epsilon_1$ is still small; that is, for a random element $A$, we still have $A \approx A + \epsilon_0 \times \epsilon_1$

One way to do this is to define a 'small vector' as one whose elements all have small absolute values; if you define 'small absolute value' tightly enough, then the elements of $\epsilon_0 \times \epsilon_1$ (ignoring the modulus operation) will still probably [1] have terms with absolute values less that $q/k$ (which is 'close enough' - the original schemes had $k=4$).

Of course, you might ask "why don't they define small vectors to have elements with small nonnegative terms?".  Well, if they defined the ring over $x^n+1$ (for example), then something strange happens.  Element $i$ of $A \times B$ can be expressed as

$$A_iB_0 + A_{i-1}B_1 + … + A_0B_i - A_{n-1}B_{i+1} - A_{n-2} B{i+2} - … - A_{i+1} B_{n-1}$$

Specifically, there are $n-i$ terms which are added to the final product, and $i$ terms which are subtracted from the final product.

For small $i$, there are a large number of added terms; if $A, B$ consists of small nonnegative elements, then the result will be strongly weighted toward the positive.  For large $i$ (just a bit smaller than $n$), the result will be strongly weighted toward the negative.  Hence, the result will have a distinct slant, and that's harder to reason with.

In contrast, if with generate $A, B$ with small absolute values (with no bias between positive and negative), no such bias exists; the distribution of the elements of the result is independent of the position within the vector.

[1]: This is where the probability of decryption failure comes in; most systems don't define the error terms small enough that decryption failure can't happen


Diffie-Hellman Key Exchange attack on small secret keys The question as the title suggests is based on the key exchange with Diffie-Hellman protocol and is something like this:

*"We have intercepted a communication between Alice and Bob: intercepted-communication

We also have read out the code Alice was using to communicate: alice.py

Unfortunately, the flag is no longer in the code. Can you reconstruct it from the communication between Alice and Bob?

Usually, the Diffie-Hellman key exchange can not be broken easily. However, our analysts told us that Bob used a small secret key that can be brute-forced."*

I am having a really hard time understanding this. Any help with this will be helpful.

(in DH) Bob used a small secret key that can be brute-forced.

If the private key is $k$-bit, a meet in the middle attack allows private key recovery with cost $O(2^{k/2})$ group operations (here, multiplication in the modulo $p$ group $\Bbb Z_p^*$).

In its simplest form: we know Bob's public key $y=g^x\bmod p$ and want the $k$-bit $x$. We choose $a$ with $\log_2(a)\lesssim k/2$, compute and enter in a hash table the $a$ values $y\;g^{-a\;i}\bmod p$ with $0\le i<a$ and the corresponding $i$ (each additional value is computed with a single multiplication modulo $p$ by $g^{-a}$). Then we search in this table the $g^j\bmod p$ with $0<j\le2^k/a$. When we have a match, $x=a\;i+j$.

There are various optimizations: we can make the table more compact by perusing the near uniform distribution of the values in the hash table, truncate these values to below $k$ bits and filter out any false positives. For more time/memory tradeoffs see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

Update: but now that I have seen the linked files, this general method (while working) is way overkill.

We have Bob's public key (or "contribution") $y$ that is much shorter than $p$ is, and $g=3$. The simplest way (and in fact, the only known way for a good choice of $p$) to have such a small $y$ is that $x$ is very, very small and $g^x\bmod p$ is $g^x$. We thus we want to check if $y=g^x$ has a solution $x$ in $\Bbb N$ (hint: take an approximation of the logarithm on both sides to get an approximation of $x$, then check that guess). If we get Bob's secret $x$, then we can proceed the way he did to decipher the flag.


Encryption schemes and pseudorandom permutations Can an encryption scheme (deterministic or not) be viewed as a pseudorandom permutation taking as input a message and returning a value of the same bit-encoding length?

The term "pseudorandom permutation" is normally used for a family of (computable) bijections $f_k : M \to M$, where $M$ is some finite set, and usually $M = \{0,1\}^n$. (Usually we also have a computable inverse for each $f_k$, and some security properties.)

If we stretch the meaning a bit, we can expand this to any finite set $M$, like "the set of all byte strings shorter than $2^{100}$ bytes" (i.e. more than anything you would ever want to encrypt. But when using this set, all common encryption schemes are, while permutations, not pseudorandom, because we can guess from the length of the output to the length of the input.

If we instead use as $M$ a set like "the set of all byte strings of length 1 KB", any good deterministic encryption scheme restricted to $M$ indeed should fulfill the properties of a random permutation on $M$.

A non-deterministic encryption scheme first will have to expand the ciphertext (e.g. by writing the IV into it), and secondly is not a permutation (a permutation is deterministic).

If we can extract the randomness part and use it as a separate input to a deterministic function (or, as a chooser for a family member), we can treat the encryption itself just like before.

But normally the term "random permutation" is used only for the actual building blocks of such encryption schemes, also named "block cipher".


Am I using these key derivation functions correctly? I am a bit confused about key derivation functions. I am trying to use the argon2 KDF from the passlib python module to do the following:

The user provides a password which I provide to the hash function combined with a salt (which is autogenerated by the function)
I use the resulting hash as a master key to encrypt some other key(s) along with some data about some system, for example a set of files. The salt is also stored along this data (but not encrypted).

My confusion comes from the fact that the library only provides the hash results in the form of strings which may be used to identify if the user of some website typed in the correct password, for example the string
'$argon2i$v=19$m=512,t=2,p=2$aI2R0hpDyLm3ltLa+1/rvQ$LqPKjd6n8yniKtAithoR7A'

as shown in this example.
Can I use a KDF like argon2 for this purpose? Of course I would have to extract the key and the salt along with the settings from this string to make this work.

Can I use a KDF like argon2 for this purpose? Of course I would have to extract the key and the salt along with the settings from this string to make this work.

Yes, but preferably you would not use the part of the function that creates a string.
Basically a password hash and PBKDF (password based key derivation function) are identical functions. The string that is put out is not part of a description of a PBKDF though, it is the output that is generated if it is used as a password hash (and then only for a specific format).
It is a bit annoying if the string is the only possible output, because the last part of the string is the password hash in base 64 (it's the "digest" in the this description). Now strings are pretty hard to delete from memory in most runtime environments, so you cannot easily clean up after decoding the derived key.
Preferably then you'd find or isolate the PBKDF function itself and use the resulting byte array before it is encoded. Or you could of course use another library that provides this functionality.


Modifying an Enigma machine to allow unchanged letters One of the biggest flaws of Enigma was that a letter couldn’t represent itself because the route through the machine was one-way. I was thinking a quick fix could be to introduce a rotor position that deflected the signal so that nothing would light up - no response would indicate that the letter you just pressed is unchanged. When decrypting, the rotor position should also produce no response and so you know that letter in the message is unchanged.

Would the fix really have been that simple or am I missing something?

There was at least one late Enigma derivative, the Russian M-125 Fialka, that did modify the reflector to allow a letter to encrypt to itself.

Curiously, rather than simply making the cipher alphabet size an odd number (which would've been natural enough for Russian, with its 33-letter Cyrillic alphabet), the designers of the Fialka instead used a rather complicated (and, for its time, advanced) "magic circuit" to replace two wire pairs with a single "plaintext enable" signal (which caused the plaintext input to be output unchanged) and a set of three wires connected to a transistorized "binary rotator" that mapped an input signal on any of the three wires to an output signal on the next wire out of the three, as in (1 → 2, 2 → 3, 3 → 1).

Of course, the magic circuit also meant that the Fialka lacked the self-reciprocal property of the Enigma: encryption and decryption were not (quite) the same operation.  Thus, the Fialka also needed an "encrypt" / "decrypt" mode switch that simply swapped two of the three wires going into the magic circuit.

Quite why this feature of the Fialka was implemented in this specific manner is, as far as I'm aware of, not known.  One might suspect that the original Enigma-based design of the Fialka, with an even number of letters and an Enigma-style reflector, may have been finalized before someone became aware of the cryptanalytic significance of the Enigma never encrypting a letter to itself, and that this flaw was fixed in a manner that minimized changes to the rest of the design.  Or some Russian cipher machine designer might have just been eager to play with fancy new transistor technology.


Constant Time algorithms for $\mathbb{Z}/m\mathbb{Z}$, $\mathbb{Z}/m\mathbb{Z}[x]$, and $\mathbb{Z}/m\mathbb{Z}[x] / (f(x))$? I want to implement some (lattice based) protocols to better familiarize myself with a programming language (Rust). These tend to do arithmetic over rings like $\mathbb{Z}/m\mathbb{Z}$, or "extensions" of this ring (meaning $(\mathbb{Z}/m\mathbb{Z})[x] / (f(x))$. Since it seems like I'll need to implement the ring arithmetic myself (there are finite field libraries, but this stops certain optimizations I am interested in exploring such as double-CRT arithmetic), I might as well do something slightly-more-than-naive, and use constant time algorithms (which I am assuming are quite well-known at this point).
I am somewhat interested in algorithms that assume special structure of $m$ and $f(x)$ (say $m = 2^k \pm c$ for small $c$, or $f(x)$ a cyclotomic polynomial), but my primary interest is of algorithms that make no special assumptions on the structure of $m$ or $f(x)$.
Is there a particularly good reference for these algorithms? Chapter 14 of Handbook of Applied Cryptography seems to be a good start. It doesn't appear to discuss polynomial arithmetic directly, but it seems like you could piece together something by using their MPI arithmetic section. Additionally, this chapter doesn't discuss constant time algorithms directly, but quickly glancing over their algorithms I don't see anything that is too obviously variable time.
Still, is there some better reference for the task I am interested in?

While this is not a total answer (it does not discuss polynomial arithmetic), the Big Integer Design section of the BearSSL page seems like a good resource to share on this problem. Many of the algorithms are roughly similar to those in chapter 14 of Handbook of Applied Cryptography, but care has been made to make them constant time (not all of the algorithms in chapter 14 are by default). In general BearSSL aims to be a "pedagogical" implementation of TLS. Practically speaking, this means it is well-documented, and algorithmic decisions seem to be explained well.
I have not yet looked into algorithms for $\mathbb{Z}/n\mathbb{Z}[x]$ or $\mathbb{Z}/n\mathbb{Z}[x]/(f(x))$, so won't accept an answer until I get to there (or someone else suggests references).


How to verify most appropriate cleartext? So basically I was implementing a decryption tool (just for fun) and the first encryption logic I decided to implement was Caesar Cipher. So if I  have the input as cvggbmp and I have to find what the cleartext is, I would pass this through the decrypt function 26 times. I get 26 outputs. Is there some way I match each of these outputs against a words.txt for like legible word density and then display the output with the most number of legible words ? Or is there a better optimized way to do this ?

A simple approach is to do char gram frequencies.
There are readily downloadable dictionaries of char-gram frequencies.
You can lookup each set of consecutive characters of the requested length and multiply the probabilities.
For numerical reasons you don't actually multiply probabilities but sum the logarithms. You probably want to use some minimal frequency to prevent multiplying be zero.


What's the difference between substitution and permutation in DES? What's the difference between substitution and permutation in DES?
From my understanding substitution is replacing the data with new data and permutation is just rearranging the data?

You pretty much answered your own question:

Substitution replaces a section of data with another chunk of data
Transposition moves data from one place to another

Substitution is usually responsible for non-linearity or "confusion", while transposition is useful for "diffusion" and ensuring that changes in one bit propagate to the rest of the state.