algorithmic scheme to compare these two number encrypted using paillier cryptosystem I have been going through https://eprint.iacr.org/2006/287.pdf (Conjunctive, Subset, and Range Queries on Encrypted Data by Dan boneh)

I am trying to implement the paillier system to create a secure tunnel for gps related data on cloud.

There is a simple implementation of the system in python @https://github.com/mikeivanov/paillier

I am currently stuck at understanding how to code a comparision scheme for any two encrypted values

I am currently stuck at understanding how to code a comparision scheme
  for any two encrypted values

This is to be expected as what you are trying to do is impossible with standard Paillier encryption. To see this, first note that Paillier encryption is IND-CPA. We are now going to construct an attacker that wins the IND-CPA game with probability $1$ assuming they can relieably check for equality of two encrypted messages and thus proves that a scheme supporting this cannot be IND-CPA and thus Paillier can't actually allow for this.

Let $=_p:\mathcal C\times \mathcal C\to\mathbb B$ be a predicate that returns true for a given pair $(c_1,c_2)$ iff $D(c_1)=D(c_2)$ that is if the decryptions of the given ciphertexts are equal. This predicate models the functionality you are trying to realize. Now let's start with the IND-CPA game:

We pick two arbitrary distinct messages $m_0,m_1$ of the same length (the exact values don't matter) and send them to the challenger.
We receive $c_b=E(m_b)$ with $b$ being randomly chosen by the challenger. We compute $c_0'=E(m_0)$ on our own using the public key.
If $c_b=_pc_0'$ we return $b=0$, else we return $b=1$.

As $c_b=_pc_0'$ if and only if $b=0$ due to the construction of $c_0'$ and the way $=_p$ works, we always win the game with probability $1$ which yields the "advantage" $0.5$ which is clearly non-negligble and thus breaks IND-CPA security.


Encrypting data at rest using AES-GCM, where should I store MAC (Message Authentication Code) I am trying to secure user's profile in database (data at rest). This user's profile is downloaded only after successful authentication at server (based on user's entered password and user name).

The user's profile is encrypted using AES-GCM

PBKDF2 derived symmetric key (derived from entered password)
A random salt
The nonce

The operation returns me the encrypted data and a MAC (Message authentication code)

I need to decrypt the data without authenticating from server using the same entered password

New PBKDF2 derived symmetric key
Same salt as used for encryption
Same nonce as used for encryption
Same MAC as generated from encryption

My question is where (along with encrypted data? somewhere else?) and how (encrypted? hashed?) should I store the MAC in database?

My question is where (along with encrypted data? somewhere else?) [...] should I store the MAC in database?

In theory you can store the MAC wherever you want, as long as you store it and get the association right between MAC and ciphertext.
Practically however it's smartest to append the tag to the cipher text. This minimizes the chances that you screw up the association somewhere and it will make your implementation compatible with most libraries, which more often than not just append the tag and don't provide you explicitely with it.

  [H]ow (encrypted? hashed?) should I store the MAC in database?

Usually the MAC is stored in plain and this is actually covered by the usual security games and reductions. So an attacker can't even break the security of the scheme (ie decrypt messages in any attack model or forge a message) if the MAC-tag is available in plain. Thus there's no need for further encryption or hashing.


How to prove NIZK proof of knowledge? Assuming we have an El-Gamal pk tuple $(G,q,g,g^s)$. Someone, knows only the first three parameters.

In round $i$, I send him $X_i=(g^s)^{t_i}$ (the $t_i$ values are chosen randomly for each round), and I want to prove to him that I know also $s$ or $st_i$, so I choose a random $\rho \in \{0,1,...,q-1\}$, and send him the proof $P$:

$$P = [p_1, p_2] = [g^\rho, hst_i+\rho]$$

$h$ is define as $H(i || X_i)$, such that $H$ is a secure cryptographic hash function.

Now, he can verify that I know $st$ by comparing ${X_i}^h \cdot p_1$ and $g^{p_2}$.

My questions are:

How can I prove that the procedure I described is a NIZK proof of knowledge?
Considering the fact that this procedure is repeated for several rounds. Is it possible to link between the proofs? Namely, can someone learn that in some two proofs there was the same $s$? Does the fact that someone can't learn anything about $s$ or $st_1$ (ZK) implies that he can't link the proof for $st_1$ to $st_2$ (and learn that they both use the same $s$)?
If the ZK property is not enough, how can I prove such a property (if possible)?

You said in the comments, that $H$ can be a random oracle, but in this case it needs to be a random oracle. Basically your protocol is a Schnorr protocol in disguise, and you throw in the Fiat Shamir heuristic to make it noninteractive.

But considering your questions:

Well, the basic Schnorr protocol is not zero-knowledge. There exists no simulator for this, because the simulator can't (more or less) reliably pick the correct commited value. If you choose $\rho$ as single bit, you might end up with a ZK protocol, which you then can turn into NIZK with the Fiat Shamir heuristic, like D.W. suggested in the comments.
Well, actually there is no $s$ in your protocol. You never use $s$ alone. You don't let anyone know $g^s$. All you use is the product "$st_i$", which is from the verifier's point of view a single value. And since it has the index $i$, it will change from round to round. And no, you can't prove that to get to that value you used some common $s$, if you don't give out any information about $s$ alone (e.g. $g^s$).


How do I communicate the value of the initialization vector to the end user? Should it be part of the encrypted message? I am taking a cryptography class and our first homework is to implement a 32-bit block cipher. I implemented a simple block-cipher that uses CBC. Currently, my implementation reads both the 32-bit IV and the 32-bit key from a key file.

However, I read that the initialization vector is generated randomly, and can be public as well. If I changed my algorithm to generate a random IV, where would I store this IV (or communicate it to the user)? Would I simply output the value of the IV to the user after I finish encrypting the message? Or could I store the initialization vector as part of the message itself (perhaps at the beginning).

Then my decryption algorithm can simply read the first 32-bits of the encrypted message, which will be the initialization vector. Is this the right way to do it?

For CBC encryption, you would store the initialization vector as the beginning of

the ciphertext, regardless of whether you read in an IV or generated it yourself.

The CBC decryption algorithm would do what you described at the end of your post.

Your implementation should also offer access to the block cipher itself, without any mode of operation.


Is it possible to use X.509 for a symmetric-key algorithm? I read on wikipedia what is X.509:

  In cryptography, X.509 is a standard defining the format of public key certificates. X.509 certificates are used in many Internet protocols, including TLS/SSL, which is the basis for HTTPS[1], the secure protocol for browsing the web. They are also used in offline applications, like electronic signatures.

but as a beginner it looks still unclear to me, do you please have any concretes examples of daily use cases concerning X.509 ?

As I assume it is a standard defining the format of public key certificates, could it still be used concerning Symmetric-key algorithm ?

No, X.509 cannot be used for symmetric cryptography directly. Inside the certificate is a public key of the subject of the certificate. The subject controls the private key.

The X.509 name is a reference to CCITT / ITU-T X.509; X.509 certificates are used as base of PKIX,  the Public Key Infrastructure. PKIX is a tree structure where a Certificate Authority can be used to give trust to end entity certificates by signing them using their own private key. That way a chain of trust is created from the root certificate to the leaf certificate. These certificate chains can be validated if the end user received the root certificate or any intermediate certificate in an initial trust store. The verifier receives a leaf certificate which contains an issuer, which can be used to create a chain to a initially trusted certificate. Of course the certificate should also be validated: the entity name (the server name for TLS), the validity period, certificate status (CRL / OCSP) need to be valid for the certificate and the public key inside it to be trusted.

This kind of trust cannot be build using symmetric cryptography. It is obviously impossible to put the secret key in the certificate as that is supposed to be public; it needs to be trusted by the other party after all. As symmetric cryptography lacks a public key, symmetric cryptography cannot be directly used for X.509 certificates.

The most prevalent use of X.509 certificates is probably TLS. TLS may also be used using other authentication methods, but X.509 is most common. With TLS the initial trust store is distributed with your browser. TLS itself does use symmetric cryptography such as AES and / or HMAC. However, in that case X.509 is mainly used for entity authentication, authenticating the server and optionally the client. The

TLS 1.2 and earlier also used the public key within the certificate to encrypt symmetric master key material. This key material can then be used to derive the session keys. These session keys are used to protect the messages of the transport layer, HTTP data in the case of web technology. Generally however, the RSA key is only used to authenticate the Diffie-Hellman key exchange that performs key agreement creating the same master key material on both sides. In that case RSA is not directly involved in the symmetric part of the protocol. For TLS 1.3, RSA cannot be used anymore to directly establish keys by encrypting them and sending them over.

Generally X.509 certificates and their private keys can be used for any purpose that requires either authentication, non-repudiation (i.e. document signing) and encryption / decryption. The private key is used by the signer for the first two purposes and by the receiver for the latter.

Protocols that use X.509 besides TLS are: Cryptography Message Syntax (both document signing and encryption), XML-DigSig and XML-Enc including in Web-security, PDF signing, application code signing, Windows authentication etc. etc. There are use cases for sectors such government identification / authentication, driver licenses, banking...

Obviously autentication, non-rep and encryption / decryption is pretty broad so countless public or proprietary protocols can benefit from asymmetric crypto and therefore X.509 based PKI.

X.509 may be trickier to use if there is no networking is possible, as the checks for certificate status commonly rely on networking to be present. Similarly, a trusted time source is often needed as well, although with networking NTP is commonly possible. Obviously parties also need to trust one or more Certificate Authorities.

Finally, many protocols and schemes also require some kind of random number generator to be present. Finally, especially for embedded devices and (smart) cards, the processing requirements for generating keys, signing or decryption may be hard to fulfill or hard to secure.

As an extreme hack, you could use the same certificate / private key or two certificates for the same private key for multiple parties, turning the private key into a secret key of sorts. As a public key must be present in the X.509 certificate this is easier than adopting the PKI for symmetric cryptography.

However, to do that a good understanding of the cryptography used is absolutely required, as an adversary can for instance perform encryption with the public key, which is not possible when using symmetric cryptography.


Help to understand the chameleon hash function? Recently, I'm reading Non-Interactive Key Exchange, in the section 4.2(Towards a factoring-based scheme in the standard model,Page 10), the authors uses

$$t\gets ChamH_{hk}(Z||ID;r);\\
Y\gets  u_0u_1^tu_2^{t^2};X=Y^x$$
this way, I don't understand why the authors use the chameleon hash function like this, who can tell me why? And I also don't understand the corresponding proof in the appendix D(Proof of Theorem 4,Page 22)

Edit: Sorry, I know this is bad form, but I'm replacing my entire answer :).

The proof takes place in the so-called CKS-light model, which allows the adversary only two "register honest" queries, i.e. the ability to register two identities of his choice and receive their generated public keys. In the end, he must distinguish the shared secret of these keys from random.

In the proof, the fact that the public key involves a degree-two polynomial in $t$ is used to generate a uniformly random pair of keys satisfying $p(t) = a_0 + a_1t + a_2t^2 = 0$ for the same polynomial $p$, and these $t$-values are used to satisfy the adversary's two honest-key queries. This strongly suggests that the 2 in "degree-2 polynomial in $t$" and the 2 in "adversary only gets 2 honest queries" are one and the same.

One way to test this intuition is to adjust the security game so that the adversary gets 3 honest queries and see if this lets you break it. Another way is to drop the polynomial in $t$ to degree 1 and see if you can break it under the same security model. I think either one will give you some intuition as to why $t$ is used the way that it is.

(My original answer suggested that if the polynomial in $t$ had only degree 1, and the adversary was able to register two identities with the same secret key $x$, this would give him undue power. This is true but irrelevant, since the security game does not let the attacker do this.)

Edit2: As for problems in the proof in the appendix: I'm pretty sure that we need $u_i = g^{b_i}$ for $i = 0, 1, 2$; but I don't see this written anywhere. Also the line
$$ X_i = D^{\alpha_{3-i}b(t_i)} = (u_0u_1^tu_2^{t^2})^{\frac1{\alpha_i2^{3k}}}$$
is wrong; it should be
$$ X_i = D^{\alpha_{3-i}b(t_i)} = (u_0u_1^tu_2^{t^2})^{\frac1{\alpha_i}}$$
which sets the secret key $x = 1/(\alpha_i 2^{3k})$ as claimed.


How robust is discrete logarithm in $GF(2^n)$? "Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime $p$. However, there exist other finite fields out there, in particular binary fields $GF(2^n)$. There is a specific attack described by Coppersmith for discrete logarithm in a binary field, and it was later on refined into the more general Function Field Sieve by Adleman and Huang. The FFS was used by Joux and Lercier to obtain the current record in $GF(2^n)$ discrete logarithm, where $n = 613$.

What I would like to know is:

How does discrete logarithm in $GF(2^n)$ compares to discrete logarithm modulo a prime $p$ of $n$ bits ? At the time when Coppersmith published his algorithm, it made discrete logarithm in binary fields look easier than its prime $p$ counterpart, but the latter also got improved later on.
Is it important, for discrete logarithm in $GF(2^n)$, whether $n$ is itself prime or not ? The current record is for $GF(2^{613})$, beating the previous record of $GF(2^{607})$, and both 607 and 613 are prime numbers. Would discrete logarithm in $GF(2^{1024})$ be easier than in $GF(2^{1021})$ ?

Discrete logarithms in $\mathbb{F}_{p}$  share the same asymptotic complexity as integer factorization for general numbers: $L_p[1/3,1.923]$ for general integers, $L_p[1/3,1.587]$ for special integers. Discrete logarithms in $\mathbb{F}_{p^n}$ have the same asymptotic complexity as factoring special integers, i.e. $L_{p^n}[1/3, 1.587]$, via the Function Field Sieve.

So, extrapolating from the factoring records, we can handwave that a discrete log in $\mathbb{F}_{2^{1021}}$ is an order of magnitude easier than a discrete log modulo a 768-bit general prime, and about the same as modulo a pseudo-Mersenne prime $2^{1021} - c$.

As to whether composite degree extension fields are easier to solve, maybe. It is possible to represent the same composite field in a number of ways (usually known as tower of fields), and it is possible that some representations allow for faster breaks than others. Here's a quote from Andrew Odlyzko's 1985 paper Discrete logarithms and their cryptographic significance:

  In fact, these ﬁelds may be very weak because of the possibility of moving between the ﬁeld and its subﬁelds.

However, there is no data on significant asymptotic advantages of composite degree over prime degree (if there was, pairing-based schemes would be toast, as embedding degrees are by and large composite).

One shouldn't also forget to check the smoothness of $p^n-1$, to avoid embarrassing Pohlig-Hellman breaks.

May 2013 Update

It seems that composite degree is indeed weaker than prime degree. The recent results of Göloğlu et al and Joux attack fields $\mathbb{F}_{2^n}$, for composite $n$, much faster than the function field sieve referred above. See this question for more information.


SHA3 HMAC key padding According to the pseudocode, keys longer than the block-size of the underlying hash function are shortened by hashing the key. Furthermore, keys shorter than the blocksize are zero-padded up the length of the block-size.

    if (length(key) > blocksize) {
        key = hash(key) // keys longer than blocksize are shortened
    }
    if (length(key) < blocksize) {
        // keys shorter than blocksize are zero-padded (where ∥ is concatenation)
        key = key ∥ [0x00 * (blocksize - length(key))] // Where * is repetition.
    }

Taking into account that the block-size of SHA3-512 is 72 bytes, and it's output is 64 bytes, does that mean the keys longer than 72 bytes should first be hashed and then the resulting 64 bytes should be zero-padded?

In lieu of any answers; I've compared my own implementation with the few test vectors I've been able to find (one of which can be found here) and it would appear that yes, keys longer than the block-size are hashed and zero-padded. It feels counter-intuitive to shorten a key and zero-pad it, but that's what the specification stipulates.


Why work in a subgroup for Naor and Pinkas oblivious transfer? In section 4 (protocol 4.1) of the paper by Naor and Pinkas [1], why did the authors decide to operate in a subgroup? When they say "the messages are in the subgroup" does that mean $x, y, z_0, z_1$, $w_0, w_1$ and the encryption keys are in the subgroup but the private values such as $a, b, r_0, s_0$, etc. are not? Does the construction work for any subgroup or is it more typical to use group of quadratic residues modulo prime?

Sorry if this is a bit elementary, any references regarding how subgroups are used in DH-based protocols are also appreciated.

[1] "Efficient oblivious transfer protocols" http://www.pinkas.net/PAPERS/effot.ps

The protocol's security comes from the DDH assumption, which is only secure when operating in groups of prime order [1]. The more typical groups, e.g. $\mathbb{Z}_p^*$ is not of prime order, but of order $p - 1$. Fortunately, a subgroup of $\mathbb{Z}_p^*$, namely the set of quadratic residues modulo $p$ doesn't have this problem. This answers the first question.

To answer the second question, the public values such as $x, y$ and so on are in the subgroup. The private values are selected uniformly at random from $\mathbb{Z}_q$, where $q$ is the order of the subgroup (and the generator $g$).

Finally, the set of quadratic residues is one of the simpler subgroups to understand, but others are also possible as long as DDH is hard. Some alternatives are outlined in [2].

[1] Katz and Lindell, Introduction to modern cryptography, Chapter 7.3.3

[2] Dan Boneh, The decision diffie-hellman problem, Section 1.1, http://crypto.stanford.edu/~dabo/pubs/papers/DDH.pdf


How many polynomials are used in Secure Multiparty Computation? Secure Multiparty Computation based on Samir Secret sharing methods rely on Polynomials. Imagine corpus of data should be outsourced to bunch of untrusted servers for any computations. Now the data could be split by a trusted client using Secret Sharing and distributed among the multiple untrusted servers. Subsequently any operations on the data could done using Secure Multiparty Computation protocols such that no single untrusted server has access to complete data in clear.

If the corpus of data are confidential documents and the client tokenizes them into each word then secret shares those words into say three shares. Distribute them to three untrusted servers. So that subsequently the client could search the documents for keyword using some SMC protocol.

Should the client use different polynomials for each word (or collection of words) or same polynomial could be used for entire corpus of document

Precisely,

If same polynomial is used for secret sharing all the words then searching the corpus with the share of keyword would be easy. But then the secret shares of each word would be pretty deterministic and frequency analysis could be launched to identify the words.
If different polynomial is used then how is the search for keywords work on the entire corpus ?

The same might hold good not only for search , for any other operation including arithmetic. Any help ?

For "standard" Shamir secret sharing you use a new random polynomial for each secret you want to share (including when you use Shamir secret sharing in SMC). I.e., you would use different polynomials for each secret. Note, that Shamir secret sharing does not directly work on "words" but rather elements of some field. You would have to translate your data into field elements and then share those elements individually.

There is, however, a variant of Shamir secret sharing called "packed secret sharing". In this variant you are able to share a "block" of $l$ secrets using a single polynomial. This means you would be using a factor $l$ less polynomials. There are SMC schemes that rely on this kind of sharing as well, although they are somewhat more complicated than those using standard Shamir secret sharing (an example of such a scheme can be found here: iacr eprint link).

As to how search would work, this is really not something that is standardized. The SMC allows you to compute any arithmetic circuit over the shared data. You can essentially express any function, including keyword search, as an arithmetic circuit. However, exactly how to do this is not trivial to figure out.

In fact, for this particular task you may be better off picking a different SMC technique, based on Boolean circuits instead of arithmetic circuits. This is because keyword search probably involves a lot of comparisons. Something that Boolean circuits are much more well suited for.


Is using 7-8 random words from all words of a language as password a good idea? The Bitcoin Bip-39 dictionary has 2048 words. And a random 24 of them are pretty secure together. What if the source is bigger (all words in the language) but there are only about 7-8 words? These words will be totally randomly selected by their index.

The Bitcoin Bip-39 dictionary with 2048 words can create $\approx 2^{263}$-entropy by tossing the coin 256 times to choose the words randomly. The random bits are converted into 24 11-bit blocks and every block is mapped into one of the 2048 words by ID. Since the random choice allows repetition, we need $n^r$ not $P(n,r)$;

$$2048^{24} \approx 2.9642774844752946\mathrm{e}{+79} \approx 2^{264}$$

If we assume that English has 171,476 words. Then with 8 words;

$$ 171476^{8}  \approx  7.475267765296064\mathrm{e}{+41} \approx 2^{139}.$$ Therefore you will have lower entropy the Bip-39, again. With 7 words;

$$ 171476^7   \approx  4.3593667716158903\mathrm{e}{+36} \approx 2^{121}.$$ Therefore you will have lower entropy than the Bip-39.

As one can see, the choice 2048 and 24 in Bip-39 is clearly designed to reach $2^{264}$ entropy. If you use 16 words as passphrase ( as noted by Dan Neely)

$$ 171476^{16}   \approx 5.587962816287441\mathrm{e}{+83} \approx 2^{278}.$$ that will exeed the Bip-39. 15 words reaches $3.258743390496303\mathrm{e}{+78} \approx 2^{260}$.

  Is it still considered secure

Yes, it is still secure and beyond the reach of any collective power, like the total power of bitcoin miners that can reach $2^{92}$ double SHA256 hashes in a year.

Note: I used to round a lot. I've decided to use full numbers since that changed at least one bit. So, here the Python;

import math

def prinPowInBase2(b,p):

    print(b,"^",p)
    print("\t", math.pow(b,p))
    print("\t", math.log2(math.pow(b,p)+1))
    print("\t", math.floor(math.log2(math.pow(b,p)+1)))

prinPowerInBase2(2048,24)


Calculation of the avalanche effect coefficient Given a strict avalanche criterion matrix/dependence matrix for a hash function,how do I calculate the avalanche coefficient for it. I want to calculate a single parameter(value) which represents the amount of avalanche effect for the given hash function.

I have thought of computing mean all over the matrix but am not sure that's the correct thing to do.

The following paper talks about the avalanche coefficient but they haven't mentioned the way they calculate it.

I believe the only way you can do this is to assume you have fixed length inputs to the hash function $f$. Otherwise, it is problematic what probability distribution you'd want to impose on the input set $\{0,1\}^{\ast}$ which is the collection of all finite input strings. In practice, hash functions do have an upper limit on the input string, but that's astronomical, in terms of testing all input strings.

So, let's assume the hash function has security parameter of $k$ bits. This corresponds to the function acting like a random function with outputs of length $n=2k$ bits.

Your testing would generate a large number of random values from a uniform  distribution on $\{0,1\}^{m},$ thus treating the hash function as a random function $f:\{0,1\}^m\rightarrow \{0,1\}^n.$ Let this random set of inputs be denoted by $X$. Now define
$$
a_{ij}=\#\{x \in X:[f(x\oplus e_i)]_j \neq [f(x)]_j\}
$$
for $1\leq i\leq n,1\leq j\leq m,$
where $e_i$ is the vector with a one in the $i^{th}$ position and zeroes everywhere and $[u]_j$ denotes the $j^{th}$ component of vector $u$. $a_{ij}$ counts the number of inputs from $X$ which differ in the $j^{th}$ output bit when the $i^{th}$ input bit is flipped.

You can now define a degree of strict avalanche criterion $D_{SAC}(f)$ as
$$
D_{SAC}(f):=1-\frac{\sum_{i=1}^n \sum_{j=1}^n \left|\frac{2a_{ij}}{\#X}-1\right|}{nm},
$$
with the expectation that $D_{SAC}(f)$ should be approximately 1, i.e., the sum of the absolute differences $$\left|\frac{2a_{ij}}{\#X}-1\right|$$ over $i$ and $j$ should be small. One way of expressing this may be to say $E[A_{ij}] \approx (\#X/2)$ if $A_{ij}$ is a random variable representing the $a_{ij}$ with $A_{ij}$ distributed as the binomial variable $Bin(\#X,1/2).$ From here you can then model the overall experiment in terms of chi squared variables, by using the Gaussian approximation to the binomial. So take the properly scaled $nm$ variables as being from a chisquared distribution with $nm-1$ degrees of freedom.


Is an elliptic curve over $\mathbb{F}_p$ order preserving for the points $(x,y) \in \mathbb{Z}_p$? Let $E\colon y^2=x^3+ax+b$ be an elliptic curve, and consider its realisation over the finite field of prime order $p$: $E(\mathbb{F}_{p})$.

Then if $0<a,b$ is the following true?

$$\forall x,y\in[0,p) \text{ s.t. }E(x)=y \text{ : }(x_i<x_j)\implies E(x_i)<E(x_j)$$

The question as currently stated is true if we assume the equation takes place in $\mathbb{Z}$, since all the values are small integers.

Proof: If $x<x'$, then $x^3<(x')^3$ and $ax<ax'$, so
$$
E(x)= x^3 +ax+b < (x')^3 +ax'+b = E(x')
$$

The problem with trying to answer the more general issue you appear to be considering is working out what it means to say $x<y$ for $x,y\in\mathbb{F}_p$. There isn't a reasonable ordering on elements of a finite field, or indeed on $\mathbb{Z}/p\mathbb{Z}$.  Intuitively, one might wish that $x<y$ if and only if $x<y$ when considered as integers. However, this doesn't work because there is no mapping that will respect the required properties. Consider the following [attempt] at defining this:

  For any $x\in\mathbb{Z}$, let $\bar{x}$ denote the image of $x$ under the projection into $\mathbb{F_p}$. Then,[try to] define an ordering $\prec$ on $\mathbb{F}_p$ by $\bar{x}\prec\bar{y}\iff x<y$.

The biggest problem with this is that it isn't even well defined. For example, let $a,b\in\mathbb{F}_7$, with $a=\bar{3}$ and $b=\bar{6}$. Then since $3<6$ we deduce $a\prec b$, but since $a=\bar{3}=\bar{10}$ we must also have $b\prec a$ (since $6<10$). This would imply $a=b$, which is clearly false.

For more information, this wikipedia page might help.


how can identify which cryptanalysis is used ( Indistinguishability cryptanalysis against classical ciphers) I have 10 ciphertexts and 10 plain texts I want to know which cipher is from which plain text
how can I know this
I  know the name of substitution cipher,  transposition cipher,  Vigen`ere cipher and  case-insensitive letters-only one-time pad that are used in these 10 cipher and plain text

Do frequency analysis by counting the number of occurrences of each letter.
For a transposition cipher, the counts will be similar to the underlying language (e.g. E T A O N will be common in English).
For a substitution cipher there will be the same distribution of counts as the underlying language, but the high counts will match with the wrong letters.
For Vigenere, the counts will be more uniform and closer to being equal.
If you have matching plaintext, the counts for transposition will be identical; the counts for substitution will be the same numbers in a different order; the counts for Vigenere will be very different.


Authenticated encryption using asymmetric keys I know this may be marked duplicate. It is based off of this question and this answer.  However, I feel like I'm missing something...
My example:
Bob wants to encrypt a message and send it to Alice using Alice's public key.
However, Bob also wants to sign the message using his private key before encrypting the (message + signature).
For sake of argument lets assume Alice and Bob are using RSA2048. According to PKCS #1 v2.2, both, RSASSA-PSS and RSASSA-PKCS15 signature schemes produce an output the size of the key's modulus (in this case 256 bytes).  However, both OAEP and PKCS15 encryption schemes require the message size to be less than the modulus size (less than 256 bytes).
How can one sign and then encrypt a message according to this spec?  Would the plaintext just be broken into two chunks?  Hybrid encryption seems like overkill if the message is small.  Even a single ASCII character would be too large to sign then encrypt this way...

You will always need at least to blocks (=512 bytes in your case) if you want to encrypt and sign some data.
Any RSA signature block, be it armored with PKCS#1 v1.5 or PSS (or even textbook RSA) will have the size of the modulus (256 byte), since it is the output of a RSA operation. So if you want to add some plain text data to that, you will automatically need to start a new block.

All said is under the assumption of using two keys of equal size (2048 bit), as you suggested. You could get away with one block if your signature key has a smaller bitsize (e.g. 2048) then the encryption key (e.g. 4096).


Secure hashing when the input comes from a small space I have a problem that I'll simplify here. Let's say I want to store a table of {person, fav color}. Only, I don't want anyone to ever be able to look up a person't favorite color; the only thing someone should be able to do is group people if their favorite color is exactly the same (not just merely similar). The obvious solution would be to not store the favorite color, but {person, hash(fav color)} using a good crypto hash(). Only, turns out that there is a very small list of color names, and anyone can easily enumerate all the colors, and compute the hash thereby reversing the hash and extracting the fav color for a person. I can stretch, but that makes computing hash() slow -- it needs to be a fast operation.

Basically, I have input x chosen from a small, easily enumerated space. I want a fast-to-compute function H that will guarantee x==y <=> H(x)==H(y) (with high probability). But knowing H(x) does not allow one to easily compute x.

I'm creating a secret key, and using H(x) as Hmac-Sha256(x, key).

Does this work? Is there a better, more accepted way of doing this?

What you want is the below query is possible but the database is secure against; Frequency/Inference attacks
Select * FROM users WHERE 'fav_color' = RED

What we have; small values space for the color names as people's favorite colors. We can consider this is as an example of the small message space like gender, age, weight, scale, the illnesses they have, etc. The more the information is leaked the more to identify a target.

Case: Cryptographic Hash: Hash functions are considered as a candidate for a one-way function. This means that they are hard to invert. In hash terms, they need to have pre-image resistance. Keep in mind that they are deterministic in the sense that one gets the same hash value whenever the same input is hashed again.
Select * FROM users WHERE 'fav_color' = Hash(RED)

Pre-image resistant: for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage $x'$ such that $h(x') = y$ when given any $y$ for which a corresponding input is not known.

In a normal pre-image attack, the success of the attack requires around $\mathcal{O}(2^n)$ search to be successful. This can be executed random $2^n$ input search for the hash value. Since the input space is small, once the attacker access the database they can infer the input values very easily. If one assumes that they have all the knowledge of the system, they can prepare a hash table beforehand.
Using slow and memory hard hashing like Scrypt/Argon2id will not much against this attack. It will only make the attack time slower and very small input spaces like color will be still an easy target.
Using salt can kill the hash table/ rainbow tables, however, one cannot execute the query anymore since the same color name will have different values.

Case: Cryptographic Keyed Hash: Keyed hash function like HMAC and KMAC requires a key to operate and the security also relies on the key. They are also deterministic.
Select * FROM users WHERE 'fav_color' = HMAC-SHA256(RED)

In this case, the attacker has no chance of executing a search as in unkeyed hash function since the key prevents it. This is not preventing them to infer data from the tables. The frequency attack is possible as in the case of the CryptDB.

Case Encryption: We can remove the case of stream cipher since the no padding option will leak information about the data as $\color{Blue}{\textbf{Blue}}$  will be longer than $\color{Red}{\textbf{Red}}$. We may assume that with proper padding all the colors have the same plaintext size that result in the same block size.
Select * FROM users WHERE 'fav_color' = ENC(RED)

One can use ECB mode that enables equal queries like in CryptDB since it is not Ind-CPA secure. In this case, the attack same as in the HMAC case, look for the frequency.
Using Ind-CPA secure ciphers modes like CBC and CTR will hide the frequencies, however, that will remove the equality query.

Other options These are slow, however, can hide the frequency on the data at rest since these are using randomized encryptions.

Once can use PIR (private information retrieval) schemes to access the data with the required fav_color. This may need a special design to access all.
FHE (fully homomorphic encryption) base database; we will see.


Is AES-CTR-NoPadding resistant to variable-length chosen-plaintext attack? Consider the following scenario: an adversary $A$ with access to an encryption oracle $\mathcal{O}$ is able to choose $n \in \mathbb{N}$ and pick $p_1,\dots,p_n$ such that $\forall i \in \{1,\dots,n\}:$ $A$ queries $\mathcal{O}$ with $p_i$ in order to obtain ciphertext $c_i := \texttt{AES_CTR_ENC}(p_i,k,IV)$ for some unkown key $k$ and initialization vector $IV$ (n padding scheme). Furthermore, assume that $|p_i| \neq |p_j|$ $\forall i\neq j $.

Is it possible that the abovementioned encryption scheme (AES-CTR without padding) is somehow resistant to this type of attack?

Your fundamental misunderstanding is that encryption does NOT provide security for plaintexts of different lengths. This is explicit in the definition, where indistinguishability only holds as long as the challenge plaintexts (of which one is encrypted) are of the same length.

In practice, in cases where length reveals information, one needs to pad.


Why are LFSRs represented as polynomials? Disclaimer: I am neither an electronics engineer nor am I a mathematician.
I understand what an LFSR is. I can derive the periodic sequence if an LFSR is described by it's taps.
My question is - why are LFSRs represented as polynomials?
What is the advantage of representing taps as x^n? What is the x? What is the constant at the end?
I see a very similar question - Why is the polynomial of an LFSR called so?
But I am still asking my question because I don't understand the answers. I don't understand what a delay operator is. So the answer is not useful to me.
Also that answer doesn't really cover the advantage of representing it as a polynomial.

why are LFSRs represented as polynomials?

Because it gives useful insights into the behavior of the LFSR.
If the feedback terms are represented by the polynomial $P$, and if the initial state of the LFSR is represented by the polynomial $Q$, then the state of the LFSR after $n$ steps will be the polynomial $x^n Q \bmod P$ (where the calculation is done on polynomials, and not on the underlying field - algebra on polynomials is not difficult, however it is different than what you may be used to).
Why is this a useful insight?  Because we can determine the long-term behavior from this observation.  For one, we have $x^n Q \bmod P = (x^n \bmod P) \times Q \bmod P$; assuming that the constant term of $P$ is relatively prime to the field characteristic, then $x^n \bmod P = 1$ for some $n$, and so the LFSR will eventually return to its initial state (and not fall into an intermediate-state loop).
Furthermore, we can deduce that, as long as $Q$ is relatively prime to $P$, then the number of steps that the LFSR will take before it returns to the original step is independent of the actual setting of $Q$.
Thirdly, if $P$ is an "irreducible polynomial", that is, if there do not exist polynomials $R, S$ with degree > 0 s.t. $P = R \times S$, then the amount of time taken before the LFSR returns to its initial state will be a factor of $p^k$, where $p$ is the size of the field used (2 if we're doing out LFSR in a binary field) and $k$ is the degree of $P$.
These observations (except for the first) are not obvious from the abstract definition of an LFSR.
And your final question:

What is the final constant in the polynomial?

It's just another feedback term from the LFSR.  The LFSR can be represented in 'Fibonacci' or 'Galois' modes (and the above abstraction works for both, so it doesn't matter which for the above discussion).  In the 'Fibonacci' mode (which appears to be what you are asking about), this constant term corresponds to the sum of the feedback terms that is used to generate the new bit within the LFSR.


Possible issues with ECIES using a static (non-ephemeral) sender key After looking at this bitcoin-related ECIES repo I believe the intention is that, at least in some cases, the recipient would know that the message is intended for them and use an secp256k1 public key that they know belongs to you to perform the key derivation process on their end.  Even if that is not their intent, I am curious about the security implications of such a schema.

That is, a recipient of ECIES ciphertext data (containing an IV, AES ciphertext, and a HMAC), performs key derivation with a known, static sending public key and their private key.  As is done in this library, they compute the diffie-hellman shared secret and use SHA-512 as a key derivation function.  The first half of this has is used as an AEC-CBC decryption key, but before that the second half is used to authenticate the ciphertext with HMAC-SHA256.

Assuming all goes well they are confident of both the origin of the message (by virtue of the key derivation being successful and the HMAC authenticating the ciphertext) and of the data itself.

The primary issue I see with this schema is that that encryption/HMAC keys will be the same for any messages sent between the two parties.  However, assuming the IV is chosen intelligently I believe this should be safe, though it removes any forward secrecy provided by using an ephemeral sending key.

Are there any other downfalls of this approach?  Is this regarded as just a form of ECIES or is it possibly something different since the sending key is not ephemeral?  (At the very least, Wikipedia seems to imply the key should be ephemeral.)

Finally, it seems to me that a saner way to achieve the goals of this library would be to generate an ephemeral key for the key derivation process, send that ephemeral public key with the cipher text, and include a signature with the known key either as a part of the message plaintext (to avoid the possibility of the public key being derived from the signature) or simply included with the ciphertext data.  What trade-offs exists with this alternate approach?

What trade-offs exists with this alternate approach?

Unless you need the non-repudiability you produce a larger ciphertext in a slower way for no interesting gain in security when signing and encrypting over using the static keys (apart from the "other downfalls" below).

  Are there any other downfalls of this approach?

Indeed if now either of your long term secret is compromised all ciphertexts can be decrypted unlike in traditional PKE schemes where only one party has such a long-term secret.

  Is this regarded as just a form of ECIES or is it possibly something different since the sending key is not ephemeral?

Technically speaking it doesn't fit the traditional signature of a public key encryption scheme because there the encryption isn't allowed to maintain state and obviously a sender secret can't be part of the public key. The most common name for this I know would probably be crypto_box (taken from NaCl's naming) which does essentially this. Academically speaking the correct name is "public-key authenticated encryption" because it is the public-key equivalent of authenticated encryption.


Is it possible I can open pedersen commitments without revealing r? With setup $p$ and $q$ where $p = 2q + 1$, and $g$ and $h$ is the generator with order $q$.

In Pedersen commitment, I commit the value m with $c=g^m h^r \bmod p$,
then de-commit by revealing $(m, r)$. $c' = c$, then the commitment hold.

I am wondering if I don't need to reveal $r$ to verifier, instead I can reveal $m$ only and construct a proof of knowledge on $r$ to have the sample result. As $s = h^r$ if $s = {{c}\over{g^m}}$, I can use Schnorr Protocol to prove that I know $r$ in $s = h^r$ for $s = {{c}\over{g^m}}$.

If verification hold, mean that provers know $r$ with $m$ in a relationship $c=g^m h^r$. Am I right?

I would like to add follow-up question if the answer is yes.

To prove the knowledge of $r$ in $s = h^r$ for $s = {{c}\over{g^m}}$. I can use Schnorr Protocol to construct the proof. But if it is possible to make it only available for designated verifier to verify the proof?

I read a paper is about Designated Verifier Signature, but it is about creating proof on a signature $s=m^x$ where $m$ is the message and $x$ is the private key of signer.

So is it possible to make Schnorr Protocol only can be verified by a selected verifier with know public key?

So is it possible to make Schnorr Protocol only can be verified by a selected verifier with know public key?

Here's the obvious way using a two dimensional Schnorr proof; this is a proof that, given $A^xB^y = C$, you know $x, y$.  It's a straight-forward extension of the regular Schnorr proof:

The prover selects random $r, s$, and computes $T = A^rB^s$.  He also computes $t = \text{Hash}(T)$ and publishes $T$, $u = x + rt$ and $v = y + st$.
The verifier checks whether $A^uB^v = C T^t$

We'll denote $K$ as the public key of the verifier, that is, she knows the value $k$ such that $G^k = K$.

Then, to do a Selected Verifier Proof that the commitment $C = G^m H^r$ is to the value $m$, the prover generates a two dimensional Schnorr proof that he knows the values $x, y$ such that $H^x K^y = C G^{-m}$.  The valid prover can generate such a proof, because he knows such a pair $(x = r, y = 0)$.  On the other hand, the verifier can not convince anyone else that this proves any specific value $m$, because for any $m$, she can construct a $y$ that allows her to generate such a proof.

Here's another idea that occurs to me; it appears to be a way to have a designated verifier Schnorr proof:

The prover wants to prove knowledge of a value $x$ s.t. $A^x = B$, for public $A, B$.  We'll denote $K$ as the public key of the verifier.
The prover selects two random values $r_1, r_2$, and computes $T_1 = A^{r_1}, T_2 = K^{r_2}$ and $U = G^{r_2}$ and computes $t = T_1 + T_2 \bmod q$ (where $q$ is the size of the subgroup).  Then, he publishes $T_1, U$ and $u = x + r_1t$
The designated verifier uses her private key $k$ to compute $T_2 = U^k$, and $t = T_1 + T_2 \bmod q$.  Then, it proceeds like a standard Schnorr proof,  checking whether $A^u = BT_1^t$

No one can verify this proof without the knowledge of $k$ (as they cannot compute $t$).  The designated verifier knows no one else knows $k$, and hence the prover cannot select $t$ arbitrarily.  And, if the verifier tried to forward this proof (possibly by forwarding the value $T$), this doesn't work (even if she exposed her private key $k$), because it is straight-forward to generate a validating $T_1, U, u$ set with the knowledge of $k$ (for arbitrary $A, B$)

Somebody should vet this 'designated Schnorr' proof before you use it; it looks like it meets the requirements.  Here's the reasoning for the 'proof of knowledge' portion: a putative prover can set an arbitrary $T_1 = A^c B^d$ (for arbitrary $c, d$).  However, in that case, the verification equation is $A^{ckt-u}B^{dkt+1} = 1$; this can be satisfied only if $dkt+1 \equiv 0$ (but to set the value $d$ appropriately, the prover would need to know $k$); otherwise, the prover would know that $x = (ckt-u)(dkt+1)^{-1}$, and so knowledge of $k$ (and $c, d$) would imply knowledge of the discrete log.


Total anonymity against malicious agents Suppose we have $N$ parties, two of whom are Alice and Bob, while some fraction of the remainder are malicious agents working together. We form a network where each party can pass an encrypted message to another indirectly by routing it through other parties. Alice and Bob know a key secretly, so they can communicate privately because the other parties who look at the message just see noise and pass it on.

But now suppose the malicious agents are really malicious; they can sneak into Bob's home and learn the key, and they also can spy on the entire network to track every movement. Now it becomes easy to unmask Alice. The malicious agents check every message they get with the key, and they'll eventually notice that they always see messages meant for Bob originating with Alice.

So my question is, assuming the agents can acquire as much info through Bob and the network at large as desired, is there a way to modify this protocol such that Alice can't be unmasked? I.e., that the agents will have no way (or a computationally-infeasible way) of guessing Alice is a more likely candidate than any of the other parties? The protocol can be somewhat unreliable if necessary. Obviously it will require some second layer of encryption, but I don't know what to look for.

Dining cryptographer networks are information theoretically secure to the anonymity set size. This is ultimately a traffic analysis question; however, it's very closely related to, and somewhat hard to delineate from, cryptography. In practice a DC-net is, in numerous ways, a lot like a one time pad. Primarily useful in theory and some niche cases. Anonymity is very much dependent on having a large anonymity set size, and DC-nets aren't very scalable.

Constant rate cover traffic is something else for you to read about.

Not just the semantics to be concerned about in this area. Malicious party will delay packets and create a watermark in interpacket arrival timings, then do end to end correlation analysis looking for that actively created pattern. This rapidly explodes into the massive complexity of mix theory. Pynchon gate is the state of the art in mix theory; it uses PIR for message retrieval from nymservers.

Traffic analysis still is largely successful even if all traffic is encrypted and impossible to decrypt. The goal is maintaining -- across all of myriad dimensions -- invariance from the anonymity set. Anonymity is at least typically severely degraded by any variation from the set, other than if there is variation in the form of randomization per hop (i.e. layers of encryption being removed at each hop still has variance of ciphertexts across the anonymity set, but the variance is made statistically independent from itself at each hop by the adding or removing of a layer of encryption).

Interpacket arrival timings are far from the only thing. Need the packets all padded to the same size, or else the packet sizing disparity across streams of packets creates a variance from the anonymity set that can be followed throughout the network.

Traffic analysis is extremely meta. It isn't about the communications, it's about the signals carrying them.

Check out freehaven.net bibliography.

Almost all experts say that Tor is the best bet for anonymity, and that this will not stop being the case any time soon. There is a big disconnection between theory and practice in this area. Plethora mix network designs, and things like DC-nets, are technically much stronger and -- arguably, perhaps anyway -- more sophisticated than Tor is. It's just they have such significant constraints on them, and oftentimes such poor scalability, that in the real world Tor blows them away even though it has major variance in terms of things like stream byte counts for example.


Bilinear pairing arithmetic Is  this $e(g^x,g^yH^z) = e(g^x,g^y)e(g^x,H^z)$ expression is true?

where $ g$ is the generator and $ H \in G  $

Yes, as @DrLecter said in the comments, that equation holds from the bilinear property. Here is a step-by-step proof.

Let $e : \mathbb G_1 \times \mathbb G_2 \to \mathbb G_T$ be a bilinear pairing.
The bilinear property states that:

\begin{align}e(g_1 ^ a, g_2 ^b) = e(g_1,g_2)^{ab}\end{align}

Since you don't seem to distinguish between $\mathbb G_1$ and $\mathbb G_2$, we will assume that the pairing is symmetric, so $\mathbb G_1$ and $\mathbb G_2$ are the same group and will be denoted as $\mathbb G$, with generator $g$.

Now, you said that $H  \in \mathbb G$. Since $\mathbb G = <g>$ (i.e., $g$ generates the cyclic group $\mathbb G$), then we can assume that $H = g^h$, for some unknown $h$ (we don't need to know $h$, it is just needed for proving that the equation holds).

Using elementary algebra, we have that:

\begin{align}e(g^x,g^yH^z) = e(g^x,g^y\cdot (g^h)^z) = e(g^x,g^{y + hz})\end{align}

Next, we apply the bilinear property:

\begin{align}e(g^x,g^{y + hz}) = e(g,g)^{x(y + hz)}\end{align}

Again, applying basic properties of the exponentation:

\begin{align}e(g,g)^{x(y + hz)} = e(g,g)^{xy} \cdot e(g,g)^{xhz}\end{align}

Finally, you just "undo" some of the transformations, using the bilinear property:

\begin{align}e(g,g)^{xy} \cdot e(g,g)^{xhz} = e(g^x,g^y) \cdot e(g^x,g^{hz}) = e(g^x,g^y) \cdot e(g^x,H^z)\end{align}

Using this technique, you can prove any of the derived identities of bilinear pairings. The following is a general identity that involves the product of pairings:

\begin{align}e(g^a, g^b) \cdot e(g^c, g^d) = e(g,g)^{ab+cd}\end{align}


Example Rainbow Table Generation I have read up on rainbow tables and think I understand the idea behind them. However, I find that it would be better for me to actually attempt to implement a (very basic) rainbow table generator in order to get a proper feel to using rainbow tables.

However, I face the problem of there not being descriptions on how to actually generate one. More specifically, I have found no descriptions on what reduction functions to use. Nor have I found out how many hashes a chain contains. Everything I have found has all been "hash then reduce" or "use OphCrack/RainbowCrack".

Is there information that takes me through the actual steps to generate chains and search through them? I want to learn how to make the tables, not how to use other peoples' programs.

Please do not link me to these websites:

http://kestas.kuliukas.com/RainbowTables/
http://project-rainbowcrack.com/tutorial.htm
http://www.ethicalhacker.net/content/view/94/24/
http://www.thetazzone.com/tutorial-rainbow-tables/
http://en.wikipedia.org/wiki/Rainbow_table

Wikipedia shows you how to create a rainbow table.

The information you are looking for is under "Precomputed hash chains"

The reduction function tries to create a new input, the non hashed part which is the password in rainbow tables, from a hash.  We want to choose a reduction function that will try to equally reduce the hash into new inputs such that it tries not to create the same input so many times.

Consider the following example.  We want to create a rainbow table for all 5 character number combinations for the md5 function.

Lets start out with 12345 as the input. The md5 hash is 827ccb0eea8a706c4c34a16891f84e7b.  The reduction function can be as simple as taking the first 5 numbers and using that as the next input.  This method will produce reasonably distributed new inputs.

So the hash

"827 ccb 0 eea 8 a706c4c4a16891f84e7b" would create "82708"

The next hash would be 71b8e22700e63c2a0c1bad6506549d3b then would be reduced to 71822 accordingly.

So our current chain will consist of:

12345 -> 827ccb0eea8a706c4c34a16891f84e7b ->

82708 -> 71b8e22700e63c2a0c1bad6506549d3b ->

71822

The chain can go as long as you want, until it his a previous input, after which it enters a cycle - i.e.  when it hits that point, it will just repeat itself and it will be useless.

Having a longer chain is going to reduce the space need to store these values but increase the time it needs to recalculate the entire chain.

All that would need to be stored would be the starting and ending point of the chain.

Given a hash, you use your same reduction function on it to get an input and repeats itself until that matches the end of a chain.

If it matches the end of a chain, you can just recalculate those values to determine which input it was.

NOTE: You want to make sure that you have every value from 00000 to 99999 in these chains, otherwise it will be incomplete.

If you need characters a to z instead of 0 - 9, you could just convert the hash to base 26.


Can length extension attacks be avoided by a single bit flip? It always seemed to me that length extensions are possible simply because no special operation is performed after the last operation - for instance in a Merkle-Damgård construction. Basically the MD construction makes sure that the hash state is secure after processing each block, and therefore the hash state can be directly used as the output of the hash function.

All the bits in the state should depend on all the input bits. That should mean that it will be as hard to find a hash with a short Hamming distance to an existing hash value as to find a hash with a much larger Hamming distance.

So if this reasoning is correct then any operation that:

doesn't affect the security of the hash;
cannot be reduced to the operation performed on each block;

should be able to turn a hash that allows length extension attacks to a hash that doesn't allow length extension attacks.

Questions:

Any problem with my reasoning? Is any bit flip enough for the full output of the hash (see note below)?
If it is that simple, is there any reason why it hasn't been performed on SHA-2? Were length extension attacks unknown or not seen as a problem?
Would such a stupidly simple construction be an viable alternative to HMAC (with $K \| M$ as input message and a static size of $K$)?

Note: Flipping a single bit could do the trick if my reasoning is correct, but it has the drawback that partial hashes may not be affected. Flipping every bit - to get the complement of the hash value - should work as well - I think.

The mistake I made is that flipping a bit (or all bits) of the output will still leak the full state of the hash function, after which it is possible to perform a length extension attack by updating more data from the given intermediate state. The bit flip is of course easily reversed by an adversary. Thanks go to fgrieu and yyyyyyy for pointing this out.

Performing a final calculation may still work, but it should of course not allow an attacker to retrieve the state after the last block was compressed. That means that the final operation needs to be one-way as well. This disallows simple instructions such as XOR (with known data) that can be reversed.


Extending key sizes in Salsa20 and ChaCha? I've written implementations of Salsa20 and ChaCha that accept 384 and 448 bit keys. It was fairly trivial to implement, the 'sigma' constant is replaced with key material, and the counter, (which was initialized at 0), rotates and can be initialized at any value. So along with the 64 bit vector, the entire 512 bit state can now be initialized via a key/vector.

This does not affect the performance in any way, and if a key is constructed using key + sigma + 0, the output aligns with an implementation that uses a 256 bit key. Provided that the key used is created using a strong PRNG, and the values that replace the constant are sufficiently asymmetric, this should not present a problem, as the constants function seems to be purely to reduce symmetry.

Is there anything incorrect in the description given above?

One other question: I am considering extending max rounds to 24, I have looked at the mathematical model and it seems that this should not do anything other than further diffuse the input. Is that correct?

You are correct about extending number of rounds. It is safe to increase number of rounds. In most cases it will increase safety margin.

Removing constants doesn't seem to be a good idea to me, as Salsa20 and ChaCha don't have any round constants. Purpose of constants is also to reduce number of bits that can be controlled by attacker, however key is not assumed to be controlled by attacker. Constants also separate different key lengths. I'm also concerned about sliding attacks, however I don't know, if they are applicable to Salsa20 and ChaCha as they are not a block ciphers.

Setting start value of counter with key will cause same block outputs with different keys at some points as counter will change key.

Even if replacing constants and counter with key is secure, setting 448-bit key into Salsa20 or ChaCha doesn't guarantee 448-bit security. For longer keys cipher (permutation) has to be stronger. Best attack on Salsa20 with 128-bit key breaks 7 rounds, while with 256-bit key it breaks 8 rounds. Also see Keccak permutation distinguishers.

Mouha and Preneel proofed that 15 rounds of Salsa20 is 128-bit secure against differential cryptanalysis. This means Salsa20 with 15 rounds and 448-bit key could possibly be broken with differential cryptanalysis with complexity of about 128-bits.

You could use XSalsa20 to extend key (instead of nonce) by 128-bits. This would be at least as secure as 256-bit Salsa20.


Unforgeable CPA-secure private-key encryption scheme that is not CCA-secure This is exercise with 4.26 in Katz and Lindell's introduction to cryptography 2nd ed.

The question is: Show a CPA-secure private-key encryption scheme that is unforgeable but is not CCA-secure.

This is what I've come up with.

Let $F$ be a pseudorandom function.

$Gen(1^n): k \leftarrow \{0,1\}^n$.

$Enc_k(m): r_1\leftarrow \{0, 1\}^n, r_2 \leftarrow \{0,1\}^n\setminus \{r_1\}$,
    output $c = (r_1, r_2, F_k(r_1) \oplus m, F_{k}(r_2) \oplus m)$.

$Dec_k(r_1,r_2,c_1,c_2): \perp$ if $r_1 = r_2$ or $F_k(r_1)\oplus c_1 \neq F_k(r_2) \oplus c_2$, else output $m = F_k(r_1)\oplus c_1$.

I have somehow proved that this is unforgeable and CPA secure.
I wonder if there is an easier way to go about it or if this scheme indeed has the required properties.

The notation $\perp$ means decryption fails. To summarize, unforgeability means that an adversary with encryption oracle can't come up with a valid ciphertext whose underlying message wasn't queried to the oracle before except with negligible probability.

Thank you.

EDIT: This scheme doesn't work. Flipping the last bit of the 3rd and 4th components of the ciphertext yields a valid encryption of $m$ with last bit flipped.

EDIT: To provide the formal definition of unforgeability.

Define the unforgeable encryption experiment $EncForge_{A, \Pi}(n)$:

Run $Gen(1^n)$ to obtain a key k.
The adversary $A$ is given input $1^n$ and access to an encryption oracle $Enc_k(\cdot)$. The adversary outputs a ciphertext $c$.
Let $m = Dec_k(c)$, and let $Q$ denote the set of all queries that $A$ asked its encryption oracle. The output of the experiment is 1 if and only if $m \neq \perp$ and $m \notin Q$.

An encryption scheme $\Pi = (Gen,Enc,Dec)$ if for any PPT adversary $A$,
$$
  P[EncForge_{A,\Pi}(n) = 1] \le negl(n)
$$
for some negligible function $negl$.

Take an authenticated (unforgeable and CCA-secure) encryption scheme, such as the one constructed in the book using encrypt-then-authenticate with a CPA-secure encryption and a strongly secure MAC.

Define a new scheme by appending to the ciphertext a random string.

This new scheme is still CPA secure and unforgeable. But it's not CCA secure because the adversary can change the random appendix and thus ask the oracle for decryption and win the CCA game.


Do Carter–Wegman MACs allow key reuse if the MAC tag is kept secret? Poly1305 (and GHASH) are secure authenticators, but only for one use.  Thus, nonce reuse in Poly1305-AES, ChaCha20-Poly1305, and AES-GCM all reveal the authentication key.  However, my understanding is that this is because (in Poly1305-AES, ChaCha20-Poly1305, and AES-GCM) the output of the hash function is encrypted using a stream cipher, and as such nonce reuse gives away the XOR of the hashes.

Suppose that one uses AES in ECB mode to encrypt the authentication tag instead (using a secret key that is unrelated to the other keys, the message, and the nonce).  In this case, nonce reuse gives away no information unless the auth tags collide (which will only happen with probability about $2^{-56}$ or so).  Similarly, one could use Blake2 or Keccak to hash a nonce, secret key, and the tag to produce a larger tag.

At least this is all my understanding.  I am not a cryptographer, and I could be wrong!  Am I?

Note: I do not plan on using this in any actual software.

You can use methods for hiding the output of the polynomial hash that don't require nonces, such as encrypting with a block-cipher of matching block-size or hashing it with a keyed hash (PRF).

Not using a nonce reduces the security bounds (security decreases as the attacker sees more messages using the same key), makes it incompatible with stream ciphers and increases latency, but avoids the risk of total failure due to nonce reuse.

You can avoid the reduced security bounds while keeping nonce misuse resistance by hashing both the nonce and the polynomial hash output, but the other downsides remain.

The Poly1305 paper justifies the use of nonces as follows:

  There are several reasons that Poly1305-AES uses nonces.

  First, comparable protocols without nonces have security bounds that look like $C ( C + D ) L / 2^{106}$ rather than $D L / 2^{106}$ --
  here $C$ is the number of messages authenticated by the sender, $D$ is the number of forgery attempts, and $L$ is the maximum message length -- and thus cannot be used with confidence for large $C$.

  Second, nonces allow the invocation of AES to be carried out in parallel with most of the other operations in Poly1305-AES, reducing latency in many contexts.

  Third, most protocols have nonces anyway, for a variety of reasons:
  nonces are required for secure encryption, for example, and nonces allow trivial rejection of replayed messages.

In the popular XSalsa20Poly1305 combination, you already have a severe confidentiality failure if you reuse nonces, so a MAC failure on top of that doesn't seem to be a big deal. You could use Salsa20 as a hash instead of a stream cipher to hide the polynomial hash output, but that'd add a non-parallelizable Salsa20 computation (SIMD implementations of Salsa20 benefit from parallelism, even in software), making it expensive for small messages.


Finding the period of a function with a single output qubit - impact on RSA In this paper,May and Schlieper claim that one can find the period of a function $f()$ by embedding $h \circ f = h(f(x))$ for input $x$. This would have the immediate consequence of reducing the number of output qubits. What's more, they say that even a one-bit hash function would be enough to run Shor's algorithm and get reasonably good results. This is at the price of performance.
My questions are, how reasonable are these claims? What is the impact on post-quantum RSA security? Post-quantum RSA security is considered by some people as not that worrisome since it requires a non-negligible number of qubits to be practically broken.

My questions are, how reasonable are these claims?

Sounds fairly reasonable; they suggest an alternative factoring algorithm where they trade-off circuit depth to reduce the number of qubits required.
Would this trade-off be a good thing in practice?  We don't know.  We don't have a large scale quantum computer in front of us, and so we don't know the relative cost of different things, such as how expensive qubits are compared to a longer time to complete the computation (and if your logical qubits aren't perfect, a longer computation implies a larger probability of an intermediate error somewhere).
On the other hand:

What is the impact on post-quantum RSA security? Post-quantum RSA security is considered by some people as not that worrisome since it requires a non-negligible number of qubits to be practically broken.

Even if the number of qubits were the major cost factor in quantum algorithms, this algorithm doesn't reduce them all that much overall.  After all, I don't believe we have that good of a view about the size of a quantum computer an adversary might have when they get one; if they did have a 2k logical qubit computer (and so could use this algorithm to factor a 2048 bit number), they could plausibly have a 4k qubit (and so could use standard Shor's).  Our ignorance of the size of a quantum computer someone might have is far greater than just a factor of 2.


Vigenère cipher - sorted order i'm new to cryptography so i feel sorry for this newbie question!
Can anyone tell me how Vigenère work with sorted order?
For example i have this in my book:

LADY(KEY)
3124(SORTED ORDER)
312431243(REPEATED KEY)
PLAINTEXT(PLAINTEXT)
SMCMOUGBW(CIPHERTEXT)

Can you tell me how we get this number(3124) and ciphertext from this key(LADY)?

ADLY is the order those letters appear in the alphabet, so A=1, D=2, L=3, Y=4.

But I've never seen such a substitution in a Vigenere cipher, and it's dumb, since it makes a weak algorithm even weaker. Normally you just identify A with 0 or 1 and then assign increasing numbers to subsequent letters. A=0, B=1, C=2, ... Z=25, so LADY would map to 11,0,3,24 (or 12,1,4,25 if you start with A=1 and end with Z=26=0).


Many time pad if cleartext contains arbitrary bytes I understand the problem of reusing the same key in the one-time pad if the cleartext message only contains characters such as A-Z, a-z and spaces.

But what if our cleartext is composed of arbitrary bytes? Which type of attack can we make to find the key or/and decrypt the ciphertext?

I think you misunderstand the concept of the one-time pad encryption method since the one-time pad treats messages like a binary sequence.

What is done is actually for a message $m$ (this message could be an image, a text, anything, ...), you use its binary representation and XOR its binary value with a binary key $k$ : $m$ $\oplus$  $k$.
So it doesn't matter what kind of characters your message contains, you still can't break the security of the scheme when using the same key.

Check out this question: Taking advantage of one-time pad key reuse?


Potential weaknesses when combining hash functions? For consistency's sake, M is the message, H1 and H2 are separate hash functions.

I've heard that concatenation or XORing hash outputs together do not provide improved security against preimage and collision attacks. In some cases, they actually reduce the security instead. Therefore, consider the following scenarios:

(1) Scenario A: H1(M)||H2(M)=Z

In this scenario, the hash output of H1 and H2 are concatenated to form the final output Z. Let's say H1 is a weak hash function, and H2 is a strong hash function. If I find a preimage M for H1(M), does it mean that I have found a preimage for H1(M)||H2(M) as well?

(2) Scenario B: H1(M)||H2(M)=Z

In this scenario, H1 and H2 are both 256-bit hash functions truncated to 80-bits output, and are concatenated together to form the 160-bit output Z. Let's say we want to find a preimage for Z, which is an 160-bit string consisted entirely of "1"s. Let's say H1 is weak, and I can instantly find 2t preimages for H1(M), in which these Ms can produce an H1 output of 80 bits of 1. In this case, how much remaining work do I need to find a full preimage M for the H1||H2 concatenation that would hash to an output Z of 160 bits of "1"?

(3) Scenario C: H1(M)+H2(M)=Z, where "+" denotes an XOR operation

In this scenario, H1 and H2 are both 256-bit hash functions truncated to an 80-bit output, and are XORed together to form the 80-bit output Z. Let's say we want to find a preimage for Z, which is an 80-bit string consisted entirely of "0"s. Let's say H1 is weak, and I can instantly find 2t preimages for H1(M), in which these Ms can produce an H1 output of 80 bits of 0. In this case, how much remaining work do I need to find a full preimage M for H1+H2 concatenation that would hash to an output Z of 80 bits of "0"?

For generic weakness no.
Consider two weak hash functions H(x) = 1
This isn't preimage resistant but obviously concatenating a 1 to a hash function does not make it easier to find a preimage to it.

And consider H(x)=x
A very different kind of weakness and concatenate the message or parts of it would be super helpful in finding a preimage for the other function.


Breaking RSA when some bits of one prime are known RSA primes are 100 bit. You know first 80 bits of one of the primes. In this system, come up with an efficient way to decrypt the cipher-text.

This was the question on my quiz. I'm not sure how to go about it. Any hints?

The attack here is a simple factoring of the modulus. If you know the first 80 bits of a prime, you have 20 bits of search space using the most naïve trial division method, and 19 bits by just throwing out even numbers. Now you could use more advanced factoring techniques, but for only 19 bits of search space, you have 524288 candidates to test, which would take most modern processors a couple of seconds at the very most, so unless you have a large number of bad RSA keys to break, not much more effort than that needs be invested.

After factoring the modulus, you can decrypt at will.

The simplest approach is to make a counter, start at 1, and increment by two every iteration. Add the counter to the known starting point, and try to divide the modulus. If there's a remainder, continue the loop.

If the known bits are anything but the large end, its only slightly more complicated, and the search space is larger as we can't automatically throw out even numbers, so you have just over a million candidates to test. Here we use a counter then shift the bits into a mask to add to the known bit vector.


Elliptic Curve Digital Signature algorithm fails I would like to monitor step by step running of ECDSA.

Parameters I am working on:

The elliptic curve satisfies the equation: $y^2 = x^3 + x + 1$.
I picked up the base point $G$ as: $(0, 1)$
Finally, the modulo $p$ is $977$

My private key is $19$. Thereby, my public key is equal to $19\times G$ and its coordinates are $(396, 650)$. Suppose that my hash is equal to $14$.

Then, I picked up a random key. It would be $17$. So, random point would be $17\times G$ and it is equal to $(699, 739)$.

My signature is pair of $r$ and $s$, where $r$ is $x$ coordinate of my random point, and $s$ can be calculated as:
$$\begin{align}
r &= 699\\
s &= ((\text{random key})^{-1} \bmod p)\cdot(\text{hash} + r \cdot (\text{my private key}))\\
&= (17^{-1}\bmod 977)\cdot(14 + 699\cdot19)\bmod 977\\
&= (115\cdot13295)\bmod977\\
&= 1528925\bmod977\\
&= 897
\end{align}$$
So, my signature is $(699, 897)$.

Let's verify the signature
$$\begin{align}
w &= s^{-1}\bmod p\\
&= 897^{-1}\bmod 977\\
&= 403\\
u_1 &= \text{hash} \cdot w \bmod p\\
&= 14 \cdot 403 \bmod 977\\
&= 5642 \bmod 977\\
&= 757\\
u_2 &= r \cdot w \bmod p\\
&= 7699 \cdot 403 \bmod 977\\
&= 281697 \bmod977\\
&= 321
\end{align}$$

Now, I calculate the checkpoint
$$\begin{align}
\text{checkpoint}&=u_1\times G + u_2\times(\text{public key})\\
&= 757\times(0, 1) + 321\times(396, 650)\\
&=(707, 48)
\end{align}$$

Finally, I need to compare the $x$ coordinate of checkpoint and $r$ value of signature. But $x$ coordinate of checkpoint is $707$ whereas $r$ value was $699$. They are not same. This means that signature is invalid. But they should be equal! Anyone can help where I am wrong?

In the question, $p$ designates the modulus of the base field $\mathbb Z_p$, as confirmed by the fact that for  $p=977$ and the curve $y^2\equiv x^3+x+1\pmod p$, it holds that $19\times(0,1)=(396,650)$ and $17\times(0,1)=(699,739)$.
Problem is, in other steps, the question reduces $r$, $s$ and related quantities modulo that same $p$, rather than modulo the order $n$ of the group generated by $G$. That's more than enough to cause the observed failure.
As an aside, the ECDSA specification requires that $n$ is prime . In the question, the curve and $G$ is such that $n=987=3\cdot7\cdot47$ is composite. One consequence is that nearly half the choices of $\text{random key}$ are invalid, and I'm uncertain about if it otherwise makes some signature unverifiable. We do not care about the possible security implications since $p$ is so small as to make the whole thing insecure anyway.
I suggest $p=1033$, which will give a prime $n=1061$.


How to decrypt unusual Many Time Pad How does one decrypt the many time pad:

($R$ is a random string, $C$ is ciphertext, $P$ is plaintext)

$R_0 \oplus R_1 = C_0$

$R_2 \oplus R_1 = C_1$

$P_0 \oplus R_1 = C_2$

assuming that $R_n$ are perfectly random pads, plaintext is writing and $C_n$ are the encrypted pads. The key $R_1$ is used three times but it doesn't seem like Crib Dragging (the solution I've seen described to decrypt many time pads) would work (edit: to retrieve $R_0$, $R_2$, and $P_0$ or even just $P_0$) since the other values that $R_1$ is added to are random. Is there something I'm missing?

This cannot be used to compromise $P_0$. Suppose that, instead of generating $C_0$ and $C_1$ as $R_0\oplus R_1$ and $R_2\oplus R_1$, the attacker instead picked $C_0$ and $C_1$ at random from the set of bit strings the length of $C_2$. This situation is indistinguishable from yours; in both cases, $R_0$ and $R_2$ are independent and follow a uniform probability distribution, and the same is true for $C_0$ and $C_1$. If you can compromise $P_0$ in your case, you can compromise it if the sender had actually generated $C_0$ and $C_1$. But that would mean that sending two completely random strings alongside an OTP message somehow helps compromise the message. Obviously, that's not true; the attacker could otherwise create his own random strings and break the OTP that way.


How to generate $k$ random numbers that add upto a number $d$ and are coprime with respect to $p-1$ This is something that is needed while generating additive shares ($D_i$) for decryption key (represented by $d$) where each additive share must be coprime with respect to $p-1$  i.e $\gcd(D_i , p-1) = 1$

My guess is that the actual requirement is: given

RSA modulus $n$ (odd and square-free)
$\lambda(n)$ per Carmichael's function
Note: $\lambda(n)=\dfrac{(p-1)(q-1)}{\gcd(p-1,q-1)}$ if $n$ is the product of distinct primes $p$, $q$
an RSA private exponent $d$, thus with $\gcd(d,\lambda(n))=1$
moderate $k>1$

draw $k$ positive integers $d_i$ less than $\lambda(n)$ at random except they are such that

$\gcd(d_i,\lambda(n))=1$ for all $i$
$x^d\bmod n\ =\ \left(\displaystyle\prod_{i=0}^{k-1}x^{d_i}\bmod n\right)\bmod n$ holds for all $x$

The condition 1 is equivalent to $\gcd(d_i,p-1)=1$ of the question applied to all primes $p$ dividing $n$. It insures that $x\mapsto x^{d_i}\bmod n$ is a bijection of $[0,n)$, which possibly is desirable in the context of 2.

The question requires $d=\displaystyle\sum_{i=0}^{k-1}d_i$. That's not necessary for 2 to hold. We'll relax that requirement to $d\equiv\displaystyle\sum_{i=0}^{k-1}d_i\pmod{\lambda(n)}$, which is equivalent to 2, gives more choices for the $d_i$, makes the selection simpler.

Update: no matter what, we still must restrict to odd $k$: since $\lambda(n)$ is even, $d$ and all $d_i$ must be odd.

The limit $\lambda(n)$ for the $d_i$ is usual in modern expositions of RSA. It is pointless to choose a larger upper limit, for RSA exponents are equivalent modulo $\lambda(n)$.

Following closely the approach suggested in Daniel's comment, we can

for $i$ from $1$ to $k-1$

pick $r$ random in $[0,\lambda(n)/2-1]$ and set $d_i\gets2r+1$ until $\gcd(d_i,\lambda(n))=1$

compute $d_0=\left(d-\displaystyle\sum_{i=1}^{k-1}d_i\right)\bmod\lambda(n)$
if $\gcd(d_0,\lambda(n))\ne 1$

pick a random $i$ in $[1, k-1]$
pick $r$ random in $[0,\lambda(n)/2-1]$ and set $d_i\gets2r+1$ until $\gcd(d_i,\lambda(n))=1$
proceed at 2

Note: if we fixed $i=1$ in step 3, we'd end up with a slightly biased, but probably tolerable choice.

A comment states

  we need to find the inverse of $d_i\bmod p$

Perhaps that really means computing $e_i={d_i}^{-1}\bmod\lambda(n)$, which allows to verify $y_i=x^{d_i}\bmod n$ because for all $x$ in $[0,n)$ that's equivalent to $x={y_i}^{e_i}\bmod n$.

Beware however that we can't distribute public-key encryption in this way, for knowledge of $n$, $e_0$, $e_1$, $x^{e_0}\bmod n$ and $x^{e_1}\bmod n$ allows recovery of $x\bmod n$ when $\gcd(e_0,e_1)=1$, which is not unlikely.


Encrypted query parameters via HMAC I have an unsubscribe link, which needs to be passed a customer id, and a product id, producing a query string something like:

?cid=100&pid=2

I would like to ensure the customer is the one doing the unsubscribing, and that they are unsubscribing from the exact product.  HMAC seems like a logical choice:

?cid=100&pid=2&hmac=<HMAC generated from secret key and cid=100&pid=2>

...and I can validate the HMAC to guarantee authenticity and integrity.

BUT I would also like to keep the customer id and product id confidential if the link is passed around in email, for example.  I can't do that if the HMAC is based off of them.  For example if I just passed the HMAC:

?hmac=<HMAC generated from secret key and cid=100&pid=2>

In this case I cannot not infer the customer id and product id in question (without brute forcing the hash).

Is there a standard way to return encrypted/hashed query parameters?

No, I can't use SSL/TLS.

Not using cryptography on URI:

If you store subscribers on a database, maybe you could also store additional (say) 128-bit random value on some column when there somebody about to unsubscribe. This way there is no meaning for the value beyond this transaction and it cannot e.g. leak anything about the key.

If you cannot use additional data on the database, then use e.g.:

Your favorite AEAD scheme (or Encrypt+HMAC scheme) to encrypt cid+pid pair and to attach authentication tag. Maybe e.g. GCM using 96 bit random IV and 96 bit authentication tag. If there is less than four billion customers and less than four billion product, that would fit in around 256 bits or the same size than (non-truncated) HMAC-SHA256. You may use some variant of base64 to encode the value in URI to 43 characters.

The HTTP standard does not specify how to encrypt or hash parameters. The TLS/SSL is the standard way to apply confidentiality and other security properties.


How to compute the output length of randomized encoding (or garbling)? We consider randomized encoding for circuits as a equivalent primitive as the circuit garbling scheme. However, I have a question arised from their syntax, that is, how to compute the output length of randomized encoding?

From the syntax, the encoding algorithm of randomized encoding takes as input the circuit $C$ and an input $x$ and outputs a randomized encoding $\widetilde{C}(x)$, but the circuit garbling scheme handles the circuit $C$ and input $x$ separately, that is, the circuit garbling algorithm takes as input the circuit $C$ and outputs a garbled circuit $\widetilde{C}$ and a garbling key $K$; the input garbling algorithm takes as input the input value $x$ and the garbling key $K$ and then ouptuts a garbled input $\widetilde{x}$

does it mean $|\widetilde{x}|+|\widetilde{C}| = |\widetilde{C}(x)|$? I know that the online complexity of garbling scheme gives a bound on the size of $\widetilde{x}$, but what is the size of the garbled circuit $\widetilde{C}$? Can we implicitly regard it as $poly(1^\lambda, C)$

The size of the randomized encoding (or garbled circuit) produced by a given construction will be specific to that construction. (Indeed, there are major efficiency improvements to GCs/REs that are still being discovered every year.) So, to answer your (own) question, it would require focusing on a particular construction's details to answer fully.

However -- Yes -- it must be the case that any garbled-circuit / RE that is output by any probabilistic polynomial-time $\mathsf{Garble}$ or $\mathsf{Encode}$ procedure has size at most $\mathsf{poly}(1^\lambda, C).$ For the procedure to output something significantly larger, e.g. exponential in $1^\lambda$ and $|C|$, is impossible (in prob. poly time). Moreover, the typical constructions that come to mind -- e.g. Yao's Garbled Circuits and Applebaum-Ishai-Kushilevitz's randomizing polynomials -- have size approximately $O(\lambda\cdot |C|).$ (It's likely that whatever you're looking at is 'loosely in this range,' though schemes close to the state-of-the-art will have various fine-grained differences..)


Efficient way of generating a random number of N (less than 64) bits with exactly M bits equal to one Would there be an efficient way to implement a function with the following signature:

unsigned long long int random_word(size_t n, size_t m)

that would generate a random machine word (64 bits here) such that exactly m bits over the n least significant ones at set to 1. For example: random_word(10, 3) would generate a 64-bit random number such that 3 bits over the 10 LSBs are set to 1. For a given n and m every possible output should have equal probability (uniform distribution of possible permutations).

If assembly bit twiddling hacks to do that are known, great, if not, I am looking for references and research directions.

I'd guess that you can simply split this into two problems:

create 64 - n random bits, call this R
shuffle n bits where m bits (at any location) are set to 1, call this P

Finally you can simply perform R | P (presuming big endian notation).

Shuffling lists of elements is an operation present in almost any language. If there is any inefficiency it would be in the shuffling algorithm (although Fisher-Yates is optimal, so you'd expect some form of that algorithm, possibly the inefficiency is getting values in a range...).


Construction of secure Elliptic Curve subgroup over a much larger field How can we construct an Elliptic Curve subgroup of cryptographic interest out of an Elliptic Curve over a much larger finite field, including the familiar $\Bbb F_p$ for prime $p$? The Discrete Logarithm Problem and related should conjecturally require $\mathcal O(\sqrt q)$ field operations, where $q$ is the subgroup's order, which must be known.

Motivation: in a signature à la Schnorr, having an analog to Schnorr (sub)groups, but with resistance to NFS and index calculus regardless of choice of $p$; yet still with  parameter $p$ to slightly tune up the cost of field operations, for likely increased security against ASICs and hypothetical quantum computers usable for cryptanalysis, at a given group/signature size.

One way to fulfill that need would be a randomized generation procedure parametrized by bit sizes for $p$ and $q$ (much larger for $p$), yielding primes $p$ and $q$ and the equation of an Elliptic Curve group over field $\Bbb F_p$ having order a multiple of $q$, with some presumption of hardness of the DLP.

I care much more for security for a given size of $q$, and simplicity of implementation on the signature verifier side (where side channels are a non-issue), than on speed, and on ease of making a secure (side-channel resistant) implementation on the side with the private key.

I envision a 192 to 512-bit $q$ for 96 to 256-bit conjectured security (counted in field operations in $\Bbb F_p$), and $p$ several times that size (at least twice).

Hasse's theorem notes that for an elliptic curve over a finite field with $\mathcal{Q}$ elements (which would mean $\mathcal{Q}=p$ for a prime field $\mathbb{F}_p$) that has $N$ points, the following holds:

$|N-(\mathcal{Q}+1)|\le 2 \sqrt{\mathcal{Q}}$

For the sake of illustration, let's take $\mathcal{Q}=p=8191$. This gives us $|N-(8191+1)| \le 2\sqrt{8191}$, leading to this range of possible numbers of points (rounded): $8011 \le N \le 8373$. Since this gives a hard lower and upper bound on the number of points, clearly, a prime-order curve over a large field with the constraint that the order of the curve $q$ is significantly smaller than the field prime $p$ isn't possible.

Thus you need to ignore prime-order curves and instead have a large group $\ell$ and a significantly smaller prime subgroup given by cofactor $h$ on which we operate. The worst case impact of a large cofactor is limited to a speedup of a factor of $\sqrt{h}$ compared to the standard Pollard $\rho$ attack—but that focuses on the large group $\ell$, not the cofactor itself. With $\ell$ being the “cofactor” and the real main group being what normally is considered a cofactor, things seem to get hairy and unclear in their actual impact.

Even if this is an acceptable risk, Igor E. Shparlinksi and Andrew V. Sutherland, Finding Elliptic Curves With a Subgroup of Prescribed Size, 2017 gives you a very dense outline of what an algorithm could look like to find curves with a cofactor in a pre-determined range. Even then, the runtime of the algorithm is painfully slow for sufficiently large $p$ for $\mathbb{F}_p$ (assuming you're in the 2048-bit range for $p$), namely $mp^{1/2+o(1)}$ to the point that it is likely impractical.


DH key exchange with only one end authenticated We know there is a man in the middle vulnerability with unauthenticated DH key establishment. And the way to negate that is to use authenticate the keys used. But what if I only verify the signature of one end. Is there any vulnerability then?

EDIT: To be clear, I am not referring to the fact that the authenticated party does not know who its talking to. I am specifically thinking about a cryptographic vulnerability where someone who does not have control over the machine (of the unauthenticated end) can do some damage.

…what if I only verify the signature of one end?

Bob would not be able to know if he is looking at a signature by Eve, or if it’s a valid signature coming from Alice. In case if Eve is messing with the exchange, Eve would be able to inject her own (as it is handled non-authenticated) and Eve would be able to verify that it’s Bob on the other end (which boils down to “non-deniability”).
Depending on the individual situation, these can be a real neck-breakers.

  Is there any vulnerability then?

Yes! As described above, there is a vulnerability in that case because one authenticated party would be “talking” to an non-authenticated other party… whoever that may be. That’s why authentication is regarded to be so important in the realms of cryptography – to detect if Eve is messing with things.


Randomness Testing of Cryptographic Algorithim I am new to algorithim randomness and confused at I guess a basic level question. Is it common for any cryptographic algorithim to have repetitions in its output i.e.let say 34 and D8 are two consective bytes which are repeting at random intervals.

I have got an encrypted file and it has 34 D8 at line 5 and then same sequence at line 903 and then again at 1002. File has total 1500 lines.

This also goes for other byte sequences. Is there any safe threshold in which there shouldn't be any repetition? I am asking it generally for any good encryption algorithim (AES 256, AES 128, Triple DES etc.)

One of the features of a good encryption is that the cipher text should be indistinguishable from pseudo random. That means that it'll look like output from a good random number generator. Since there are only 256 possible values for any byte, of course they will repeat if you've got 300 million of them.

Repeats tend to occur at the rate of $1 \over 256^n$ where $n$ is the number of bytes within the tuple you're looking for. So you'd expect $L \over 256^n$ number of $n$ length tuples in a randomish file of length $L$.  For example, {6, 6, 6} should occur ~18 times.

  Is there any safe threshold in which there shouldn't be any repetition?

From the above, you must have repetitions otherwise the cipher text wouldn't be very good and it would in no way resemble random.  {6, 6, 6} may not have occurred 18 times (check for yourself with a hex editor).  It may have occurred 20 times. That's random again, and it can vary within expected (but squidgy) bounds.

We can obtain the probability $P$ of a certain sequence occurrence randomly via a chi-squared test. We would view the cipher text as suspicious if $P < 0.01$.  There's a more grown up example of looking for repeat sequences in section 2.7 of NIST's A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. The example there looks for "000000001", resulting in $P$ = 0.344154, which is a pass.

Consider though that this only tests the computational indistinguishability of the cipher text.  We've expect that to be virtually perfect if you've used the correct algorithms/library.  It can't test the inherent security aspects of say, constantly reusing an IV.


Why does a fixed key not make MACs like CBC-MAC or GMAC into secure hash functions? Why does setting the secret key to a fixed, public value not make MACs like CBC-MAC or EMAC into secure unkeyed cryptographic hash functions?

In other words, why is the resulting hash function not 1st pre-image, 2nd pre-image, and collision resistant?

What about HMAC? Still not pre-image and collision resistant?

GMAC, for example, is trivially broken if used as an unkeyed hash algorithm.

GMAC is effectively a series of operations on blocks where you take the previous state, XOR it with the next block, then multiply it in $GF(2^{128})$ by the derived secret subkey $H$.  That is, for data block $A_i$, the next hash value is computed from the previous one as follows:

$X_i = (X_{i-1} \oplus A_i) \cdot H$

$H$ is itself simply the result of encrypting a block of entirely zero bits with the cipher and secret key.  Thus, if the secret key is fixed, $H$ is known to an attacker.

With this design, with $H$ public, preimage attacks are trivial.  Let's say that you have a previous state $X_i$ and want to cause the next state of the hash, $X_{i+1}$, to be equal to $P$, your target hash.  You need to determine $A_{i+1}$ such that:

$P = X_{i+1} = (X_i \oplus A_{i+1}) \cdot H$

Solving for $A_{i+1}$, we get this, with $H^{-1}$ easily computable from $H$:

$A_{i+1} = (P \cdot H^{-1}) \oplus X_i$

Thus, you can arbitrarily control what the next hash value will be, a preimage attack.  If you don't know $H$, though, you can't do this attack.

In short, don't use MACs as general hash functions, even though it happens to work for some MACs (e.g. HMAC).


Security of CFB on a public channel Given a server that broadcasts all received data to all connected peers (except the sender), two participants can have an encrypted conversation using a self-synchronizing method like CFB and some error detection.

How secure is this given that anyone can not only listen but also paste in chosen text into the stream? Is it enough to prepend random padding to make it secure? Anything else that could be done?

There are two possible ways (I can think of) an attacker could mess you up here, but they both stem from very poor design. So I don't know how realistic they are.

Note: the following figure assumes a 64-bit blocksize

CFB is only self synchronizing against insertions/deletions of a specific length. The length is determined by the shift register. If the attacker can insert symbols that don't follow this length, then they can throw everything off in effect causing a DoS. Thus, when designing the system, you have to take into account the # of symbols that can be accidentially or maliciously inserted (deleted). If an attacker can inject down to a single symbol, then you'll have to set $k=1$ in the figure.
Another possible attack came to light in your comment about forcing CFB to behave like ECB. This can happen if you use the same instance of the block cipher to encrypt and decrypt. This is not how I would design the system. I'd use two separate instances of the block cipher, one for encrypting my messages to you and one for decrypting your messages to me. Furthermore, I would use different keys for each direction. If you do it this way, what the attacker injects will only mess up your decryption instance (which thanks to the self-synchronizing nature of the mode, is a problem from which you can recover).


Multi Party System with n-1 adversaries Novice here. Is there a MPC function where no information is leaked even if all parties are not trustworthy ?

Yes there  are. The search term you are looking for is either "dishonest majority" (which doesn't necessarily mean n-1, but often that is the case) or "full-threshold". The SPDZ protocol is one that works in the malicious model that would meet your description.


Which test suit is better to say if PRNG is CSPRNG:TestU01 or NIST? Actually my concern is that I am planning to apply xoshiro256+ for implementation of stream cipher https://prng.di.unimi.it/
for my cryptographic application. It passes the BigCrush tests. Will it provide me the same level of secuirty as any other cryptographically secure PRNG (CSPRNG)?
On the webiste, they claim that xoshiro256+ is a general purpose PRNG and not to be used for cryptography. But I still want to find out how far this PRNG is from being CSPRNG, may be a mathematical expression because my limitation is speed and this seems to be very fast PRNG and remember that it passes BigCrush.
My other question is that NIST statistical test suite https://www.nist.gov/publications/statistical-test-suite-random-and-pseudorandom-number-generators-cryptographic says that if a PRNG passes NIST tests then it is a CSPRNG. So how similar is BigCrush to NIST, again to know how far xoshiro256+ is from being CSPRNG?
P.S: I want to do a theoretical study of this issue as I am not well-versed in statistical testings practically on software.

Please don't.

TestU01 or NIST?

Neither.  Trust what they say on the xoshiro256+ website. A CSPRNG is not defined by it's speed. It's defined by security against predictability, i.e. the next bit test. And that's determined by it's construction.
All that TestU01, NIST's STS and all the others do is check for uniform randomness of output (within a certain degree of confidence). A good PRNG will pass, as will a good CSPRNG. I don't think that a mathematical expression can be formed to enumerate the difference between an invertable PRNG and a non-invertable CSPRNG, other than something derived from $\text{xoshiro256+} \ne \text{CSPRNG}$. See note.
It's as mathematically defining the difference between apples and bananas.

My other question is that NIST statistical tes...

They say that because they are talking specifically from a computer security perspective. That's their raison d'etre. As in the last word of your linked title :-) NIST is not interested in PRNGs.

Note. With hindsight, something may be possible along those lines. Formulae can be written to invert PRNGs. How Brittle Are LCG-Cracking Techniques? discusses this with extensive formulae/code for a simple PRNG.  No complete formulae are (yet) possible for inversion of a CSPRNG. This is a form of mathematical distinction if you will.