Identity-based proxy re-encryption using different system parameters I am wondering if there is an identity based proxy re-encryption scheme (such as the Green-Ateniese scheme https://eprint.iacr.org/2006/473.pdf) that converts an encryption computed with ID1, system parameters1 into one intended for ID1, system parameters 2, i.e., the ID is the same but the system parameters change.

This concept is called inter-domain identity-based proxy re-encryption. In this case, the notion of "domain" implies a separate KGC and a set of system parameters.  There are a couple of schemes doing this:

Tang, Q., Hartel, P., & Jonker, W. (2008, December). Inter-domain
identity-based proxy re-encryption. In Information Security and
Cryptology (pp. 332-347). Springer Berlin Heidelberg. Han, J.,
Susilo, W., & Mu, Y. (2013). Identity-based data storage in cloud
computing. Future Generation Computer Systems, 29(3), 673-681.


Can I find the encryption key if I know the plain text and the encrypted text (DES and AES)? If I have the plain text and its output after encryption with a key K1, is it algorithmically feasible to find K1?

I am specifically interested in the cases of DES and AES encryption algorithms.

The most cost-effective way to do this is to try each key and see if it works.  The expected number of trials is $2^{55}$ with DES, $2^{127}$ with AES-128, and $2^{255}$ with AES-256.

You can speed the search up by making many trials in parallel, e.g. by using a million DES circuits making one trial every microsecond, which will give an answer in a few hours, at most under a day—a task that has even been commercialized (note: I do not endorse this commercial service; I am only mentioning it for practical scale comparison).  Note that parallelizing the search doesn't change the overall cost: powering a single circuit for an hour will cost approximately the same energy, and same number of rubles, as powering sixty circuits in parallel for a minute.

If you have many keys $k_i$ which you want to recover any one of given their respective ciphertexts for a common plaintext, then you can do better with a parallel machine that saves repeated effort using Oechslin's rainbow tables.  Say you have $n$ target keys.  A machine parallelized $n^2$ ways with each parallel circuit not much larger than an AES-128 circuit, with a small constant amount of memory for each circuit, can give you your first answer with probability $p$ in about $2^{128}p/n^3$ time, at the same cost as about $2^{128}p/n$ AES-128 evaluations.

For AES-128, these numbers are large, but not unimaginably so.  The Bitcoin network today performs about $30\times10^{18}$ SHA-256 computations every second, about $2^{64}$ per second or $2^{90}$ per year.  If we had trillion ($10^{12}$) AES-128 circuits in parallel attacking any one of a million ($10^6$) keys, we would break at least one of them with high probability using a couple hundred thousand times the annual cost of the Bitcoin network (which has been increasing exponentially since about 2015), assuming the cost of one AES-128 evaluation is approximately the same as that of SHA-256.

Can you break AES-128, or any generic 128-bit function, using this method?  No.  Can humanity?  Maybe.  But definitely not AES-256 unless there's a cryptanalytic breakthrough.  (Quantum computers don't make much of a dent in AES-256 or even AES-192 either.)


RSA: Danger of using p to create q Assume my prime generation is as follows:

Pick a number $p$ between 1000 and 9999. $p=abcd$.
Make sure $p$ is prime
Construct $q$ such by taking the last 2 digits of $p$ and the first 2 digits of $p$, i.e. $q=cdab$
Make sure $q$ is prime.

Is the resulting $n = p·q$ more easily factorable?

My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?

You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 \lt x, y \lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.

The rightmost digit of $n$ in base $B$ is $(x y) \bmod B$. Since $\{x,y\} \le B-1$, $(x^2 + y^2) B + x y \le 2 (B-1)^2 B + (B-1)^2 \lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) \lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 \le z \lt 2$, i.e. $z \in \{0, 1\}$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y \in \{W_0, W_1\}$.

Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.


Why Curve25519 for encryption but Ed25519 for signatures? NaCl and libsodium libraries use Curve25519 for authenticated encryption (actually for sharing a key which is used for encryption) and Ed25519 for signatures. What is the purpose of using different primitives for these operations? Why just not to use the same primitive for both key-sharing and signatures?

Are there some security or performance considerations? But both key-sharing  and signing rely on multiplication of curve point by scalar so I guess you can't gain anything here by using different curves. If one of the curves is faster it should be faster in both cases.

While it is true that Elliptic Curve Diffie Hellman, Elliptic Curve Signature Generation and Elliptic Curve Signature Verification rely on scalar multiplications, these are usually implemented as different types of scalar multiplication for both security and efficiency reasons.

In fact there are three types of scalar multiplications used in practice for these schemes:

Fixed-Base: when the input point of the scalar multiplication is known at design time
Variable-Base: when the input point of the scalar multiplication is not known in advance
Double-Base: when the protocol actually requires to compute two scalar multiplications and then to add the both results. (e.g. $kP+rB$ )

Variable-Base is what is usually needed in ECDH, as you receive the input point of the scalar multiplication from another peer.

Fixed-Base is used in key generation and signature generation. Here the fixed-base is always the "generator point", which is the point who generates the prime-order subgroup that is provided together with the curve's equation.

Double-Base is used for signature verification (both ECDSA and EdDSA and Schnorr) require to compute something of the form $kP+rB$. Note that unlike ECDH or Signature Generation the Signature Verification doesn't make use of any secret values and therefore there are no requirements for constant time execution.

X25519 provides a very simple, constant time, and fast variable-base scalar multiplication algorithms. This is very good for ECDH and this is why it is used specifically for ECDH.

Ed25519 instead provides a very fast fixed-base and double-base scalar multiplications, thanks to the fast and complete twisted Edwards addition law.
In fact, the fixed-base algorithm of Ed25519 is, on most platform, faster than the variable-base of X25519.

And using X25519 for signature verification is just a bad idea because you need to execute it twice (to compute $kP$ and $rB$) and then to add a new function to perform the full addition of the two resulting points. Furthermore you are using constant-time computation where it's not needed. Instead, you can achieve a much faster implementations using interleaved NAF methods and the twisted Edwards addition law.

Note: for the purpose of this answer I'm not distinguishing between different elliptic curve signature algorithms such as ECDSA and EdDSA.


How many bits of entropy are leaked for every derived password from a master? Given a master password that has a lot of entropy (similar to Bitcoin HD wallet seed words, 130 bits of entropy or more) how many bits of entropy are lost per leaked generated password?

Let's take an example of the master password hello stack exchange good to see you and some passwords generated by PBKDF2 with SHA512 with 256k iterations using a tool I wrote

foo.com   mr7i?O5til?2
bar.com   PYOT1-AOhX.D
baz.com   rk!Vxf8G_HgO

Given an attacker has these generated passwords how much easier can they guess the original master password? How many if they have 2/3, 1/3, and how it compares to 0/3 as well?

Thank you!

From an information-theoretic perspective, and with an ideal password hash function,  with $k=68$ possibilities for each character of derived password, each such character leaks about $\log_2(k)\approx6.1$ bit, but only as long as that remains significantly lower than the entropy in the master password. That's a leak of about $73$ bit per derived password. With $130$ bit of entropy in master password, the entropy leak would be about $73$ bit for one derived password, and just shy of $130$ bit for more.

The example password hello stack exchange good to see you is meaningful English text, uniformly-cased, properly-spaced, without digits or punctuation, with 30 non-space characters. It is doubtful that it is representative of passwords with 130-bit entropy; I'd guesstimate 40 to 90 bit, and would not be surprised if almost no entropy remained after one derived password; or/and if that password was by far the simplest for an english speaker (thus most likely) matching a single domain / derived password pair.

However, assuming that PBKDF2-HMAC-SHA512 is unbroken (as it stands), a complete entropy leak is not enough to find the master password (or a derived password for another site) for a compute-bound adversary, as real adversaries are. The entropy computation is useful only to tell how many derived passwords are necessary to carry an attack (here, two are most likely enough, and one might be enough). The best attack remains trying all the possible master passwords, from most likely to least, against one derived password hash (which will weed out most candidate master passwords), then a second selectively in case of success.

With enough derived passwords, the expected difficulty of attack is mostly dependent on the entropy in the master password, and the parametrization of PBKDF2 (which is untold): $2^n$ iterations stretch the entropy in the master password by about $n$ extra bits.

From an information-theoretic perspective, if the master password is chosen in a finite set with probability $p_i$ for each master password and $1=\sum p_i$, it initially has entropy $H=\sum(p_i\log_2(1/p_i))$. When a derived password for a known site (or a symbol of that) gets known, that makes some master passwords impossible, some probabilities $p_i$ go to zero (and are removed from the sum) and the others are increased to $p'_i$ in proportion, so that $1=\sum p'_i$ still holds. The entropy leak is the difference between initial and residual entropy.

In other words, the entropy leak is
$$\sum_\text{all MPs}p_i\left(\log_2{1\over p_i}\right)\ -\ \sum_\text{remaining MPs}\left({p_i\over\displaystyle\sum_\text{remaining MPs}p_i}\log_2{\displaystyle\sum_\text{remaining MPs}p_i\over p_i}\right)$$

When only one master password remains possible, only the left sum remains, and the entropy leak is that of the master password.

If all master passwords are equally likely, the entropy leak is the base-2 logarithm of the ratio of the number of initially possible master passwords, to the remaining number of possible master passwords. When only one master password remains possible, the entropy leak is the base-2 log of the number of all initially possible master passwords.

Assuming the derivation function is a Pseudo Random Function, knowing one of its output (or a symbol thereof) will rule out passwords irrespective of their initial probability. With each output symbol about uniformly distributed among $k$, it can be shown that the entropy leak for $s$ revealed symbol is expected to be almost $s\log_2(k)$ if that's much less than the initial entropy; and is expected to be almost all the entropy in the initial password if $s\log_2(k)$ is much larger.


Relation between Threshold Cryptosystem and Secure Multiparty Computation ? Is there any relation between secure multiparty computation and threshold cryptosystem ?

Yes and no.

A threshold cryptosystem means the decryption key can be split into $n$ shares such that only $t\leq n$ are required to recover it. That property in isolation is not useful for multiparty computation.

However when you combine a threshold cryptosystem with one that is at least partially homomorphic (meaning you can do some operation, like addition or multiplication, under encryption), then the two properties combined can make a useful basis for multiparty computation.

The model is that each party encrypts their inputs, you use the homomorphic property to do some computation on the ciphertexts while they are still encrypted, and the threshold property enforces that only the final value is decrypted assuming less than $t$ dishonest key share holders. Without the threshold (or at least a distributed $n$-out-of-$n$ key), the keyholder could simply decrypt the inputs and learn everyone's value.

The most famous paper on this is "Multiparty Computation from Threshold
Homomorphic Encryption." This approach is used in lots of papers. A different approach in the same model is "Mix and Match: Secure Function Evaluation via Ciphertexts." It is less used (I think maybe a bit overlooked) but you can do interesting things with it.


Is it hard to get Least Significant Bit for Elliptic Curve Discrete Logarithms? It is hard to get Least Significant Bit for Discrete Logarithm systems with composite moduli. However this is because of the hardness of the factoring problem.

Is it hard to get Least Significant Bit for Elliptic Curve Discrete Logarithms?
For which cases is it hard to get Least Significant Bit for Discrete Logarithms?

For any discrete log problem where the order of the generator is even and known, then the lsbit is easy to recover.

Notation I'll use:

I'll be writing things in additive notation (the notation we typically use for Elliptic Curves).  This is just notation; these ideas translate directly to multiplicative groups.
I'll designate the generator used as $G$, and the order of $G$ as $n$; the problem we're given is, given $H$, find $x$ (or the lsbit of $x$) with $H = xG$

And, in this subcase, we assume $n$ is even.

So, to recover the lsbit of $x$, we just compute $(n/2)H$; if this is the identity element, this $x$ must be even; if this is not, then $x$ must be odd.

Next case; for any discrete log problem where the order of the generator is odd and known, then the lsbit is a 'hard bit'; that is, recovering that lsbit is as hard as recovering the entire exponent.

We show this by demonstrating that, if we were given an Oracle that gave us the lsbit, we can use that to recover the the entire exponent.

We start by finding the lsbit of $x$; given $H$, we can query the Oracle directly, giving us $x \bmod 2$.

Now, to find the next bit; we compute $H' = (2^{-1} \bmod n)(H - (x \bmod 2)G) = (\lfloor x/2 \rfloor) G$; we can then query the Oracle with $H'$; this gives us the second bit of $x$.

We can repeat this process, and read all the bits of $x$ in succession.

(This is a bit more complex if the Oracle we get is probabilistic; I won't bother you with the details)

The last subcase is if the order of the generator is unknown.  If we're talking about multiplication modulo a composite, then if the generator has a Jacobi symbol of -1, then it is easy (compute the Jacobi symbol of $H$; if it is 1, then $x$ is even, if it is -1, then $x$ is odd).

And, as Geoffroy Couteau points out, in the case that the Jacobi symbol is 1, this is reducible to the quadratic residuosity assumption:

If the generator $G$ is a quadratic nonresidue, then $H$ will be a quadratic residue iff the lsbit of $x$ is even; an oracle that is able to determine the lsbit of $x$ will allow us to the test whether $H$ is a quadratic residue.
If we had an oracle which worked in the case that $G$ is a quadratic residue (but not if it is a QNR, as above, that's a hard problem), then that could be used as a test to determine whether $G$ is a quadratic residue; generate a random value $x$, compute $H = G^x$, and give $G, H$ to the oracle; if it gives us the correct lsbit of $x$ on a consistent basis, then $G$ must be a quadratic residue.


Are there any noisy homomorphic encryption schemes? Are there any Homomorphic Encryption(HE) schemes that result in noisy answers ? By noisy i mean , the answers could be approximately near the actual answers by noise factor $\epsilon$.

For example , we could get $dec_{sk}(eval_{pk}({enc_{pk}(5) + enc_{pk}(10))) = 16}$ where as the real answer is 15. Here $enc,eval,dec$ are functions of an HE scheme and $sk,pk$ are private and public keys. The scheme could be Fully HE or Semi HE or Partial HE

Yes, on the paper Homomorphic Encryption for Arithmetic of Approximate Numbers, Cheon et al. propose a scheme in which the error is not completely eliminated during decryption.

That is, if $c$ is an encryption of $m$, then $Dec(c) = m + e$, where $e$ is some small error.

Roughly speaking, that scheme simulates floating-point arithmetic, since this type of arithmetic also accumulate errors.

With that, the authors manage to perform operations that are hard to do with exact homomorphic encryption schemes. For example, in Algorithm 2 (page 15), they show how to compute homomorphically $\frac 1 m$ with $r$ bits of precision (with other schemes, that is only possible using bootstrapping...).


SHA-256 exhaustive search How do I calculate the number of computations needed to break SHA256 in case we are using it for safely storing passwords (together with a salt)?
Are there any formulas that can be employed?

For example:

  Passwords are chosen to be 5-character strings composed of lowercase Latin letters and numbers, and are stored as SHA256(password XOR s)||s, with s chosen as a 5 byte array filled with random content.

Possible password search space = $36^5$ = 6.05 million possible combinations or ~$2^{26}$.  If the passwords were randomly generated it would be 26 bits of entropy which isn't just weak it is pointless.

To put that into perspective the throughput on modern GPUs is on the order 1 billion SHA-256 hashes per second.  So the exhaustive search time to break an account would be 60ms.  An attacker could break about 60,000 accounts per hour.

Rainbow tables are a non issue as you are using per record random salt.  It is too short to be fully effective but given how weak it is generating the rainbow tables would take far longer than just breaking all the accounts.


What is the rationale design of TinyJambu-LWC? My understanding of duplex construction is usually initialized with the key at the beginning of the mode, but  I have noticed that TinyJambu (in addition to key intilization) is using key in each processing call (keyed permutation)  as shown in figure.

my questions :
Is there a particular advantage of keyed permutation in duplex construction than an unkeyed permutation ?

There is indeed an advantage but it only makes sense if you understand how the initialization stage works.

TinyJambu is generally designed for a hardware implementation with a fixed key, and the key also burned into the hardware. Think an IOT device that reports data, but where there is a chance of theft and you dont want the key extracted, as the attacker has copies of all the ciphertext. Even worse, the attacker may want to forge messages.

TinyJambu uses a single keyed permutation $P$ based on a NLFSR, this is iterated a number of times depending on how it is used and how large the key is. $P_n$ refers to the permutation iterated $n$ rounds. Note the diagram P1 and P2 are NOT $P_1$ and $P_2$, but rather a permutation step where $n$ is based on key size.

In the initialization stage, the key is not added to the state by XOR like in a typical sponge based cipher, rather it is permuted using $P_{1024}$, this effectively mixes the key into the state, but allows the key to stored only as part of the permutation.

After the state is keyed, the nonce is added 32-bits at a time. First a domain separator bit is added to the state, then it is permuted with $P_{384}$, then a nonce word is XOR'd. Once again the permutation is keyed here, so there is additional key mixing into the initial state.

In P1 and P2, P1 is equal to $P_{384}$, and P2 is $P_{1024}$ or larger, based on key size, in 128 round increments. The nonce is basically added using P1, just like the AD. Additionally, since the AD comes after the nonce, it changes the state in the same way, so nonce reuse with different AD does not compromise security.

So back to the question, what is the advantage of keyed permutation in duplex construction? Primarily to keep the state small, but also to make the cipher lightweight, as all key addition and permutation are part of a single operation. The designers also say:

  When a key is already stored in the device, the state of the cipher could be very small since we can use the keyed permutation to prevent an attacker from computing the states offline and launching the state collision attacks using the computed states

With a state size of only 128-bits, it is possible (not probable) to compute the keyed initial state in advance and crack the whole cipher, but making the permutation keyed makes that even more infeasible.


Checking for factor base In algorithms like Dixon's factorization a factor base is used, which contains all primes below a bound.

Then calculates  $x^2 \mod n$, and then checks it is in factor base or not.

Suppose $P$ is the factor base for bound $B$.

We calculate the value $x^2 \mod n$, then how to check whether the result contains only prime factors from the factor base?

Let $x^2 \mod n=q_1^{e_1}q_2^{e_2}q_3^{e_3}\cdots q_k^{e_k}$
and $P=\{p_1,p_2,p_3,\cdots,p_l\}$

Then how to check whether each $q_i$ is present in factor base? and how to get corresponding arity $e_i$?

Is it achieved by repetitive division or by means of any other efficient methods?

It can be done using any method you have at your disposal. Obviously, the more efficient method you use, the more efficient your algorithm will be, but even using trial division will yield a significantly more efficient algorithm than if you used trial division for the entire factorisation. Algorithms based on elliptic curves are also commonly used since they are especially good at identifying small prime factors.

By the way, this is not directly related to cryptography so you may get better answers on Math.SE.


AES column mixing and S-Box confusion I am trying to understand the AES encryption algorithm. I know that we process 128 bits at a time for a 128 bit key in a 4x4 octet form, but am confused by the following:

How does the substitution subround work, as the size of the Rijndael's S-box is 16x16 Octets and size of the input is 4x4?
How does the mixed column operation work on the 4-octet column?

You should think of Rijndael's S-box as a function that maps bytes to bytes, where a byte (octet) is considered to be a member of a finite field of size $2^8$ (with xor as addition). It's not seen as a 16x16 octet array, really.

The substitution is then just done byte-wise: every octet in the 4x4 block is replaced by its function value under the S-box table.

The mix column is just a matrix multiplication of the column with a 4x4 matrix, all in the field of size $2^8$. See the wikipedia entry for a worked example.


Guessing the IV for CBC If I have the key, the ciphertext under AES-CBC and the plaintext, then how can I guess the initialisation vector?

CBC mode decryption for the first block is defined as:

$$P_0 = IV \oplus D_k( C_0 )$$

where $P_0$ is the first plaintext block, $C_0$ is the first ciphertext block, and $D_k$ is the decryption by the block cipher using the key $k$.

This can be rearranged as:

$$IV = P_0 \oplus D_k( C_0 )$$

which allows you to reconstruct the IV, if you know the key, the plaintext and the ciphertext.


Secure Multiparty Sum in malicious model using threshold encryption Suppose $n$ actors each hold a plaintext $p_i$. We wish to find $\sum p_i$, without leaking any information about individual $p_i$. Any actor (or any link in the network) could be controlled by an active adversary. More precisely, these protocols can be proved secure against a polynomial time bounded adversary who can corrupt a set of less than $n/2$ parties initially, and then make them behave as he likes, we say that the adversary is active.
In article Multiparty Computation from Threshold Homomorphic Encryption there is approach to multiparty computation (MPC) basing it on homomorphic threshold crypto-systems. I'm unsure how to make multiparty sum secure in malicious model (against less than $n/2$ active adversaries) following this approach. I'm under impression that it's quite simple:

each player uses additive homomorphic encryption to calculate ciphertext $E(p_i)$ of his own imput, sends the ciphertext to other parties and attach proof of plaintext knowledge to the ciphertext
verify proofs, add ciphertexts to calculate $E(\sum p_i)$
decrypt sum $E(\sum p_i)$ using threshold decryption to calculate $\sum p_i$

Could you confirm that what I described above is secure in malicious model (against less than $n/2$ active colluding adversaries)?

You are on the right track. However, as Ricky Demer points out in the comments, your suggestion would not work because the input is encrypted with different public keys. To fix this you need to use the properties of the threshold-encryption scheme.

In a threshold-encryption scheme the players run a key-generation protocol in order to generate a common public key $pk$, and a secret sharing of the secret key $sk$. This means that while all players hold $pk$ no single player holds $sk$. I.e., all players can encrypt but no one can decrypt without the help of the other players. In order to decrypt the players run a special decryption protocol.

So in other words your suggestion is almost correct, only the players do not hold different public encryption keys. To fix it you need to add an other step before step 1 where the players collaborate to generate keys. And in step 3 the players do not decrypt on their own. Instead they run a decryption protocol among each other.

This works because you only want to compute a sum (i.e., you are only doing additions). However, in general you could compute any arithmetic function. The only problem is that since you are using a additively homomorphic encryption scheme, doing multiplication is not as simple as addition. This is solved by running a special multiplication protocol among the players for every multiplication.

These days of course you could use a fully homomorphic threshold encryption scheme instead of a additively homomorphic one. In that case you would no longer need a special multiplication protocol. The reason why the authors of the paper you are linking to do not use a fully homomorphic scheme is simply that those were not invented when the paper was written.

This is just a rough description of course. For more detail I recommend you read the paper you linked to.


Decryption of message in IBE without random oracle using bilinear pairing registration? I find the following IBE scheme from the videos posted and i don't understand the decryption algorithm, will any one please elaborate  the  6th step

scheme

Setup($\lambda$)  :     $(\mathbb{G}, \mathbb{G}_T, g, P)$   <-- GenBilgroup($\lambda$)

$\alpha\leftarrow_R\mathbb{F}_p$
Public Parameters :   $pp = [ g , y = g^\alpha  , g_1, h ] \in \mathbb{G}$
Master secret : $mk = g_1^\alpha $
Keygeneration:  $k(mk,id)$: $d_1= mk\cdot(Y^{id\cdot h})^r, d_2 = g^r $
where   $r\leftarrow_R\mathbb{F}_p $
Encryption: $E(pp,id,m)$ :  $c_1 = g^s, c_2=(Y^{id\cdot h})^s, c_3=m\cdot e(y, g_1)^s$
Decryption: $e(c_1,d_1)/e(c_2,d_2)$ will give $e(y,g_1)^s$  How?
             and $m$ is obtained by dividing $c_3$ by that value.

I don't know whether it is correct

$$e(c_1,d_1) = e(g^s, mk\cdot(y^{id\cdot h})^r)$$

$$=e(g^s,mk)\cdot e(g^s, (y^{id\cdot h})^r)$$

$$= e(g^s , g_1^\alpha ) \cdot e(g^r , (y^{id\cdot h})^s)$$

$$= e(y , g_1^\alpha ) \cdot e(g^r , (y^{id\cdot h})^s)$$

$$e(c_2,d_2)  = e((Y^{id\cdot h})^s , g^r)$$

$$= e((Y^{id\cdot h})^s , g^r)$$

therefore $e(c_1,d_1)/e(c_2,d_2) =  e(y , g_1^\alpha )$


How many computations does it take to figure out the input if you know the function and you know its output to another known function? I have no background in cryptography so excuse me if this question is a little basic or poorly defined. I'm trying to build a circuit using microcontrollers that implements a hash function of some arbitrary number that a user inputs. I want to make it such that the person is able to select from a small list of hash functions the circuit is able to accommodate, for example SHA-2, MD5, etc.

What I'm wondering is how "easy" it would be to figure out what someone's input was if they knew exactly what hash algorithms they used and they knew the outputs, where by "easy" I mean how would the number of computations it would take to figure out the input scale up with the bits of the input? Linearly? Exponentially? Is there some general equation or guideline to figure out the maximum number of computations it would take (based on the number of inputs) that doesn't depend on the hash functions themselves, or would it always? I'm assuming that with infinite computations it would be possible, but correct me if I'm wrong.

For the above question I was assuming that you didn't know the number of bits of the input, but if you DID know the number of bits of the input, would that make computing it any "easier" in the same sense?

And lastly, if you also assumed that you knew that the bits were preceded by leading zeros when the number of bits of the input was smaller than the number of bits that the hash function can accommodate, would this change anything?

Please let me know if there are any details I'm missing and I'll try to reformulate. Thanks!

What you are describing here is attacking a password. The very definition of a cryptographic hashing function includes resistance to preimages. If you are given hash(x), it should be impossible to recover x. So not a lot of the information you state here will help you recover the preimage.

However, what you are touching on is brute forcing attacks. In that case you would take preimage X and perform hash(X) to determine if hash(X)==ExpectedHash. You do this for every possible combination that X could be until they are in fact equal. Then you do this for each hash.

As for how many computations would be required. That is a function of entropy. For example, the required information:

how many bits are required [min-max]
what is the maximum possible combination on each byte
is there any known space

and yes this problem would rise exponentially. say I have a password that can only consist of 0 or 1. That means I have 2 possible combinations for any position of my password. However adding an additional character to the password means that there are 4 possible combinations now, 00, 01, 10, 11. For each additional character I add adds more combinations in the form of 2^n. For very large bit counts this problem becomes extreme (which is kind of the point really). The end result of computations would be:

[# of computations per hash function of one preimage and compare]*[2^n]=[# of computations required]

Where n is the length of the password. This problem is even worse if you don't know the length of the password.

Some things you can do:

If you know certain things about the preimage you can reduce the number of calculations required. In your example you mentioned per-appending 0s. Well it might help, but only if it means you always know the length of the preimage. In that case it helps and in no other way (you cant say for sure how many 0's are in the image, and where they are). All you have done is said "there is no less number of bits than this, and no more" reducing the problem to a certain number of bits per preimage. Otherwise you would also have to try each combination from [0] all the way to [111111111...n]. The only thing you could do is say, I know that there are this many bits in the preimage. so only 2^n combinations. Now start from 0 and pre-append 0s from the last bit to the first. This would be the best method for this. But still require at maximum the number of computations listed earlier. Since you don't know if any 0s at all were pre-appended.

So to sum it up, Yes it can help, but in reality only in reducing the problem to one exponent. I don't think you can get lower than that without something really clever. Hope this helps!


why was padding changed when keccak became sha3? In the original Keccak you would pad by adding a 1 bit proceeded by a predetermined amount of 0 bits and then another 1 bit.

When Keccak was standardized to sha3 the padding was changed. It was then (unless you needed to pad by just one character) 0x06, followed by a predetermined number of 0 bytes and then 0x80.

My question is...  why was this change made?

It accomplishes 2 things.

SHA-3 hashes of the same input will be distinct from Keccak hashes with the same rate/capacity.
XOFs (SHAKE) with the same rate/capacity will start also with distinct hash output, when compared to both SHA-3 and Keccak

There is no change to security or performance, although having SHAKE share a prefix with a hash of the same input would have been considered a security concern.

Also, padding conventions differ between the implementation and the code, the difference between SHA-3 padding and Keccak padding is minimal. SHA-3 still supports inputs in bits rather than bytes, and the padding is also bit based.


Proven secure scheme under random oracle Currently I am trying to understand random oracle model in order to make a small presentation about it but I seem to be very confused about it.

Since it's an hypothetical model without a real life application (no function can be completely random), how cryptographic functions are modeled as random oracles (e.g are all hash functions modeled as random oracles?) and how can a cryptographic scheme can be secure under random oracle if there is not concrete proof or implementation of that model?

I think that one difference of standard model with the random oracle model is that is actually secure under some assumptions. Are there any security proofs for random oracle at all?

Can you give an example of a cryptographic protocol/function modeled as an random oracle and one that is not?

Is a hash algorithm an secure under RO until there is a proof that it isn't? (Doesn’t  sound very logical).

I have read various sources and most posts from this sitw for random oracle but I didn't find much answers to the ones I stated, so I hope this won't be labeled as duplicate.

Indeed, this question is answered by What is the "Random Oracle Model" and why is it controversial?. However, I would like to add a few more thoughts on this. (Please read the other answer as well, since I will not repeat the very important things said there.)

First and foremost, the random oracle is a model and not an assumption. We do not assume that hash functions are random oracles (until proven otherwise) because they are provably not random functions, and they are trivially distinguished from such. Rather, we prove a scheme secure when a random oracle is used instead of the hash function. This is all that the proof of security says. It says nothing whatsoever about the security of the scheme with a concrete hash functions instead.

The claim to security of the real scheme with a concrete hash function is then a "leap of faith" that if the scheme cannot be broken in the random oracle model, then it is very unlikely that it will not be broken with a real hash function. In other words, this is a heuristic argument. Although highly unsatisfactory from a theoretical perspective, this has proven itself quite well over the past decade or two in that real protocols proven secure in the random oracle model are rarely (if ever) broken.

Some people claim that the random oracle model is no different from assuming things like that the discrete log problem or RSA problem is hard. I completely disagree with this. If someone breaks a protocol that is proven secure under the RSA assumption then this will be translated into an attack on RSA. Thus, this is a rigorous proof of security that holds under a given assumption. In contrast, as I have mentioned, the random oracle is a model and not an assumption.

Finally, consider a MAC defined by $h(k||m)$. This is secure in the random oracle model but not secure for any Merkle-Damgård based hash function. Thus, there is clearly a separation.

Personally, I am happy to live with a random oracle in practice when there are not efficient enough alternatives. However, I will always prefer to get rid of a random oracle, and view doing so as an important research goal. We only have IBE since the first constructions used a random oracle, and afterwards future research managed to get rid of this use. Thus, as with many cryptographers, I have a love-hate relationship with the model.


What is the keyspace of 2-key 3DES? I am assuming that 2-key 3DES is equivalent to 2DES. I know the key size is 2x56 = 112 bits.

Is this key size the same as the keyspace? e.g. Would the keyspace be 112 bits ($2^{112}$)?

Yes, two-key triple DES has a 112-bit keyspace.  That is to say, it has 2112 distinct possible keys, each of them made up of two arbitrarily chosen 56-bit single DES keys.*

Note that, for historical reasons, DES keys are typically represented as strings of 8 bytes, with each byte containing 7 key bits and one parity bit, for a total of 56 + 8 = 64 bits.  But since the parity bits cannot be freely chosen (they are calculated based on the key bits) and are not used for any cryptographic purpose, they are not counted as part of the effective key length.  As 3DES keys are made up of single DES keys, they inherit this historical peculiarity.  Thus, a two-key 3DES key would typically be stored as 16 bytes containing a total of 112 key bits and 16 parity bits.

It's also worth noting that the keyspace size is not necessarily the same as the security level of a cipher, even though both are commonly measured in bits — they are only the same if there is no known way to break the cipher faster than by exhaustive brute force enumeration of the key space.  Two-key 3DES does have known attacks that are faster than brute force, which is why, despite its 112 bit key length, its security level (as estimated by NIST) is only about 80 bits.  That is to say, breaking two-key 3DES encryption using the best known attacks is estimated to require about as much computing power as exhaustively testing an 80-bit keyspace by brute force would require.

And no, as Christoph Egger notes, two-key triple DES is not the same thing as double DES.  While both have the same keyspace size, double DES is vulnerable to even worse attacks than two-key triple DES, and its security level is not significantly higher than the approximately 56-bit security level of plain old single DES.

*) Sufficiently pedantic readers might quibble about whether all of those 2112 keys should really be considered valid.  Certainly one could argue that keys where both 56-bit halves happen to be identical, or where both halves happen to be weak, should be avoided.  But that really makes no difference either way, since such questionable keys only make up a vanishingly small fraction of the full keyspace.


OCB and GCM security Is OCB as secure as GCM or CCM ?

Since OCB design is quite different from GCM and CCM, I was wondering if the security properties of these latters are satisfied by OCB, as well.

If you look in the OCB submission for CAESAR, you will see that the designers state the security is similar to that of GCM. I would note, however, that GCM has been shown to posses weak key classes, see for example:

https://eprint.iacr.org/2013/144.pdf
https://eprint.iacr.org/2011/202.pdf
http://www.ecrypt.eu.org/hash2011/proceedings/hash2011_03.pdf
https://about.bozhu.me/paper/lgcm.pdf


Simultaneous Discrete Logarithm with Small Exponent Given two distinct safe primes $p_1 = 2 \cdot q_1 + 1$, $p_2 = 2 \cdot q_2 +1$, consider the following two instances of the discrete logarithm problem with the same unknown exponent $x$.

$$ g_1^x \equiv y_1 \mod p_1 $$
$$ g_2^x \equiv y_2 \mod p_2 $$
where the multiplicative orders of $g_1, g_2$ are $q_1, q_2$ respectively.

In general, we can solve the two discrete logarithms independently to find $(x \mod q_1)$ and $(x \mod q_2)$, then combine with the Chinese Remainder Theorem to get $(x \mod q_1 q_2)$.

Can we do better if we know that $x$ satisfies $ 0 < x < \min(q_1, q_2)$? Is there any approach faster than solving one of the discrete logarithms?

For $i\in\{1,2\}$ it is given prime $p_i$ with $q_i=(p_i-1)/2$ also prime, integer $g_i$ of multiplicative order $q_i$, and integer $y_i$ such that for some untold integer $x$ common to both $i$, it holds ${g_i}^x\equiv y_i\pmod{p_i}$.

With the additional information that $0<x<\min(q_1, q_2)$, if we can solve either of the two Discrete Logarithm Problems, then we can solve the other with a single modular reduction.

Proof: WLoG, say we solved for $x$ the DLP ${g_1}^x\equiv y_1\pmod{p_1}$ and a solution is $x=x_1$ (swap the indices if we solved the other DLP). Compute $s=x_1\bmod q_1$. It holds that all solutions to that DLP are of the form $x=k\,q_1+s$ with $k\in\Bbb Z$. And $x=s$ is the only solution to that first DLP with $0\le x<q_1$. Hence $s$ is the only possible solution to that first DLP matching the stronger condition $0<x<\min(q_1, q_2)$. Hence that $s$ must be a solution to both DLP, and the only such one (formally, we do not even need to check that $0<s<\min(q_1, q_2)$ and ${g_2}^s\equiv y_2\pmod{p_2}$, even though in practice we would).

Since we need to solve only one DLP, and anyone of the two possibly according to which we find easier, that's "better" than "solv(ing) the two discrete logarithms independently"; and that improvement is directly enabled by $0<x<\min(q_1, q_2)$. This answers in the affirmative a possible reading of the question.

But we are told that the question really asks: assuming $0<x<\min(q_1, q_2)$, is there an approach which solves the two DLPs simultaneously that is faster than solving either DLP? That's a much harder question, and right now I have no clue.

Note: even the weaker additional information $0<x<\max(q_1,q_2)$ and solving one of the two DLPs in isolation would greatly help towards solving both. When $p_1\ge p_2$, the $s$ computed as above would be the only possible $x$. And for $p_1<p_2$ we could reduce the search of $x$ to the search of $k$ in a DLP of the form $g^k\equiv y\pmod{p_2}$ with $0\le k<\lceil q_2/q_1\rceil$, making the search easier (by enumerating $k$ when $p_1$ and $p_2$ have about the same size, or Baby-Step/Giant-Step if they differ by a few dozen bits). $g$ and $y$ are easily computed as $g={g_2}^{q_1}\bmod p_2$ and $y={g_2}^{-s}\,y_2\bmod p_2$.


Question about modular arithmetic (division) I have a question about division operation.

There are two entities, Alice and Bob.

Bob randomly selects a finite set of numbers (set K). (about 10K or 100K)

Alice randomly generates one big number $x_1$ and chooses one element $y_1$ (from Bob's set K).

Alice makes $X$ ($X=x_1*y_1 \bmod n$) and sends $X$ to Bob.

In this case, can Bob figure out what Alice chooses from the set K?

Small number example: 3 ($x_1$) * 5 ($y_1$) mod 7 = 1 ($X$).

Bob knows that there is '5' in the set K, but I think that 1 divided by 5 (mod 7) equals 1.

So I don't think that Bob can figure out what Alice chooses from the set K.

Am I right?

Sorry for my bad English.

Thanks.

The answer depends on how $n$ is chosen.

If $n$ is coprime with each of the $y_j$ (including if $n$ is prime and all the $y_j$ are in range $[1..n[$), and $x_1\bmod n$ is uniformly random on $[0..n[$ (including if $x_1$ is uniformly random on that interval, or on a much larger interval), then demonstrably, Bob can not determine what $y_i$ Alice has picked by examination of $X\;=\;x_1*y_i\bmod n$. Proof sketch: the application $F_i:x_1\to X$ is a permutation of $[0..n[$; therefore $X$ is uniformly random on $[0..n[$, regardless of $y_i$; thus $X$ can't leak information about $y_i$.

However, if $n$ is the product of all the $y_i$ and these are distinct moderate primes, then Bob can find with fair odds which $y_i$ was chosen: $X$ is divisible by that $y_i$, and only those few (perhaps no) other $y_j$ that divide $X$.

There are gradations between theses two extremes.


What are the differences between proofs based on simulation and proofs based on games? what are the main pros and cons of proving the "security" of a crypto scheme under simulation proofs instead of game based proofs?

As the other answers already state here, game-based definitions are easier to write proofs for, but simulation-based definitions are often clearer in terms of the security guarantee that you get. The best example of this is IND-CPA (game-based definition) versus semantic security (simulation-based definition). Note that IND-CPA is really not a convincing definition: why does not being able to distinguish between an encryption of 2 ciphertexts guarantee that you can't learn any partial information? It is only once you prove equivalence to semantic security that it becomes clear (both because semantic security is clear, and because the proof of equivalence is very illuminating).

Unfortunately, in most cases, the game-based and simulation-based definitions are not equivalent. So, which is better? It depends on the situation. However, there is one very important thing that simulation gives you that game-based definitions do not, and that is security under composition. The stand-alone simulation-based definitions give you security under sequential composition, and universal composability and its variants give you security under concurrent composition. Note, that this security is not only concurrent executions of the same protocol (since this is also often guaranteed in a game-based definition), but concurrent executions with arbitrary other protocols. This is not guaranteed by any game-based definition (to the best of my knowledge). Even when considering the stand-alone definition, it is much easier to plug your protocol into something larger and prove its security, using the modular sequential composition theorem. In short, these composition theorems let you analyze a larger protocol while relating to the subprotocol as an ideal functionality call. This greatly simplifies things.

I believe that simulation-based definitions are qualitatively better, in most cases. The guarantees are clear and composition is guaranteed. This does not mean that game-based definitions are not good, and in fact, they are often the way to go (especially for lower-level primitives). But, it really depends on the case.

I have written a tutorial on how to write simulation proofs. This should help.


Attack of the Middle Square Weyl Sequence PRNG The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer (now deleted). This PRNG was introduced by Bernard Widynski in Middle Square Weyl Sequence RNG (arXiv, 2017). That was without claim of cryptographic security, but v5 of the paper conjectures that it would "be difficult to determine the internal state by examining the outputs".

The PRNG has a 128-bit state consisting of two 64-bit variables $x$ and $w$. The PRNG input consists of the initial $x_0$ and $w_0$, and an odd value $s$. The state's evolution and 32-bit pseudorandom outputs $r_i$ are defined (for $i\ge0$) by
$$\begin{align}
r_i&\gets x_i\bmod2^{32}\\
w_{i+1}&\gets(w_i+s)\bmod 2^{64}\\
x_{i+1}&\gets((x_i^2+w_{i+1})\bmod 2^{64})\ggg32
\end{align}$$
where $\ggg32$ swaps the halves of its 64-bit left argument.

[The notation was modified so that $r_0$ is output, for consistency with an answer]

The paper gives a reference C99 implementation (with input $x_0=w_0=0$ and a certain $s$; the output starts at $r_1$)

uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
inline static uint32_t msws() {
   x *= x; x += (w += s); return x = (x>>32) | (x<<32);
}

Assume we have a $r_i$ for $0\le i\le9$. How can the rest of the sequence be predicted efficiently? That would be a total break.

If not feasible, lesser breaks (only distinguishing the output from random, or requiring more plaintext, or working only for a fraction of the inputs) are also welcome.

Lets look at the computations that the function does to the internal state.
We'll denote the state of the variables when we start the attack as $x_0 = (a, b)$ and $w_0 = (c, d)$, where I will use the notation $(i, j)$ to mean the 64 bit number which has $i$ as the upper 32 bits, and $j$ as the lower 32 bits (and so $a, b, c, d$ are 32 bits each).  Note that $x_0, w_0$ need not be the initial state of the PRNG, instead it's the state when the initial output was generated.
Then, the previous step exposes $b$ (and so that is known to the attacker).
Then, it squares $x_0$ modulo $2^{64}$, replacing $x_0 = (a, b)$ with $x_0^2 = (2 a b + (b^2 >> 32), b^2\  \bmod 2^{32})$.  As the attacker knows $b$, the attacker can replace this with the linear operation $x_0^2 = (h_0 a + h_2, h_1)$, where $h_0, h_1, h_2$ are known (to the attacker) constants (as it gives the same mapping from previous state to new state).
Then, the algorithm adds $w$ to $x$, that can be modeled as:
$x_0^2 + w_0 = (h_0 a + h_2 + c + \epsilon_0, h_1 + d)$, where $\epsilon_0$ is either 0 or 1, depending on whether a carry from the lower 32 bits happened.
Then, it adds the constant $s$ to $w$, this can be modeled as $w + s = (c + s_{hi} + \epsilon_1, d + s_{lo})$, where $\epsilon_1$ is either 0 or 1, depending on whether a carry from the lower 32 bits happened (and $s = (s_{hi}, s_{lo})$
Then, it rotates $x$, giving $x_1 = (h_1 + d, h_0a + h_2 + c + \epsilon_0)$, and outputs the lower 32 bits $h_0a + h_2 + c + \epsilon_0$.
The new state is $x_1 = (h_1 + d, h_0a + h_2 + c + \epsilon_0)$ and $w_1 = (c + s_{hi} + \epsilon_1, d + s_{lo})$; that is, it is one of 4 linear functions of the previous state (depending on the values of $\epsilon_0, \epsilon_1$)
Continuing on for three more iterations, the resulting states will remain one of a small number of known linear functions of the initial state; the output will also be a linear function of the state.  With four outputs, the attacker can iterate through the possible $\epsilon$ values, and solve for the initial states.  If you go through the equations, you'll find that you can recover $c, d$ from the third and fourth outputs; using the value $c$ gives you the value of $a$ from the second output (and you're given $b$ as the first output).


Finding the private key for this signature scheme Assume the signature scheme where $x$ is the private key and the public key $y = g^x \pmod{p}$. The signature works as:

Choose $h \in \{0, \dots, p-2 \}$ s.t.: $\mathcal{H}(m) + x + h \equiv 0 \pmod{p-1}$, $\mathcal{H}(m)$ collision-resistant hash function.

The signature is the triple $(m, (x+h) \pmod{p-1},g^h \pmod{p}) = (m,a,b)$

Verification checks if:
\begin{align}
yb &\equiv g^a \pmod{p} \tag{1} \\
g^{\mathcal{H}(m)}yb &\equiv 1 \pmod{p} \tag{2}
\end{align}

The objective is to achieve and forge signatures for arbitrary messages of our choice.

Let $m'$ be an arbitrary message. Then, the triple $(m', a', b')$ with:
\begin{align}
a' &= -\mathcal{H}(m') \pmod{p-1} \\
b' &= g^{-\mathcal{H}(m')} \cdot y^{-1} \pmod{p}
\end{align}
is a valid signature on $m'$. Since we forged a signature on an arbitrary message, we've achieved total break for this scheme.


Is it safe to store both the AES-related data and the PBKDF2-related data (except passwords) in one file? Assume an "encrypted data package" file format which includes the following data

PBKDF2

algorithm
salt
rounds
keylen

AES

algorithm & mode
IV
ciphertext

where the PBKDF2 salt and AES IV are generated using a CSPRNG upon individual encryption.

This would make the individual password (used as PBKDF2 input parameter) the only seperately stored data (secret to the "encrypted data package" file) which is stored in a secure place.

Is it safe to store both the AES-related data and the PBKDF2-related data (except passwords) in one file, or are there any cryptographic implications when doing so? If there are implications, what would be the advantages (from a security point of view) of storing the PBKDF2 data separately from the AES data?

When describing potential pitfalls, it would be nice when answers would assume and expand on the following two scenarios:

AES-256-CTR, with the PBKDF2 parameters simply prepended to the ciphertext, and
AES-256-GCM, with the PBKDF2 parameters fed into the AES mode as associated data.

Think of this more as a canonical question, hinting at

*“Do seperate storages resemble security by obfuscation?” and
”What's the minimum data we would need to store in a secure location, and what other data can we safely store next to the ciphertext 'out in the open' so that we don’t introduce cryptographical problems?”

All the parameters you've mentioned can be public. Furthermore, only the salt, IV and ciphertext cannot simply be guessed.

The IV is generally easy to retrieve once the key is known, so the making the IV secret doesn't make sense. In CBC mode and many other modes you may just not get the first plaintext block if the IV is completely absent, but the rest of the ciphertext will be available. In CTR mode you would get the IV directly once the key is known and if part of the first plaintext block is known.

So that basically leaves the salt. Now the salt is sometimes kept partially secret. This static, secret part is called a pepper. If you keep this secure then it can be seen as an additional input key that is required to generate the resulting output key. There still should be a random or at least unique salt otherwise identical passwords will result in the same key, which is definitely something you would want to avoid.

TL;DR you could use a pepper which sometimes makes sense if the pepper has different access requirements. All the other information can simply be stored with the ciphertext (but read on).

Note that there certainly is a danger when storing the algorithm with the ciphertext. The problem is that if an attacker can switch the algorithm from GCM to CTR that you suddenly get unauthenticated plaintext. You'd better make sure that an attacker cannot simply change a few parameters to make your protocol less secure.

That would be a lot more dangerous than storing any of these public parameters together with the ciphertext.

If you decide to use authenticated ciphertext then yes, please make all the parameters part of the Additional Authenticated Data (AAD). Note that all AEAD modes already include the IV in the verification, so there is absolutely no reason to include it in the AAD.


How to hide multiple types of information in the same file? I have a vague memory of watching a video of a guy "unraveling the secret story / lore" from the game Doki Doki Literature Club.
And I remember that he took a file, converted it to .txt and had certain information, converted the same file to .jpg and had other totally different information. Information that can only be seen if you convert the file to .txt and other information that can only be seen if you convert the file to .jpg.
How do I hide different messages in the same file that can only be deciphered by converting it to other file extensions?
If that is not possible then it must be something that my brain messed up in my memories, but I am pretty sure it was like that.
And I don’t have any more details, so I can’t research it properly. This would open up new possibilities for more immersive mystery or horror games.
By the way, I know the basics of steganography but I have never seen anything like it, hiding multiple types of information in the same file.

One simple steganographic technique is to just use the comment structure of a mark-up language to embed plaintext messages. For example, the html code
<!-- ATTACK AT DAWN -->
<img src="lolcat.jpg">

inserted in a web page and opened in a browser will render as an image (presumably of an amusing cat), but if opened in a text editor the comment line can be read (and the cat picture can not be examined).
In particular the jpg format allows COM segments which are preceded by the bytes 0xFF 0xFE and a length field which then allow insertion of ASCII text.
Note that this is pretty trivial to detect and provides only steganographic protection (vice cryptographic).


Schnorr protocol is witness-hiding? Regular 3-steps Schnorr protocol is a proof of knowledge system for discrete logarithm.
It's honest-verifier zero-knowledge,
but not full zero-knowledge.
My question is, is it witness-hiding?
(I guess it should be the most important property in many cases,
rather than too strong and not required ZK, and too weak HVZK).

I found the answer:
Schnorr protocol is witness-hiding - proved in GGM model in https://www.shoup.net/papers/dlbounds1.pdf (as part of proof that Schnorr identification protocol is secure).

At the same time, it's not possible to prove it in standard model based on discrete-log problem: http://www.cs.cornell.edu/~rafael/papers/schnorr.pdf


Commuting hash and encryption function? I wonder if there are secure cryptographic hash function $H$ and encryption function $E$ such that: $H(E(m)) = E(H(m))$ for all $m$.

Do such functions exist?

Short answer: NO

especially for all $m$

as a secure hash function generate significant different output for even a small change in $m$. (see Random Oracle Model for further references).

therefore
\begin{equation}
m \neq E(m)
\end{equation}
\begin{equation}
H(m) \neq H(E(m))
\end{equation}

now a hash function is not same as encryption function.

therefore

\begin{equation}
m \neq H(m)
\end{equation}
\begin{equation}
E(m) \neq E(H(m))
\end{equation}

now from above equations, you can see it is only possible if $H() = E()$ but it is not plausible as

Hash function must be irreversible and producing a fixed length output where

Encryption function must be reversible and variable length output.

so it is not possible to exist even a single function obeying such criteria.


Constraint about encrypted values Let V = $[x_1,\ldots ,x_n]$  be a binary vector of length $n$, and let $E(V)$ be the entrywise encryption of this vector.

Suppose I want to give to another player, $E(V)$, but also let him have the ability to verify that the plain vector contains  m values that are equal to 1, and they are  consecutive.

For example, n=5,m=2:

Valid V = 0,1,1,0,0;
Not valid V = 0,1,0,1,0.

Note that: If the requirement was without the consecutive property, I've just used an homomorphic encryption. (to see if the multiplication of the values are equal to the encryption of $m$).

To capture value/position relations, a "sequence polynomial representation" was suggested, in the context of proving properties of DNA. Self-citing: IACR preprint 2008/357. This technique could apply here in case of ElGamal ciphertext, that could be proven with Schnorr-like responses. The major idea remains to re-state "consecutive" as a property of "characteristic polynomial", that (I believe) is doable. Hamiltonicity test (2008/363) could be another example.


How were the AES key and block length subsets of Rijndael selected? My intuition tells me it's a trade off between speed and security, but how did the standardisation process select these three seemingly arbitrary key lengths (namely, AES-128, AES-192, AES-256).

Prompted by Paŭlo's comment, I took a look at the original requirements set out for the AES candidates.  A useful page for that turns out to be AES - The Early Years (1997-98) on the NIST web site (and surprisingly hard to find there; the internal links are broken and Google doesn't find it either).

The AES key lengths were specified in the original Request for Candidate Algorithm Nominations for the AES published in the Federal Register on September 12, 1997, in section 3, Minimum Acceptability Requirements (emphasis original):

  "The candidate algorithm shall be capable of supporting key-block combinations with sizes of 128-128, 192-128, and 256-128 bits.  A submitted algorithm may support other key-block sizes and combinations, and such features will be taken into consideration during analysis and evaluation."

So where did those key/block size combinations come from?  In the earlier notice Announcing Development of a Federal Information Processing Standard For Advanced Encryption Standard, posted in the Federal Register on January 2, 1997, the "proposed draft minimum acceptability requirements and evaluation criteria" include:

  "A.3  AES shall be designed so that the key length may be increased as needed."

This proposed requirement received many comments, and was discussed in the AES workshop on April 15, 1997.  Bruce Schneier, in his notes on the workshop, writes:

  "Discussion followed. All the pre-lunch arguments were about block and key size. Block sizes of 64 bits and 80 bits were quickly eliminated, as was a 64-bit keysize. People wanted variable keysizes of some subset of 128, 192, 256, or even 512 bits, and block sizes of either 128 bits or 128 and 256 bits. There was no discussion of stream ciphers, or using block ciphers as hash functions."

Apparently, the three key sizes and one block size specified in the NIST minimum requirements, and later in the AES standard, were selected at least in part based on those discussions.

Ps. I've seen it claimed, e.g. by Thomas Pornin in this answer, that the three key lengths "exist mostly to satisfy some US military regulations which call for the existence of several distinct 'security levels'".  The notes and comments cited above strongly suggest to me that this probably wasn't the only reason for the decision to require multiple key lengths, although it could certainly have been one reason.  In any case, if anyone can actually point to the specific regulations that require these distinct security levels (assuming they're publicly available), I'd be interested in seeing them.


Has anyone implemented the BB84 protocol? Has anyone implemented the BB84 protocol and put it in production?
The BB84 is a quantum key distribution scheme developed by Charles Bennett and Gilles Brassard in 1984. It is the first quantum cryptography protocol.
I am thinking of incorporating the BB84 protocol into the network list of protocols at the IETF.
Nathan Aw

Has anyone implemented the BB84 protocol and put it in production?

There are a number of commercial QKD devices on the market, including ones by IDQuantique, QuintessenceLabs, MagicQ and SeQureNet.  In addition, there are a number of other companies that are working on it (and may be actively marketing them as well).
Some of these companies use an internal protocol similar to the original BB84 protocol; others use other versions of quantum key exchange.

I am thinking of incorporating the BB84 protocol into the network list of protocols at the IETF

Now, the IETF (actually, the IRTF) has a research group, the Quantum Internet Research Group, that is already chartered to cover QKD (although that is not their main focus).  I'm not sure what your master list of network protocols is, but it should already be there.


Did NIST verify “post-quantum” claims in the SHA3 proposal papers? I have been reading Bernstein’s “Quantum attacks against Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein” paper from 2010…

  This document disproves the claims of preimage resistance for Blue Midnight Wish,
  ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein. Specifically, this document presents attacks finding preimages in each of these hash functions using time much, much, much smaller than $2^{224}$: specifically, using only about $2^{112}$ simple operations. The exponent gap is so large that it cannot be explained by the difference between “224 bits” and “approximately 224 bits.”

(emphasis mine)

The most interesting points are …

  This is, in particular, a claim of $2^{224}$ preimage resistance for 224-bit Keccak. There is no warning regarding the impact of quantum computers: Keccak claims “preimage resistance,” not merely pre-quantum preimage resistance.

and

  Each attack uses approximately $2^{112}$ iterations, disproving the $2^{224}$ preimage-resistance claims for each of these functions. The exact complexity of each iteration, and the required number of qubits, varies somewhat from function to function, but is on a far smaller scale than the $2^{112}$ complexity gap.

This contradicts some of the expectations I had after NIST validated and chose Keccak as the winning SHA3 proposal. Also, it somewhat underlines the correctness of my suspicions related the incorrect “post-quantum sufficient” claims in the Keccak papers. (You might remember my older question where I already suspected another post-quantum claim of Keccak to be incorrect: What exactly is the base for the KECCAK (SHA3) claim that a security strength of 256 bits is “post-quantum sufficient”?)

As a result, I've got two related, yet somewhat different questions:

As it stands, Bernstein showed Grover’s algorithm could successfully enable pre-image attacks on SHA3 candidates (including Keccak, the SHA3 finalist) and as far as I learned from the different replies here at Crypto.SE: if it's broken, it's broken… no matter how theoretical or far-fetched the break is, a break is a clear warning sign. Even when I would ignore that, the question remains if the claims of those SHA3 papers can be trusted at all. I mean, I did quite some research but I frequently noticed that claims can not be verified; especially in relation to Keccak. (See my question and answer: Is it possible to actually verify a “sponge function” security claim?)

Are there any papers that I should know about which contradict the findings of Bernstein’s paper?
For the benefit of the doubt, I won't start contemplating if NIST might have been influenced during their SHA3 quest or not, because similar crypto-news has been raving the press too much already. Yet, I wonder why Bernstein’s findings seem to have been ignored and I would like to understand why NIST chose to ignore the fact that most SHA3 proposals might suffer from quantum-attacks.

Did NIST actually validate any of the proposals for post-quantum security (and related claims in papers) at all, or was quantum computing simply ignored during their SHA3 security assessments? And if quantum was ignored, what was the motivation to do so?

(Maybe you can point me to references confirming NIST did or did not validate post-quantum aspects… I couldn't find any.)

With any $n$ bit hash it is possible to:

Find preimages with work $2^n$ on classical computers and $2^{n/2}$ using quantum computers
Find collisions with work $2^{n/2}$ on classical computers and $2^{n/3}$ using quantum computers

I want to emphasize that these are generic attacks that always work, no matter which concrete hashfunction is used. Grover's algorithm is the quantum mechanical equivalent of classical brute-force.

For sponges (including keccak and cubehash) if $c$ is smaller than $2n$ there are other generic attacks:

Find preimages with work $2^{c/2}$ on classical computers and $2^{c/3}$ using quantum computers
Find collisions with work $2^{c/2}$ on classical computers and $2^{c/3}$ using quantum computers

Now several authors of SHA-3 candidates simply wrote "preimages with work $2^n$" and "collisions with work $2^{n/2}$" without explicitly stating that these claims only apply to classical computers. The intention of these claims was clearly "no faster than brute-force attacks", but they only spelled it out explicitly for classical computers.

Some authors (like DJB himself) carefully specified the above limits separately for classical computers and quantum computers, and some simply wrote that the "usual security levels apply".

Now DJB argues that since the security level against quantum computers violate the security claims, they're an attack against those hashes. The same attacks apply to cubehash as well, except that they don't violate its security claims.

The paper is the simple observation that some papers didn't mention the generic quantum computer attacks and didn't clearly restrict their claims to classical computers. It's about a really minor sloppiness in those papers, I'd expect every cryptographer to know that these claims don't apply to quantum computers.

The paper does not contain any new attacks or findings, only nitpicks.


Where does the $\varphi(n)$ part of RSA come from? $e d \equiv 1 \pmod{\varphi(n)}$

Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?

$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element.

So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say that $ed-1\equiv\phi(n)$ or $ed\equiv\phi(n)+1$.

So if we look at $m^{ed}\bmod{n}$ well that is just the same as $m^{\phi(n)+1}\bmod{n}$ which is the same as $m^{\phi(n)}m^1\bmod{n}$. But since $\phi(n)$ is the order of the group, we know that $m^{\phi(n)}\equiv 1$ so we have $m^{\phi(n)}m^1\equiv 1m^1\equiv m\bmod{n}$. This proves that decryption works and we were only able to prove it since we chose $d$ accordingly.

If we didn't use $\phi(n)$ the mathematics wouldn't necessarily* work out and decryption would not be guaranteed to work. So, the designers of RSA used $\phi(n)$ out of necessity.

*See the comment by fgrieu. Any multiple of $LCM(p-1,q-1)$ would work.


Decryption formula of Plaintext Block Chaining (PBC) mode of a block cipher Considering that $C_n = E_k(M_n) \oplus M_{n-1}$ formula is used in encryption side of this mode of block cipher, and knowing that instead of M0 a randomly chosen initialization vector (IV) is used in Plaintext Block Chaining mode.
What would be the formula on the decryption side?

$M_n = D_k(C_n) \oplus M_{n-1}$

$M_n = D_k(C_n \oplus M_{n-1})$

Actually, I think as the algorithm has no access to $M$ bits on the decryption side, although I accept that by following $M$ bits, I will get to $M_0$ at the end which is IV and can solve the equations inversely from that point, it would be better to write the above equations as :

$M_n = D_k(C_n) \oplus D_k(C_{n-1})$

$M_n = D_k(C_n \oplus D_k(C_{n-1}))$

But my main question is which of the equation is correct if we want to represent the decryption side's formula?

let $$C_n = E_k(M_n) \oplus M_{n-1}$$ be the encrytion of the PBC mode with $M_0 = IV$
Then use the property of $\oplus$ and the correctness requirement of the encryption; for any key $k$ and every message $m$ in the message space it mus hold;
$$m = D_k(E_k(m))$$
\begin{align}
C_n &= E_k(M_n) \oplus M_{n-1}\\
C_n \oplus M_{n-1} &= E_k(M_n) \oplus M_{n-1} \oplus M_{n-1} & &;\text {x-or both sides with } M_{n-1} \\
C_n \oplus M_{n-1} &= E_k(M_n) & &;\text{cancel}\\
D_k(C_n \oplus M_{n-1}) &= D_k(E_k(M_n)) & &;\text{decrypt both sides} \\
D_k(C_n \oplus M_{n-1}) &= M_n\\
\end{align}
Therefor to decrypt you need $M_n = D_k(C_n \oplus M_{n-1})$


Reusing message in One Time Pad One of the main rules of the OTP is, that a key should never ever be reused.

But if we use some commutative operation (XOR for example) for generating the cipher text, then I don't see any difference between the message and the key, so can we also say that a message should never be reused?
With other words - even if we use different key for every message, could the system be weakened if we sometimes use the same message as before?

No, you can reuse a message as often as you want with the OTP. (But never reuse the key!)

What happens if you reuse a key? The attacker can xor the two encrypted messages (ciphertexts) and gets the xor of the two plaintexts. The xor of two messages is highly insecure and can be easily turned into two plaintexts with some know patterns.

What happens if you reuse a message? The attacker can xor the two encrypted messages and gets the xor of the two keys. What happens if you xor two fully random keys? The resulting string is also fully random, and it's not possible to get any information out of it. You see, there's no problem with reusing the message.


Is there an encryption scheme that provides $Pr\{M_1 = m_1\wedge M_2 = m_2 | C_1 = c_1 \wedge C_2 = c_2\} = Pr\{M_1 = m_1 \wedge M_2 = m_2\}$ Question:

Consider the following definition of perfect secrecy for the encryption of two messages.An encryption scheme (Gen, Enc, Dec) over a message space M is perfectly-secret fortwo messages if for all distributions over M, and for all $m_1,m_2 \in M$ an d $c_1, c_2 \in C$ with $Pr\{C_1 =~c_1 \wedge C_2 =~c_2\} > 0$:

$^{(*)}$$Pr\{M_1 = m_1\wedge M_2 = m_2 | C_1 = c_1 \wedge C_2 = c_2\} = Pr\{M_1 = m_1 \wedge M_2 = m_2\}$,
where $m_1$ and $m_2$ are sampled independently from the same distribution over M. Prove that no encryption scheme satisfies this definition.

My induction:

So I think if an encryption scheme provides $^{(*)}$ then it can't provide the corectness condition.

($Pr\{k\longleftarrow Gen();c=Enc_k(m);\hat{m}=Dec_k(c):m=\hat{m}\}=1$)

because let $m_1,m_2=m$ and $c_1,c_2=Dec_k(m)$ in $^{(*)}$.
it's seems that we can't determine if $c$ is the cipher of $m$ or not but I can't also prove that

$Pr\{k\longleftarrow Gen();c=Enc_k(m);\hat{m}=Dec_k(c):m=\hat{m}\}<1$

let $M_1,M_2$ be a distribution where $\exists m_1,m_2$ that $ Pr\{M_1=~m_1 \wedge~M_2=~m_2\} \neq 0$ and $m_1 \neq m_2$ it is clear that such distribution exist.

suppose $\Pi$(Gen,Enc,Dec) satisfy the question's statement and $|M|\neq 1$

Let $m_1\neq m_2$ but $c_1=c_2=c$

$^{(*)}$ $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}=Pr\{M_1=~m_1 \wedge~M_2=~m_2\} $

if $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}\neq 0$
then $m_1,m_2$ are encrypted with the same key the above probability is not equal to 0 so

$Pr\{k\leftarrow Gen();c=Enc_k(m);\hat{m}=Dec_k(c):m=\hat{m}\} \neq 1$ but this is in paradox with $\Pi$ being a encryption scheme.

so $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}= 0$ and according to $^{(*)}$ $ Pr\{M_1=~m_1 \wedge~M_2=~m_2\} $ is also equal to zero $\forall m_1 \neq m_2$ which is also in paradox with the way we chose our distributions.

So no encryption scheme could satisfy $^{(*)}$


Real life systems that use concepts of crypto computing Are there any working cloud/internet solutions/products that operates on encrypted data such as systems using homomorphic encryption, secure multiparty computation, electronic voting, private information retrieval?

IACR uses electronic, encrypted voting for their elections every year. They use Helios
Sharemind has been used in a few applications (financial data analysis, social study)
CipherCloud claims to do a number of things on encrypted data. There was some discussion of their work on here that was partially removed due to a DMCA request.
Skyhigh Networks does functionality-preserving encryption of cloud apps
CryptDB aims to build encrypted databases.
Dyadic uses multiparty computation to protect cryptographic keys that would otherwise be compromised by a break of a single server.
ShareMonad has been used to prototype MPC voice accumulation, regular expressions, SHA, AES, and SAT.


Proof possession of private key in libsodium I would like to proof that I am in possession of private key sk for public key pk using libsodium.

Therefore I am signing a constant message m using libsodium's crypto_sign function. The signed message (signature + m) is then published.

libsodium crypto_sign uses Ed25519 as digital signature scheme.

Questions:

Does the reuse of a constant message might introduce any attack vectors?
The libsodium documentation on crypto_sing states:

  Verifiers need to already know and ultimately trust a public key before messages signed using it can be verified.

https://libsodium.gitbook.io/doc/public-key_cryptography/public-key_signatures#purpose

Is that information relevant for my case as I actually do not want to verify the message, but want to proof the possession of sk?

If you are going to public the same message with a signature multiple times, it is vulnerable to a replay attack. This is where another party basically copies your message and signature and can re-publish it at any time, implying that they own the key. To counter this, add a small piece of information to the message before signing, say a counter or random number that is unique per signature published.

As for trusting signing keys, a trusted party ie a Certificate Authority or a PKI must be used so that any data received from them is trusted. So when Alice publishes a message and a signature, the CA tells people Alice's static public key, this is trusted, and then everyone can safely verify the fact that Alice does indeed own the private key she claims to own.


ESP header and trailer I investigated the IPsec Protocol.
I am wondering if I can remove/reduce any field to save space,
is there a way to save overhead in ESP packages?

I am wondering if I can remove/reduce any field to save space, is there a way to save overhead in ESP packages?

Well, there was an old IETF draft here to address this very problem; however it didn't get enough traction in the IPsecME working group (for the complexity it has, it doesn't save that much space) and thus was abandoned.
Sticking to standard IPsec, well, you could remove the space used by the nonce by using RFC8750; that saves 8-16 bytes (depending on what transform you were previously considering)
And, you could decide not to use an authentication transform (thus eliminating that overhead).  On the other hand, that could bring up the possibility of active attacks; I can't recommend it.
And, as you are probably aware (but I'll mention it anyways) if you're protecting traffic between two endpoint devices, transport mode will allow you to not include an IP header in the payload data (thus saving you another 20-40 bytes).


Challenge to prove possession of file Suppose Bob wants to give Alice a large file, in such a way that:

Bob cannot keep the file, but is able to use it to precompute anything he needs before he gives it to Alice
Bob must be able to challenge Alice periodically, and Alice can only successfully answer the challenge if and only if she is in possession of the file at the time the challenge is made (no shortcuts are permitted)
The challenge cannot consist of Alice sending Bob the file for him to check (each challenge must consist of an exchange of small, constant-size messages)

The naive approach is for Bob to generate a bunch of random nonces $N_0, N_1, \cdots$ and precompute $S_i = HMAC(N_i, file)$ and for the challenge to consist of sending the next $N_i$ and expecting back the corresponding $S_i$, but this has the downside that you can only prepare finitely many challenges in advance (Bob needs to get to the file to make some more) and Bob's space usage is proportional to the number of prepared challenges.

Can we do better? Is there an on-line protocol for this that doesn't require precomputing challenges in advance?

Basically I'm looking for a way to challenge a device to prove that it has access to a specific, potentially unbounded in size, piece of information (which the challenger only knows by some unique identifier and some kind of fingerprint) at the exact time the challenge is made without having to send the entirety of it over.

Thanks

This is called a proof of retrievability or provable data possession (slightly different definitions for these two concepts). You will find many papers discussing constructions. Two of the most cited papers in this area are:

Shacham & Waters: Compact Proofs of Retrievability
Ateniese et al: Provable Data Possession at Untrusted Stores


What about using only XOR gates in homomorphic encryption? What if we were substitute the ANDs with XORs in some homomorphic encryption scheme like BGV(https://eprint.iacr.org/2011/277.pdf), LTV ( https://eprint.iacr.org/2013/094.pdf) ? It may be more efficient ?
For example if we can substitute an AND with 6 XORs, we would achieve a better efficiency for some choice of the parameters.

As poncho comments, a homomorphic encryption scheme that only supports the XOR operation would not be fully homomorphic, i.e., it would not allow evaluation of all functions. However, you can try to optimize the implementation of a function in order to minimize the number of AND's at the cost of extra XOR's. This is not only relevant for FHE but also in secure multi-party computation (MPC), where the XOR operation can also usually be computed much faster than AND.

Optimizing the circuit of a function to include less AND's, and possibly more XOR's, is a well known technique to make FHE and MPC applications run faster. In fact people have made special compilers to automate this process. An example of such a compiler in the MPC space can be found in this paper (although by now there are probably better ones around).


Feasibility of using a base 26 LFSR for cryptography by hand I have been playing with base 26 LFSRs (i.e. using the alphabet) and noticed that the XOR operation for base 26 is just the tabula recta and so can be done very quickly. This made me wonder whether a base 26 LFSR (combined with a technique such as self shrinking) could be used as a PRNG that could be performed by hand and then XORed with the plaintext.

A base 26 LFSR would have to be of length 27 to have $\approx2^{128}$ possible states (giving 128 bit encryption?) but depending on the number of taps this could still be performed relatively quickly on paper.

I am not sure about my understanding of non-binary LFSRs so some of my assumptions may be incorrect but any help would be appreciated.

LFSR theory, for an $n$-bit register uses an isomorphism between the shift operation, and the multiplication of a polynomial in $\mathbb{F}_2[X]$ by $X$; the multiplication is taken modulo a given polynomial $P$ of degree $n$; that modulus polynomial is the one defined by the position of the "feedback" bits and we usually want it to be primitive (i.e. irreducible, and such that $X$ generates, with the multiplication, all the non-zero polynomials modulo $P$). The XOR operation is, in fact, an addition of polynomials, i.e. a pairwise addition of monomials. In $\mathbb{F}_2$, values are bits and addition is XOR.

This extends to any finite field. But there is no finite field of size 26. What you can do is to map letters to integers modulo 26, and compute in the ring of such integers. By the Chinese Remainder Theorem, when you do arithmetic operations modulo 26, you are actually doing them in $\mathbb{F}_{13}$ and $\mathbb{F}_2$ simultaneously. So the theory can be applied through the CRT.

Namely, you could select a polynomial $P = X^n + \sum_{i=0}^{n-1} p_i X^i$ where each $p_i$ is equal to $0$ or $1$ (only), such that $P$ is primitive both in $\mathbb{F}_2$ and $\mathbb{F}_{13}$. The corresponding base-26 LFSR will then operate as the CRT mixture of a base-13 and a base-2 LFSR, of respective periods $13^n-1$ and $2^n-1$. Total period would be the least common multiple of these two values.

Notes :

Though LFSR have good statistical properties, for cryptography they tend not to be very good (e.g. you cannot keep the feedback polynomial $P$ secret, because of the Berlekemp-Massey algorithm). A secure LFSR-based stream cipher will need a trick, normally irregular clocking, as in A5/1. Resistance of A5/1 to cryptanalysis is roughly two thirds of its internal size (i.e. $2^{64·2/3}$) which is not high and allows for a lot of practical precomputations. For a "manual" LFSR, you may need to use a state size which will make it impractical. Also, the CRT duality can make analysis more complex. I suppose that a A5/1-like base-26 stream cipher can be designed and be secure, with a big enough internal state, but I don't have clear ideas on how big is "big enough".
You may have better luck using 32 signs (26 letters and some extra for spaces and punctuation). $\mathbb{F}_{32}$ is a field (not integers modulo 32, mind you; in $\mathbb{F}_{32}$, addition is indeed a XOR and each value, added to itself, yields a 0). However, you would also need a feedback polynomial where not all coefficients are $0$ or $1$ (otherwise you end up with running 5 binary LFSR in parallel). This can make the feedback rule application more complex.
A "manual" base-26 LFSR can be efficiently executed with a Scrabble game.


Exactly what part of SIDH is proven to be NP-hard? SIDH is quantum secure, why is it quantum secure? Exactly which part of the algorithm is proven to be NP-hard? Computing the isogeny function?

SIDH is believed to be quantum secure because the fastest known quantum attacks against it (which is based on claw finding algorithm) require exponential time with complexity $\mathcal{O}(p^{1/6})$.


How to calculate the key size of my cryptographic system I have a 'for fun' project, which is a pure software based redesign of the Enigma I.  I'd like to compute the key length of my design, but I need some help with that.

I have a write-up here (see section 1), but in summary:

Conceptually it's a rotor based system, that can take any number of rotors (i.e. as set by the operator).
Rotor components: stator (input/output), N number of rotors, stator (input/output). Unlike Enigma I, it has no reflector and data can be enciphered in either direction.
Rotor supports 94 unique characters (A-Z, a-z, 0-9 and some special characters).

I've attempted to map out all the variables that I think contribute to the key size:

In summary for those unable to see the image clearly:

Rotors of 94 characters
T - Total possible rotors (permutations of 94): 1.08736615665674E+146
A - rotors available for selection by the operator.  Theoretically T, but practically I have an initial implementation that uses 1147 unique rotors.
N - the number of rotors selected by the operator.  Unlike Enigma I there's no strict limit, and there's the further complication that you can use multiple instances of the same rotor (whether or not that enhances its cryptographic strength, I'm not sure).
O - the order in which the selected rotors can be arranged (including instances of repeated rotors).  I believe the calculation for Enigma I would be 26! × (26! - 1) × (26! - 2) - which takes into account the non-reuse of rotors, which doesn't apply in this case.
R - starting position for rotor Rotation.
D - direction of rotation (forwards or reverse).
F - flow direction through the rotors (left-to-right or right-to-left).

Do you agree those variables all contribute to the key size (they seem to me to all be variables the operator can set, and therefore part of the key)?

Can you give me a hand to compute the key size, or point me in the right direction? I'm afraid math isn't really a strong point of mine.

Update (Re comments to Huberts answer)

Enigma I has a specific number of rotors, which reflects translates both into the key size and the size of the cryptographic problem attackers face.  Calculus doesn't place a limit on the number of rotors used, which I think means that from an attacker's point of view you'd need to consider how many rotors might be being used (i.e.e a range).  Where as, key size is a specific measurement of how big a specific key is.

Update (April 2018)

Project complete.  Info available in the link below, including access to download (win10 only) and user guide.

https://morphological.wordpress.com/projects/enigma-x/

To compute bit length equivalent of your key, you need to compute $\log_2(\Omega)$ where $\Omega$ is the space of possible keys. Now, I have myself been computing the equivalent key sizes of many non-modern cryptosystems so it proved a really interesting exercise.

The formula I'm left with is

$$
\log_2(1147^N \cdot 94^N \cdot 2^N \cdot 2)
$$
where $N$ is the number of rotors.

First, we select the rotors. For $N$ rotors, there are $1147^N$ possible choices. Then, we select their initial state (which were historically distributed by a codebook, different for each day). For each rotor we have $94$ possibilities, therefore for the whole setup there are $94^N$ possibilities. Then, each rotor can have two directions, hence $2^N$. The flow direction, I assume, is global, therefore we finally multiply all of this by $2$.

So, for the calculation, we have

$$
\log_2(1147^N \cdot 94^N \cdot 2^N \cdot 2)\\
= \log_2(1147^N \cdot 94^N \cdot 2^N)  +  \log_2(2)\\
= N \cdot \log_2(1147 \cdot 94 \cdot 2) + \log_2(2)\\
\approx N \cdot 17.718 + 1
$$

You will therefore have over 128-bit keyspace with 8 rotors and you will need 15 of them for 256-bit keyspace.

As previously noted by Adrian K Luis Casillas [edit], it doesn't mean this cryptosystem has this much "bits of security". This notion is much less strict and takes cryptanalysis into account, e.g. a cryptanalyst can find the attack which, after collecting sufficient material, will reduce the effective key space by either a couple of bits or even a large factor, halving it or worse.

Note that if you have any objections for this analysis I will happily discuss this topic further. It has been fun.


Is it possible to construct a $3*3$ MDS matrix in $GF(2^4)$? I'm trying to construct a minimal MDS matrix for a toy cipher. I'm not entirely sure, how the various code parameters are tied to my block size, and how exactly is the binary matrix formed, when you have a generator polynomial.

I'm also having a hard time in understanding what's the smallest field and matrix size, where MDS makes sense.

A matrix $M$ of order $n$ is an MDS (Maximum Distance Separable) matrix if and only if every sub-matrix of $M$ is non-singular. Therefore, if you have an $n\times n$ MDS matrix $M$, constructing the $(n-1)\times (n-1)$ MDS matrix $M'$ is so easy. $M'$ can be constructed by choosing an arbitrary $(n-1)\times (n-1)$ sub-matrix of $M$. Here you can find some information about constructing the MDS matrices over $GF(2^q)$.


Assure Integrity and authenticity I want to assure integrity and authenticity in data sent trough a TLS channel.
What are the best techniques? For integrity a hash (sha, bcrypt,...) should do the job right?
And for authenticity? Should i use MAC?
Or is it the best way to use HMAC and achieve both integrity and authenticity?
Thanks for your time!

There is no need to do that manually. A TLS tunnel is not only encrypting the data, it is also guaranteeing the authenticity (and thus integrity) of the data it transmits. This used to be done by a seperate MAC (HMAC, usually), but these days (TLS $\geq 1.2$ and with modern cipher suites) you rather use an AEAD mode for encryption like AES-GCM or ChaCha20-Poly1305.


Does a concatenation of hashes of differently prefixed variations of any chosen message contain all possible finite bitstrings? Let $A$ denote a sequence of bits.

Let $H$ denote a cryptographic hash function that has no limit on the length of its input (for example, SHA-3).

Consider the following infinite sequence of bits: $$B = H(A) \mathbin\Vert H(0 \mathbin\Vert A) \mathbin\Vert H(1 \mathbin\Vert A) \mathbin\Vert H(00 \mathbin\Vert A) \mathbin\Vert H(01 \mathbin\Vert A) \mathbin\Vert H(10 \mathbin\Vert A) \mathbin\Vert \ldots$$ (that is, the prefix goes through all possible bitstrings, sorted by their lengths).

Can we assume that for any chosen $A$, its corresponding $B$ is unique and contains all possible finite bitstrings (similarly to a binary representation of a fractional part of Pi)? If yes, can we use such technique as a cryptographically secure pseudo-random number generator that has no theoretical period?

Can we assume that for any chosen A, its corresponding B is unique and contains all possible finite bitstrings

No. Due to your requirement $H$ is compressing. This means that collisions must exist. Depending on your hash function construction, a collision might lead exactly the same output sequence. As a constructed example assume a hash function that processes input blocks from right to left and feeds them to SHA3. Any SHA3 collision would then work. Indeed, you cannot argue that your assumption above holds just with standard properties of a hash function.

However, finding such messages is extremely hard. Already finding two messages that lead one identical block of B is hard by the collision resistance of the hash function.

  can we use such technique as a cryptographically secure pseudo-random number generator that has no theoretical period?

No. There are also several arguments against building a PRG this way. For example with common hash functions like SHA3 this construction would be extremely expensive as you cannot reuse previous results in computing B.


How does using a really small block size reduce the key space? I read this online and was confused:

Modern block ciphers tend to have block sizes of 128 bits or larger, because if the block size is too small there is the same problem as a small key space as described previously—the adversary can enumerate all the possible options and thus undermine the algorithm.

How does a small block size reduce the key space?

How does a small block size reduce the key space?

Let $b$ be the block bit size of a block cipher. There are $2^b$ possible block values, for a plaintext, and for a ciphertext. For a fixed key, there is a single ciphertext corresponding to any given plaintext, and vice-versa. A key and the block cipher thus implement a bijection on the set of $n=2^b$ possible block values. Given a set of $n$ elements, there are $n!$ bijections on this set. Thus there are at most $(2^b)!$ possible plaintext-to-ciphertext correspondences/bijections for our block cipher.
No matter how large a key for our block cipher is, it is bound to generate one of these $(2^b)!$ correspondences/bijections. A $k$-bit key can take $v=2^k$ values, thus for $v$ values we need $k=\log_2(v)$ bits of key. Thus the effective key space is limited to $k=\log_2((2^b)!)$ bits.
$$\begin{array}{r|rr}
b&1&2&3&4&5&6&7&8&9&10\\
\hline
k&1&4.6&15.3&44.3&117.7&296.0&716.2&1684.0&3875.2&8769.0
\end{array}$$
For example, with $b=3$, there are $2^3=8$ possible block values, thus $8!=40320$ possible plaintext-to-ciphertext correspondences, corresponding to a key somewhere between $15$ and $16$ bits (giving $2^{15}=32768$ and $2^{16}=65536$ keys).
Thus for REALLY small block size (less than about 6 bits), the block size indeed limits the key space.

But the quote¹ in the question is about something else: the risk of reuse of a block value, without consideration about the keyspace. For a random distribution of block values, there's >39% chance that a value gets reused after $2^{b/2}$ blocks (see this). This is a concern for less small blocks.
For $b=64$ (as in TDES), $2^{b/2}$ blocks is a mere 32GiB of data. If we have two 32GiB files TDES-CBC-encrypted with the same key, and the first file is known, there is >63% chance we can decipher at least 8 bytes of the second file, because a block in the second file matches one in the first file.

¹ That quote does not say that we moved to larger blocks like 128-bit because smaller blocks dangerously reduce the key space, which would be wrong. It says small blocks harm security, much like small key space does, and that is correct (even if the justification given is rather vague).


Curves intended for both signing and key agreement I need some guidance on elliptic curves that support signing and key agreement.

I am trying to develop a protocol for sending encrypted, deniably authenticated messages. To do this I will sign the message with a 2-key ring signature using the sender's signing key and the recipient's encryption key.

Is there a sensible elliptic curve to use for this? Ideally it would meet the safe curves standards and provide the same level of security as Curve25519 (i.e. 256 bit length / 128 bit security).

Ed448-Goldilocks looks like it fits the bill as a curve intended to support both functions but is there anything more lightweight?

Technically, any elliptic curve can support both signing and key agreement. However, Curve25519 as described in the original paper is meant for $x$-only arithmetic. This means that one never computes the $y$-coordinate. The issue is that you need the $y$-coordinate for signature verification in the standard algorithms (ECDSA, EdDSA).

Therefore, if you want to do signatures with the Curve25519 curve, you need to compute the $y$-coordinate. There are different ways to do this, one is to simply leave the curve as is (in "Montgomery form") and compute its $y$-coordinate. A different way, is to transform the curve into a new shape (the "twisted Edwards form") and do arithmetic there. This new curve is called Ed25519, and it is "(birationally) equivalent" to the old curve. There are even more flavours.

Again, the choice you make will be for efficiency and security. Not because one curve can be used for signatures while the other can't. I suppose the $y$-coordinate computation on Curve25519 is slow enough for people to prefer using Ed25519 instead.


Can several run of a semi-honest protocol be used to infer malicious security? In the ideal world, $A$ sends several inputs $x_1,...,x_\lambda$ to the functionality and $B$ sends input $y$. Functionality sends $f(x_1,y),...,f(x_\lambda,y)$ to $A$ and nothing to $B$.

Suppose that we have a protocol which is secure against semi-honest adversaries to realize this functionality.

In this protocol, $A$ sends encrypted values of $x_i$s to $B$. $B$ computes the encrypted result of each $f(x_i,y)$ and sends them back to $A$. $A$ decrypts these values to know each $f(x_i,y)$.

Is it possible for $A$ to choose $x_i$s in a way that this protocol is also secure against malicious $B$? For example, $A$ can choose some $x_i$s equal or with some specific relation in such a way that any deviation from the protocol is detected?

What I am intended to say is something like cut-and-choose but for outputs instead of inputs.

More generally, is it necessary to force the malicious party to act honestly at each intermediate step or it is sufficient to force him to output correctly?

Detection of malicious behavior can happen anywhere. However, it is not true that you can run semi-honest protocols and then check later. This is because such protocols can reveal the honest party's input when interacting with a malicious adversary. In such as case, even if you detect the cheating, security is not achieved. Thus, you need to make sure that no cheating happens that can break privacy; for correctness, it suffices to detect at the end. (There is a model called covert for which privacy can be breached as long as detection happens with good probability.)