Minimizing exchanges for ZK proof of a message with given SHA-256 Consider the problem of proving knowledge of a message $m$ which has a certain public SHA-256 hash $h$, without disclosing $m$ or usable information about it, while minimizing the information exchange (across a bidirectional channel assumed to provide integrity). First restrict to single-block SHA-256 ($m$ less than 448 bits).

Are there firm lower bounds on the necessary information flow in both directions, number of exchanges, and probability $\varepsilon$ of reaching a wrong conclusion?

How far from that are current implementations, perhaps Irene Giacomelli, Jesper Madsen, Claudio Orlandi, ZKBoo: Faster Zero-Knowledge for Boolean Circuits, in proceedings of SEC'2016 ?

Independently, can such proof be non-interactive (becoming a static proof that knowledge of $m$ hashing to $h$ was used in making the proof, with no indication about the proof's origin or freshness)?

The question is motivated by these two.

To answer every part of this question in full details would require almost a book. Here, I’ll attempt to address all sub-questions and give a brief summary together with pointers each time. If you want me to develop some specific aspect, you can ask in the comments. Most of what I will say will not be specific to proving knowledge of a SHA-256 preimage, but follows from general results about zero-knowledge proofs.
EDIT: Bottom Line
Since my answer is long, here is a shorter bottom line:

There exists zero-knowledge proofs of knowledge for arbitrary NP statements (in particular, proving knowledge of a preimage to SHA256) with

Tiny information flow (e.g. 768 bits in total, independently of the size of the statement)
Minimal interaction (single round, assuming a global trusted reference string available to all parties)
"Implementable" concrete efficiency (like, those proofs systems have been implemented, are used, and have reasonable performances on sufficiently simple statements)
Bonus point : these proof systems (typically, SNARKs) have a tiny verifier computation (even shorter than checking that the statement is true given the witness!)

However, these "optimal features" come usually at a cost: high prover computation. The prover cost is often "asymptotically reasonable" (e.g. quasilinear in the size of the circuit checking the statement), but concretely very high (large constants are involved). Therefore, in practice it will most commonly be the case that one will prefer to give up on some of these optimal features, in exchange for a more reasonable prover cost. For example, the NIST candidate post-quantum signature Picnic v2 uses the latest developments in the line of work on ZK proofs from MPC-in-the-head (a line of work to which ZKBoo belongs), which leads to a proof linear in the size of the circuit, but much better computational costs. There are also tradeoffs, like Ligero, with "intermediate" prover costs, and smaller proof sizes on large instances (square root of the circuit size).
Additional Note: this is completely orthogonal to your question, but since you mention explicitly SHA256, you might be interested in knowing that there are important and fruitful lines of work that pursue the opposite direction: building new candidate collision-resistant hash functions (or block ciphers, stream ciphers, etc) which are zero-knowledge-friendly, in the sense that their structure is tailored to some existing zero-knowledge proof systems and seek to optimize the efficiency of proofs for these primitives. Standard examples include LowMC, Rasta, Trivium, Kreyvium, and many others. For example, the Picnic NIST candidate signature scheme is in fact a proof of knowledge of a preimage of a LowMC-based hash function.

Below is the detailed answer to the question.

Are there firm lower bounds on the necessary information flow in both
directions, number of exchanges, and probability $\varepsilon$ of reaching a
wrong conclusion?

This is a deep and vast question. Let me cut it into pieces.

Are there firm lower bounds on the number of exchanges?

What follows should also answer your last question:

Independently, can such proof be non-interactive (becoming a static
proof that knowledge of m hashing to ℎ was used in making the proof,
with no indication about the proof's origin or freshness)?

I gave some partial answer to this question here. The answer changes fundamentally if we assume that the parties are given access to some common reference string (CRS), generated honestly and given to all parties before the start of the protocol, or if we consider zero-knowledge in the plain model (where we do not assume a CRS, or any other trust assumption). Quoting from my answer:
Without a CRS:
« Assuming only one-way functions, we need a superconstant number of rounds to get zero-knowledge proofs for NP. Assuming further the existence of collision-resistant hash functions, we can build five rounds zero-knowledge proofs for NP. This is essentially the best we can hope for: under black-box simulation, a 4-round zero-knowledge proof for NP would collapse the polynomial hierarchy (but there exists some candidate constructions based on exotic assumptions, such as knowledge-of-exponent assumptions or keyless multi-collision resistant hash functions, with non-black-box simulation). Even with non-black-box simulation, a 3-round ZK proof for NP would break indistinguishability obfuscation. Furthermore, 2-round ZK proofs can simply not exist for languages outside BPP. »
With a CRS:
« Every language in NP has a non-interactive (1-round) zero-knowledge proof, under standard assumptions (e.g. factorization). »
Hence, without a CRS, 2 rounds is hopeless and 3 rounds seems very unlikely; with a CRS, one round suffices under standard assumptions.
(cautionary note: for the sake of simplicity I did not distinguished between common reference strings and common random strings; if one wants to delve into the full details of these characterization, this difference matters, but it is not of utter importance for a high level overview).

Are there firm lower bounds on the necessary information flow in both directions?

A trivial lower bound is that to reach soundness error $\varepsilon$, the total length of the prover messages must be at least $\log(1/\varepsilon)$: by the zero-knowledge property, there must exist one sequence of messages that cause the verifier to accept, even when proving a wrong statement (otherwise, we could not simulate), and just guessing this sequence would already contradict the soundness error bound if the total length is less than $\log(1/\varepsilon)$.
In fact, we cannot do much better - because we know zero-knowledge proof with very small information flow. Much, much smaller than the size of the statement itself. More precisely:
Interactive setting:
In the interactive setting, assuming collision resistant hash functions, every length-$n$ statement in NP can be proven in zero-knowledge using only $O(\log n)$ bits of total communication. This is the famous Killian protocol.
Non-interactive setting:
In the non-interactive setting (one round of communication, but we assume a CRS, which is necessary), this is more messy. In the random oracle model, you can apply the Fiat-Shamir heuristic and make Killian’s protocol non-interactive. This gives you a heuristic candidate non-interactive zero-knowledge argument (NIZK) with $O(\log n)$ communication.
But we can do even better!

Assuming a specific and very strong ‘knowledge of exponent’ assumption, there exists a NIZK proof system for any statement in NP, with total communication of 4 group elements - i.e., 1024 bits of total communication for any statement (assuming a 256-bit elliptic curve).

In the generic group model (which gives a heuristic construction in the standard model), we can even go further down, to only three group elements (768 bits).

Can we go even lower? A single element is impossible (in a model that treat the group as a black box). 2 group elements is open, as far as I know.

Eventually, assuming the very strong notion of indistinguishability obfuscation (iO), we can achieve optimally small NIZKs in the designated-verifier setting (where the verifier is allowed to have a secret key to check the proof): under iO, there is a designated-verifier NIZK which achieves soundness $1/2$ with a single bit of communication (hence, by parallel amplification, it achieves soundness error $\varepsilon$ with a communication $\log(1/\varepsilon)$). Since iO is completely inefficient, this construction is only of theoretical interest.

Summary: under strong assumptions and assuming a CRS, we can have both minimal communication and minimal interaction.

How far from that are current implementations?

It depends how computationally efficient you want your system to be - i.e., are you willing to pay for having small communication?

Succinct non-interactive proofs of knowledge (SNARKs), with constant-size proofs, are implemented and available. Here is an example; but since SNARKs are used in important applications, such as the cryptocurrency zcash, there are probably dozen of implementations available. Many should achieve constant size proofs, with 768 or 1024 bits in total.

However, the above solutions will usually be computationally very heavy on the prover side (not even mentioning that it relies on rather extreme assumptions). If you want better computational efficiency, it is common to trade it for proof size, and rely on proof systems with larger proofs (but smaller prover computation). ZKBoo is one possible choice, but it’s not state of the art anymore. The latest result in this line of work is the scheme of Katz et al, which refines ZKBoo and ZKB++ by introducing new techniques to improve the MPC-in-the-head paradigm on which these proof systems rely. The resulting proof is still of size linear in that of the boolean circuit computing the function you care about (in your case, SHA256), but with much smaller constants and a much better soundness error. This result is the basis of the latest version of the Picnic NIST candidate post-quantum signature scheme Picnic v2. This candidate has been fully implemented, optimized, and benchmark, and you should find all the data you want in their detailed specifications.

(Quick note: all the above are described as NIZK, but what they do is in fact constructing an interactive zero-knowledge proof system, and then making it non-interactive and heuristically secure using the Fiat-Shamir heuristic).

There are many other tradeoffs in between SNARKs and Picnic. Here, I could mention dozen of candidates (Aurora, STARKs…). One particularly interesting « middle spot » is Ligero: it achieves proof size $O(\sqrt{|C|})$ ($C$ being the boolean circuit computing SHA256, in the concrete case you consider), at reasonable computational costs. Actually, this protocol was used as the basis for a company providing solutions for decentralized anonymous cryptocurrencies.

Answering questions from the comments

One thing I do not get is which techniques would "just" encode SHA-256 as a boolean-SAT problem, or if (and how and to what degree) it is critical to make use of regularities. Like a lot of XOR, or a lot de 32-bit additions can come for free according to section 5.1 there. This matters because I could come with an approximation of the size fo SHA-256 as 3-SAT, but I do not understand if that's relevant.

Right, theoretical cryptographers have a tendency to forget about the "practical" issue of encoding your instance into the appropriate model the ZK proof is built upon :) But here are some details:

protocols built from the MPC-in-the-head technique (ZKBoo, ZKB++, Picnic, Picnic v2) can essentially benefit from any "MPC-style" optimization. There are way too many variants of MPC protocols to cover every subtlety, but a good rule of thumb is as follow: MPC will deal with boolean circuits, or arithmetic circuits. XORs, or additions, will cost nothing. The default "cost" is the number of ANDs, or multiplications. If your function is well written as a mixture of arithmetic and boolean operations (like, XOR, AND, and addition over $\mathbb{Z}_{32}$), then you can use MPC protocols tailored to evaluate these operations efficiently. But I cannot tell you by default what will be the best choice: that depends on the current MPC literature, and that's hundreds of new papers per year.
If I use the Picnic signature scheme as an example, they use an MPC protocol which works especially well when the circuit is a boolean circuit, with XOR and AND gates, with an arbitrary number of XOR gates but as little AND gates as possible. This is why they replace SHA256 by another hash function, LowMC, chosen to minimize the number of AND gates in its boolean circuit.
SNARKs, which achieve minimal proof sizes, rely on a different representation: quadratic span programs. Hence, to get a SNARK for SHA256, you must first encode SHA256 as a quadratic span program. I do not know how efficiently this can be done, but it has already been done: SHA256 is implemented in libsnark.
Ligero relies on representing the function (e.g. SHA256) as an arithmetic circuit. Then, for each gate of the circuit, a constraint is added to some list of constraint, depending of the gate type, and an "Interactive PCP" is built on top of this representation as a list of constraints. As for ZKBoo and others, they can get a better result by not decomposing the additions over $\mathbb{Z}_{32}$ as XOR and ANDs, but by treating these ring additions as individual constraints directly (see the Ligero paper, page 2100). SHA256 is explicitly used as a benchmark in their paper: they achieve proof size 34kB, prover runtime 140ms, and verifier runtime 62ms.

Answering more globally the first part of your question:

One thing I do not get is which techniques would "just" encode SHA-256 as a boolean-SAT problem, or if (and how and to what degree) it is critical to make use of regularities.

All techniques can "just" encode SHA256 into the right representation (boolean circuit, arithmetic circuit, or quadratic span program). All concrete implementations will try to optimize as much as they can this representation ,e.g. by finding a way to deal directly with the ring operations involved in SHA256. Unfortunately, people do not usually implement the "naive, brainless" representation together with the optimized one, so it is hard to estimate what is the cost of not optimizing the representation. But just to give a very rough sense of it, naively representing SHA256 solely with XOR and ANDs can give a representation up to two orders of magnitude larger than when dealing with the ring additions in a more clever way.


Alphabetic Substitution with Symbols I was reading on a site about the Zodiac Killer and how he used a basic substitution cipher, but instead of substituting english letters and characters he substituted symbols.

I was wondering, if you had a large enough subset of symbols to use for commonly repeating letters like E,T,S ... then by what means could someone decipher the cipher.  This is also referring to the fact that no one has yet to decipher his last message.  Obviously this type of system of cryptography would not withstand in modern computing.

I am more interested in other techniques that could be used, I also found this site '340 Cipher', which includes frequency counts.

If I understand your cipher idea right, you would have a larger ciphertext alphabet than the plaintext alphabet, where each plaintext symbol maps to multiple ciphertext symbols (and the number is dependent on the frequency of the plaintext symbol), one of which is used randomly.

This is known as a Homophonic substitution, and with it the single-symbol frequency analysis usable for simple substitution ciphers is thwarted, since all symbols now have similar frequencies.

But as soon as we start to look at frequencies of letter-pairs (and triplets), we will observe enough structures to break this, too. For example, q is almost always followed by u, and thus the ciphertexts of q will almost always be followed by one of the ciphertexts of u. (I don't know enough about the statistic properties of the English language to give more examples, but you can be sure that an attacker would know.)

Some examples from German:

As in English, q is almost always followed by u.
A c is almost always followed by either k or h.
ei has about same frequency as ie (and i is the only letter who has this property related to e).

Some more details are given in David's answer.

Of course, if the ciphertext is so short (or the translation table so large) that each symbol is only used once or twice (or not at all), cryptanalysis is more difficult (or even impossible).


Can elliptic curve point common factors be detected? Consider the two EC points $X=abG$ and $Y=bG$. Is it possible for someone to examine $X$ and $Y$ to determine if there is a common factor, as long as $a$ and $b$ are randomly chosen numbers between 0 and the size of the finite field? Even if the common factor $b$ cannot be determined, can it be determined if there is, or if there is likely to be a common factor? Assume the ed25519 curve is being used.

Is it possible for someone to examine $X$ and $Y$ to determine if there is a common factor, as long as $a$ and $b$ are randomly chosen numbers between 0 and the size of the finite field?

(Actually, you mean the size of the group)

Technically, the answer is "yes, it is easy to determine that".  The easiest subcase is if $G$ (and hence $X$ and $Y$) belong to the large prime subgroup of x25519; then the rule is "unless Y is the point-at-infinity and X is not, the answer is "yes".

That is, there will always be an $a$ such that $X = aY$.

It's a little trickier if $G$ generates a larger subgroup, but it is still easy (it might take a little computation on the attacker's part).

Of course, the fact that it's always true (whether or not you consciously generated such a relationship between $X$ and $Y$) means that the attacker can't deduce anything from that information.


How to implement "online" feature of GCM? I've heard that Galois Counter Mode (GCM) is an "online" encryption algorithm—it is not necessary to know the size of the input ahead of time.  But does GCM require that all authenticated-but-not-encrypted data ("adata") be provided to the algorithm before processing the data to be encrypted?

If there is no ordering requirement, how can an implementation combine the two independently-calculated sides into a single GHASH result?  My guess is that if it is possible, it involves rearranging the GHASH results into a polynomial.

I wasn't able to find anything on this with some searches on here and Google.

As you suspect, it's possible to rearrange the GHASH computation so that can compute both the AAD and the encrypted data online and independently.

As you recall, GHASH is defined as:

$$\mathrm{GHASH}( \{a_{i-1}, a_{i-2}, ..., a_0 \}, \{ p_{j-1}, p_{j-2}, ..., p_0 \} ) = \\ a_{i-1} H^{i+j+1} + a_{i-2} H^{i+j} + ... + a_0 H^{j+2} + \\p_{j-1} H^{j+1} + p_{j-2} H^{j-1} + ... + p_0 H^2 + C H$$

where $\{a_{i-1}, a_{i-2}, ..., a_0 \}$ is the AAD, and $\{ p_{j-1}, p_{j-2}, ..., p_0 \}$ is the plaintext, and $C$ is a block containing the lengths of the AAD and the plaintext.

We can rearrange this into:

$$(a_{i-1} H^{i-1} + a_{i-2} H^{i-2} + ... + a_0 H^{0}) \cdot H^{j+2} + \\(p_{j-1} H^{j-1} + p_{j-2} H^{j-2} + ... + p_0 H^0) \cdot H^2 + CH$$

We can online compute $\Sigma a_i H^i$ and $\Sigma p_i H^i$, and so you are iteratively computing $\Sigma p_i H^i$, you also compute $H^{j+2}$.  Once we have those collected, compute:

$$\mathrm{GHASH} = (\Sigma a_i H^i) H^{j+2} + (\Sigma p_i H^i) H^2 + CH$$


Can minimum encrypted message length be used to identify public key algorithm or derived some of its features? Encrypting a very small message using public key cryptography always result in larger encrypted messages. Is it possible to deduce the algorithm used, key length, etc just by looking at the minimum encrypted message length?

More specifically, if I have black box system and when I input a small number of characters to encrypt I get the encrypted version back. Can I deduce anything about the algorithm in the black box using the encrypted message length?

For the most common public key encryption mechanisms such as RSA PKCS#1 encryption mechanism, it is indeed possible to deduce the key length from encrypted length.

In addition to encrypted length, you may want to look at encrypted data. In case of RSA observing encrypted data will reveal e.g. modulus, i.e. basically the public key.

This is generally the case with public key encryption: observing encrypted messages eventually allow to learn the public key.

It is not usually not possible to detect what one of of PKCS#1 paddings was used. However, occasionally, the encrypted message is encapsulated so that it conveys more information on the message. Have you been able to examine encrypted bytes produced by the device, to check if there are e.g. some DER encoded header or other additional information?


Choice of bilinear group for implementation of BLS signature with NIWI proof? I am trying to sign the multiple (millions of) different readings but the receiver should not be able to link multiple signed readings together (unlinkability) or with the identity of the signer (anonymity).

As a potential solution, the sender sends the reading $m$ along with non-interactive witness indistinguishable (NIWI) proof of knowledge (PoK) of signature on $m$. I am looking at certified signature scheme where CA certifies the public keys of legitimate signers. The signer signs the reading $m$, generate NIWI proof of knowledge of his/her signature on the reading $m$ and sends ($m$ and the NIWI proof) to the receiver. I want to use BLS signatures as the signature is one element in $G_1$ (and the signature size can be as short as 161 bits). BLS signature scheme uses gap Diffie-Hellman (co-GDH) groups $(G_1,G_2)$ of prime order $p$, where co-DDH is easy but co-CDH is hard.

Now, in order to construct proof of knowledge of BLS signature, I want to use the Groth and Sahai's NIWI proof in Efficient Noninteractive Proof Systems for Bilinear Groups which can be constructed based on one of the three assumptions:

sub-group assumption
SXDH assumption
DLIN assumption.

I am confused, which assumption can I make for generating NIWI PoK of BLS signature?

Q1. Can I use SXDH assumption based NIWI PoK i.e. is it valid to simultaneously make co-GDH and SXDH assumptions on the group pair $(G_1,G_2)$?

Q2. DLIN based NIWI proof will require me use symmetric pairings for BLS signatures. Is symmetric setting suitable for secure and short BLS signatures?

Q3. Can I use subgroup assumption for NIWI PoK of BLS signature? as $|G_1|=|G_2|= p$.

If you want to try a scheme that is already being used in the industry, you may try EPID.

A paper describing it is on IACR eprint 2009-095.


What is the shortest type of text encryption? I have the following text that I want to encrypt with a password:

"This is my secret password: 1234567890"

encrypted with AES:

SgAHzFc3vluxLqZuzZKg8dzhy918N41SUU1BfBXN8CoEDfVJ0R9hox8PT2jKYA==

pass: 12345

When I encrypt this with a password using AES, the encrypted string is 64 characters.

Is there another type of encryption that is less than 64 characters? Or maybe there is an encryption that also compresses the encrypted string?

You don't say what mode of operation you are using with AES. The mode of operation can have a big impact on the ciphertext expansion. There are streaming modes, such as CTR, for which the ciphertext will be the same size as the plaintext. For these modes (an pretty much any mode you would want to use in practice) you will also have to transmit a nonce or IV in addition to the ciphertext.

One thing you should be aware of is that modes like CTR are malleable, which is a huge security issues. So, I highly recommend you use authenticated encryption so that you don't have these security issues. This could be done by computing an HMAC over the ciphertext or using an authenticated mode.


How to distribute system parameters in identity-based encryption Identity-based encryption papers describe that system parameters are declared as public. However,in real scenario, how to distribute system parameters to users?

Public parameters (or system parameters as you call them) can be distributed however you want. Papers which introduce Identity-based Encryption schemes usually only present the scheme and not how it can be applied in the real world 1. The public parameters in IBE can be compared to the pre-shared data in the Diffie-Hellman key exchange protocol where both parties have to agree on a shared modulus and generator before starting the protocol. There are different ways to distribute such data. Here are two:

Bake (put into the application code) the public parameters into the application, so that every client has the same parameters and don't need additional trust negotiations. This will be a trust root.
Query the public parameters from some other party in a secure manner (signed and not necessarily encrypted). Each client has to have some trust root (certificate of the third party) for this to work.

1 If you see a commercial product which uses IBE/HIBE/ABE/PE/HVE/FE, please write a comment.


Message space of substitution cipher I know that the message space is the set of all possible messages, but I'm not sure how to generally define it, rather than for a specific cipher. For example, I've seen $$\{\forall c \in A\}$$, where "$A$" is the set of characters being used.
But I think there should be a superscript at the end to denote the length. Would this be correct?

How to generally define it

Modern applied cryptography usually defines the (unbounded) message space as:
$$\mathcal M=\{0,1\}^*$$
where the star denotes you can have arbitrary lengths. Formally, $A^*:=\bigcup_{n\geq0}A^n, A^0=\varepsilon,A^{n+1}=A^n\cdot A,n\in\mathbb N$ where $\cdot$ denotes concatenation.

If you ask somebody who's really into the theory of programming languages, they're gonna basically say you the same, but will probably replace the $\{0,1\}$ with an arbitrary alphabet $A$.

Now to the formula you asked about:
$$\{\forall c\in A\}$$

This is not only syntactically wrong (a quantor always needs an accompanying statement), but also makes no sense at all. After all, you're saying that "the set consisting of 'for all c in A' " which is at most a set of syntactically wrong logical formulae. However if we were to leave the $\forall$ away, you basically wouldn't have gained anything over a plain use of $A$, as the set consisting of all elements in A basically is just A.
If $A$ is assumed to be an alphabet, you'd indeed need a length qualifier, something like the star in the above notation or a concrete instance where you'd fix the length to some (arbitrary) value $n$.


Identify the cryptosystem where $\ m = c^2 \bmod n$? I came across with cryptosystem whose decryption method is: $\ m = c^2 \bmod n $. It's exact opposite of Rabin's, where's the same formula is used for encryption.

What is the name of this cryptosystem?
How does the encryption function in this system work?

I doubt this is an encryption scheme, except in the limited sense of that in code obfuscation. If indeed this is the decryption part of an encryption scheme, that's a very weak one: it is a symmetric encryption scheme which decryption key is $n$, and two distinct plaintext/ciphertext pairs are typically enough to recover that key. Often $n=\gcd({c_0}^2-m_0,{c_1}^2-m_1)$ (though sometime, pulling out small factors or a third pair is necessary).

This cryptosystem seems to be a simplified variant of Rabin signature. As any signature scheme, it aims at integrity and proof of origin of the message, not at protecting the confidentiality of the message.

Like in RSA, security relies on the difficulty of factoring $n$, which distinct prime factors $p$ and $q$ are the secret key. $m$ is the message to sign, assumed to have internal redundancy. Or better (true Rabin signature) $m$ is a full-domain hash of the message. Further, somewhat $m$ has to be made a square modulo $n$ (or equivalently, modulo $p$ and modulo $q$). $c$ is the signature. Schematically, verification is computing $c^2\bmod n$, and comparing it against $m$. Calling that decryption (as the question does) is an error in terminology.

There are several methods for generating $p$ and $q$; then for adjusting $m$, computing $c$ (which is signing, not encrypting), and checking $m$ against the result. One is described in algorithms 11.29 and 11.30 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography. Be sure to ignore the section 11.3.5 (which describes ISO/IEC 9796(-1) padding, dated and insecure).

If the rationale is that making a cryptogram $c$ leading to an $m$ that makes sense is hard without the factorization of $n$, again that's not a cipher or encryption, and $m\gets c^2\bmod n$ is not decryption. The proper name is Rabin signature with total message recovery, and $m\gets c^2\bmod n$ is signature verification and message recovery (and lacking validation of redundancy in $m$). This is standardized by ISO/IEC 9796-2 (with proper padding) including with exponent $2$.


Is SZK better than CZK? Is it better to have statistical zero-knowledge or computational zero-
knowledge in a system?

If it depends, is there a slightly accurate generalisation that can be made?

Maybe one can be somewhat reduced to the other (doubt it)?

Maybe one of them solves a larger class of problems?

Security-wise having statistical security is always better than computational security if the security parameter is equal. This is because statistical security ($\forall A: Pr[A(f(x)) = x] \le negl(n)$) implies computational security ($\forall B: Pr[B(f(x)) = x] \le negl(n)$) with B all algorithms in P-SPACE and A being all algorithms (which includes all algorithms in B).

However, there is a catch. In practice the security parameters differ by a large amount. While one can argue by just using the same security parameters for statiscial security and computational security, it's still a problem. This is because statistically secure functions usually use smaller security parameters compared to computationally secure functions in practice to reduce computation time and space since they aim different targets; and most statistically secure protocols are usually not designed to be used as functions with computational security (but it's not impossible doing so either; the Fiat-Shamir transformation is one example since it can transform interactive zero-knowledge proofs with statistical security into non-interactive proofs with computationally security secure in the Random Oracle Model).

Typically you want to archive different targets with statistical security and computationally security:

Statistical secure functions are usually used in interactive settings which are repeated fixed times. For example, think about lotteries. If one could repeat a lottery unlimited times for free at any time, everyone would be winning. But in reality you can participate in a lottery only once per week and you need to pay per participation.
Computational security functions usually deals with algorithms which try to extract a secret x out of the information y (and have some additional power I skip here). The adversary is allowed to use any stragegy he wants, but is limited to the time and space. Because the problem is that 'hard' (being in NP) the adversary still is unlikely to be successfull, unless he is very lucky.

In the protocols which implement secure functionality computational security and statistical security are differentiated if both are needed since the security parameters do differ in practice.


How does Flatten really make the coefficients of a vector matrix small in LWE In Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based, Gentry et. al defined Flattening as follows;

Let $\vec{a},\vec{b}$ be vectors of some dimention $k$ over
$\mathbb{Z}_q$. Let $\ell = \lfloor \log_2q \rfloor +1$ and $N = k
 \cdot \ell$
Define $\operatorname{BitDecomp}(\vec{a})$ be the $N$-dimentional
vector $ = (a_{1,0},\ldots,a_{1,\ell-1} \ldots,a_{k,0},\ldots,a_{k,\ell-1})$, where $a_{i,j}$ is the $j$-th
bit in the $a_i$'s binary representation, bit ordered least
significant to most significant.
For $\vec{a}' = (a_{1,0},\ldots,a_{1,\ell-1},  \ldots,a_{k,0},\ldots,a_{k,\ell-1})$, let
$$\operatorname{BitDecomp}^{-1}(\vec{a}) = (\sum 2^j\cdot a_{1,j},
 \ldots, \sum 2^j\cdot a_{k,j}) $$ be the inverse of
$\operatorname{BitDecomp}$, but well defined when the input is not a
$0/1$ vector.

This is nothing but usual decomposition into bits and the data has already stored in the decomposed way.

For $N$-dimensional vector $\vec{a}'$, let $\operatorname{Flatten}(\vec{a}') = \operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1} (\vec{a}'))$.
When $A$ is a matrix, let $\operatorname{BitDecomp}(A), \operatorname{BitDecomp}^-1(A)$, or $\operatorname{Flatten}(A)$ be matrix formed by applying the operation to each row of $A$ seperately.
An interesting feature of $\operatorname{Flatten}$ is that it makes the coefficients of a vector matrix $small$ without affecting its product with $\operatorname{Powersof2}(\vec{b})$, and without knowing of $\vec{b}'$

It is not clear for me how the $\operatorname{Flatten}$ makes the coefficients of a vector matrix $\boldsymbol{small}$. What I see that the two operations, $\operatorname{BitDecomp}$ and $\operatorname{BitDecomp}$, are just the inverse of each other. Could someone elaborate on what I'm missing here?

The important part you missed is the last sentence of the first block:

$BitDecdomp^{-1}$ is still well-defined, if it doesn't get a $N$-dimensional bit vector (all entries from $\{0,1\}$).

In the second quote,  $Flatten$ is defined as first using $BitDecdomp^{-1}$, and then use $BitDecomp$. So the output of $Flatten$ will be a bit-vector. This will be the same as the input only if that input was also a vector from $\{0,1\}$ - but it is defined for any vector over $\mathbb{Z}_q$.

The basic idea here is to use a continuation from a smaller domain to a larger one.


Information leakage in real-time voice encryption I saw some time ago a post discussing the issues surrounding encryption of speech/voice in VoIP and how it can leak information (can't find it now). Can someone provide an insight into some of the issues and how to mitigate them if one wants to use symmetric encryption to encrypt voice between two devices? Is asymmetric encryption possible (give the processing time required)?

I'm not sure which post you're referring to, but one possible source of leakage results from using a variable-bit rate codec. If different sounds compress at different rates, than this will be reflected in the lengths of outgoing encrypted packets. By examining those sequences of lengths, it can sometimes be possible to accurately guess what phrases are being uttered.

See "Spot me if you can: Uncovering spoken phrases in encrypted VoIP conversations" by Wright, et al. This extends an earlier work, Language identification of encrypted VoIP traffic, in which the authors showed they could classify a speaker's language, encryption notwithstanding.

Padding the ciphertext packets, to, say, the nearest multiple of 128 or 256 bits can greatly reduce the ability of an attacker to make this type of attack. I would assume that using a non-variable bit rate codec would also work. Of course, there's a trade-off with bandwidth here; you'd have to weigh that against the security risks.

I strongly suspect assymetric crypto is not fast enough for the job. Typically, it's just used to establish a secure, authenticated channel so that users can agree on a symmetric key, which is used to encrypt the actual traffic.

Performing type of attack---looking at lengths, timings, etc. to infer information about content---is called traffic analysis.


Security implications of using a high entropy password with a low iteration count for a key derivation function This question is related to my other question, but also this entropy calculation question as well as this article about PBKDF2. It may also be considered as a duplicate of this question, although in our current case the password's entropy isn't as high.

If a low iteration count is used, it can allow for fast brute-forcing, but what if the entropy of the password is high enough (50 bits? 100bits? more?)? Would it still matter this much?

Would there even be a way of determining a minimum entropy?
A limited charset like "0123456789ABCD" would surely hinder reaching high levels of entropy, but given a long enough length, it's rather hard for me to guess if it could still be considered safe or not.

If a low iteration count is used, it can allow for fast brute-forcing, but what if the entropy of the password is high enough (50 bits? 100bits? more?)? Would it still matter this much?

If the entropy of the process used to choose the password is high enough, then it doesn't matter how cheaply an attacker can test a guess for what the password might be.  Provided the hash is uniquely salted for each user, if your password selection process has 128 bits of entropy, nobody will ever guess the password.  (The story is more complicated if the hash is not salted, but suffice it to say that 256 bits of entropy is enough.)

  Would there even be a way of determining a minimum entropy?

Study the process, not any particular password.  For example, if your process is that you roll a d6 enough times to draw a ten-word diceware password from a 7776-word list, this process has 128 bits of entropy.

  A limited charset like "0123456789ABCD" would surely hinder reaching high levels of entropy, but given a long enough length, it's rather hard for me to guess if it could still be considered safe or not.

From a 14-character alphabet like that, if you choose each character independently and uniformly at random, to attain 128 bits of entropy it suffices to use $\lceil\log_{14} 2^{128}\rceil = \lceil128\log 2/\!\log 14\rceil = 34$ characters.  (For 256 bits of entropy, 68 characters.)


RSA and difference between factors As I understand, for RSA $n = p \cdot q$. For the key to be safe enough from getting factored, $p$ and $q$ have to be far from each other. How far do they have to be? For example, if I have two $1024$-bit primes that both start with a 1 and the difference between them $(p-q)$ is ~$1022$-$1023$ bits, is that good enough?

Yes, it is good enough. In the case of random primes the distance as large as the numbers with high probability.

With the recommended key-size ($2048$-bit) one only needs to generate two random primes of the right size ($1024$-bits each). This is generally done throwing a random number of $1024$ bits, forcing the first one and the last one bits equals to 1 (the Most significant bit is equal to 1 to guarantee the right size and the Less significant bit is equal to one to get an odd number) and check the primality of this integer. Sometimes the second most significant bit is set to 1, too. As  fgrieu explained in his comment mandating that the second highest-order bit of $p$ and $q$ is set insure that $N=pq$ has exactly as many bits as the sum of the numbers of bits in $p$ and in $q$, because $(\frac{3}{4})^2>\frac 1 2$. That's not quite the way ANSI X9.31 and derivatives (including FIPS 186-4) RSA key generation methods do this; they tend to prescribe $2^{(n−1)/2}<p<2^{n/2}; 2^{(n−1)/2}<q<2^{n/2}$; and (w.r.t. Fermat/Lehman factorization) $|p–q|>2^{n/2–100}$ where $n$ is the number of bits in $N=pq$, with $n$ multiple of $2^6$ or some higher power of two.


Extract data from certificate I wrote application client-server. Now I would like to add safe connection.

First

When client connect to server - server send certificate in *.crt file.

Now I want to extract from this file the public key and validate certificate - check it is safe.

I use Lazarus/Delphi/Free Pascal

Can you tell me how can I extract from this file public key ready for use in hexadecimal (byte) format?

I know that in this file is $p$, $q$ and rest but I want final public key ready to use.

Maybe if not in my programming language then I can do this on my computer? Linxu, Windows?

How can I do this with private key? I have key in file with header:

-----BEGIN RSA PRIVATE KEY-----

It is very easy to do this with openssl.

Say foo.crt is your crt file. Then,

$ openssl x509 -in foo.crt -text -noout

will print all the necessary information (issuer, pkey : modulus rsa and exponent, signature algorithm etc) in text format.

If you  give

$ openssl x509 -in foo.crt -text -noout > foo.txt

you will save the previous information to foo.txt file.

To answer your question

  Can you tell me how can I extract from this file public key ready for
  use in hexadecimal (byte) format?

one way to do this is first export the public key and then convert it to  hex form

  $ openssl x509 -in foo.crt  -noout -pubkey > foo-public
  $ openssl rsa -noout -text  -in foo-public -pubin > foo-public-hex

Now foo-public-hex contains your pkey in hex format.

Then you wrote

  I know that in this file is p, q and rest but I want final public key
  ready to use.

I am not sure I follow you...
the private key is not in the .crt file but in .key file and server wont sent it to the client.

If foo.key is you private key  then giving

$openssl rsa -noout -text  -in foo.key

you will see the private exponent and the primes p,q in hex form.


When to use /dev/random over /dev/urandom in Linux In my response to my question "what does the letter 'u' mean in /dev/urandom?" the myths about /dev/urandom
page was posted in two comments and an answer.

The myths about /dev/urandom page is trying to steer people heavily into using /dev/urandom over dev/random.

This guy knows more than I do, so it would be easy for me to nod and accept, but I'd like to post it here so that other people who also know more than I do could comment.

What irks me about myths about /dev/urandom is that:

The two devices still have a differing behaviour depending on the size of the entropy pool
There are no use cases given where /dev/random is the better choice (which seems unbalanced)

I note that cryptsetup has an option --use-random:

  NOTES ON RANDOM NUMBER GENERATORS

  Using /dev/random on  a  system  without  enough
         entropy  sources  can  cause  luksFormat  to  block until the requested
         amount of random data is gathered. In a low-entropy situation (embedded
         system), this can take a very long time and potentially forever. At the
         same time, using /dev/urandom in a low-entropy situation  will  produce
         low-quality  keys.  This is a serious problem, but solving it is out of
         scope for a mere man-page.  See urandom(4) for more information.

So my question is:

In which practical situations would one want to use /dev/random in preference to /dev/urandom, and why?

In which practical situations would one want to use /dev/random in preference to /dev/urandom, and why?

Basically none on a typical desktop or server system. Assuming the PRNG produces cryptographically secure random numbers, there is no reason to use /dev/random instead.

There are a couple of corner cases, however:

You use the random numbers for a one-time pad. In that case if you wanted information theoretic security you should not use pseudorandom numbers. (No real reason to do that in my opinion.)
Early boot on a very low entropy device. The /dev/urandom device cannot guarantee that it has received enough initial entropy, while when using /dev/random that is guaranteed (even if it may block). However, in this case you could use the newer getrandom interface (man page) instead.

Running cryptsetup on first boot of an embedded device is the kind of thing where you would need to consider your options. (Modern desktop and server CPUs tend to include hardware random number generators which are used to seed /dev/urandom.)

There is some work underway to make /dev/urandom block when initial entropy is insufficient, but it may not be possible due to programs which assume it will never block. (See e.g. this LKML thread.)


Can someone give me an example of a Merkle–Damgård transformation? I started reading "Bitcoin and Cryptocurrency Technologies - Princeton University" (coursera) and in the first chapter it talks about Merkle–Damgård transformations for SHA-256. I was trying to understand it by working out an example, but I keep getting problems.

Here is my work:

Take a compression function that takes inputs of 4-bits and outputs 2-bits
For our hash function we create an arbitrary input of 6-bits
Since input-output = # of blocks, the 6-bit input should be divided into two blocks, each with the 3-bits
Now from my understanding the initialization vector should be 1-bit because 3-bits+1-bit = 4-bits which is the input the compression function takes
Now the output of the first pass is 2-bits, which is a problem because if I add on the other 3-bits, the total is 5 and the compression function only takes in 4-bits. What am I doing wrong?

If someone can help explain where I am messing up or explain the idea in a different way, with an example, I will greatly appreciate it.

You get it wrong when saying

  Since input-output = # of blocks, the 6-bit input should be divided into two blocks, each with the 3-bits

because you have a

  …compression function that takes inputs of 4-bits and outputs 2-bits

You don't split the message in half and then fiddle with some initialisation factor to make all pieces fit. That's not how it works.

Instead, if the bits you feed to the compression function are too many, you split them up in according pieces; in your example 4 bit inputs. If you end up with the final piece not being 4 bits, you pad it with the number of missing bits so that you can again feed the expected 4-bit length to the compression function.

So, you would feed those 6 bits into your compression function like this:

You take the first 4 bits of the message, which you feed to the compression function.
Next, you take the remaining 2 bits of the message, followed by 2 bits of padding to fill it up to 4 bits so that you can again feed 4 bits to the compression function-

Simplified example: Let your message be 6 bits 111111, the padding be 0, and the compression function takes a 4-bit length input. You first feed 1111 to the compression function, finally, you feed 1100 (notice the two padding bits) to the compression function.

Same example using bit positions: Let your message be 6 bits at positions 654321, the padding be 0, and the compression function takes a 4-bit length input. You first feed 6543 to the compression function, finally you feed 2100 to the compression function.

As you can see, the initialization vector is rather irrelevant at this stage where you're feeding the message to the compression function. All that's done is splitting up your message into appropriately sized pieces, and using padding at the end (final block) to fill up what's missing.

Nota Bene: You only asked about a specific part of SHA-256, but I nevertheless would like to point out that (when talking about SHA-256 and alike cryptographically secure hashes) the final block doesn't only contain padding but also includes the length of the input message to avoid length extension attacks. In case the message happens to fit the compression function input length and/or doesn't leave enough room to append the input message length, an additional piece (containing nothing but padding | length of the input message) is fed to the compression function.

If this last note confuses you, you might want to check the “Length padding example” at Wikipedia’s article about the “Merkle–Damgård construction”, or maybe even read the complete article offered there as it practically covers all points mentioned here… and more.


Are there any Implementations of Secure Indexes? There are several papers about Secure Indexes, for Example "Searchable Symmetric Encryption:
Improved Definitions and Efficient Constructions" and "Secure Indexes".

I'm trying to build a system, that uses secure indexes to store and search data. Are there any existing solutions out there which implement these types of schemes?

Cryptdb has a search component which implements techniques from this paper this might be helpful to get some insights and get started , cryptdb is open sourced code is available


Secure Communication Focus:
I have to design a secure keep alive communication protocol and was wondering if it was necessary to sign the ciphertext after the session key has been generated as an attacker will not know the key.

Protocol Overview:

Both the client and server have a copy of their respective public keys.
Generate session key using ECDH. Parameters will be signed and sent to both parties.
Further communication encrypted with AES in GCM mode. IV and Tag are appended to the ciphertext and sent to the other party.

Side Note:
How can I introduce forward secrecy?

I ... was wondering if it was necessary to sign the ciphertext

No, there is no need to sign the ciphertext. The secret key is already derived by the key agreement protocol, and that is secure because you verified the parameters (which, I presume, includes the ephemeral public key of each party).

At this point you just have to verify that each party does indeed have the same shared secret. One way to do this is to verify a GCM encrypted message.

The problems with that are that:

you need to send a message (which could take some time after you've agreed upon a key) and
you're now mixing up entity authentication and message authentication.

Part 2 is a major pain in the back for developers and maintainers as they will have to mix concepts. For instance, what will you log if the first message fails? Was it data corruption for the - often much larger - authenticated message or was it a failure to establish the session in the first place?

So you're probably better off sending a MAC specific to entity authentication to the other party as soon as the shared secret is established, preferably using a different derived authentication key. You can use a KDF to e.g. establish an authentication key and message encryption key for that purpose.

The first MAC can be send with the ephemeral public key that is exchanged last; at that point one party already has the other party's public key and can establish the shared secret after all. Unfortunately it may cost you an additional message if the other party needs to be authenticated quickly. Of course there are solutions to that as well, but yeah...

  How can I introduce forward secrecy?

If you used ephemeral (EC)DH key pairs for both parties to establish the session keys then you already have obtained forward secrecy. Of course this assumes that you destroy the ephemeral private keys asap after establishing the session keys.

Note that sessions are not immune to attack where the private keys are found e.g. by quantum computers in the future. Forward secrecy is not a panacea (which is why I generally stick with "forward secrecy" rather than "perfect forward secrecy" even though the "perfect" part isn't related to breaking the key agreement algorithm).


Time Based encryption Looking for the language to describe a solution I am looking for...

As a systems admin for an educational institution, I would like to:
a) post our tests in an encrypted form
b) at a certain time, make the contents available to the user (online or not)
c) after a certain time, re-encrypt the file, and/or delete the content.

During the unencrypted time, I would like to prevent copy operations, cut/paste etc. to protect the content...

Is this "mission impossible" type encryption style even possible to protect our content?

If so, what would it be called?

Many thanks for your assistance

"Impossible" might be appropriate.  And "Not really a cryptography issue." Summing up Artjom's and Geoffroy's comments, nothing can stop you pointing a camera at the screen. Or perhaps taking a screen grab. There is the notion of an Analogue Hole, which means that ultimately if you can see it, you can record it.

But that's not really necessary.  Virtually all mainstream content transmission protocols have been cracked directly via interception software or accessing a master key.  You can easily record directly from the BBC, PornHub and YouTube as simple examples.  These services have huge incentive to prevent unauthorised copying and can't, so it's unlikely a school can succeed where major global players can't. This all becomes much easier on Linux powered devices where you have total control over the kernel. Linux also comes by default with the ability to record anything playing on the sound card, so audio protection is non existent on that platform. And text can be spoken by   a screen reader, which can then be recorded via the sound card feature above. Then speech recognition $ \rightarrow $ text and so on and on.

Clearly you can release encrypted content, then either repost the plain text or the key to allow users to decrypt.  But then you've lost all control of the data.  It's out.  Re-encrypting will just create a copy of the files you already had before decryption.  The decrypted content may have been copied off machine.  USB stick perhaps.  The whole of the political European Union wants content to be able to be deleted for ever, but they haven't achieved it yet.  Perhaps  General Data Protection Regulation might work, but I doubt it.  And a server restore can bring it all back, and this has   happened as you   hear it in the news occasionally.

Another comment provides us with a fine example of irony - Google's attempt at self destructing emails.  I'm assuming that this is exactly the kind of copy protection that you're looking for. The irony is found in the mere existence of the following screen grab of   such a test email featuring a clear expiry date. Assume it expired yesterday:-

So what? Not only has it been screen grabbed and made immutable, I've just reposted it here. So the irony is further exacerbated in that whilst the email might disappear off the Gmail system in a puff of smoke, Googlebot has already indexed this answer and made it available on the Google search engine!  And as the email text is a nice clear modern machine font, OCR techniques allow for it to be extracted automatically from image format to text. This is a perfect measure of the size of the Analogue Hole and how even a billion dollar company cannot fill it in.

There's my answer here to "Can a device prove the identity of its own code?"   which really asks if a voting machine can be hacked, even with specialist hardware protection.  You're asking almost the same question, regarding a computer displaying some content. Yes it can be.


DH with AES - is that an acceptable security scheme over UPnP? I'm trying to devise a good security scheme to protect comms over Wi-Fi.

Right now, I have 2 devices that already communicate via UPnP but I need to secure this communication. I've come up with this:

Once the client sees the other host, picks a pair of Diffie-Hellman parameters (out of 1000 pregenerated pairs of $g$ and $p$) and enacts a DH key agreement with the host. This happens each time both devices want to initiate a session, and auth persistence is not needed (generated keys are discarded after the session finishes).
Once both devices have calculated the same secret, this secret is hashed with SHA-256 to create a common key.
When the client wants to send a message to the host, it encrypts it with AES-CBC-PKCS#7, using the key, it appends the generated IV and sends it to the host. The host's response follows the same method.

Whoever observes a session can only see $g$, $p$, $A$, $B$, the ciphertexts and their corresponding $IV$s.

Is this secure enough?

P.D.: I'm under the impression that trying to use TLS is way too much for such a simple need and it would be too complicated to get out in a reasonable timeframe.

No. First, you've exposed a padding oracle by using unauthenticated AES. Secondly, you've not authenticated the devices: it's easy to mount a man in the middle attack. Thirdly, I don't understand the role of changing parameters all the time in your protocol.


Is it feasible to build an index of prime factors? Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing prime keys up to $2^{2048}$?

I understand this would take an immense amount of time to do, but it would only be done once. Obviously, computing such an index would take a considerable amount of time and would have to be done with someone having the right amount of resource. Given the public key, you would be able to look up what the two primes are, and hence retrieve the private key instantly.

Breaking an 256 AES would then be easier, as AES keys are often generated using the RSA private key.

Would it be possible to build such an index? How long would that take in permutations and perhaps with the fastest computer in the world?

Let's assume for an instant that you could build a large table of all primes. Then... what ? How would you use it ? What would you look up ?

If you "just" scan the table and try to divide the number to factor by each prime, then this is known as trial division; there is no need to store the primes (they can be regenerated on-the-fly; that's the division which is expensive). Yet this is an highly inefficient factorization algorithm. We know much better factorization algorithms (which nonetheless utterly fail at making the slightest scratch on the surface of a 2048-bit RSA modulus).

Of course, the list of 1024-bit primes is so large that storing it, or even simply generating each prime, is ludicrously infeasible. There are about $2^{1014}$ such primes; that's close to  $10^{308}$. Suppose you are an omnipotent but severely bored deity, and you decide to store these primes, using a storage device which uses the size of an hydrogen atom for each prime (we, as humans, can certainly not store that much information in so small a space, but hey, that's a piece of cake for an omnipotent God). The known universe has an approximate volume of $10^{79}$ m3. The volume of an hydrogen atom is close to $10^{-30}$ m3. So our eccentric divinity can pack about $10^{109}$ values in the whole Universe. He would still need $10^{199}$ complete Universes to store them all. $10^{199}$ is a mind-boggling number (if your mind is not boggled by it, then it must already be much more boggled by something else). It is ten billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions. In other words, a lot. And we are still talking about complete Universes packed with atom-sized integers.


Homomorphic encryption of logical OR/AND Are there any ways to perform homomorphic encryption of logical OR (or logical AND) without using fully homomorphic encryption?

One practical (if not theoretically satisfying) way would be to use Pallier, with the mapping "any encrypted nonzero value is an encrypted TRUE; any encrypted zero value is an encrypted FALSE".  To encrypt a TRUE value, you pick a random value and encrypt that, and the logical OR operation is the standard Pallier homomorphic addition.

Now, obviously, the OR of two TRUE values has a tiny probability of becoming FALSE; however it is far more likely that your computer is hit by a meteor...


Crypto AES for authentication Is it secure to use authentication strategy like this:

store key in database - crypto.randomBytes(32)
store IV and encrypted data in user cookies - crypto.randomBytes(16)

On request decrypt encrypted data using cookies.iv, cookies.data, database.key. If decrypt was successful proceed with request.

Encrypted data is random string with no value.

If database key was hacked, login is impossible because IV that stored in user cookies is needed.

If cookies was stolen, than I think it's user problem.

My only concern is that there is a way decrypt will be successful for some random attacker key. And that decrypt will be heavy for performance for most of the requests.

Example code for cookie encryption / decryption:

/**
 * @param {string} data dummy
 * @param {string} userKey from database or create new
 * @return {object} {iv, key, encryptedData}
 */
function encrypt(data, userKey) {
  let key = userKey ? Buffer.from(userKey, 'hex') : crypto.randomBytes(32)
  let iv = crypto.randomBytes(16)
  let cipher = crypto.createCipheriv('aes-256-cbc', Buffer.from(key), iv)
  let encrypted = cipher.update(data)
  encrypted = Buffer.concat([encrypted, cipher.final()])
  return { iv: iv.toString('hex'), key: key.toString('hex'), encryptedData: encrypted.toString('hex') }
}

/**
 * @param {string} iv
 * @param {string} key
 * @param {string} encryptedData
 * @return {string} decrupted dummy data
 */
function decrypt(iv, key, encryptedData) {
  try {
    iv = Buffer.from(iv, 'hex')
    key = Buffer.from(key, 'hex')
    encryptedData = Buffer.from(encryptedData, 'hex')
    let decipher = crypto.createDecipheriv('aes-256-cbc', key, iv)
    let decrypted = decipher.update(encryptedData)
    decrypted = Buffer.concat([decrypted, decipher.final()])
    return decrypted.toString()
  } catch (err) {
    return false
  }
}

The aspects regarding IV has already addressed @Maarten - reinstate Monica. There are some more issues.

1) If you store encrypted data in cookies once for all future requests, then it will not work, because many users clean cookies and local storage regularly. Some do that manually, some use add-ons that clean up cookies and local storage on browser exit or every 2-3 hours. Some users cannot even control that, because in serious companies users have no admin permissions and usage of such add-ons is just enforced.

2) If you set encrypted data to cookies each time for login purpose, then cleaning cookies doesn't break your solution. But if an attacker stole the key database, then he can easily decrypt whatever your send him during login.

3) The idea that user should prove he knows the key without sending this key to the server is good. But it is good only if user obtains the key via some channel other than channel used later on for authentication. Where as you want to transfer key via the same channel (same HTTPS connection) as later on authentication/decryption request. Thus you don't have more security. This would be more complexity without any additional security. I would discourage you from doing that.


What prevents continued hashing of a key from being used as a cipher when xored with plaintext? This is just an idea I had while looking through some threads so take it as you will.

Given a plaintext of any length and a key that a specific hash function is capable of taking as input(I mention this as I know bcrypt has issues with extremely large inputs), what would be the potential issues/attacks of hashing the key and then xoring the resulting key with a plaintext block of the same length? For the next block you would hash the previous hash created via the key and xor that with the next plaintext block. Repeat till you reach the end of the plaintext, pad it to the needed length, and commit the last xoring

I would imagine that it would make for a high speed stream cipher that is reasonably capable as long as the initial key is sufficiently strong.

Thanks.

This is essentially a (bad) stream cipher. It has multiple problems:

You might hit a cycle much sooner than you'd want.
It's not parallelizable - this is a large performance issue on modern CPU's compared to algorithms that parallelize well.
The key is only inserted at one point of the stream, meaning if an enemy knows only one block of plaintext it can XOR it out to retrieve the internal state of the cipher compromising all further blocks.
There is no nonce, meaning that every cipherstream will be the same.

(5.)  Padding plaintext is not necessary in a stream cipher - you can simply discard the unneeded bits from the cipherstream.

However, the answer to the question in your title (What prevents continued hashing of a key from being used as a cipher when xored with plaintext?), is nothing. For example the ChaCha stream cipher works by repeatably hashing the key, nonce and an increasing counter for each block. Note that the hash function ChaCha uses is very specialized - it doesn't compress or is collision resistant, and as result can be much faster than "regular" hash functions that have much more stringent requirements.


SHA-1 Keyed Hash Function I know that SHA-1 is an unkeyed cryptographic hash function when used in practice. But, in the theory, all hash function are defined with keys. My question is:

How I will be able to formalize the SHA-1 hash function using keys?
In security proof, which approach could be used - theoretical or practical?

We are talking about hash-function families $\{h_k\}_{k\in K}$ here. The parameter $k$ is used to rule out the trivial collision search algorithm that simply prints a collision for a given $h$ (such algorithms exist, but are difficult to find). For large  $K$ such an algorithm would be too large. The parameter $k$ is called a key, but it is not actually secret.

The issue is that concrete hash-functions are unkeyed. This is not a problem in practice, since such ``printing'' algorithms are never found. However, to prove the security of a protocol that uses such a hash function, one needs to show a proper reduction: the protocol is secure as long as the hash function is collision free. The latter is easily formulated for keyed hash functions, but for a single hash function it has been formalized rather recently. This answers your second question.

For the first question, there is no standard way of making a keyed hash function out of SHA-1, because this is not needed in practice. One may think of HMAC-SHA-1, but I doubt its collision resistance when the key is known (it is probably reduced to the chosen-prefix attack).


Making counter (CTR) mode robust against application state loss Counter (CTR) mode, which is a block cipher mode of operation, has some desirable qualities (no padding, parallel encryption and decryption), but at the cost of failing badly when non-unique counter blocks (the nonce combined with the counter that acts as input to the block cipher) are used.  I'd like to share my ideas about how the counter block can be made reasonably unique even when there is application state loss (reinstalls, etc.) that may otherwise cause non-unique nonces.  If my ideas turn out to be reasonable maybe they'll be helpful to others.

According to appendix B of the NIST guidelines the counter block should either be a simple counter that is incremented without concern for message boundaries (the "first approach") or it should be a combination of a nonce that is changed with each message and a counter (the "second approach").  Either approach is sound, but what if the history of either the counter and or the nonce is lost due to an application reinstall or other reasons?

For a cipher with a 16 byte block size, such as AES, I'm proposing a counter block that has the following layout:

  NNNNNN0CCCCCCCCC

The six "N"s are the nonce, followed by "0", a zero byte, and finally the nine "C"s for the counter bytes.  Consider the following pseudo code for getting the nonce:

static last_nonce = 0
synchronized get_nonce()
    if (last_nonce == 0)
        last_nonce = get_last_nonce_from_db() // returns 0 on failure
    local nonce = last_nonce + 1
    local since_epoch = get_time_since_epoch_in_msecs()
    if (nonce < since_epoch)
        nonce = since_epoch
    last_nonce = nonce
    return nonce

For each new message the counter ("C") bytes are random.  The increment function simply treats the entire 16 byte counter block as a 16 byte big endian integer where the right most bytes are incremented first.  This is the way Java's CounterMode.increment() seems to do it.  This approach should have the following properties:

In the normal case where the database is intact the nonce is always unique.  In this case the "0" assures that it's possible for the message to be at least 256*10 - 256*9 blocks long before colliding with the next possible nonce.
If the database is reset (this could be restoring the database from a backup, reverting a snapshot on the database system, etc., combined with restarting the application) the system time should assure unique nonces.
If both the database is reset and the system time is reverted the nine random counter bytes should assure that the odds of two one block messages colliding (having a counter block in common) with the same nonce is only one in 256**9.  As the messages get longer the odds get worse.

So it should work correctly in the normal case, but still behave reasonably in the degraded case.

I know this was long, but I wanted to explain it clearly.  I also realize that some of this leverages existing concepts (I think getting a unique incrementing value the way I did with the system time is similar to what's often done for unique identifiers), but I'm interested in how these concepts can be applied to CTR.

Relying solely on randomization for the block counter is actually more likely to cause a nonce collision in case of a system time reset. This only gets worse as the message length increases. This is further exacerbated if the PRNG takes the system time as input, or does not have enough seed entropy. There is also no reason for the static 0 byte in the nonce.

How about a 48-bit time(in ms) counter, a 48-bit random value, and a 32-bit counter than increments from 0 for each block of the data?

This gives 9000 years of unique nonces each millisecond, a 280 trillion to 1 chance of a random collision in case of a system time reset, and a 64GB max data limit per nonce. This also makes the code for nonce incrementation more simple since it starts at 0 and is only a 32-bit unsigned integer.

Values above are approximations, but close and provide a reasonable example of the periods with those given bit sizes.


What happens if you increment MAX counter in AES-CTR? Suppose you use a IV/counter = ffffffffffffffffffffffffffffffffin AES-CTR. What will happen if you encrypt the next block, and thereby increment the counter by one? Will it result in an overflow error of sorts?

In AES-CTR, the ‘IV’ and ‘counter’ are different concepts.  To encrypt a message, you specify a nonce, like a message sequence number—sometimes called an ‘IV’.  The nonce is usually 64 or 96 bits, but it could be anywhere from 0 to 128 bits long.  For security, you must never reuse a nonce with a key.  The length of the nonce for the particular AES-CTR system you're using determines the maximum message length: inside AES-CTR, the remainder of a 128-bit string after filling part of it with a nonce is used to count blocks within a message.

So, for example, if you send the message $m_1 \mathbin\| m_2 \mathbin\| m_3$, and then the message $m'_1 \mathbin\| m'_2$, you might in your protocol choose the nonce 42 for the first message, and the nonce 69 for the second, and the ciphertexts will be internally computed as:

\begin{align}
  c &= \bigl(m_1 \oplus \operatorname{AES}_k(42 \mathbin\| 0)) \mathbin\| (m_2 \oplus \operatorname{AES}_k(42 \mathbin\| 1) \mathbin\| (m_3 \oplus \operatorname{AES}_k(42 \mathbin\| 2)\bigr), \\
  c' &= \bigl(m'_1 \oplus \operatorname{AES}_k(69 \mathbin\| 0)) \mathbin\| (m'_2 \oplus \operatorname{AES}_k(69 \mathbin\| 1)\bigr).
\end{align}

(Here the $m_i$ and $m'_i$ are exactly 128 bits long apiece; it is inside AES-CTR that the block counter 0, 1, 2, …, is maintained.)

For (say) AES-CTR with a 96-bit nonce, the maximum message length is $2^{32}$ 128-bit blocks, or $2^{36}$ bytes.  What happens if you try to encrypt a $(2^{36} + 1)$-byte message?  It's simply not defined in that case—like dividing by zero.  You should avoid designing a protocol in which this question might even arise; what an implementation might do may vary: it could silently wrap around, effectively encrypting messages with a two-time pad; it could fail noisily and abort the computation; it could make demons fly out of your nose.

What if you use a 0-bit nonce, so that the maximum message length is $2^{128}$ 128-bit blocks, or $2^{132}$ bytes?  You don't have that many bytes and you don't have enough time to wait for all the computers in the world to encrypt that many bytes.

What if—internal block counter aside—you use a 64-bit message sequence number as a nonce?  Will you have to worry about wrapping around?  Hint: You are doing this in sequence.  Let's say it takes you a nanosecond to encrypt each message.  How many centuries do you have to wait for a 64-bit message counter to overflow?


What are the chances that AES-256 encryption is cracked? I'm currently building a web application and would like to encrypt all data on the back-end. I was thinking of using the AES-256 encryption but wasn't sure how safe it was. I did that math and felt safe.

I took this model to a professor at my college, who is a cyber security expert, and he seemed to have quite a different take. He told me there are only two encryption schemes that he knows of that cannot be broken, and AES is not one of them. He said sure, put it in, but just know that there are people out there who can crack it.

I Googled everything I could about the AES and it being cracked, and the only information I could find was this paper: Distinguisher and Related-Key Attack on the Full AES-256
(Extended Version). Sure it says the AES has been cracked but is still has a practical use, right? I believe it is $2^{231}$ instead of $2^{256}$.

So what gives? Is it practically secure to use or not? Does he just know something that most people don't? If my web application database credentials are somehow exposed, and a hacker gets the raw encrypted data, how can I ensure he won't be able to decrypt it within his lifetime?

He told me there are only two encryptions that he knows of that cannot be broken, and AES is not one of them

This tells me you asked your professor the wrong question.  You asked a cyber security expert if an algorithm could be cracked, to which the answer is always yes, with the exception of a handful of inconvenient algorithms, such as One Time Use Pads used in exactly the correct way.  Even in those cases, there's exploits to worry about.

AES-256 is an algorithm.  It can be broken.  If you look at the history of cryptography, every algorithm gets broken eventually.  That's why we make new algorithms.  The question is how long it takes to figure out the math to break it.

The real question to ask is "what is your threat model?"  What sort of attack are you trying to prevent?  Are you creating a digital lock on a diary to keep it safe from your sister's prying eyes, or are you Edward Snowden, on the run from several three letter agencies with billions of dollars of funding?

AES-256 is currently labeled as sufficient to use in the US government for the transmission of TOP SECRET/SCI information.  That's pretty much the highest classification level they could clear it for, so the US government is pretty darn confident that nobody can break AES-256 on the timescales required to protect our nation's greatest secrets.

(Well, almost.  What it really says is that they are confident that nobody outside of the US government can break AES-256.  What you believe that that says about whether the US government, themselves, can break it depends on your threat model... and whether you engage in discussions of whether heavy-duty tin foil  makes better hats or not)


Need literature or link to family of cryptographic invertible polynomials which has distribution similar to inverted bell curve Please help me identify a family of polynomials P(x,k) with the following properties:

$x\in Z_{2^n} $
$\forall k, \forall p_k\in P,\ \exists\ p_k^{-1} |\ p_k^{-1}(p_k(x)\equiv x\ mod\ 2^n $
Frequency distribution of $y = p_k(x)\ mod\ 2^n$ is an inverted bell curve

Thanks for suggestions

These requirements are impossible. If $p_k$ is a permutation, then the distribution induced by "choose $x$ uniformly in $\mathbb{Z}_n$, output $y=p_k(x)$" is also uniform in  $\mathbb{Z}_n$. It can't follow a normal distribution. For every possible $y$, there is exactly one $x$ that makes it happen, and that $x$ is assigned probability $1/2^n$.


How to find the keyword of the Playfair cipher, given the plaintext and the ciphertext? I know how the Playfair cipher works. I would like to know how to find the keyword of the Playfair cipher, given some ciphertext and the corresponding plaintext.

For example:

encrypted: gy mm ko kc gc
plaintext: he ll ow or ld

I searched all over the internet, but it seems there is no tutorial that would explain, step by step, how to get the keyword.

First of all, you cannot uniquely determine the keyword of a Playfair cipher, or even the key table constructed from it, simply because there are multiple equivalent key tables that will produce the same ciphertext (and multiple keywords that will produce each table).

In particular, the following key tables are all equivalent:

Original:        Row shift:       Column shift:
                                     <--
A B C D E        F G H I K        B C D E A
F G H I K      ^ L M N O P        G H I K F
L M N O P      | Q R S T U        M N O P L
Q R S T U        V W X Y Z        R S T U Q
V W X Y Z        A B C D E        W X Y Z V

We can shift any Playfair key table like this to obtain another different table that produces the same ciphertext.  The row and column shifts can be repeated and combined to move any letter of the grid into the top left corner, yielding 25 distinct equivalent tables.

In principle, we can never tell which of these equivalent tables was used just by examining the plaintext and ciphertext.  Of course, in practice, if the original table was constructed based on a keyword, it may be possible to recognize one of these equivalent tables as being more likely than others, but in principle each of them could be obtained from some keyword.  (Trivially, just take the keyword to be all the letters in the table, written out row by row.)  And of course, since repeated letters in the keyword are ignored, each table has a limitless number of possible keywords that can produce it (although, again, some may appear more likely than others in practice).

OK, so we can't uniquely determine the key table.  What can we do, then?

If we have a piece of ciphertext and know the corresponding plaintext, we can just break them up into two-letter groups and compile a list of which plaintext pair corresponds to which ciphertext pair, like this:

Plaintext:  AT TA CK AT DA WN
Ciphertext: DQ QD EH DQ EB XM

Pairs:
  AT -> DQ
  CK -> EH
  DA -> EB
  TA -> QD
  WN -> XM

In principle, with enough known plaintext / ciphertext pairs, we can just compile a (nearly) complete dictionary of letter pairs like this, and use it to decrypt unknown messages.  Basically, by doing this, we're just treating the Playfair cipher as a simple substitution cipher on letter pairs.  Even if we never figure out the actual key table, having such a dictionary is basically as good as having the key.

The only problem is that, while common letter pairs like TH, HE or AT are likely to occur pretty often both in our known plaintext and in any unknown messages we might want to decode, other less common pairs of letters might not happen to appear in our known plaintext.  Of course, we can infer some new pairs directly, e.g. from the letter exchange symmetry of the Playfair cipher: if we know that XY encrypts to PQ, then we also know that YX encrypts to QP.  But it would be nice to do more than that.

In fact, we can learn quite a lot about the structure of the key table just by applying some simple logic to the observed letter pairs:

Generally, any time we observe that a letter X encrypts (or decrypts) to some other letter Y in any letter pair, we know that X and Y must belong either to the same row or to the same column.
If we observe any two pairs of letters that encrypt to each other, like AX ⇆ BY, then we immediately know that:

A and X do not belong to the same row or column (and neither do B and Y),
A and B belong to the same row (and so do X and Y),
A and Y belong to the same column (and so do B and X).

(Of course, using the exchange symmetry, observing that AX → BY and YB → XA yields the same information as well.)
If we observe that the plaintext and the ciphertext pair share a letter, like XY → YZ, then we know that all these letters must belong to the same row or to the same column, and in particular, that this row or column must contain the (left-to-right or top-to-down) letter sequence X Y Z (which might, of course, wrap around the edge).
If we observe that XY encrypts to PQ, but PQ encrypts to, say, YA (or to BX) then we know that all these letters must also belong to the same row or column, and that this entire row or column must be some shifted version of X P Y Q A (or Y Q X P B).

(If XY encrypts to PQ, the encryption of PQ must contain at least one of X and Y; the only way in which an encryption chain like XY → PQ → AB would be possible in Playfair would be if all those six letters shared the same row or column; but, of course, a standard Playfair key table only has five letters in each row or column!)
Similarly, if we observe e.g. that XA encrypts to YB, and XB encrypts to YC, then all these letters must belong to the same row or column, and their order must be X Y A B C.
Finally, if we observe that X encrypts to Y both in AX → BY and in PX → QY, where all the six letters are distinct, then we know that all these letters cannot all belong to the same column (since they would not fit), and so X and Y must be in the same row (and so must A and B, and also P and Q).  Since all six letters also cannot fit into a single row, we can further deduce that they must be arrange in one of the following three patterns:

X Y            X-Y A-B            X-Y P-Q
A B                               A-B
P Q            P-Q

where the rows and the columns can be rearranged in any order, and the remaining rows and columns of the key table inserted at any position around or between them, except that the columns joined with - in the last two patterns must be adjacent in the key table and appear in the order shown (possibly wrapping around the edge, of course).

(Of course, this is not an exhaustive list; other similar rules can also be deduced from the constraints of the Playfair key table structure and the encryption rules.)

The rest is just basic puzzle solving, not entirely unlike, say, solving a sudoku.  Since any shifted version of the key table yields the same encryption, we can arbitrarily place any letter we want in, say, the top left corner of the table.  It's of course most convenient to pick one of the letters for which we've already figured out a complete row or column using the deduction rules above, if we have any, because then we can immediately fill it in (or make two candidate tables, if we're not sure if the sequence we've figured out is a row or a column) and proceed from there.  Then we just keep filling in more and more letters (possibly sometimes tentatively at first, until our guess is confirmed) based on what we can deduce from the known ciphertext / plaintext pairs, until the entire table is solved or until we run out of clues.

For example, let me encrypt a piece of text using the (trivial) key table given earlier above, and try to reconstruct the key table from the result:

Plaintext:  EX AM PL EA QU IC KB RO WN FO XI UM PS OV ER TH EL AZ YD OG
Ciphertext: CZ BL LM AB RQ HD GE TM XM IL YH RP NU LY BU SI AP EV DI MI

Let me first look for cases where the plaintext and the ciphertext pair share a letter (since those always mean that all the letters must share a row or a column).  We find a bunch of these near the beginning (PL → LM, EA → AB and QU → RQ) and one more near the end (YD → DI).  So we know that the sequences P L M, E A B, U Q R and Y D I must occur (horizontally or vertically, possibly wrapping around) in the key table.

The next thing to look for would be letter pairs that occur both in the plaintext and the ciphertext, but alas, in this case there aren't any, not even reversed.  There's a few near misses (like the ciphertext pair EV, which occurs reversed in the plaintext, but split between two pairs) but those don't really help.

So let me next look for common letters and their en/decryptions, to see which letters they share their row and column with.  The letter E, for example, encrypts to C, A and B and decrypts to B and A.

We already know that the sequence E A B occurs horizontally or vertically in the table, and therefore that A is below or to the right of E.  The only way in which AZ can thus encrypt to EV is if the sequence E A B is horizontal, and the sequence Z V ? (where the letter marked by ? is yet unknown) occurs at the same position in some other row.

Arbitrarily fixing E to the top left corner (because why not?), we thus already have two partial rows:

E A B ? ?
Z V ? ? ?

Can we expand them somehow?  Looking for the letter B next, we find (besides the EA → AB pair we already considered) the pairs AM → BL, KB → GE and ER → BU.

The AM → BL pair tells us that L M must occur in some row at the same position as A B.  It doesn't fit into the rows we already have, so we end up with yet another partial row.  In fact, we can also place P on the same row, based on the known sequence P L M.  The pairs KB → GE and ER → BU (and the known sequence U Q R) give us two more partial rows, yielding:

E A B ? ?
Z V ? ? ?
P L M ? ?
K ? G ? ?
U Q R ? ?

That's half the table filled in already!  Note that the order of the rows is still unknown, but we can leave that for later.  (It actually affects only a relatively small fraction of the ciphertext / plaintext pairs, since it only matters when both plaintext letters happen to be in the same column.)

To fill in the rest, we can try to look for pairs where one of the already placed letters appears in the plaintext and another letter from the same column appears in the corresponding ciphertext.  (Due to the way Playfair encryption works, that's actually really common.)  For example, the very first plaintext / ciphertext pair is EX → CZ, where we already know that E and Z share a column, letting us tentatively place C and X in the corresponding rows:

E A B ? ?  +  C
Z V ? ? ?  +  X
P L M ? ?
K ? G ? ?
U Q R ? ?

Note that I've placed them off to the side for now, since we still don't know which of the last two columns they belong in.  The next pairs with two letters that we know to belong to the same column are RO → TM and PS → NU, giving us:

E A B ? ?  +  C
Z V ? ? ?  +  X
P L M ? ?  +    O N
K ? G ? ?
U Q R ? ?  +    T S

Again, I still don't know which of the remaining columns these letters belong to, so I've also set them off to the side as partial columns.  The next pair OV → LY is interesting, though, since besides the letters V and L (which we know belong to the second column) it also includes the letter O, meaning that Y must belong to the same column as O.  This in turn leaves no place in that column for C and X, so they must belong to the same column as N and S, giving us the following table (with the order of the rows and the relative order of the last two columns yet to be determined):

E A B ? C
Z V ? Y X
P L M O N
K ? G ? ?
U Q R T S

Next we have the pair TH → SI.  We know that T and S belong to the same row, and there's no room in that row for H and I, so they must belong to the only other row where both of those columns are still free:

E A B ? C
Z V ? Y X
P L M O N
K ? G I H
U Q R T S

Now we have two letters from the consecutive sequence Y D I that we determined earlier in the same column, so we can finally start to figure out the order of the rows (and to fill in the missing letter D in the only place it can go):

Z V ? Y X
E A B D C
K ? G I H
P L M O N
U Q R T S

We now know the order of the first three rows and the first three columns, and have two letters (F and W) yet to be placed.  At this point we could even start simply guessing, since we really only have three two-way choices left (order of last two rows, order of last two columns, position of F and W), for a total of 2 × 2 × 2 = 8 possible key tables.  Or we could try to narrow down the choice further, say, by looking for letter pairs with F or W in them, of which we find two: WN → XM and FO → IL.  These let us confidently place W in the first row and F in the third, giving us the full (but still partly unsorted) table:

Z V W Y X
E A B D C
K F G I H
P L M O N
U Q R T S

Can we figure out the order of the remaining two rows and columns?  For that, we'd need to find some more pairs where all the letters share the same row or column.  Alas, it turns out that there aren't any in this example plaintext / ciphertext pair, so we're left with four non-equivalent key tables (and all their shifted equivalents) that all could have produced this ciphertext:

Z V W Y X    Z V W X Y    Z V W Y X    Z V W X Y
E A B D C    E A B C D    E A B D C    E A B C D
K F G I H    K F G H I    K F G I H    K F G H I
P L M O N    P L M N O    U Q R T S    U Q R S T
U Q R T S    U Q R S T    P L M O N    P L M N O

Of course, by visual examination, we might be able to notice that one of these key tables shows a simple pattern that is broken in the others.  Or, if we're more systematically inclined, we could try shifting all of them so that the letters X, Y and Z are in the bottom right corner (where they're most likely to end up, using the standard method of constructing a Playfair key table based on a keyword) and then checking which of the tables could be generated by the shortest keyword (which, or course, in this example turns out to have been a zero-length one).


Verification of NIZK proof with algebraic MACs The paper Algebraic MACs and Keyed-Verification Anonymous Credentials, includes a way to instantiate a NIZK proof with algebraic MAC. This is given in Appendix E where this NIZK is a part of the Show protocol. I understand the proof generation given in E.1, where the protocol outputs proof P. The hash $c$ in P is given as:
$c = H(param||\{C_{m_i}\}_{i=1}^{n}||C_{u^\prime}||\{\tilde{C}_{m_i}\}_{i=1}^{n}||\tilde{V})$
But I do not understand the Proof Verification part given in E.2. Particularly, I do not understand the construction of $c^\prime$ which is given as:
$c = H(param||\{C_{m_i}\}_{i=1}^{n}||C_{u^\prime}||\{C_{m_i}g^{s_{m_i}}h^{s_{z_i}}\}_{i=1}^{n}||VX^{s_{z_1}}...X^{s_{z_n}}g^{s_r})$
The verifier checks whether $c = c^\prime$. But I do not see how they can be computed to be equal even if everything is right. The first 3 parts of the construction of $c^\prime$ have the same elements as $c$, so for them to be equal, the particular equations below should be satisfied.
$\{\tilde{C}_{m_i}\}_{i=1}^{n} = \{C_{m_i}g^{s_{m_i}}h^{s_{z_i}}\}_{i=1}^{n}$, and
$\tilde{V} = VX^{s_{z_1}}...X^{s_{z_n}}g^{s_r}$
But upon expanding the left-hand-side of either of the equations, they do not equate to their corresponding right-hand-sides. Where am I going wrong here?

Yes, you are correct that this is an error. I discovered the same thing myself a couple of months ago and emailed the authors. Greg Zaverucha responded and agreed with me. More specifically, this was what he agreed with:
"
Hi,
I've been studying https://eprint.iacr.org/2013/516.pdf and in Appendix E.2 part 3(b) in the verification algorithm, there appears to be an error, wanted to check it with you:
In order for the verifier to reconstruct the challenge hash $c$, you concatenate items in the preimage, the 4th item (or set of items) is given as:
$$C_{m_{i}} . g^{s_{m_i}} . h^ {s_{z_i}} \quad \forall i$$
but this does not appear to be the correct way to construct the items $C_{m_i}$~ that were in the prover's challenge hash preimage. As far as I know the correct way to reconstruct the $C_{m_i}$~ terms would be:
$$(C_{m_i})^c . u^{s_{m_i}} . h^{s_{z_i}} \quad \forall i$$
(where $c$ lower case is of course the challenge hash provided by the prover).
"
I figured out what it should be based on analogy with sigma protocols in general, but it's been a little while; hopefully you can see that this version makes sense.
Additional edit: today I have been studying this again, and realised that you were also stating that the final element of the hash preimage construction also does not validate. Looking at it carefully I can see there is a very similar issue: $V$ should be replaced with $V^c$.


Vertical bar and comma in hash function input I came across to a definition of a term PMKID while studying 4-way handshake in IEEE 802.11i. It is defined as:

PMKID = H(PMK,"PMK name"||AA||SPA)

I know the vertical bar || in the input of the hash function means concatenation, i.e. joining them end-to-end. How about the comma? Any difference?

And also, does "PMK name" means that the string is converted into binary form and serve as part of the input or is it there for demonstration purpose only?

I don't know anything about IEEE 802.11i, so I can't be sure about my answer, but hopefully this provides some insight.

From the way in which the formula is written, $H$ is probably some sort of keyed hash algorithm—probably HMAC.  HMAC takes two parameters: the secret key to the MAC and the data to hash.  The first parameter is probably the secret key to HMAC, with the concatenated data being the data to hash with HMAC.


Select a single message without showing which one has been selected Can anyone suggest a cryptosystem for the following problem?
We are working on a university research project.

Problem

Alice has multiple messages $M_i$, $i = 1,\ldots ,n$.
Bob should obtain any, but exactly one $M_i$, without obtaining other $M_j$, $j \neq i$.
Alice, on the other hand, shouldn't get the exact $i$, which has been selected by Bob.

Analogous physical world scenario

Alice writes each $M_i$ onto a distinct piece of paper, and puts these pieces into a hat.
Then, Bob shuffles the pieces by hand without seeing them, draws one piece and, finally, burns the others. Obviously, Bob doesn't have a chance to peek into the hat. Also, Alice cannot see which piece Bob has selected (she is not able to leave secret marks in the pieces).

Disclaimer: I'm not by any means an expert on this, and my answer is based on things I've read, which may only be the surface of the iceberg. Comments are welcome.

You can create oblivious transfer from any public key encryption scheme for which there is an algorithm that can output strings indistinguishable from real public keys or the same with ciphertexts instead.

Basically, Bob sends $(p_1, \ldots, p_n)$ to Alice where $p_j$ is his real public key and the others are "fake" public keys. Alice sends back encryption of each $M_i$ under the key $p_i$, and Bob is only able to decrypt $M_j$. Moreover, by the properties of the "fake" keys, Alice does not learn which message Bob picked. Of course, this is only secure against passive adversaries that follow the protocol.


Using ChaCha20 as a PRNG with a variable-length seed As far as I understand, the key stream of the ChaCha20 cipher may be used as a seeded PRNG, where the seed is used to set the key and the nonce. As described in RFC7539, ChaCha20 can be used with a 256-bit (32-byte) key and a 96-bit (12-byte) nonce, allowing a seed of maximum 352 bits (44 bytes), thus limiting the counter to 32 bits (4 bytes).

My problem is, how can I use this PRNG if I want to provide a larger seed? Say, I seed the PRNG from an entropy source where I a can guarantee a minimum of about 4 bits of entropy per byte, and want to seed the PRNG with 64 bytes or more to be confident that it has been provided about 256 bits of entropy.

I reckon a cryptographic hash function, such as SHA256 or SHA512, could be used to compress the collected entropy bytes to be used as a seed, but it would be desirable if this could be solved by only using the available ChaCha20 primitive.

Another possibility seems to be to use ChaCha20 to construct a Davies–Meyer one-way compression function, treating a variable-length seed as blocks of 44 bytes (to input as key and nonce for the next block), taking the final 44 byte output as input seed to the PRNG.

It seems that Davies–Meyer was designed to be used with block ciphers, but ChaCha20 is a stream cipher.

My questions are:

Are there any obvious problems with using Davis-Meyer like this?
Are there any obviously better approaches to feed this PRNG with a variable-length seed?

Davies–Meyer?  That would be a very unusual way of seeding a PRNG.  The standard way of entropy extraction is to use a vetted hash algorithm such as SHAx.  I'm not quite sure how you want to use your RNG, and I'm having trouble deciphering how many bits of what you want.  I'm going to assume that you simply want 256 bits of entropy to inject into the state.

Having an entropy source available changes things somewhat compared to a plain PRNG. You don't need a key or a nonce in this case.  You'd collect 128 bytes from your entropy source.  It's twice 64 as NIST recommend that you double the input entropy for each bit of output entropy when using a hash based extractor.  Then run it through SHA256 and inject into ChaCha in place of the nonce and key.

Further I'm also assuming that this is to be only a PRNG.  With seeding from a true entropy source, you won't be able to repeat the output sequence.  Intuitively it feels wrong to use a PRNG to self seed, but I can't demonstrate this mathematically.  Follow the hash route as it's the obvious way, well proven and likely to be simpler than rolling your own recursive version of Davies-Mayer.