Error Correcting Codes Post Quantum Finalists I have been looking into error-correcting codes in lattice, I am specifically hoping to find some information on hardware implementations for the NIST PQ PKE/KEM finalists (Saber, CRYSTALS-Kyber, NTRU).
I was reading this article on Timing Attacks on Error Correcting Codes in Post-Quantum Schemes and it mentions:

Kyber [31] and Saber [11] choose their parameters so that
their failure probability is small enough without need for ECC. NTRU [36] and
NTRU prime [6] even eliminate all decryption failures without using any ECC.
These schemes are therefore not vulnerable to side-channel analysis on ECC and
do not need the extra protection against these types of attacks.

I also understand the Lattice codes are also referred to as "Sphere packing". Something I have read about conceptually, although I am not sure how it works practically.
However, I have also seen a few articles (such a this) that have been published recently about RLWE (Ring-Learning with Error) that tackle error correction and fault detection in that space, however none of the finalists use RLWE (as far as I can tell?)
My question is somewhat broad:
I want to investigate ECC/fault detection in hardware (or more accurately their lattice counterparts), specifically with one of the NIST finalists. Does anyone have any insights into this sector of Lattice Cryptography? I am very new to this field (I'm a student, looking to define a thesis topic) but any insights would be appreciated.

I want to investigate ECC/fault detection in hardware (or more accurately their lattice counterparts), specifically with one of the NIST finalists. Does anyone have any insights into this sector of Lattice Cryptography?

Actually, none on the NIST Lattice finalists (Kyber, NTRU, Saber) use error correction; for that matter, neither do the NIST Lattice alternates (Frodo, NTRUPrime).  Hence, that wouldn't be a promising avenue to research.  Several round 2 candidates (LAC, Round5, probably others) did, however they didn't make the cut.
As for fault detection, well, that's always a possible concern.  Glancing through the paper you cited, it would appear that they are concerned mostly about deterministic faults (e.g. a gate within the hardware breaks), and less about deliberate fault attacks (e.g. the attacker glitches the power supply at just the right time to cause a single value to be miscomputed).  You might consider investigating that (possibly starting with figuring out how out would perform a fault attack on the reference implementation, and using that to form a generalized concept about how a fault attack would work; then, you form a defense against that (assuming some limit on how powerful the attacker is; obviously, if he can fault things arbitrarily, he can make the hardware do anything...)

however none of the finalists use RLWE (as far as I can tell?)

No, but as ideal lattices, they aren't that different; of course, as a part of your thesis, you would need to explore them in detail...


Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate Given an x-coordiante of a point on the SECP256K1 curve, is it possible to calculate the corresponding y-coorindate? (Assuming the point is a verifying public key that complies with the Bitcoin standards.)
I am new to the cryptographic realm so please forgive me if the question is naive. From what I know, the public key is a point, or a pair of integers. The SECP256K1 curve is a curve where any point (x, y) on it satisfies
(y ** 2) mod p == (x ** 3 + 7) mod p

where p = 2**256 - 2**32 - 977.
Now let's confine the discussion within the Bitcoin scope. Assume we have a private key that complies with the Bitcoin standards, and from it we can derive the public key, which can be represented as a point (x, y) on the SECP256K1 curve.
Now given only such a x, is it possible to calculate the y?
As a real example, given only x as
0x6778ec0abf66f1ba4d93aa45cad77dc26c593f520448f6fff5b70357270154ba

is it possible get the y as
0x6a5e8cd7276f80ee2f7c081702eff3e14134b006acd0afc8467be94a0a3a0558

Given an $x$-coordinate of a point on the SECP256K1 curve, is it possible to calculate the corresponding $y$-coordinate?

Yes, if there exists such $y$ for the given $x$. And, absent other indication, such $y$ can only be found within sign (or equivalently, parity). That limitation is because if $y^2\equiv x^3+7\pmod p$ with $p=2^{256}−2^{32}−2^{10}+2^6-2^4−1$ as in secp256k1 has a solution $y_0$ in $[0,p)$, then $y_1=p-y_0$ also is a solution.
Note: in some cases including secp256k1 as used in Bitcoin, a public key with $x$ and without $y$ (that is, in compressed form) comes with a prefix of 02 if $y$ is even, 03 if $y$ is odd, and that allows to fully recover $y$.
By Euler's criterion, $x^3+7$ has a square root modulo $p$ if and only if $(x^3+7)^{(p-1)/2}\bmod p=1$. That holds for the question's $x$, thus there are solutions.
In the general case, the Tonelli–Shanks algorithm can be used to find modular square roots. Since $p\equiv3\pmod4$, that algorithm reduces to computing $y_0\gets (x^3+7)^{(p+1)/4}\bmod p$ and $y_1\gets p-y_0$. The question's $y$ happens to be $y_1$.
Justification: when we have checked $(x^3+7)^{(p-1)/2}\bmod p=1$, and computed $y_0$ as $(x^3+7)^{(p+1)/4}\bmod p$, the later is such that $$\begin{array}{}
{y_0}^2 &\equiv&\left((x^3+7)^{(p+1)/4}\right)^2 &\pmod p \\
& \equiv&(x^3+7)^{(p+1)/2} &\pmod p \\
&\equiv&(x^3+7)^{(p-1)/2}\,(x^3+7)&\pmod p\\
&\equiv&x^3+7 &\pmod p & \text{since}\;(x^3+7)^{(p-1)/2}\bmod p=1\end{array}$$
thus $y_0$ is a solution to $y^2\equiv x^3+7\pmod p$.

Definitions:
$$\begin{array}{l}
u\equiv v\pmod p&\underset{\text{def}}\iff v-u\;\text{ is a multiple of }\;p\\
u=v\bmod p&\underset{\text{def}}\iff v-u\;\text{ is a multiple of }\;p\;\text{ and }0\le u<p\;
\end{array}$$


Are there predictable, yet secure hashes? My original problem: I want Alice to be able to promise that at some point in the future she will upload a statement to an address in a hash-table, which is computable/predictable from everyone without knowing her secret key (to be able to look at that address, if the statement is already there). However, the statement should not be predictable for everyone.

One solution path:
Alice has a secret key $S$ and the corresponding public key $P$ (solutions for any (secure) key generation algorithms are appreciated). Is there any combination of (any) functions $f_1, f_2$ and (any) hashing algorithms $h_1, h_2$, s.t. the following holds?

$h_1(f_1(P)) = h_2(f_2(S, P))$

I.e. an algorithm that gives a predictable hash for data generated by the secret key. A hash that can be generated from the public key only, which will be the same for a string generated from the secret (and possibly the public) key.

Important note: $f_1$ may not be aware of $S$, of course, and $f_2$ may not ignore $S$. Otherwise there are of course trivial solutions...

My question: Can my proposed solution be workable or is there a better way to accomplish this?

It sounds to me like you want to is produce a hash that proves integrity, and can be authenticated with some key pair.

In that case, I would release a HMAC using a RSA public key and your statement along with the RSA signature of the aforementioned HMAC.

That way someone could verify the integrity and authenticity of your statement while only knowing your RSA public key and the signed HMAC.


What is the purely mathematical definition of encryption strength? An encryption function can be used to obfuscate pieces of information and later on retrieve them.

What is the yardstick for measuring how well the function encrypts the information ? Given any invertible function, which are the quantified parameters which measure how effective the function is to encrypt a message ?

I am assuming a finite domain for the function. Any other assumption may be stated.

Motivation: Is there any mathematical/set theoretic formulation at all... I ask this specially because I don't see this approach ever being used as has been rightly observed. My motivation is to find out weather the notion of 'encryption' can be captured fully in a mathematical formalism.-- or that we require other kind of 'concepts' to describe it fully. –

There isn't just one, because there are many different scenarios where you'd use such a function, where the attacker has lesser or greater powers, or variably stringent success goals—different attack models.  For example:

Does the attacker know any plaintext/ciphertext pairs encrypted with the same key?  (Known plaintext attack)
Is the attacker able to trick the defender into encrypting plaintexts of the attacker's choice, and observe the corresponding ciphertexts?  (Chosen plaintext attack)
In the latter case, is the attacker able to observe the ciphertexts in real time, and use this to make smarter choices of plaintext to submit?  (Adaptive chosen plaintext attack)
Is the attacker's goal to decrypt a message, or something weaker like telling true encrypted messages apart from random bits?  (The latter is what's called a "distinguishing attack," and strengths are often expressed in terms of that.)

So it's common for algorithms to have different security levels in different scenarios. If you look for example at the "Known attacks" section in Wikipedia's entry on AES, you'll see a variety of figures, all qualified by the relevant attack model.

Another detail is that strengths are often expressed not as one number but as a function of the resources that the attacker expends in some model (e.g., in a chosen plaintext attack, the number queries, i.e. the number of plaintexts that they submit to the defender).  Such functions generally give the probability that a randomized attacker will succeed if they expend that many resources.

And yet another detail is that often for some algorithms like block cipher modes of operation, which are parametrized by one or more primitives, the strength is often given as a function of the strengths of the primitives.  If you're math-inclined or even just math-curious, two papers I found very useful to understand this are:

Bellare, Kilian and Rogaway's "The Security of the Cipher Block Chaining
Message Authentication Code"
Bellare, Desai, Jokipii and Rogaway's "A Concrete Security Treatment of Symmetric Encryption"

These two papers are perhaps overwhelmingly detailed, but even just skimming the major points might be instructive.


Is encrypting credit card numbers one by one with rsautl secure? I wish to encrypt credit card numbers one by one using asymmetric encryption on the command line. My current approach is this…

Encrypt:

/usr/bin/openssl rsautl -encrypt -inkey 'myKey.pub' -pubin | /usr/bin/openssl enc -base64

Decrypt:

openssl enc -base64 -d | openssl rsautl -decrypt -inkey myKey.pem

It is my understanding that this is secure, even when using the same key for each number, because rsautl introduces randomization to prevent finding patterns in the cyphertext.

Am I correct, and is the approach therefore secure?

As long as you use a secure padding mode (i.e. -pkcs or -oaep, not -raw).  The default padding mode for openssl rsautl is -pkcs (i.e. PKCS#1 v1.5), so you should be OK.  That said, OAEP is recommended over PKCS#1 v1.5 padding, so you might want to use the -oaep switch.


Compression step of PGP We do compression in PGP.
Does this step increase/decrease or either have any effect regarding the authentication of a message?

From RFC 4880 - Open PGP Message Format (emphasis added)

  OpenPGP implementations SHOULD compress the message after applying
     the signature but before encryption.

As the signature provides authentication, and you specifically ask about authentication, I think that quote from the RFC should answer your question. Compression does not affect authentication of the message at all as the authentication step (signing) is applied before compression. See the question archie linked for other issues with compression.


Why is lattice-based cryptography believed to be hard against quantum computer? Why is lattice-based cryptography believed to be hard against quantum computer?

Learning With Errors(LWE) problem (reduction to SVP) is just one example.

Can you provide some intuition of the hardness?

Why is lattice-based cryptography believed to be hard against quantum computer?

Because no one has developed a quantum algorithm (yet) that breaks these crypto primitives.

Wish we could do better than that, but that is the best we have at the moment. We believe these primitives to be quantum resistant because no one has given evidence otherwise.


Type A Curves of Supersinglular In the Type A curve used in Pairing based Cryptography, what is meant by sign0 & sign1 in the expression below?

a_param struct fields:

exp2, exp1, sign1, sign0, r:
  r = 2^exp2 + sign1 * 2^exp1 + sign0 * 1 (Solinas prime)
q, h:
  r * h = q + 1
  q is a prime, h is a multiple of 12 (thus q = -1 mod 12)

Reference: http://crypto.stanford.edu/pbc/manual/ch08s03.html

The values $\mathtt{sign0}$ and $\mathtt{sign1}$ are just signs, i.e., indicating negative or positive sign (elements from the set $\{-1,1\}$).


How is pre-image resistance defined, formally? Earlier today, forest asked in our chat, The Side Channel whether the definition of first pre-image security actually requires that an input that evaluates to the challenge hash result must be known to exist a-priori.

This got me thinking. How does one actually, formally define first pre-image security for hash functions?

This is also motivated by the fact that formal definitions are crucial in cryptography to actually understand what is needed to break security. For example, the RSA problem isn't "given $c$ that was constructed as $c=m^e\bmod n$, find $m$" but rather requires specific properties from $n$ (by requiring correct key generation) and requires correct choice (uniformly at random) of $m$ as well.

$\newcommand{\xs}{\xleftarrow\$}\newcommand{\mc}{\mathcal}$
There is a paper from 2004 (last revised 2009) by Rogaway and Shrimpton "Cryptographic Hash-Function Basics: Definitions, Implications and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance" which talks about this very topic (among others). I shall use it as the primary reference of this answer.

In the paper, there are three definitions given for first pre-image resistance. One which is separate from the others, one somewhat weaker and a strong one (to which quite a few other properties also reduce to). So we shall go through them in order.

Before we can start though, we need to take a moment to acustom to the fact that any hash function is written as $H_K(M)$ from here on, i.e. that the hash functions take a "key" as well. This is done to be able to model them as random functions and in practice this "key" can be assumed to be fixed and e.g. represent the initial internal chaining value of the hash function or a salt-like input to the hash. So from here on, let our hash function be $H:\mathcal K\times \mathcal M\to\mathcal Y$ and let $m$ be an integer such that $\{0,1\}^m\subseteq\mathcal M$, i.e. pick a length $m$ of bit strings that is a valid input length to the hash function. This set is useful because it allows us to reason about a finite subset of the potentially infinitely large hash input and we can make any choice of $m$ to our liking to model a particular string length.

Also all the definitions will talk about advantages for some adversary and some auxilliary parameters. Usually you want to bound this advantage to be negligble (in some security parameter, e.g. the digest length or the input entropy) for all adversaries that run in polynomial cost (i.e. efficiently and don't just enumerate the hash) and for all auxiliary parameters.

Definition 1: everywhere Preimage resistance (ePre)

$$\mathrm{Adv}^{\text{ePre}}_H(A)=\max_{Y\in\mc Y}\{\Pr[K\xs\mc K;M\xs A(K):H_K(M)=Y]\}$$

So what does this definition say? First, iterate over all possible output values $Y$. Next pick a hash function uniformly the selection. Then ask the attacker to come up with a value given the function selection. The attacker "wins" for the given $Y$ value if they actually found a pre-image. Now take the advantage of the attacker to be the maximum over all possible choices of $Y$.

Now this definition essentially says that it should be hard for an attacker to come up with a pre-image for any output value, given that they had no a-priori knowledge of the concrete (secure) variation of the hash.

It may appear that this definition isn't all that useful in practice, because an attacker may just always guess the empty string, but as the range point is fixed first and then the hash is selected uniformly at random, there's a $1/|\mc K|$ probability of being right with the guess, which is negligible. Thanks to Maeher for pointing this error out in a previous version of this answer.

Definition 2: always Preimage resistance (aPre)

$$\mathrm{Adv}_H^{\text{aPre}[m]}(A)=\max_{K\in \mc K}\{\Pr[M\xs\{0,1\}^m;Y\gets H_K(M);M'\xs A(Y):H_K(M')=Y]\}$$

What does this mean? Well, first it asks to iterate over all possible hash selections and fix one, e.g. the concrete instance. Now pick a message uniformly at random. Hash it using the hash instance. Hand the result to the adversary and ask them to come up with a value. If this value is actually a pre-image of the value given hash function then the adversary won.

Now practically speaking it appears that this definition is the one most closely modeling actual hash functions, because you fix the selection of the function and then ask the adversay to find a pre-image for a randomly chosen message.

Definition 3: Preimage resistance (Pre)

$$\mathrm{Adv}_H^{\text{Pre}[m]}(A)=\Pr[K\xs\mc K;M\xs\mc \{0,1\}^m;Y\gets H_K(M);M'\xs A(K,Y):H_K(M')=Y]$$

So what does this mean? Well it first says that you should pick an instance of the hash function uniformly at random. Then we pick a message uniformly at random from the set of bit strings of length $m$. Next we compute the challenge output value $Y$ using the previously determined message and function selection. Finally we give the adversary, ie the attacker both our function selection and the output value and ask it to come up with a value. If that value is indeed a first-preimage then the attacker "won". The advantage an attacker has now is the probability over the choice of the function selection and the value selection that they can come up with a valid pre-image.


CBC encryption + CBC MAC reusing key in MAC-then-Encrypt I'm reading the Handbook of Applied Cryptography by Alfred J. Menezes et al. Especially, I'm stuck with the case that reusing key for CBC encryption and CBC-MAC in MAC-then-encrypt structure.

My question is: in MAC-then-encrypt structure, that textbook's p.367 states

  Example (improper combination of CBC-MAC and CBC encryption) Consider using the data integrity mechanism of equation $\big(\ C'=E_k(x\mathbin\|h_{k'}(x))\ \big)$, with $E_k$ being CBC-encryption with key $k$ and initialization vector $IV$, $\ h_{k'}(x)$ being CBC-MAC with $k'$ and $IV'$, and $k=k'$, $IV=IV'$. The data $x=x_1\mathbin\|x_2\mathbin\|\ldots\mathbin\|x_t$ can then be processed in a single CBC pass, since the CBC-MAC is equal to the last ciphertext block $c_t=E_k(c_{t−1}\oplus x_t)$, and the last data block is $x_{t+1}=c_t$, yielding final ciphertext block $c_{t+1}=E_k(c_t\oplus x_{t+1})=E_k(0)$. The encrypted MAC is thus independent of both plaintext and ciphertext, rendering the integrity mechanism completely insecure.  Care should thus be taken in combining a MAC with an encryption scheme. In general, it is recommended that distinct (and ideally, independent) keys be used.

Why is it problem that MAC is independent of both plaintext and ciphertext? Are there any instances where an attacker could use this fact? (I know that MAC-then-encrypt structure vulnerable to padding oracle attack.. however, in that case, the attacker could perform the actual attack.) I think that encrypted MAC part always results in 0 being encrypted, but there is no practical way to exploit this fact. Isn't it?

Why is the comment needed that encrypted MAC part is constant?

With the scheme in the question, in a cryptogram with the correct MAC, the last block of the encrypted message is a constant. Importantly, that goes both ways: if the last block of the encrypted message is that constant, then the MAC is correct and whatever plaintext is deciphered will pass the MAC test.

This allows forgery: an adversary can observe one encrypted message, get that constant, and from then on forge encrypted messages that will pass the MAC check after decryption. That goes against the purpose of ensuring integrity of the (deciphered) message.

We combined a secure encryption, and a secure MAC (for constant message length), and got an insecure combination (w.r.t. the goal of the MAC) because we did not obey the principle: a key shall only serve one purpose (or: one usage, one key).

In the context, it gets worse than letting garbage pass the MAC check: CBC encryption is malleable enough that the adversaries can partially choose the deciphered plaintext. For example, with a long known plaintext, they can copy/paste large segments of ciphertext, cutting at block boundaries, and that does the same for deciphered plaintext, albeit with one block of garbage after each cut. Other example (that can combine): an adversary can put an arbitrary chosen value one block wide in the deciphered plaintext, by putting it in a ciphertext block followed by a copy of the last block $E_k(0)$.


Kryptos : K2. What is the origin of the “abscissa” keyword? I'm studying the Kryptos sculpture with its cryptographic puzzles K1 to K4.

Similar to the "palimsest" keyword for K1, the keyword "abscissa" for K2 was determined by brute-force.

To better understand the puzzle as a whole and ultimately solve K4, it's important to understand how the "agent in the field" might have discovered these keywords.

One suggestion is that the keyword "abscissa" is derived from the plaintext of K1 which reads:

  BETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT LIES THE NUANCE OF IQLUSION

Which, given a sort of "cryptic crossword" reading can give you:

Between "Subtle Shading And" -> "SSA"
... the ABSence -> "ABS"
... of Light (speed of light == "C" in physics) -> "C"
... lies the nuance of Iqlusion -> "I"

And with standard sort of anagram "fun", one comes up with "ABSCISSA."

Not very strong, but maybe believable.

Is there a better theory out there?

I think the best theory is crib-dragging the phrase "virtuALLYINVISIBLE" from the morse code sections. This will line up with "itwastotALLYINVISIBLE" from K2 and reveal the entire keyword, repeating and removing any doubts.

Come to think of it, it may very well have been the intension of Sanborn to have us decode K2 first by this method, and then from K2's ending (IDBYROWS/XLAYERTWO) derive the word palimpsest, because that´s basically what it is. One text scraped away to make room for another text and hinted at by the use of "LAYER TWO".


What can we recover with an invalid curve attack According to the "Guide to Elliptic Curve Cryptography" (page 182), it's possible to recover $d$ with an invalid curve attack.
How can this value be used once recovered?
For example, with Elliptic Curve Diffie Hellman (in TLS for example), what can we do with $d$?

Weierstrass Curves point addition formulas
Consider the Weierstrass equation
$$y^2 = x^3 + a  x + b$$
Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

$P+O=O+P=P$
If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align}
x_3 = & \lambda^2 -x_1 - x_2  \mod p\\
y_3 = & \lambda(x_1-x_3) -y_1 \mod p
\end{align}
$$
\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1},  & \text{if $P \neq Q$} \\[2ex]
\frac{3 x_1^2+a}{2y_1},  & \text{if $P = Q$} \\[2ex]
\end{cases}$$
The addition law on Weierstrass curves doesn't use the constant $\color{red}{b}$. This is the core of the attack.
Invalid curve attack
Consider that the used curve is Secp256k1 with curve equation $y^2 = x^3+7$.
Now, using the fact that the addition formulas don't use $7$, an attacker $A$ can choose a public key $(x_a,y_a)$ such that it is on another curve $$y^2 = x^3+c$$ with small order $n$. Now, you did not validate this public key and used $[a](x_a,y_a)$ as an input for the KDF to derive the key. Now the attacker can try all $n$ possible values $[i](x_a,y_a)$, $ 0 \leq i <n$ and validate the result form the encrypted message that you send.
Now, you are not aware of anything and $A$ doesn't stop there, next time chooses another point on the same curve with a different small order or carries the attack on another curve. Finally, they combine all extracted information with the Chinese remainder theorem (CRT).
Now the attacker accessed the key, and use it.
TLS
If the public key of the attacker is not validated with a CA and you assume that as it is then you have a problem.
In pre-TLS 1.3 the EDHK doesn't have to be ephemeral (ECDHE). In this case, it is called static. If you use static then the attacker can extract your key. The recorded past communications are no longer safe.
Since you computed the exchange points during any DHKE by $[d]Q_b$ with $Q_b = [d_b]G$ is the Bobs public key then they can recalculate $[d]Q_b$. After that, we can decrypt all recorded sessions.
If you use TLS 1.3 (you should) then you have to use ECDHE. In the ephemeral case, the private and public keys are generated on the fly. They are protected with signatures. In this case, the attacker can only recover the current private key that is not used for any other session.
This is good since it is the forward secrecy as defined in the original DHKE paper. To achieve forward secrecy the old keys must be deleted and this is exactly what TLS does.
Therefore it can be dangerous in pre-TLS 1.3 where static DHKE is allowed.
The countermeasures

Validate the point
The CA verifies the point and you trust the CA by a chain of trust.
Use compressed points on your protocol, during the uncompressing the validation is included.
Use EDHKE


Restoring a point on an elliptic curve I received a representation of a point on an elliptic curve $GF(2^m)$ (with curve coefficient A, B) in specific format and some description how to decode it but not all is clear to me. I would be appreciate to someone to explain some issues to me.
So I have an array of the bytes $\tilde{P}$ (array's size equal to m) and to get a point $P= (x_p, y_p)$ from it I need to do the following:

If  $\tilde{P} = 0$, we set $x_p=0, y_p=\sqrt{B}$, and then go to step 7
We take the right byte $k$ of the $\tilde{P} = (\tilde{P}_{m-1},..., \tilde{P}_0)$, i.e $k = \tilde{P}_0$
We set the the coordinate $x_p$ of the $P$ point as $x_p = (x_{p, m-1}, ... , x_{p,1}, x_{p,0}) = \tilde{P}$ and then make $x_{p,0} = 0$. But if trace $tr(x_p)\neq A$ we set $x_{p,0} = 1$
Calculate $w=x_p^3 + A x_p^2 + B$
Solve the equation $ z_2 + z = v, v = w x_p^{-2}$
If trace $tr(z)$ of the solution $z = (z_{m-1},...,z_0)$ is equal to $k$ then we take $y_p = zx_p$,  otherwise $y = (z+1) x_p$
The result of the calculation is a point $P = (x_p, y_p)$

So the first (1) item above is clear absolutely :)

Second (2) item is clear and the trouble begins from (3) item because i need calculate $tr(x_p)$ operation to determine $x_{p,0}$: it can be 0 or 1 here.
How could i calculate the $tr$ ? Can i use any simplifications?

(4), (5) are clear as well

In (6) we need to calculate $tr$ again, but in my case the right byte $k$ from  $\tilde{P}$ equal to 40 !!! (not to 0 or 1)

So my question is whether can i utilize mentioned instructions to restore point or maybe it has mistakes in description??

The described method appears to be point decompression. Take care first that what you call "bytes" are actually bits. The value $k$ must be the right bit (hence $0$ or $1$), not the right byte.

Below is the general treatment of the question.

Binary Fields

Everything here happens in a binary field $GF(2^m)$ where things are somewhat different from integers. In a nutshell:

Every element of $GF(2^m)$ can be expressed as a polynomial of degree at most $m-1$, with coefficients in $GF(2)$. I.e. an element $d$ will be:
$$ d = \sum_{i=0}^{m-1} d_i X^i $$
such that each $d_i$ is either $0$ or $1$ (it's a bit).
Addition is done term-by-term in $GF(2)$, with no carry propagation of any sort: if $f = d + e$, then $f_i = d_i + e_i \bmod 2$. It is usually expedient to represent an element of $GF(2^m)$ by a string of bits (i.e. an array of bytes, each byte containing a bit); in that case, addition is really a bitwise XOR. Note that the addition of an element with itself yields $0$ (that's why the field is called "binary").
Multiplication is more complicated: you multiply the polynomials together (again, the coefficients are $0$ or $1$, and there is no carry to propagate anywhere); then the result must be reduced modulo the irreducible polynomial of degree $m$ that defines the field representation.
Every element in $GF(2^m)$ is a square, and has a unique square root.
Squaring in $GF(2^m)$ is actually known as the Frobenius automorphism and preserves both addition and multiplication:
\begin{eqnarray*}
  (ab)^2 &=& a^2 b^2 \\
  (a+b)^2 &=& a^2 + b^2 \\
\end{eqnarray*}
(The latter holds because $(a+b)^2 = a^2 + 2ab + b^2$, but $2 = 0$ in $GF(2^m)$.)
Since the field $GF(2^m)$ has order $2^m$, it follows that for every element $z \in GF(2^m)$, we have $z^{2^m} = z$.

Trace and Half-trace

Let's now consider the equation:
$$ z^2 + z = \beta $$
in $GF(2^m)$. To analyze it, it is convenient to define the trace:
$$ \text{Tr}(z) = \sum_{i=0}^{m-1} z^{2^i} $$
(This is still an addition in $GF(2^m)$. We don't use integers anywhere here.)

Now note that the trace is linear, i.e. $\text{Tr}(z+z') = \text{Tr}(z) + \text{Tr}(z')$ for all $z$ and $z'$ in the field (this is because the trace is really a lot of Frobeniusing). Moreover, the trace is preserved by squaring:
\begin{eqnarray*}
  \text{Tr}(z^2) &=& \sum_{i=0}^{m-1} (z^2)^{2^i} \\
                 &=& \sum_{i=0}^{m-1} z^{2^{i+1}} \\
                 &=& z^{2^m} + \sum_{i=1}^{m-1} z^{2^i} \\
                 &=& z + \sum_{i=1}^{m-1} z^{2^i} \\
                 &=& \text{Tr}(z) \\
\end{eqnarray*}
We used here that $z^{2^m} = z$. The squaring simply "rotates" the term, so we end up on the same value at the end.

Frobenius strikes again: since squaring preserves additions and multiplications, it will also preserve anything built out of additions and multiplications, including the trace. Thus:
$$ \text{Tr}(z^2) = (\text{Tr}(z))^2 $$
Taking the two together, we find that:
$$ \text{Tr}(z) = (\text{Tr}(z))^2 $$
for all elements of $GF(2^m)$. There can be only two elements in a field that are equal to their own square ("$t^2 = t$" is a polynomial equation of degree $2$, and thus can have only two solutions in a field). The values $0$ and $1$ are equal to their own square. This therefore demonstrates that the trace, formally an element of $GF(2^m)$, can only be $0$ or $1$.

Let's come back to our equation:
$$ z^2 + z = \beta $$
If we apply the trace on both side, then we get:
$$ \text{Tr}(z^2 + z) = \text{Tr}(\beta) $$
By linearity, and by equality of $\text{Tr}(z^2)$ with $\text{Tr}(z)$, we get that the left half of this equation can only be $0$. Therefore: if $\text{Tr}(\beta) \neq 0$, then there is no solution.

We will now show that if $\text{Tr}(\beta) = 0$, then there are exactly two solutions, that can be built with the half-trace.

The half-trace is defined as:
$$ \text{H}(z) = \sum_{i=0}^{(m-1)/2} z^{2^{2i}} $$
It really is the sum of half of the terms we used in the trace, hence the name of "half-trace". Also, an important note: I used the fact that we are working in $GF(2^m)$ for an odd integer $m$ (you did not say it, but I am willing to bet on it because $m$ is prime for all standard curves, and there are good reasons for that).

The half-trace, contrary to the trace, is not reduced to $0$ or $1$; however, it is still linear, because Frobenius. Consider now an element $z$, and compute the following:
\begin{eqnarray*}
  (\text{H}(z))^2 + \text{H}(z) &=& \sum_{i=0}^{(m-1)/2} z^{2^{2i+1}} + \sum_{i=0}^{(m-1)/2} z^{2^{2i}} \\
  &=& z^{2^m} + \sum_{i=0}^m z^{2^i} \\
  &=& z + \text{Tr}(z) \\
\end{eqnarray*}
Here, I am relying on the fact that $m$ is odd (I told you it's important), so that the first sum yields an extra $z^{2^m}$; and, of course, it is still a total Frobenius fiesta (you'll get used to it).

This expression gives us a solution to our equation. Indeed:
$$ (\text{H}(\beta))^2 + \text{H}(\beta) = \beta + \text{Tr}(\beta) $$
We saw that our equation can have solutions only if $\text{Tr}(\beta) = 0$. If that is the case, then one solution is $z = \text{H}(\beta)$.

It is easy to see that is $z$ is such that $z^2+z = \beta$, then $z+1$ is also a solution (because $(z+1)^2 + z = z^2 + 1 + z + 1 = z^2 + z$). Our equation is polynomial and of degree $2$, so it cannot have more than two solutions.

To sum up: the solutions to $z^2+z = \beta$ are $\text{H}(\beta)$ and $\text{H}(\beta)+1$. These solutions work only if $\text{Tr}(\beta) = 0$; otherwise, the equation has no solution. Note that "adding $1$" means, in a binary field, XORing the low-order bit with a $1$. In other words, the two solutions, when they exist, differ only by their low-order bit.

Point Decompression

Let $E$ be the elliptic curve of equation $y^2 + xy = x^3 + Ax^2 + B$ over $GF(2^m)$, for two given constants $A$ and $B$. Suppose that I give you the coordinate $x$, and I challenge you to find the coordinate $y$.

If $x = 0$, then the equation becomes $y^2 = B$, so a solution $(0,y)$ must be such that $y$ is a square root of $B$. In a binary field, $B$ has exactly one square root, so this is one solution.

If $x \neq 0$, we can divide both sides of the curve equation with $x^2$. We get this:
$$ \left(\frac{y}{x}\right)^2 + \frac{y}{x} = x + A + \frac{B}{x^2} $$
We recognize here the equation $z^2+z = \beta$, by setting $z = y/x$ and $\beta = x + A + B/x^2$. We know how to solve that: with the half-trace, as described above.

So solve it to get $z$, then multiply by $x$ to get $y$. And you're done.

Note that when $z^2 + z = \beta$ has solutions, it has two solutions, that differ by the last bit. Hence, $y$ will be equal to either $zx$ or $(z+1)x$. The choice of the solution must be conveyed in the encoding.

Extra Subtleties

The method you describe is more or less point decompression. However, there is an extra twist. True point decompression requires $m+1$ bits: $m$ bits for $x$, and the extra bit for the choice of the solution for $y$. However, once can save one bit, in the following way.

A normal (non-supersingular) curve over $GF(2^m)$ has an even order. For cryptographic purposes, we want to work in a subgroup of prime order, hence odd. Standard curves will thus have order $2q$ (or $4q$) for some prime integer $q$. We are thus interested only in half the points at most.

Moreover, the "interesting half" can be distinguished with the trace! It can be shown that for the "interesting" points (those in the subgroup of prime order), the trace of the $x$ coordinate must equal the trace of $A$. Thus, we can use the trace of $x$ and infer its last bit.

So back to your description:

If the provided $x$ coordinate is $0$, then the solution is $(0,\sqrt{B})$. Done.
Separate the rightmost bit of the provided input, and call it $k$; this is the bit that will be used to choose the solution for $y$.
Decode the input as coordinate $x$. Note that the rightmost (least significant) bit is missing, since that slot was used for bit $k$, so just suppose that the missing bit is $0$. However, if the result has the wrong trace (i.e. $\text{Tr}(x) \neq \text{Tr}(A)$, then flip that bit (which has the effect of flipping the trace, thus restoring the equality). Note: in your description, you compare $\text{Tr}(x)$ with $A$ itself; this is because you work with one of the standard curves that have $A$ equal to $0$ or $1$, not any other element of $GF(2^m)$.
Compute $w = x^3+Ax^2+B$. This is the right-hand side of the curve equation. No worry here.
Compute $v = wx^-2$ and solve the equation $z^2+z = v$; this is where the half-trace is used. Take care that there may be no solution, in case the provided $x$ is not actually the $x$ coordinate of a valid curve point; this may happen because the encoded point comes from the outside, where there are evil people who may send you invalid data.
The bit $k$ that you used before tells you which solution $z$ you must keep. The way you describe it appears to be somewhat mangled. One simple way is to say that $k$ and the low bit of $z$ must match, but there can be other conventions, including stating that $\text{Tr}(z)$ must match $k$. In standard point decompression, there is no trace here, bit $k$ is supposed to be equal to the low-order bit of $z$. However, standard (as in "ANSI X9.62") point compression does not use the extra trick of not encoding the low order bit of $x$, so I must assume that you are doing something non-standard here.
This step is trivial.

Now for computing the trace and the half-trace. The expressions above work, but are complicated. Since the trace is linear, and outputs only $0$ or $1$, then it follows that $\text{Tr}(z)$ is just the XOR of a few bits of $z$. Which bits to use depends on the field representation, but usually there won't be many. For the half-trace, the result has length $m$ bits, so it can still be done with linear algebra: for a given input $z$, XOR together some precomputed values $h_i$ for all $i$ such that $z_i = 1$. These $h_i$, again, depend on the field definition; precomputing them is a nice exercise. Take care that table lookups, if not done carefully, are prone to make side-channel leaks.

All of this assumes that you can compute things in $GF(2^m)$. This requires functions to add, multiply, and divide values in that field. Implementing these correctly is not easy. Some guidance can be obtained from the Guide to Elliptic Curve Cryptography, especially section 2.3, which talks about binary fields (and it so happens that the chapter 2 is a free download as a PDF!). Making such code constant-time is possible, but harder (especially for division). For a basic Diffie-Hellman, decoding of points occurs on data which has travelled over the wire, hence non-secret, which helps here. Implementing cryptographic algorithm is a path fraught with perils, in particular side-channel attacks; elliptic curves over binary fields are certainly not the easiest thing to do among cryptographic implementations.


Is this method of speeding up a symmetrical algorithm secure? (AES output joining) I was trying to find out a way of speeding up a given symmetrical algorithm the reason and programing launguage in this case are unimportant. I have came up with the following thing:

Divide data into n parts
Run n threads
Each thread encrypts its part of the data
Take the output of all of the threads and concatenate (join) all of them together

And for the decryption:

Divide the cipher text into the same parts that where joined
If feasible Run the same amount of threads as parts If not decrypt one after another
Join the outputs

Things that i can not do with my enviorment:

Change the algorithm code (I can only use encrypt and decrypt)

I am aware that i can use Electronic Code Book (ecb) for this goal but i would like it work for all modes.

My question is does the above method compromise security in any way?
If it does. To what extend?

Sorry for making any mistakes this is my first question

The issues here are not so much security wise (that's downstream of this topic) but pragmatism.  The penguin problem rules out ECB mode for most cipher use, so lets look at your requirements:-

  Divide data into n parts

The easy bit

  Run n threads

Not as easy as it sounds.  This is very language dependent.  For example Python doesn't do well with parallel tasks due to it's global interpreter locking system. Java threads can be cumbersome.  And then there is the inter-thread communication - more overhead and slowdown.  Even C/C++ threads will have to talk amongst themselves.  Will you write a thread pool yourself?  I guess there must be an extant library you could use as mitigation.

  Each thread encrypts its part of the data

The crux of the cryptography.  Have a close look through the wiki entry on cipher modes. You cannot hope to achieve parallel operation on all modes as that's fundamentally impossible for some as they're sequential.  CBC mode is a simple example of one ciphertext passing into another subsequent block operation. Yes it can be run with multiple threads, but each thread will be paused waiting for the previous one in the chain to complete. That said, CTR mode seems to be a mode that's suitable for your scheme.

  Take the output of all of the threads and concatenate (join) all of them together

Even in CTR mode the chunks have to come out in the correct order, requiring more thread collaboration. And again inter process communication has to be addressed which will siphon off   speed gains.

So in conclusion, and without even dealing with  specific security problems, this scheme is troublesome.  Since only a few modes are possible in this scenario, and their security issues are mode dependent, it is quite difficult to give more detail.  But just to mention a generic one, clones of the key and plaintexts will be floating around the machine that might open an attack vector.  And the time of complete thread destruction can be uncertain under a garbage collector.

This   falls into the realm of writing your own crypto, with key management, inter process communication and a large case of debugging. With modern CPUs featuring hardware AES circuity, that is clearly the way forward.  I cannot think of any circumstance that warrants this level of cryptographic development, testing (heartache) and security risk.  Remember that time is money if this is a commercial venture, and in that case does dubitable and possibly  marginal performance gains offset just getting a faster CPU?


Socialist Millionaires variant, where only one party learns $x=y$? In the Socialist Millionaires protocol, Alice selcts some $x$ and Bob selects some $y$, and both parties learn whether or not $x=y$ without learning the other party's selected value. However, on a successful match, both parties do learn the other person's value -- it's the same as their own value. Does there exist a variant protocol (or way of cheating the existing protocol) wherein only one party learns $x=y$ and the other party learns nothing?

My particular case goes something like this:

Bob has a small list of people he has invited to his birthday party.
Bob is happy to let people query his entire list, item by item, via a Socialist Millionaires exchange to see if a particular person is included in the list. However, he does not want to give out the entire list wholesale.
Alice has a secret crush on Charlie and wants to learn if Charlie is invited to the party. She could learn the answer by engaging Bob in a Socialist Millionaires exchange for every item in Bob's list.
However, she does not want Bob to learn that she is interested in Charlie's invitation. If Charlie is on Bob's list, Bob will see that he and Alice participated in a matching exchange for his entry for Charlie.

Can Alice learn the equality of "Charlie" against every item on Bob's list, without Bob learning whether any particular item on the list was a match?

To put it another way, I think that this could be done with fully-homomorphic encryption, e.g.:

Bob encrypts each item in his list with Alice's public key
Alice sends her request for "Charlie" also encrypted with her public key
Bob performs a homomorphic equality comparison of each encrypted list item against Alice's encrypted query (that is, Bob performs a $map$ of the encrypted list into a list of encrypted booleans, based on the homomorphic equality comparison of each item)
Bob sends back a list of homomorphically encrypted booleans describing the matching-state of each comparison
Alice decrypts Bob's reply with her private key

This case satisfies my requirement (I think?) that Bob learns nothing, because he can decrpyt neither Alice's query nor the results of his own homomorphic equality comparisons.

Is there a way to get a similar guarantee using a zero-knowledge proof exchange?

A protocol consists of parties taking turns sending messages. Therefore one party will naturally learn the output before the other (only very few exceptions exist to this rule). This means that in almost every protocol you find (especially in the semi-honest setting) you will see that either (1) the last protocol message literally is nothing more than the party-who-learned-output revealing the output to its counterpart (so you can exclude this message) or (2) the protocol is already described so that only one party gets output. In things like Wikipedia articles, it is often just simpler to describe MPC protocols as "both parties get the output", but under the hood there is generally one-sided output.

(In the Wikipedia article you reference, the protocol is written in a way that obscures the interaction pattern. The last communication between parties is in step 7 "$\langle Q_a Q_b^{-1} | \alpha,\beta\rangle$". But this step is an abstraction of Diffie-Hellman which consists of a message from each party. Just have one party omit this message and he/she will be the only one capable of learning the output.)

Protocols for private set intersection (PSI -- the generalization of socialist millionaires) are no exception. In our paper:

  Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu: Efficient Batched Oblivious PRF with Applications to Private Set Intersection.
  CCS 2016.

(and every other PSI paper I know of) we describe the protocol so that only one party gets output.

The building block of this protocol is something called a "private membership test" where a sender has a set $S$ of items, a receiver has an item $v$, and only the receiver learns whether $v \in S$. This sounds like exactly what you're looking for.

This private membership test building block goes back to this work (and perhaps earlier):

  Benny Pinkas, Thomas Schneider, Michael Zohner: Faster Private Set Intersection based on OT Extension. Usenix 2014.

Both of these papers are optimized to provide many instances of the private membership test building block primitive, since that is what is required for PSI. If you truly want just a single instance of private membership test, then there is probably nothing simpler than the classic Diffie-Hellman based PSI (homomorphic encryption is overkill if you just need semi-honest security). I describe it below, specialized to the case where Alice has just one item.

Alice (who has a single item $v$) picks random exponent $\alpha$ and sends $H(v)^\alpha$. Here $H$ is a random oracle.
Bob (who has a set of items $S$) picks random exponent $\beta$ and sends $(H(v)^\alpha)^\beta$ as well as $H(s)^\beta$ for every $s \in S$.
Alice can compute $(H(s)^\beta)^\alpha$ and check whether any of these values are equal to $(H(v)^\alpha)^\beta$. This will happen if and only if $v \in S$ (barring a negligibly unlikely collision in $H$).


Insecurity of CBC-MAC Can anyone explain why CBC-MAC is not secure for variable length message?

I read many books, but there are still some confusion. Such as the highlighted parts in previous pictures

Questions:

why need to set $T''=C_0$?
why $T'''=T''$. How to prove this relationship?
$new\ message = P_0,P_1,(P_0 \oplus T')$?

Can anyone explain why CBC-MAC is not secure for variable length message?

For the previous question I'll quote Matthew Green's post from 2013:

  A quick reminder. CBC-MAC is very similar to the classic CBC mode for
  encryption, with a few major differences. First, the Initialization
  Vector (IV) is a fixed value, usually zero. Second, CBC-MAC only
  outputs the last block of the ciphertext -- this single value forms
  the MAC.

  Many dumb implementations stop here. And that leads to big problems.

  Most notably, if your system allows for variable-length messages -- as
  it should -- there is a simple attack that allows you to forge new
  messages. First, get a MAC T on a message M1. Now XOR the tag T into
  the first block of some arbitrary second message M2, and get a MAC on
  the modified version of M2.

  The resulting tag $T'$ turns out to be a valid MAC for the combined
  message $(M1 || M2)$. This is a valid forgery, and in some cases can
  actually be useful.

  The standard fix to prepend the message length to the first block of
  the message before MACing it. But a surprisingly large number of
  (dumb) implementations skip this extra step. And many CBC-MAC
  implementations are dumb implementations.

(more info here)

  First question, why need to set $T′′=C0$?

Actually it is not set. $T''$ is computed as written in the slide and the result is $C_0$.

  Second question which is biggest question I don't understand, why $T′′′=T′′$. How to prove this relationship?
  Third question, why is $\text{new message}=P_0,P_1,(P_0⊕T′)$?

Let's compute the tag for $P'''$:
after processing second bloc ($P_1$) one have $T'$, so when processing next bloc ($P_0 \oplus T'$) one computes the encryption of $T' \oplus P_0 \oplus T' = P_O$ that is, by definition, the tag of the second message: $T''$ ($P_0$ is the second message $P''$).

Roughly the idea is to add a bloc that cancel all previous computations and restart the CBC-MAC computation for a message which MAC is already know by the attacker. "Canceling" is done by xoring to the first added bloc the tag of the previous chain to the first bloc of an other message which MAC is known.


Are LPN and LWE problems equivalent? Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits. But, this also makes LPN seem very related to the problem of decoding a random linear code. I was just wondering whether LPN is equivalent to the problem of decoding a random linear code? And whether there are some positive or negative results about the equivalence of LPN and LWE?

Yes, LPN is (essentially by definition) equivalent to the hardness of decoding a random linear code over $\mathbb{F}_2$. No, there is no known reductions between LPN and LWE. It is usually believed that LPN is (in some sense) "harder to break" than LWE, simply because we know much less attacks on LPN. It seems to have less structure that could be exploited in advanced attacks - but also, for the very same reason, has far less known applications. Yet, no formal reduction relating any of them is known. It should also be mentioned (thanks for TMM for pointing that out) that the best known attack on LPN takes time $2^{O(n/\log n)}$ (where $n$ is the dimension) while the best known attack on LWE takes time $2^{O(n)}$ - hence LWE appears stronger than LPN when considering solely the running time of the best known algorithms.

Note that while they clearly seem related, there is a fundamental difference: LWE uses a Gaussian noise, while LPN uses a Bernouilli noise. The first type crucially relies on some "non-black box" considerations on the field where it's implemented (since we need to be able to talk about "small" and "big" field elements), while the latter one is actually completely oblivious to the field (i.e., you can define LPN over a field in a way that makes a black-box use of the field).

To elaborate on your sentence "Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits": it's not really the case, actually. The natural generalization of LPN to a larger field $\mathbb{F}$ would be obtained by adding to each linear equation a noise which is a uniformly random element with some probability $p$, and $0$ with probability $1-p$ (this is the natural generalization of the Bernoulli noise over $\mathbb{F}$). LWE, instead, uses a small Gaussian noise everywhere, which is quite different.

EDIT: to clarify, the last paragraph above is my point of view, but not the formal "demonstration" that LWE is not a generalization of LPN. As pointed out by TMM and Chris Peikert in the comment, the Bernoulli distribution over $\mathbb{F}_2$ can technically be seen as a Gaussian distribution - hence LPN can be seen as LWE over $\mathbb{F}_2$ (or conversely, LWE can be seen as the generalization of LPN over larger fields). My point in the last paragraph is that this is not the only possible generalization, and the alternative one which I mention seems to me much closer in spirit to the original LPN assumption: under the "LPN over large fields with Bernoulli noise", one gets essentially the same implications as with standard LPN (e.g. public key encryption, but not collision resistance), and the same structural properties (i.e. the best known attacks on this generalization are the natural generalizations of the best known attacks on LPN over $\mathbb{F}_2$). LWE is technically a generalization of LPN over larger fields, but one with important differences compared to the original LPN assumption (different attacks, different (and much more "advanced") implications, non-black-box use of the field, etc).


Knowing a valid salted hash for an unknown secret, is it possible to compute another valid hash? $H(s,r)=d$ is a function that hashes the secret string $s$ with a salt $r$, and returns a digest $d$.
$r$ may be arbitrarily chosen and each $r$ returns a different $d$.
For any $d$, $r$ is known from a function $R(d)=r$.

Both $H$ and $R$ are not reversible, i.e. there isn't a neither a reverse function $H'(d,r)=s$ nor a reverse $R'(r)=d$.
To prove that d is a valid hash for the string $s$, it's given a function $V(d,s) ↦ \{0,1\}$ that outputs $1$ only if $H(s,r)=d$.

Is it possible to compute another valid hash $d'$ for an unknown $s$, knowing only $d$ (and therefore the salt $r$)?
That is, is it possible to find a function $G(d,r')=d'$ such that $V(d',s)=1$ for at least some $r'≠ r$ matching $d'$?

This from a theoretical point of view.

On the practical side, BCrypt is an implementation of $H$. If a know a valid digest for an unknown secret, can I compute another valid digest? I've heard about a technique called "hash extension attack", but this involves changing the length of the digest, that for BCrypt is fixed. Is BCrypt vulnerable from this point of view? For which (if not all or none) cryptohashing algorithms is it possible to have a function like G?

Let's get terminology right. If you talk of "unknown s" then s is not a salt; when some piece of data is secret, we call it a key. And your "hash function" is then a MAC. In the context of "password hashing", such things are sometimes called "peppering" (as always, technical terminology is, at its core, a collection of bad puns).

If your MAC is correct (i.e. "cryptographically secure"), then no, it is not possible to produce new pairs message+hash value without knowing the key; being able to do that would be called a forgery. The length extension attack is a forgery attack on some poorly-designed MAC algorithms, which work by simply hashing the concatenation of the key and the message, with a Merkle-Damgård hash function like SHA-256. Don't take it wrong: the "length extension attack" does not mean that SHA-256 is cryptographically weak as a hash function; it just means that making a MAC out of a hash function is not as immediate as it initially seems to be. The proper way to turn a hash function into a MAC is HMAC.

Bcrypt is not a MAC, and, arguably, not a hash function either, since it does not accept as input a sequence of bits of arbitrary length. The salt in bcrypt is not secret at all; it is often encoded in the bcrypt output; moreover, if you are using the salt as a secret for some passwords, then you are reusing the same salt value for several hashed passwords, and that's very wrong. The whole point of the salt is to be distinct for every instance (every user has his salt; when the user changes his password, a new salt must be generated).

On the concept of password hashing, read this.

Edit: it has been brought to my attention that I misread the question somehow: the salt is known to be public. The question being: can we transform a hash for some secret password with some salt value, into another hash for the same secret password, but with another salt value ?

If such a thing is feasible and the new salt value can be arbitrarily chosen, then this would be a severe flaw in the hashing function, because it would allow the attacker to transform a bunch of hashed passwords into another bunch of hashes of the same passwords but all with the same salt -- thereby nullifying the advantage of the salt: parallel and precomputed attacks are again possible. Even if the attacker could just turn the salt into another "random" salt, then it could be used to make salt collisions more probable. No such flaw is currently known for bcrypt.


How can I decrypt 8 times repeated 128-bit AES key encrypted by 1024-bit RSA? There is a 128-bit AES key $m$, and it's encrypted by 1024-bit RSA modulus $n$ as $$c = (m\mathbin\| m\mathbin\|\ldots\mathbin\|m)^e \bmod n.$$

There are eight $m$ in $m\mathbin\| m\mathbin\|\ldots\mathbin\|m$.

Is there any way to find a message $m$?

The key is repeated 8 times, but I can't utilize this information to decrypt.

There is no proper padding and the message $m$ can be recovered easily if $e$ is small.

First, we can rewrite $(m\mathbin\| m\mathbin\|\ldots\mathbin\|m)$ as
$$
(m + m2^{128} + \cdots + m2^{128\times 7}) = m(1 + 2^{128} + \cdots + 2^{128\times 7}),
$$
and when we put it back in the equation, we have
$$
c = m^e(1 + 2^{128} + \cdots + 2^{128\times 7})^e \mod n.
$$
We can compute
$$
c' = c\times (1 + 2^{128} + \cdots + 2^{128\times 7})^{-e} \mod n,
$$
so we have the relation $c' \equiv m^e \bmod n$. In the case that $m^e < n$ (which happens for $e=3$, $5$ or $7$), then this is in fact an equality:
$$
c' = m^e.
$$
The value $m$ can be recovered by taking the $e$-nth root of $c'$.


autocorrelation of non-linear shift register with the period of $2^n$ (full period) throughout the question I will talk about sequences in bipolar alphabet, meaning, over {1,-1}.

I have read in the book Shift Register Sequences by Solomon W. Golomb that sequences with the period of $2^n$ can be created by pure cycling register of order n ($PCR_n $). Moreover, it gives some properties about the autocorrelation (that I also read in some papers):
$$C(\tau)= \ \begin{cases}
      2^n & \tau =0 \\
      0 & 0< \tau \le n-1 \\
      \ne0 & \tau =n
   \end{cases}$$

Another statement (and that is where my question) is that $C(n)$ can bound by the number of cycles of the $PCR_n$ (we can denote the number of cycles as $Z(n)$)

Where this come from I don't really understand.

You have misunderstood Sol Golomb. A pure cycling register (PCR) of length $n$ generates a sequence of period $n$ and no longer period. It is physically impossible. It just cycles the loaded sequence of length $n$.
The sequence it generates may have shorter minimal period, a divisor of $n.$

Take $n=3$ and keep shifting left as in a PCR.

$000\rightarrow 000 \rightarrow 000$ actually has minimal period 1. The same for the loading $111.$

$001\rightarrow 010\rightarrow 100\rightarrow 001$ has minimal period 3. Same with the loading $011.$

The PCR of length 3 has decomposed the space
 $\{0,1\}^3$ into four cycles. This is because the minimal periods add to the size of the state space: $3+3+1+1=2^3$

Now, he proves this is always the case for a PCR of length $n$ with respect to the state space $\{0,1\}^n,$ and since all this has to do with divisibility relates the number of cycles in the PCR decomposition of length $n,$ which he calls $Z(n)$ to the Euler totient $\phi(n):$
$$
Z(n)=\sum_{d|n} \phi(d)2^{n/d}.
$$

Now if you take a maximal length sequence of minimal period $2^n-1$ in the $\pm 1$ formulation and insert a +1, next to the unique run of +1 of length $n-1$ (remember +1 corresponds to 0 mod 2) this PCR decomposition applies. So your statement about $C(\tau)$ is I believe his Theorem 4, p.124, in the reprinted edition of the Aegean Park original.

The autocorrelations of the augmented sequence of period $2^n$  now have an extra term in the sum, and the peak $C(0)=2^n,$ is clear.

Since the way to augment this period is to add a degree $n$ term into the feedback function, and that term is active only once in the period, the autocorrelations at nonzero shifts where $\tau \neq 0\pmod n$ are now 0 instead of -1 for the $2^n-1$ period sequence due to this extra term.

What about when $\tau=n$? Well this won't be zero and getting a hold on its exact value is difficult for a general sequence of period $2^n$, the sequence of theorems 5 through 10 are used here to obtain it for the case that we have an augmented maximal length sequence.


Why is Poly1305, which is based on AES, faster than AES? The web pages of BearSSL have the following performance numbers:

Poly1305 1730.92 MB/s, amd64, ctmulq
AES-128 CTR 92.38 MB/s, amd64, ct64

It seems that constant-time Poly1305 is over an order of magnitude faster than AES-128 in the counter mode, without any special CPU instruction support in either.

My understanding is that Poly1305, however, is based on AES (source). Why can something based on AES be faster than AES by a so wide margin?

Poly1305 is not based on AES, it was used together with AES in Bernstein's first description http://cr.yp.to/mac/poly1305-20050329.pdf. For pseudocode of the Poly1305 algorithm see e.g. https://tools.ietf.org/html/rfc7539#section-2.5.1.

GHASH is the 'hash function' in AES/GCM.

So if Poly1305 is faster than GHASH on some hardware this is no contradiction. And note that the peek values on your linked site are comparable: Poly1305 1730.92MB/s, GHASH 1740.96 MB/s.


How much data can I encrypt with AES before I need to change the key in CBC mode? In my cryptography class, the instructor suggested that in order to give the attacker a minimal advantage of $1/2^{32}$, we have to change the key after $2^{48}$ blocks are encrypted.

It seems that the advantage of $1/2 ^{32}$ is somewhat arbitrarily chosen, and I'm not sure where that comes from.  Can anyone explain the reasoning of why this is chosen and when it should be higher or lower than $1/2^{32}$?

My class notes:

  CBC: CPA Analysis

  $q = $ # of messages encrypted with key $k$
    AES uses 128 bit blocks
    $L$ = length of the max message

  For every adversary $A$ that attacks cbc encryption, there is a
    PRP adversary $B$ with

  $$  Adv[A,E_{cbc}] \leq 2 · Adv[B, E_{prp}] + \overbrace{2 · q^2· L^2 / |X|}^{\text{error term}}$$

  So CBC is only secure as long as $q^2·L^2  \ll |X|$.

  Example

  The error term = $q ^ 2 · L^2  / |X| < 1/2 ^{32}$

  AES:    $|X| = 2^{128}$ (bits per block)
            So after $2^{48}$ AES blocks the key needs to be changed.

  DES:    $|X| = 2^64  \Rightarrow  q·L < 2 ^{16}$

Also, the instructor said that DES needed a new key after $2^{16}$ blocks, and he said that means every .5 MB of data requires a change.  This is the formula he wrote down, Is this correct?  $2^{16} · 8 = 1/2$ MB.

The $1/2^{32}$ is an arbitrary figure, based upon one particular value for what counts as an acceptable risk.

You need to decide what is an acceptable risk.  If you think that a $1/2^{32}$ probability of failure is an acceptable risk, then this calculation is relevant to you.  If you think it isn't, then decide what you think is an acceptable risk and re-do the calculation based upon the number you think fits your particular situation.

Keep in mind a $1/2^{32}$ probability of failure is pretty darn small -- in many settings, it may be acceptable.  It's far more likely that the next time you'll get into a car, you'll end up in a car accident: the probability of that is probably much higher than $1/2^{32}$.
Also keep in mind that life is about risk: you can never completely eliminate all risk from your life.  So, decide what is an acceptable risk, then you based upon that you can decide how much data you can encrypt under a single key, using a calculation similar to that one shown here.


How exactly to extract information base 10 from a PGP RSA key pair? I think I understand the mathematics of RSA ok. I'm not so computer savvy though. How, exactly, can I extract $n$, $e$, $d$, $p$ and $q$ from a PGP RSA public key pair? Is there like a converter online? What exactly is the language used when you see a PGP key? Is it Base64 or something?

So, for example (and I am well aware that you shouldn't post private keys online). Where are $p$ and $q$ in this private key?

-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v1.2.3 (OS/2)

lQHWBD3X7JABBADfDcT9WgUZsAXC2jaLXbVRbkI/vmZWqFT1bBTicnHEOf0EZRKl
o2eIJWf0UIMvBC840efecOGKEmtubHyyas5aSDThQZM8PyCKRrJhGX02UHwCvNRi
XzAD1wteFyGtkVYmlHTR84fjyk9V1BlsZLNTZdTbKQ//Yuxww1qPTrlqNwAGKQAD
/2ddy62aG1bUsX/CyBse8B9+BbmjKS5m+6ntZ1Y1CQOFBNySvbbn0lHS5T9Eh7gh
KJ10AU4bVclZtOg+wyb5TORKNJ6ywjvj+DDMFekoWlfMwhw+utZVEpbJkK7vJNQg
jGBX0+L2uEbv/Z5wFpucoLxNX5fg+nDUxzP+d3VXAlLJAgDrZOc2usLMfMXNh+p0
5xfSAa8QmpumEM/1ARyV12BLhf0/nuVIZPkK9mfTdO5xk/OC35FhJLqQzHSoyNeW
wPRvAgDylFK+/3F5O1ssj2SQ4KRmULhoOs/Lpj9XgTPOFcbkoT58XYmkNvNbKCxS
It1QS0LQNHtOOqIvZKbagnckopq5Af9IGvyE53vEmp6lfop0yZFmO8NQPbcv+B5k
rUAValTyeDTyH7Qc2pdm/SGok47vSc+5Uyyx6/X6hUHF1sfSIoVVrC60hFJ1c3Nl
bGwgU3RldmVuIFNoYXduIE8nQ29ubm9yIChMT1cgU0VDVVJJVFkgLSBzZWUgPGh0
dHA6Ly9tYXRoLmJlcmtlbGV5LmVkdS9+cm9jb25ub3IvcHVibGlja2V5cy5odG1s
PikgPHJvY29ubm9yQG1hdGguYmVya2VsZXkuZWR1Poi4BBMBAgAiBQI91+yQAhsD
BQkB4TOABAsHAwIDFQIDAxYCAQIeAQIXgAAKCRBNPmjuaEZDWZ9vBADQCY9J5ZnV
VYfQBf5F3d6yhNxzXJaFIHEemsBA37dgwCJc3+49KBBJFB91PFlVwgz9PCgux8YJ
yUDsDh56pzXycCxcBav0O/MBapN1rq5/X22vtKrKxSfKjMLfQlto7VWv9vNwzlZA
ClJPYBDOZt5DxA3RECsuNxEvb28bfT5epQ==
=VufU
-----END PGP PRIVATE KEY BLOCK-----

And in general, given anything like this or a public key, how do I go about extracting the actual integers base 10?

Thanks!

You can use the Web tool pgpdump, available at this address http://www.pgpdump.net/ or the same tool ( http://www.mew.org/~kazu/proj/pgpdump/en/)  to install on your pc.
This latter is to use if you are poking with your real secret key.

At the moment I don't remember if the tool outputs in hex or dec, but you can easily convert to your favourite Base using python or pari/gp or whatever mathematical tool you love more.


Differential privacy noise that scales with $L_p$-sensitivity with $p>2$? It is well-known that to make the result of a $\mathbb{R}^d$-valued query $(\varepsilon,\delta)$-differentially private, you can add noise to it. If you add Laplace noise, you need to scale the noise by the $L_1$-sensitivity of the query; if you add Gaussian noise, you need to scale it by the $L_2$-sensitivity instead.
Are there noise functions that scale with, say, $L_3$-sensitivity, or any other $L_p$-sensitivity with $p>2$? If not, how to formalize and prove this impossibility result?

You can measure your sensitivity in an arbitrary norm. The exponential mechanism, that samples from the distribution proportional to $\exp(-\epsilon |z-f(x)|_p / 2)$ will give pure DP. This is more general, and the K-norm mechanism will allow you handle sensitivity measured in norms other than some p-norm. For pure DP, these p-norm mechanisms are optimal. In particular, when sensitivity is measured in the $\ell_2$ norm, the optimal mechanism adds noise from the Gamma distribution.
How then does the Gaussian noise mechanism do better? It gives you $(\epsilon, \delta)$-DP instead of pure DP. It is natural to ask what the optimal approximate DP mechanism is for other sensitivity measures. It turns out that for approximate DP, the right Gaussian mechanism is always optimal. You just convert your $\ell_p$ sensitivity bound into an $\ell_2$ sensitivity bound (by finding the smallest $\ell_2$ ball that contains your $\ell_p$ ball) and add Gaussian noise based on that. Here again, there are analogous results for sensitivity being measured in non-p-norms.
Some caveats are in order. Optimal above is for your error being measured in the Euclidean distance. Some of the results are optimal only up to logarithmic factors. When you care about error in other norms (say $\ell_\infty$), there can be other more interesting mechanisms.
References:
The upper bounds for $\ell_p$ balls are straightforward. The lower bounds are in
https://arxiv.org/abs/0907.3754, and https://arxiv.org/abs/1212.0297. Simpler lower bounds for CDP/RDP are in https://arxiv.org/abs/1911.08339.


Calculating DES key knowing message before and after encryption I've 8 bytes before encryption (for example: 01 02 03 04 05 06 07 08) and 8 bytes after DES encryption: 08 07 06 06 05 04 03 02 01. Is it possible to calculate the key?

A single p3.16xlarge EC2 instance is capable of evaluating $369\times10^9 \approx 2^{38}$ DES calls per second using hashcat.

This puts the maximum time to recover a key at around $2^{56} / 369\times10^9 / 3600 \approx 54$ hours. This costs a little over $1300 at current pricings.


Known plaintext attack on ElGamal encryption Assume that Alice uses Bob’s ElGamal public key $(\alpha=2, \beta = 8, P= 11)$  to send two messages $M = 17$ and $M' = 37$ using the same random integer $k = 9$.  Eve intercepts the ciphertext and somehow she finds the value of $M = 17$.  Show how Eve can use a known-plaintext attack to find the value of $M’$.

Your parameters that you provide are incomplete (in what group are you working?).

Anyways, lets assume that you work in $\mathbb{Z}_p^*$, your have a generator $g$ and your public key is $y=g^x$.

Then, if two ciphertexts share the same randomness $k$, they will look like $(c_1,c_2)=(g^k,m\cdot y^k)$ and $(c_1',c_2')=(g^k,m'\cdot y^k)$ for your two messages $m$ and $m'$. So as you know that let say for the first ciphertext the message is $m$, then you can compute the inverse $m^{-1}$ of the message $m$ in $\mathbb{Z}_p^*$ and can find $y^k=c_2\cdot m^{-1}$. Now, as you have $y^k$ (which you can clearly also invert in $\mathbb{Z}_p^*$) and both ciphertexts share the same randomness $k$, you can easily obtain $m'$ from $c_2'$.


Forward Patterns in SHA 256 Would it be possible to find a correlation between the inputs of SHA 256 and it's outputs? More specifically, by using deep learning, would there exist a correlation between the inputs of an SHA 256 algorithm and it's expected output?

For example, given that A, B, C and D output a Has with certain characteristics, and given that we have a very big sample of data that has a combination of inputs and their outputs (labeled based on whether the output FITS into the characteristics or not), could a pattern be found so that in the future we could know which combination of inputs would give us an output that complies with said characteristics?

Thanks in advance!

The output of hash functions is commonly indistinguishable from random (randomness of the output is not a direct requirement for secure hash functions); this is certainly the case for SHA-256. So trying to find any correlation between inputs should be impossible - if there is some kind of pattern on different inputs it was created by chance.

If you would find such a correlation then the hash function would be considered broken. Deep learning should therefore be considered another way of attacking the hash using machine learning, as the comment from SAI Peregrinus indicates.

An important note in this case is that Merkle Damgard constructions such as SHA-256 are susceptible to length extension attacks, which means that SHA-256 is not a random oracle. That won't help you finding a pattern in separate input messages so I don't think it should influence this answer.


Finding out the greater number under zero-knowledge conditions? Is it possible to construct a zero knowledge proof that one encrypted number is larger (or not) than another encrypted number without releasing the values of either numbers?

Yes, it is possible. Actually, any statement in NP can be proven in zero knowledge. This means that if something can be proven by releasing some information, it is possible to prove the same without releasing any information, i.e. in zero knowledge.


AES Decryption Process How the decryption process of AES is the reverse process of Encryption process of AES? Mean Reverse in what sense mean final round would be conducted first or steps in each round would be conducted first? Please Guide me...

Reverse in a sense that every step done in encryption needs to be reversed. For Sbox, there is an Inverse Sbox. For MDS, there is an inverse of MDS(invMDS) such the multiplication of MDS and invMDS is an identity Matrix. Since inverse of XOR is xor, so round keys are xored in decryption but in reverse order meaning, round 10 key is xored first, then round 9 and so on.

If you write down all the encrypting steps done between Plaintext and Ciphertext from Top to Bottom, then while decryption, you need to inverse of each step from Bottom to Top (moving from ciphertext to plaintext)


Secret sharing between a very large number of participants What can be a method for sharing a secret between a large number of participants?

With Shamir's Secret Sharing (k,n), n can be arbitrarily large, but increasing k increases the complexity of the keys generation.

Is there an algorithm that can realistically generate keys for value of k between 1,000 and 1,000,000?

Is there an algorithm that can realistically generate keys for value of k between 1,000 and 1,000,000?

How about Shamir's Secret Sharing method?

For $k = 1000000$, generating a share would take a million field operations (multiplications and addition); this can be done in a few milliseconds per core (depending somewhat on the field you pick; there are CPU friendly ones out there).  Obviously, for the shares to be usable, you'll need to generate at least a million of them; this could be done in circa an hour on a laptop; that doesn't sound unrealistic to me.

If taking an hour to generate a million key shares is too expensive, what are the performance requirements?

Combining $k$ shares to reconstruct the secret takes $O(k)$ field operations; this is obviously quite reasonable; actually loading the shares is going to be the bulk of the work.


Disadvantages of this crypto system Consider the following

Alice and Bob agree to an encyption system based on a solution to a complex chemical simulation
Alice announces publicly that her "key" is the chemical tryptophan. Therefore any solutions with tryptophan as an input belong to Alice.
A public distributed ledger exists.
Alice publishes her tryptophan choice on the ledger.
Now alice can create simulations combining tryptophan with other unclaimed chemicals.
The simulations are computationally expensive and can't be readily solved by quantum attacks. (Nobody is proposing a cheap way to simulate chemical reactions using quantum computers, and replicating the reactions directly requires manual effort).
Alice does not publicly publish the solution. She only publicly publishes that she has a solution for converting tryptophan to another specific chemical.
Bob values that solution and offers to trade with Alice.
Alice privately transfers the solution to Bob as payment for a good/service
If Alice decides to double-spend the solution, Bob can publicly publish it (and make it worthless).
If Eve steals the solution either can also reveal it and make it worthless.
Therefore as long as it is kept secret, the solution to this chemical reaction serves as a transferable store of value that is not subject to attack.
The value of the solution depreciates as it is spent more because more people have it.

What are the problems with this?

Also, you could also have it so the data in the solution is so enormous that it cannot be easily published or stolen. Bob would receive permission to access Alice's cluster to use the data but it would be impractical to steal it.

A chemical simulation based proof of work? Interesting, but let's ignore how the mathematics work for generating a solution based on my input key being "rhubarb". And zero knowledge based verification of said vegetable? Seems tricky. Must we assume that a 'simulation' is akin to a one way function/hash/mining?

But I would focus on #8, valuation.  A floating currency is set by the market environment, not individual consumers on a per contract basis.  How can Bob set a realistic price for your ChemiCoin(TM)? Especially as they're not underwritten by tangible assets.  I think that I'd mow your lawn for 100 ChemiCoin(TM). But if no one else values them similarly, I've effectively consumed my resources for no reward.  That's bad capitalism and realisation would be neigh on impossible.

#8, part 2. How can Alice validate execution of the contract if the other party is not reciprocating with ChemiCoin(TM) transactions on the ledger?  Did I really mow your lawn?

And on #13.  What use treasure if it can't be spent? At least the Pharaohs could spend their accumulated gold and jewels in the Underworld.  The more ChemiCoin(TM) I possess, the more I want to spend them. But they depreciate accordingly.  So why amass them in the first place?  I may be getting poorer the richer I get, and don't mean  morally.

It all seems very tricky mathematically and economically, with a highly divisive set of cryptographic ideas.


SHA's finite character set and collision From what I've researched, SHA's hex encoded string contains the characters [a-fA-F0-9]. If we represent it in Base64, it can contain [a-zA-Z0-9+/].

So the number of possible hash permutations are 22^64 and 59^64 respectively.

My question is, while we have infinite permutations for the input text, if the output hash is finite, then aren't all SHA algorithms meant to collide at some point?

I'm self taught. So please bear if this is a basic thing in cryptography.

My question is, while we have infinite permutations for the input text, if the output hash is finite, then aren't all SHA algorithms meant to collide at some point?

Due to the pigeonhole principle, all hash functions will collide at some point. Since there are more inputs than outputs, the existence of collisions is unavoidable.

The job of a cryptographic hash function is to make finding collisions cost so much that it will never happen, and to make finding preimages prohibitively expensive as well.


How were shift amount constants in MD5 found? The md5 specification gives a series of 4 rounds to execute over a 16-word block.

Each round has a repeating sequence of 4 shift amounts (s in [abcd k s i]) :

7, 12, 17 and 22 for the round 1
5, 9, 14 and 20 for the round 2
4, 11, 16 and 23 for the round 3
6, 10, 15 and 21 for the round 4

The specification only says:

  The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

How did they find these shift amounts? Is it a sequence like $u_n = (u_{n-1} + j) \; mod \; k$ ? What guarantees the "avalanche effect"?

The rotation countsr (together with the order of access of the 4 words of the state) are engineered for fast diffusion, as documented in RFC1321:

  The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect". The shifts in different rounds are distinct.

The general idea is to move bits to a 32-bit position on which they previously had no or little influence (limited to the effect of carry propagation in 32-bit addition, which works only to the left, and has odds like $2^{-n}$ to influence the $n$th bit on the left of a particular one); also, the choice made should facilitate efficient propagation in the next few steps. Among particularly bad choices would be to change the constants r to a mix of 1 and 31; or to all 16.

I do not know if the choice made for MD5 turned out to prevent or facilitate attacks on collision-resistance.

All the other constants in the question are chosen with a nothing-up-my-sleeve rationale; that is, convincingly unlikely to have been chosen according to a hidden property. That includes numbers computed according to a simple formula unrelated to the rest of the context (like floor(abs(sin(i + 1)) × 2^32) is); or numbers matching an obvious pattern (like being the representation of the hex string 0123456789ABCDEFFEDCBA9876543210 according to the endianness used in the context).


secret sharing with 3 parties under constraint Suppose we have $3$ parties Alice, Bob and Charlie such that Alice can't talk with Bob.

Suppose that Alice has some string $x\in\{0,1\}^n$ and Bob has a string $y\in\{0,1\}^n$.

Suppose that Alice and Bob have access to a shared random string $r$ and a shared secret $s$.

Suppose that Charlie knows both $x$ and $y$ and he doesn't have access to $r$.

  Describe a protocol in which Alice sends one message to Charlie (it may depend on $x,r,s$) and simultaneously Bob sends one message to Charlie (it may depend on $y,r,s$). Afterwards, if $x=y$ Charlie will know $s$ and if $x\neq y$ Charlie will not be able to know $s$.

The general context of this problem is secret sharing, e.g. Shamir's secret sharing and so on.

I have a proposition for solution to the inverse version of this question, i.e. if $x\neq y$ Charlie will know $s$ and if $x=y$ Charlie will not be able to know $s$:

My proposition is to think of $x,y,r$ as members of the field $\mathbb{Z}_{2^n}$.

Alice computes $s+rx$ and sends it to Charlie.

Bob computes $s+ry$ and sends it to Charlie.

If $x\neq y$ Charlie can interpolate to get $s$, otherwise $x=y$ and Charlie only saw some random element of $\mathbb{Z}_{2^n}$: $s+rx=s+ry$, so he can not recover $s$.

But this is not the original question and I don't know what to do with the original.

Can we generalize it to some boolean function $f:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}$, i.e. only if $f(x,y)=1$ Charlie will be able to recover $s$?

This problem is known as conditional disclosure of secret in cryptography. There have been many nice recent works on the subject, I suggest having a quick look at this one for example.

In you exact scenario, can $r$ be of length $2n$? If so, here is a simple solution: call $(r_0,r_1)$ the left and right parts of $r$, each of length $n$.

Alice sends $s + r_0x - r_1$
Bob sends $r_1-r_0y$

Because of the mask $r_1$, these two values only leak $(s + r_0x - r_1) + (r_1-r_0y) = s + r_0(x-y)$. If $x=y$, this discloses $s$; otherwise, $r_0(x-y)$ perfectly hides $s$ (addition and multiplications are performed over $\mathbb{F}_{2^n}$).

Regarding your second questions, yes, there are results on conditional disclosure of secret for arbitrary functions. The best result we know of for arbitrary predicate $f:[N]\times[N] \mapsto \{0,1\}$ has communication $2^{O(\sqrt{\log N \log\log N})}$. For predicates represented by a boolean circuit, I think we can have communication linear in the circuit size, but I would need to check this.


Using hash functions for Key Check Values (KCV) As discussed in this post, calculating key check values for block cipher keys can introduce vulnerabilites. Plus, this method only applies for block ciphers, and there is no equivalence for private keys used for asymmetric cryptography (although an alternative is given in an answer of this post, the KCV size is huge in this case).

Would it be relevant to compute a hash over the key (with SHA-2 or any other secure cryptographic hash function) and to consider the $n^{\text{th}}$ first bytes ($n = 3$ for example)? Or could it introduce weaknesses in some specific cases?

To answer this question, the first thing is consider is "why do we have a key check value at all?  What benefit do we hope to gain from it?"

From my perspective, it would appear that the main use of a KCV is to quickly catch it when we attempt to decrypt a message with the wrong key.  This implies:

It makes sense only if attempting to decrypt the message with the wrong key is a plausible occurance.  The main case where this makes sense is if you are assuming the user will manually enter the key or the seed to generate the key (and might typo it).
It makes sense only if it is necessary for you to quickly detect an incorrect key.  Normally, we strongly suggest that when you encrypt, you include some sort of integrity check (as there are a number of clever methods known where an attacker modifies the ciphertext, and learns something from how the decryptor reacts when it decrypts it); if you enter the wrong key, presumably the integrity check would fail, and you'd notice that the key is wrong.  So, the only real value a KCV would bring is that you can determine whether the key is correct quickly (before decrypting the potentially large file).

Now, if the key is low entropy (which a manually entered key or key seed would be), a KCV would make it easier on the attacker to do a brute force search; instead of decrypting the entire file and seeing if it works, he could just check the KCV, and reject most of the incorrect entries in the database.  You could try to slow him down by using, say, Argon2 to generate the KCV, however that'd void the entire reason you have a KCV in the first place.

With that background in mind, lets go over your questions:

  Would it be relevant to compute a hash over the key and to consider the $n$th first bytes

If you actually need a KCV (see above for why it is only occasionally appropriate), then this would work (assuming, of course, that you don't use the hash of the key for anything else; if you do, you'll run into exactly the same issues that Maarten warned you about).  So, yes, this could introduce a weakness, if (for example) you are using $SHA-2(password)$ to encrypt the first several bytes of your file.

And, for a block cipher, encrypting a block of all 0's, and using a few bytes from that, would work as long as the cipher block mode you use doesn't rely on the encryption of the all 0's block; for example, counter mode standard at a random nonzero counter would work; also CBC mode with a random IV would also work.

General rule: if you use the password in multiple ways, you need to consider that those multiple ways play nicely together, and the one usage doesn't leak information that the other usage needs to keep secret.

  there is no equivalence for private keys used for asymmetric cryptography

Actually, if you don't mind leaking who you're encrypting the message to (in my experience, you usually don't; if I email an encrypted message with Alice with Alice's public key, well, Alice's email address will appear in the SMTP header), then it's easy; just hash the public key and that's the KCV.  Alice knows her own public key, and so should be able to recognize the hash of it (and reject any encrypted message with a different hash).


Random data CBC padding scheme? When using AES in CBC mode, padding is required when the last plaintext block has not the length required by the cipher. Let's say $k$ mode bytes would be required to fill the block. My idea was to pad the last block with $k-1$ random bytes followed by one byte that corresponds to the integer value of $k$ (or $k-1$). That is, it tells how much padding was added. When decrypting, the previous decrypted block is held back, until it is clear that it was not the second to last block. If it was, the padding is removed accordingly and the full plain text is obtained.
Is this a secure way to pad a message?
More generally, are there problems that may arise from this method of padding, or can an incorrect padding scheme compromise the cipher?

Padding is dangerous. CBC mode with padding is secure against chosen-plaintext attacks, where the adversary can convince the legitimate party to encrypt messages and obtain the ciphertexts. But it is usually not secure against chosen-ciphertext attacks, where the adversary can craft ciphertexts and obtain information about the corresponding plaintext. Specifically, padding tends to be vulnerable to padding oracle attacks, where the adversary sends specially-crafted ciphertexts and does not obtain the corresponding plaintext, but finds out whether the padding in the ciphertext is valid. The adversary might find out, for example, because the decryptor emits an error message if the ciphertext is invalid, or because the decryptor does not carry out the action that it would carry out on a valid message, or because the decryptor takes a different amount of time to process messages with valid or invalid padding.
How devastating padding oracle attacks are depends on the nature of the padding and how much partial plaintext the adversary is likely to know. A well-known example is the Lucky Thirteen attack, where the conjunction of allowing up to 256 bytes of padding, and having 13 bytes of known plaintext in a message header, leads to a practical attack to fully decrypt a TLS connection against an unprotected implementation in many realistic scenarios.
In your case, the opportunities are more limited for the attacker, but the scheme is still vulnerable. Suppose the adversary knows or can guess the first 15 bytes of plaintext in a block and would like to know the last byte. The adversary can send that block to be decrypted as a 16-byte message, and learn at least whether the last byte is a valid value (1 to 16). This is not a complete breach of confidentiality, but it is a breach of confidentiality.
Padding oracle attacks depend on the adversary learning whether the padding is correct. A defense is to not have any invalid padding. An easy tweak to your scheme has this property: make the top 4 bits of the last byte random as well. This way no padding is invalid and therefore no padding oracle attack is possible as such. However, the adversary may still be able to learn the length of the plaintext (for example by measuring very precisely how long it takes to process), and if the ciphertext was one crafted by the adversary, this length could be in fact a confidential byte of the message.
To have an actual secure cipher, you need to use authenticated encryption. Authenticated encryption is not vulnerable to chosen-ciphertext attacks because the attacker cannot forge a superficially valid ciphertext: all valid ciphertexts include an authentication tag which cannot be calculated without the secret key. You can build authenticated encryption by taking unauthenticated ciphertexts and adding a MAC (“encrypt-then-MAC”), and that works even if the encryption part is padded CBC. On this topic, see Should we MAC-then-encrypt or encrypt-then-MAC?. However, CBC has no advantage over streaming mode, and all common proper authenticated encryption modes use CTR mode for the encryption part.


How effective is Serpent-256 in CTR mode? I downloaded a compression program known as PeaZip which offers encryption and 2-way authentication also.

PeaZip has an option to encrypt compressed file with variety of ciphers and one of them is Serpent.

It gives option of:

Serpent 128 CTR OMAC
Serpent 256 CTR OMAC

I want to know how strong any cipher, specifically Serpent, is in CTR mode. Assuming a strong password or truly random key file of appropriate size is used.

I am not aware of how effectively this cipher is handled in PeaZip, but that is a different matter.

Ideally, in which mode Serpent is more effective.

-- Edited --

The details of crypto library which PeaZip uses are here.

Author of this library says about Serpent:

  Serpent (designed by Ross Anderson, Eli Biham, and Lars Knudsen) was one of the AES finalists; it is a 128-bit block cipher with key sizes of 128, 192, or 256 bits. Please note that although my code supports OMAC and EAX, these modes are not tested against public test vectors (the usual C libraries do either not implement Serpent or OMAC/EAX).

Any block cipher within CTR operates the same way; CTR security is only dependent on the block size. Serpent was one of the candidates to become AES. It is thought to have a high security margin (and no weak keys etc). None of the currently known attacks seem to have done much damage to the security claims.

All AES candidates have a block size of 128 bit and a key size of 128, 192 and 256 bits (at least). In your case you just list two key sizes, 128 bit or 256 bit as difference. The higher key size is more secure. As the number of rounds of Serpent doesn't change the greater sized key should be preferred, although the strength of the password is much more important.

In the end, an algorithm is effective when it handles your specific requirements. And in general, the security of the system is very likely not much influenced by the choice of Serpent as block cipher (especially if timing attacks are hard to do such as with file encryption, hardware implementations of AES such as AES-NI may have a small advantage with regards to timing based attacks, besides the obvious performance benefit).


Construct a specific length-doubling pseudorandom generator from a length-doubling pseudorandom Let $G$ be a length-doubling pseudorandom generator (i.e., for any $n\in \mathbb{N}$ and for
any $s\in\{0, 1\}^n$ it holds that $G(s)\in\{0, 1\}^{2n}$). Can you construct a length-doubling pseudorandom
generator $H$ such that $H(0^n)= 0^{2n}$ for any $n\in \mathbb{N}$?

Define $\forall s\in \{0,1\}^{n} \ : H(s)=G(s)\oplus G(0^n)\implies H(0^n)=G(0^n)\oplus G(0^n)=0^{2n}$
now, we'll prove by contradiction that $H$ is indeed a pseudo-random generator.
assuming that it's not we get that there exist an adversary D (PPT algo) such that for every polynomial p(n):
$|Pr_{s\leftarrow\{0,1\}^n}[D(H(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D(r)=1]|>1/p(n)$
Now, define the adversary $D'(v):=v\oplus G(0^n)$ for the PRG "$G$", and we're almost done:
$|Pr_{s\leftarrow\{0,1\}^n}[D'(G(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D'(r)=1]|=$
$|Pr_{s\leftarrow\{0,1\}^n}[D(G(s)\oplus G(0^n))=1]-Pr_{r\leftarrow\{0,1\}^n}[D((r)\oplus G(0^n)=1]|=$
$|Pr_{s\leftarrow\{0,1\}^n}[D(H(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D(r)=1]|>1/p(n)$
$\blacksquare$


Key Derivation Function (KDF) usage for password storage Is it safe to use a KDF implementation in order to store passwords?
More broadly, is this standard? Do IT-companies really use KDF? Or do they usually rely on other algorithms?
If you have any practical example for the second question, I would appreciate it.

Yes and no, depending on what you mean by "storing passwords".
If you mean "storing my own passwords in a password store", then "no", since this is clearly not the goal of a KDF. But if you mean "storing authentication data in a database to authenticate our users", then yes, since passwords stored in that way are really hard to recover.
And "yes", companies do use KDF and will keep using it more and more. Notably because NIST has standardized their usage in their latest publication on password storage: NIST.SP.800-63b which says that:

Verifiers SHALL store memorized secrets [i.e. passwords] in a form that is resistant to offline attacks. Memorized secrets SHALL be salted and hashed using a suitable one-way key derivation function.
Key derivation functions take a password, a salt, and a cost factor as inputs then generate a password hash. Their purpose is to make each password guessing trial by an attacker who has obtained a password hash file expensive and therefore the cost of a guessing attack high or prohibitive.

and also because nowadays, data leakages are extremely damageable to any company's PR.
There are two different kind of KDFs:

those for when you have a poor entropy and are afraid of Dictionary Attacks (typically if you store humanly memorable passwords), e.g. Argon2, Balloon, PBKDF, etc.
those that you use when you have a good entropy, which would for example be the case if you rely on the DH protocol to establish a common key. Like e.g. HKDF which is thought for such need-case.

The type I'm talking about here is of the first sort, when you store passwords in a database in order to authenticate users.
I personally have a preference for Argon2. Since other like PBKDF2, can be implemented on ASIC devices, which makes brute-force attacks using such devices much easier, or have less parameters one can tweak... Plus it was chosen as the winner of the password-hashing competition.
Now regarding whether KDFs are actually used, you can simply take a look at most password authentications out there and I believe you'll see that the most important ones do... For instance, LastPass advertises using PBKDF2 to protect your password-store main password and you can tweak yourself the number of iteration done. The Django's framework documentation also mention PBKDF2 as being its default algorithm.
Finally, Wikipedia has a nice list of things using PBKDF2. (Which is still the most used KDF, despite the existence of theoretically better ones.)


multi-stage cryptographic computations One potential client is assessing our system by asking some questions to decide if they eventually will choose our service or not.

One of the question is

  All multi-stage cryptographic computations are computed within the secure boundary of the HSM.

I Googled the phrase but I could not find any relevant topics to help me to understand the meaning of the question.

Could any of you give me some example of multi-stage cryptographic computations? Is it same as multi-party computation?

It might mean that any multi-stage cryptographic protocols – which require parties to store temporary data – could be weakened by exposure/tampering of this data. To ensure that does not happen, one needs to protect these intermediate chunks of data and (preferrably) the encryption process itself so that we can trust that, if the protocol finished successfully, it's results are to be trusted.

One of the ways to protect it, is to offload all computations to HSM – which is compartmented from your regular process memory and thus is less likely to be tampered when your server gets compromised.