What's happens if we use the weakest S-BOX for AES? I'm in research of generating Dynamic Secret S-BOX for AES based on 2 Keys (Encryption Key and *I Called S-BOX key). If (worst scenario) I randomly generate the worst S-BOX in an encryption. What would happen? How much it affect to the security of the encryption? I need a reference about this issue.
Thanks

See: How can one construct the weakest S-box ever?
and How do I choose the best 3*3 s-boxes?

I believe that user Hend's question is not "how to design the worst possible S-box" but about "having generated an S-box randomly how do we know it is bad, how is that measured?".

A construction of S-boxes that was a trifle, insignificant, a minimis non curat would simply encode during half the rounds and decode during the other half, producing output equal to the input. If the number of rounds were odd the algorithm could leave the output in a state that was equivalent to a single round.

Obviously such poor design is trivial to discover. Where the problem lies is "when presented with an S-box construction that appears complex how do we disprove that". That is the question that I touch upon with this answer.

There are different cryptanalysis techniques and different ways to measure security. Some are published and some are secret. It's not particularly useful to measure an algorithm's security by a published method if a secret method exists for easily cracking the code.

For example: If it were though that there were only 10 ways to approach the cryptanalysis, the first 9 taking a little over a month each to execute but without any certainty of success and the 10th method providing absolute certainty of success but taking a year to produce the result, it makes sense to try the first 9 methods; you don't know which one will be successful but the worst case is it would take as long as simply applying only the 10th algorithm alone.

Similarly, if there were an 11th method, unknown to almost all cryptanalysists, one can not say that any S-box construction is opaque; that it does not reveal itself, and most importantly the original input. This answer can not speculate on what we don't know and will be limited to published measurements of complexity.

Some of the measurements are resistance to:

Algebraic attacks (RAA) (e.g., XL attack, XSL attack and Gröbner basis attack)

"Cryptanalysis of block ciphers with overdefined systems of equations" by Nicolas T. Courtois and Josef Pieprzyk.
Differential cryptanalysis
Linear cryptanalysis
Distance to the Strict Avalanche Criterion (DSAC)

In "An improved AES S-box and its performance analysis" by Jie Cui, Hong Zhong, Wei Yang they provide the formula for calculating the above metrics, and offer a list of papers they referenced; unfortunately the first four that I searched for are paywall only. The referenced papers are probably not necessary to understand their paper or this answer.

  "The cryptanalysis of the cryptographic strength of Rijndael has not stopped after the announcement and official publication of the AES $[11-16,19]$. Biryukov et al. $[10]$ proposed a distinguisher and related-key attack on the full AES-256. Wang $[5]$ noted that AES S-box affine transformation period is 4, and it does not achieve the most 16. Wang et al. $[6,17,18]$ studied AES S-box structure and pointed out that the iterative period of AES S-box has short-period phenomenon, and all the periods are less than 88. Murphy and Robshaw $[3]$ analyzed AES S-box algebraic expression and indicated that the algebraic expression of AES S-box is very simple and only 9 terms are involved. Much work has concentrated on AES S-box, such as the latest significant progress $[7]$ which illustrated the reason why AES S-box algebraic expression is so simple and proposed an improved S-box, and the algebraic expression of the S-box involves 255 terms, so the complexity of the S-box has been increased. However, the algebraic expression of the inverse S-box becomes very simple and only 9 terms are involved.

  In view of the shortcomings of AES S-box and the S-box $[7]$, in this paper, the cryptographic properties of AES S-box are analyzed, and an improved scheme to increase the complexity and security of AES S-box is proposed. Simulation results show that the improved AES S-box is better than AES S-box and S-box $[7]$ in cryptographic properties.

In their paper they offer this table on page 2301:

$[3]$ "Essential algebraic structure within the AES" by S. Murphy and M. J. B. Robshaw, Proc. of the 22nd Annual International Cryptology Conference on Advances in Cryptology, London, pp.1-16, 2002.

$[5]$ "Property of affine transformation in S-box of AES" by Y. B. Wang, Journal of PLA University: Science and Technology, vol.4, no.2, pp.5-9, 2002.

$[6]$ "Analysis of structure of AES and its S-box" by Y. B. Wang, Journal of PLA University: Science and Technology, vol.3, no.3, pp.13-17, 2002.

$[7]$ "An AES S-box to increase complexity and cryptographic analysis" by J. M. Liu, B. D. Wei and X. M. Wang, Journal of Systems Engineering and Electronics, vol.18, no.2, pp.427-433, 2007

$[10]$ A. Biryukov, D. Khovratovich and I. Nikoli´c, "Distinguisher and related-key attack on the full AES-256", Fast Software Encryption, Advances in Cryptology – CRYPTO 2009, pp.231-249, 2009.

$[11]$ W. Phan, "Impossible differential cryptanalysis of 7-round advanced encryption standard (AES)", Information Processing Letters, vol.91, no.1, pp.33-38, 2004.

$[12]$ E. Biham, O. Dunkelman and N. Keller, "Related-key boomerang and rectangle attacks", EURO-CRYPT ’05, LNCS, vol.3494, pp.507-525, 2005.

$[13]$ J. Kim, S. Hong and B. Preneel, "Related-key rectangle attacks on reduced AES-192 and AES-256", FSE 2007, LNCS, vol.4593, pp.225-241, 2007.

$[14]$ W. Zhang, W. Wun, L. Zhang and D. Feng, "Improved related-key impossible differential attacks on reduced round AES-192", SAC 2006, LNCS, vol.4356, pp.15-27, 2007.

$[15]$ S. Galice and M. Minier, "Improving integral attacks against rijndael-256 up to 9 rounds", LNCS, vol.5023, no.3, pp.1-15, 2008.

$[16]$ C.-C. Chang, Y.-W. Lai and J.-H. Yang, "An efficient authenticated encryption scheme based on elliptic curve cryptosystem for broadcast environments", ICIC Express Letters, vol.4, no.1, pp.95-100, 2010.

$[17]$ J. Liu, B. Wei and X. Wang, "Affine transformation observation on rijndael S-box", Journal of Xidian University, vol.32, no.1, pp.94-97, 2005.

$[18]$ L.-G. Cui, "A new S-box structure named affine-power-affine", International Journal of Innovative Computing, Information and Control, vol.3, no.3, pp.751-759, 2007.

$[19]$ Y.-S. Yeh, C.-Y. Lee, T.-Y. Huang and C.-H. Lin, "A transpositional advanced encryption standard (AES) resists 3-round square attack", International Journal of Innovative Computing, Information and Control, vol.5, no.5, pp.1253-1264, 2009.

As you can see the weakest, even stronger S-boxes, are suspicious. Belief that no one anywhere has a means to break the algorithm is probably misplaced. Some S-boxes would be more susceptible to one kind of an attack over another, so there's not one particularly strong or weak one without improvements to the original algorithm. The authors offer an improved version and their analysis of that, in addition to the original.

In the thesis "The Design of S-boxes" (direct .PDF link) (2010), by Jennifer Miuling Cheung and the paper "The Structured Design of Cryptographically Good S-Boxes" (1990) by Carlisle M. Adams and Stafford E Tavares, J. Cryptology. 3. 27-41. 10.1007/BF00203967 and "Modification in Designing of Substitution Technique Using 4x32 S-Box in Data Encryption Standard" (direct .PDF link, or 2nd source), (2018), by Sumit Chaudhary, N. K. Joshi, and Foram Suthar - the general consensus has improved over the years but is currently:

Five design factors that must be meet for Boolean functions to construct a cryptographically good S-box:

  Bijection: If the S-box is of ‘n x n’ bit then from input vectors a one-to-one and onto mapping to output vectors will be there. This can be explained later that how we can achieve this criterion when the S-box will
  be n x m bits.
  Strict avalanche criteria: Here, there will be the change in output bit with the probability of one-half only if a strict avalanche criterion of one input bit has changed. In Strict avalanche criteria, output vector will
  be significantly changed with a small/slight amount of change in the input vector. So, a function is needed that has a 50% dependency on each of its n input bits inorder to achieve this effect.
  Bit independence criterion or correlation-immunity: Here, there is a requirement that output bits should have different statistical patterns or no statistical dependencies compare to the output vectors.
  Nonlinearity: The cryptosystem is susceptible to various attacks so nonlinearity requires S-box which should not be a linear mapping from input to output. If the nonlinearity gives a bad result by linear functions
  and makes a cryptosystem more complex to crack so S-box will be constructed by using maximally nonlinear Boolean functions.
  Balance: if each Boolean vector has the S-box with an equal number of 0’s and 1’s then it is known as balance. This should meet most of the standards set by the NIST. Sometimes, it can be impossible to achieve
  all criteria to their full potential. Sometimes criteria can be compromised due to their conflicting nature. For example, maximum nonlinearity also conflicts with balance as well as correlation immunity conflicts with
  high nonlinearity.

The newest criteria is balance, essentially a test of the output compared to a true random number.

Possibly of interest: "Small Scale Variants of the AES (SR) Polynomial System Generator".


RSA function over $Z_t^{*}$ where $t$ is prime RSA function is defined over $Z_N^{*}$ where $N=pq$ with $p,q$ primes. A public key is a pair $(N,e)$ and a private key is $(N,d)$ where $d=e^{-1} \mod \phi(N)$.

Assume that RSA function is defined over $Z_t^{*}$ where $t$ is prime (instead of $t$ being composite). Show how one can compute $d$ from a public key $(t,e)$.

Could you check my solution? It looks a really easy assignment... if $t$ is prime, then $\phi(t)=t-1$, so $d$ can be calculate from formula: $d = e^{-1} \mod \phi(t)=e^{-1} \mod (t-1)$? And that's it?:)

In RSA, $\phi(N)$ is hidden and this is why nobody could calculate private key. For a prime modulus, order of multiplicative group is not a secret. Well, this question looks like encouraging your own thinking of RSA and related arithmetic, so please keep digging in.


Why mining bitcoins is difficult? As I understand to obtain a Golden Block is to finding a nonce that matches a hash lower than a given target, as shown in this research-gate article.

And here is a "py" kernel: Bitcoin mining python (Github)

As the nonce is only a 4 (8-bit)byte it is only to compare 65,536 hashes, that it seems ridiculous for any GPU.

So... Why is it difficult?

There are 4294967296 nonces, because it is 32-bit.

Most of the time, none of the nonces will produce a "Golden Block".
If none of the nonces work, the miner must make a new block (with a different Merkle root (256 bits) which means the block has different transactions in it) and try to mine that block instead.

Currently, about 99.999999994% of blocks don't have any valid nonce. That means the miner must try over 15 billion blocks before it finds one that has a nonce.

This is not a problem, because one of the transactions in a block is the one which gives the bitcoins to the miner. The miner can't change other peoples' transactions, but it can add extra unused bytes to its own transaction, which means the block has different transactions in it, and a different Merkle root.


Is it meaningful to consider the leakage of master key of KGC? In the Identity-based cryptography, the user's private key in the systems is delivered by the key generation center(KGC). My question is : Is it meaningful to consider the leakage of master key of KGC? And further, if this happens, then can I think that all the user's private keys disclose?
supplementary part (below)
Actually, in the papers(ID-based key-exchange) that I've read, I rarely encounter the scenarios where the leakage of master key is considered. Maybe(I'm not sure) it's because that since the adversary has the competence to get the master key, then what keys(including user's private keys) it cannot get?
But if we consider from another aspect, if the master key of KGC compromises, then it depends.If the KGC generates the user's private key only as a function of master key and user's identity without adding some additional ephemeral information(e.g. $sk_A=H(ID_A)^{msk}$), then the compromise of master key means the leakage of user's private key. But, if the KGC generates the user's private key also adding some additional ephemeral information(e.g.$sk_A=k+msk*H(ID_A,r)$, where $r=g^k$ is the ephemeral information ), then it's the other way around.Unless the adversary obtains the master key and the ephemeral value, then it can get a user's private key.
So many times, I don't know if the leakage of master key should be considered.

There are plenty of papers on forward-secure IBE, one could just google that term.

Here, I will focus on IBE with a property that I would call "key forgetting",

and work toward a candidate construction for depth-O(1) HIBE with that property.
One could apply either of the sections "Random Oracles, depth-O(1) adaptive-ID security,

and (lack of) Completeness" and "Hashing and Recovery" without applying the other,

but if one applies both then one should apply them in that order.

Discussion and Inherent Limitations:

In such a scheme, the KGC is able to update the main private key (that is, the KGC's secret) in order to "forget" the private key corresponding to a specific ID. $\:$ After it does so, the main private key should

be sufficient to compute the private keys corresponding to other IDs, but should not be sufficient to

violate confidentiality on that particular ID. $\;\;\;\;$ For n such that $\: 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}n \leq 2^L \:$, $\:$ one can consider an

arbitrary set B of $\:2\hspace{-0.04 in}\cdot \hspace{-0.04 in}n\:$ identities whose lengths are each $L$, and imagine having the KGC forget the provide keys corresponding to an $n$-element subset S of B. $\:$ Confidentiality implies that encrypting a

long random plaintext for an ID in B, having the KGC run extract on that ID, and applying decryption

with its output to the ciphertext, should have a negligible probability of resulting in the original plaintext.

On the other hand, functionality implies that doing the same for an ID in B-S

should have an overwhelming probability of resulting in the original plaintext.

Thus, doing that for each ID in B should have an overwhelming probability of recovering the set S.

Since there are at least 2^n such subsets of B, it follows that the probability of the main

private key being shorter than $\:\lfloor n/2\rfloor\:$ bits long is at most negligibly more than $\:1/2^{\lfloor n/2\rfloor}\;$.

Thus the size of the main private key must grow at least

linearly with the number of secret keys forgotten so far.
Now, suppose additionally that the scheme has sufficient completeness to make the next sentence true.

The not-necessarily-feasible procedure that takes as input (the public key and) the main private

key and outputs the set of IDs for which the extract procedure has a probability greater than

half of neither giving a valid private key nor successfully blaming anyone else for that failure,

always outputs a subset of the set of IDs for which the KGC has run the "forget" procedure.

Furthermore, confidentiality and computational soundness of the blame testing implies that

the procedure I just described should have an overwhelming probability of outputting all of

the IDs for which the KGC has run the forget procedure, which means the main private key is

overwhelmingly likely to uniquely determine that set of IDs. $\:$ Thus, that completeness condition

essentially requires the KGC to store a list of all IDs for which it has run the forget procedure.
Those limitations apply even to IBE schemes that only need confidentiality to hold for random IDs.

Positive Results from BTE:

Binary Tree Encryption directly allows for the construction of

selective-ID HIBE for fixed-depth-and-fixed-piece-length IDs with key-forgetting at each level, by just concatenating the parts of the IDs together to determine the relevant node, and to forget a key, store the keys corresponding to the nodes that differ from the relevant node in their last bit but nowhere else, and then erase the keys corresponding to the nodes that are prefixes of the relevant node.
Although potential encryptors would have to be informed somehow,

any KGC at any level could otherwise independently, by putting the time period before the ID, implement forward-security and revocation at the additional cost of requiring decryptors

to get a private key during each time period, which would also make it so that the KGC's

storage requirements only depend on the keys forgotten during the current time period.
By, for example, putting a 1 before each "real" part of IDs and appending an

all-zero ID-piece, one can use IDs of bounded depth, rather than just fixed depth.

By using a prefix-free code, one can also handle IDs whose pieces have bounded length,

although the next part of this answer will assume the ID-pieces are still fixed-length.

Random Oracles, depth-O(1) adaptive-ID security, and (lack of) Completeness

In order to go from selective-ID security to adaptive-ID security in the Random Oracle Model, one picks a Random Oracle whose inputs are interpreted as having two parts, the main one of which will be IDs, and whose outputs are much longer than its inputs, and an XOR-almost-universal family of hash functions whose domains are the space of IDs and whose codomains are the set of

bit strings whose lengths are each the same unit fraction of the oracle's output length.

(Multiplication in a binary field is an example of such a hash family.) $\:$ The master private key is has ident_set and func_set both initialized as empty sets, along with what the master private key would

be for the selective-ID scheme with ID-piece lengths equal to the length of the oracle's outputs.

The public key contains a list of [that fraction's denominator] claimed samples from that hash family, one of which was generated by the master KGC and the others of which weren't, the public key for

the selective-ID scheme, and a random string that will be used as the minor part of the oracle's input.

As long as the hashes chosen all do not depend on that random string (in particular, if they are all chosen before the random string), confidentiality will hold even if the hashes are all chosen maliciously.
For any real ID, let F(ID) denote the list that is [[the random oracle applied to the random string and the real ID-piece] xor [the concatenation of the hashes of the real ID-piece]]  for each piece of the real ID. $\:$ To encrypt and decrypt, use F(ID) in the selective-ID scheme. $\:$ To forget a user's private key, the KGC puts ID and F(ID) into the sets ident_set and func_set respectively, and then runs the selective-ID scheme's forgetting procedure on F(ID). $\:$ To extract, a KGC does as follows: if F(ID) is not in func_set then run the selective-ID scheme's extract algorithm on F(ID) and return that algorithm's output,

else if ID is in ident_set then reject, else [indicate a completeness failure, find the value ID' ident_set such that F(ID') = F(ID), and give the pair ID,ID' as a publicly-verifiable proof that all of the hashes in the public key came from a particular subset of their values that, unconditionally, is exponentially unlikely].

The last part is somewhat unsatisfying, since I don't see any

reason why one shouldn't hope for perfect completeness.
Although potential users would have to be informed somehow, any KGC at

any level could otherwise independently use a different list of such hashes.
The resulting bounded-depth-and-fixed-piece-width HIBE scheme is such that attacking an ID

that differs in at most $\Delta$ pieces from a pre-selected ID of depth at most d, by making at most

q Random Oracle queries, corresponds to attacking the selective-ID scheme on one of a list of

of at most $\:((\Delta \hspace{-0.04 in}+\hspace{-0.04 in}d\hspace{.03 in})\hspace{-0.02 in}\cdot \hspace{-0.02 in}(1\hspace{-0.04 in}+\hspace{-0.04 in}q))^{\Delta}\:$ randomly chosen IDs. $\;\;$ In particular, the resulting scheme is

adaptive-ID secure for IDs of depth O(1), where the constant does not need to be chosen a-priori.

Hashing and Recovery

In order to remove the fixed-ID-length restriction, one can try hashing IDs.

However, the issue is that completeness when IDs collide.

That can be dealt with by using a collision-resistant (cryptographic) hash family such that each

hash is associated with a unique and computationally-indistinguishable-from-uniform secret,

one can efficiently sample pairs consisting of one of those hashes and the secret for that hash,

and one can efficiently recover that secret from a hash collision.

(I will give a candidate construction of such families at the bottom of this answer.)
I'm getting really bored with typing this up, so for now I'll just say that

the KGC encrypts its original key with the hash, so that it will be able to

decrypt that and preserve completeness whenever it sees a collision.

Hopefully I'll finish this sometime soon.

The hash families I'm talking about are given by a (strongly) hard-core function and

concatenation of Pedersen commitments, for groups of known prime order p such that

there is an efficiently-computable, but not necessarily efficiently invertible, injective map

from the group to {0,1,2,3,...,n-2,n-1} for a known n such that (p^2)/((p^2)-n) is noticeable,

and the secret is the concatenation of values of the hard-core function on the discrete logs.


Verify partial message given hash of full message I need to verify partial downloads (retrieved sequentially), given a (preferably short) hash of the complete download.

Given a message $m_0 \mathbin\| m_1 \mathbin\| m_2 \mathbin\| \cdots$, hash function $H$, and hash value $h = H(m_0 \mathbin\| m_1 \mathbin\| m_2 \mathbin\| \cdots)$, I want to have a verifier function $f$ that can work on partial messages $f(h, m_0) = \mathit{valid}$, $f(h, m_0 \mathbin\| m_1) = \mathit{valid}$, $f(h, m_0 \mathbin\| \mathit{random} \mathbin\| m_1) = \mathit{invalid}$.

Message order is known in advance, retrieved in order.  $h$ is preferably short.  It's okay to spend more time (CPU) or space (memory) during verification.  High collision probability is okay.  I just need to say $f(h, m_0 \mathbin\| m_1)$ = so far so good, you can continue the download.

Is there a construct that can do that, even a probabilistic one?

EDIT: clarify the bits about 'preferably short'. Hash tree adds space burden to transmit O(2*n) hashes. Hash list is O(n). I'm looking for O(1) space requirement.

You've asked for a way to hash a file into a short string $h$ so that given a partial download $c'_0 \mathbin\| c'_1 \mathbin\| c'_2 \mathbin\| \cdots \mathbin\| c'_{i-1}$ of the file that should start with $c_0 \mathbin\| c_1 \mathbin\| c_2 \mathbin\| \cdots \mathbin\| c_{i-1}$ but may have been modified in transit, you can compute some verification function $f(h, c'_0 \mathbin\| c'_1 \mathbin\| c'_2 \mathbin\| \cdots \mathbin\| c'_{i-1})$ to tell you whether this partial download is good or not.

You haven't specified what security properties you want, but let's say it's random oracle indifferentiability of the hash function given an underlying short-input hash function $H$ like SHAKE128-256, which serves for preimage resistance, second-preimage resistance, and collision resistance (and therefore forgery detection).  This also works if you randomize $H$ and use $H_r$ instead, like KMAC128, which obviates the need for collision resistance.

Here is a slight variation:

The client will download, alongside each chunk $c_i$, a small set of additional hashes $a_i$ that can be used together with $h$ to verify that $c_i$ is correct.

The adversary may tamper with the chunk $c_i$ and the additional hashes $a_i$, replacing them by $c'_i$ and $a'_i$; we assume only that the client is given a hash of the complete download, $h$, that is known to be good.

We will define a verification function $F(h, c'_i, a'_i)$ which returns 1 if $c'_i = c_i$ and $a'_i = a_i$, that is if the data were unmodified in transit, and 0 with high probability under any forgery attempt.  ($F$ is defined on chunks, not on prefixes of the file, so it doesn't actually matter which order you download them in.)

In this slight variation, the original verification function $f(h, c'_0 \mathbin\| c'_1 \mathbin\| \cdots \mathbin\| c'_{i-1})$ will be replaced by

\begin{multline}
  f\bigl(h, (c'_0, a'_0) \mathbin\| (c'_1, a'_1) \mathbin\| \cdots \mathbin\| (c'_{i-1}, a'_{i-1})\bigr) \\
= F(h, c'_0, a'_0) \mathbin\& F(h, c'_1, a'_1) \mathbin\& \cdots \mathbin\& F(h, c'_{i-1}, a'_{i-1}).
\end{multline}

Transmitting the additional hashes is not likely to be an onerous burden:  The number of additional hashes for each chunk is logarithmic in the length of the file, the size of the hash can be a tiny fraction of the size of a chunk (say, 32 bytes vs. a megabyte), and most likely, the client will be downloading, e.g., an HTTP header alongside the chunk $c'_i$ anyway, not to mention TCP and IP headers and ethernet frames and any other encapsulation, like tunnels and VPNs, that may happen on the network anyway.

Similarly, storing the additional hashes on the server is not likely to be an onerous burden either:  Your file system almost certainly stores various metadata alongside each file anyway, including its modification times, the locations on disk where its data are stored, directory entries pointing to it, etc.

How does this work?

Hash computation.  Before anyone can download the file:

On the server, split the full file up into chunks $c_0, c_1, c_2, \dots, c_{2^\ell - 1}$.
On the server, compute the hashes
\begin{align}
 h_{0,0} &:= H(0, 0, c_0), \\
 h_{0,1} &:= H(0, 1, c_1), \\
 h_{0,2} &:= H(0, 2, c_2), \\
 \vdots \\
 h_{0,2^\ell - 1} &:= H(0, 2^\ell - 1, c_{2^\ell - 1}).
   \end{align}
These are the leaves of a Merkle tree.
On the server, compute the hashes
\begin{align}
 h_{1,0} &:= H(1, 0, h_{0,0}, h_{0,1}), \\
 h_{1,1} &:= H(1, 1, h_{0,2}, h_{0,3}), \\
 h_{1,2} &:= H(1, 2, h_{0,4}, h_{0,5}), \\
 \vdots \\
 h_{1, 2^{\ell-1} - 1} &:= H(1, 2^{\ell-1} - 1, h_{0, 2^\ell - 2}, h_{0, 2^\ell - 1}).
   \end{align}
These are the first level of the Merkle tree above the leaves.
On the server, compute the hashes
\begin{align}
 h_{2,0} &:= H(2, 0, h_{1,0}, h_{1,1}), \\
 h_{2,1} &:= H(2, 1, h_{1,2}, h_{1,3}), \\
 h_{2,2} &:= H(2, 2, h_{1,4}, h_{1,5}), \\
 \vdots \\
 h_{2,2^{\ell-2} - 1} &:= H(2, 2^{\ell-2} - 1, h_{1,2^{\ell-1} - 2}, h_{2,2^{\ell-1} - 1}).
   \end{align}
Repeat, combining two hashes at a time.
At the end of this process, the server will have a hash $h := h_{\ell,0}$.  This is the root of a Merkle tree, which is also a hash of the original data $c_0 \mathbin\| c_1 \mathbin\| c_2 \mathbin\| \cdots \mathbin\| c_{2^\ell - 1}$.  Share the root hash $h = h_{\ell,0}$ of the Merkle tree first.  For example, you might transmit it on another channel (like how a .torrent file is shared separately from the pieces), or the server might digitally sign it with a long-term key pair whose public key the client knows a priori.

Download process.  When the client wants to download the $i^{\mathit{th}}$ chunk $c_i$, after getting the known-good hash $h$ of the file:

The server sends a set $a_i$ of additional hashes alongside $c_i$, $$a_i := (h_{0,i \oplus 1}, h_{1,\lfloor i/2\rfloor \oplus 1}, h_{2,\lfloor i/2^2\rfloor \oplus 1}, \ldots, h_{\ell - 1, \lfloor i/2^{\ell - 1}\rfloor \oplus 1}).$$  These are the sibling hashes of a path down the Merkle tree—for the subtrees that do not have $c_i$ in them.  Here $\oplus$ means xor; that is, we are toggling between the even- and odd-numbered hash indices.
The client receives a putative chunk $c'_i$ and the putative hashes $a'_i := (h'_{0,i \oplus 1}, \ldots)$, which may be the correct chunk $c_i$ and the correct hashes $a_i = (h_{0,i\oplus 1},\ldots)$ or may have been modified in transit by an adversary.  The client can now compute
\begin{align}
 h'_{0,i} &:= H(0, i, c'_i), \\
 h'_{1,\lfloor i/2\rfloor} &:= H(1, \lfloor i/2\rfloor, h'_{0,2\lfloor i/2\rfloor}, h'_{0,2\lfloor i/2\rfloor + 1}), \\
 h'_{2,\lfloor i/2^2\rfloor} &:= H(2, \lfloor i/2^2\rfloor, h'_{1,2\lfloor i/2^2\rfloor}, h'_{1,2\lfloor i/2^2\rfloor + 1}), \\
 \vdots \\
 h'_{\ell,0} &:= H(\ell, 0, h'_{\ell - 1, 0}, h'_{\ell - 1, 1}).
   \end{align}
To ensure the data were not modified in transit, the client then checks $h'_{\ell,0} \stackrel?= h_{\ell,0}$ and drops the data on the floor if it fails.  In other words, we have the chunk verification function $$F(h, c'_i, a'_i) := \begin{cases} 1, & \text{if $h'_{\ell,0} = h$;} \\ 0, & \text{otherwise,} \end{cases}$$ with $h'_{\ell,0}$ computed from $c'_i$ and $a'_i = (h'_{0,i \oplus 1}, \ldots)$ as above.  Note that the computation of $F$, the verification function, involves only the root hash $h$, the chunk $c'_i$ itself, and the $\ell$ hashes included in $a'_i$; verifying a chunk does not require knowing anything else about any other chunk in the file.

For example, in an eight-chunk file, when you transmit chunk $c_6$, send it alongside $h_{0,7}$, $h_{1,2}$, and $h_{2,0}$; the client, given the possibly modified $(c'_6, h'_{0,7}, h'_{1,2}, h'_{2,0})$, computes $h'_{0,6} = H(0, 6, c'_6)$, $h'_{1,3} = H(1, 3, h'_{0,6}, h'_{0,7})$, $h'_{2,1} = H(2, 1, h'_{1,2}, h'_{1,3})$, and $h'_{3,0} = H(3, 0, h'_{2,0}, h'_{2,1})$, and then verifies $h'_{3,0} \stackrel?= h_{3,0}$ before accepting the chunk $c'_6$ as genuine.  The information needed to download and verify $c_6$ is illustrated in the diagram below:

The red solid boxes are data transmitted.  Note that there is no need to download any other chunk to verify $c_6$—only three hashes are needed.
The blue dashed boxes are recomputed by the receiver.
The red solid circle is the root of the Merkle tree, i.e. the hash $h$ of the whole file, which is sent first on some channel assumed not to be corrupted, and which the receiver uses to verify each chunk.

What does this cost?  Let $|c|$ be the maximum chunk size, say 64 KB or 1 MB, $|H|$ be the hash size, typically 256 bits, and $n = 2^\ell$ be the total number of chunks.

The overhead you must store is a total of $2n$ hashes (one for each chunk, and an additional one for each node in the tree) costing $2 |H| n$ bits of storage.
The overhead you must transmit alongside each chunk is $\ell = \log_2 n$ hashes, if the server does nothing to avoid resending hashes the client already has, so the total number of additional bits transmitted for hashes alongside the $n$ chunks is at most $|H| n \log_2 n$.

Thus, the total number of bits stored is $|c| n + 2 |H| n$ and the total number of bits transmitted is $|c| n + |H| n \log_2 n$.

Here are some example data volumes to get some perspective for how much this costs:

\begin{equation}
\begin{array}{rrrrrr}
\text{file size} &
\text{$|c|$} &
\text{$|H|$} &
\text{hash storage} &
\text{hash tx} &
\text{tx overhead} \\
1\,\text{MB} & 1\,\text{KB} & 32\,\text{B} & 64\,\text{KB} & 320\,\text{KB} & 31.25\% \\
1\,\text{MB} & 64\,\text{KB} & 32\,\text{B} & 1\,\text{KB} & 2\,\text{KB} & 0.20\% \\
1\,\text{GB} & 64\,\text{KB} & 32\,\text{B} & 1024\,\text{KB} & 7168\,\text{KB} & 0.68\% \\
1\,\text{GB} & 256\,\text{KB} & 32\,\text{B} & 256\,\text{KB} & 1536\,\text{KB} & 0.15\% \\
1\,\text{GB} & 1\,\text{MB} & 32\,\text{B} & 64\,\text{KB} & 320\,\text{KB} & 0.031\%
\end{array}
\end{equation}

Exercises for the reader.

Handle all the fenceposts in non-power-of-two lengths.
Extend to radix $r > 2$ with total transmission cost of $|c| n + |H| (r - 1) n \log_r n$ bits.
Generalize to unbalanced Merkle trees, e.g. backwards SHA-256 if you want to download only in start-to-end order.  What costs does this restriction on order save?


Committing Bilinear equation in Groth-Sahai framework Groth-Sahai framework enables us to commit to QE, MSME, PP equations. Now, is the equation below committable in GS framework?

A bilinear map $e: G_1 \times G_2 \rightarrow G_T$. $g_1 \in G_1$ and $g_2 \in G_2$ are the generators of the corresponding groups. $K \in G_1$ and $\tau \in G_T$ are constants. $x,y \in Z_p$ are variables to be committed. The equation is: $$e(K/g_1^x, g_2^y) = \tau$$I want to prove the knowledge of $x$ and $y$ without revealing the values. Note that groups have been written in multiplicative notations.

Firstly, note that Groth-Sahai framework doesn't provide proofs of knowledge of exponents, because all commitments to exponents in it are computationally irreversible. It only provides proofs that show that such exponents exist. That is, a prover can claim to know $x$ but actually only know $\mathcal{A}^x$ for some $\mathcal{A}$, and still be able to produce a valid proof.

Secondly, the equation can be rewritten as follows:

$$e(K,g_2)^ye(g_1,g_2)^{-xy}=\tau$$

Since $e(K,g_2)$ and $e(g_1,g_2)$ are constants, this equation is linear in terms of $y$ and $-xy$. There is an article describing proof of knowledge systems for such equations:

Camenisch, J., & Stadler, M. Proof Systems for General Statements about Discrete Logarithms.

Alternatively, if it's necessary to use Groth-Sahai framework, the equation can be rewritten as follows:

$$\mathcal{X}=g_1^x\wedge\mathcal{Y}=g_2^y\wedge e(K\mathcal{X}^{-1},\mathcal{Y})=\tau$$

The first two equations are MSME, and the last one is PP. However, there are now three equations instead of one, so the proof is larger than necessary. Also, at least in the DLIN instantiation, a prover can produce a valid proof while only knowing $\mathcal{X}$ and $\mathcal{Y}$ but not $x$ and $y$. I don't know whether it is possible in SXDH instantiation, but anyway, Groth-Sahai proofs are not proofs of knowledge of exponents.

It may also be possible to use Camenisch-Stadler proof system to prove the knowledge of exponents that correspond to commitments in Groth-Sahai proof system. This way, it may be possible to prove the knowledge of exponents as well as the validity of quadratic equations over them.


ElGamal ciphertext lenght I'm studying for an exam and answering practice questions and I would love clarification on something. Apologies if it seems really simple.

My lecture notes indicate that for ElGamal:

  the ciphertext is twice the length of the plaintext.

Here is my exercise:

the public key $y$ which is $5496$
my chosen plaintext $m$ which is $104$
$p$ which is $9323$ and $g$ which is $5261$
my secret value $k$ which is $92$

These values were all supplied for the exercise so I have to work with them.

I have calculated $g^k \bmod p$ which is $8606$

I have also calculated $(y^k×m) \bmod p$ which is $3095$

Therefore, $3095$ is the ciphertext, correct?

My plaintext $m$ was $104$ which is 3 digits, and my ciphertext is only... 4?

Realistically, if the result is $\bmod p$ then $p$ is 4 digits and no result would ever be greater than that.

So is this statement not so literal? Wherein, it's not that $3095$ is twice the length of $104$, it's that $3095$ decoded from numbers to text is twice the length of $104$ decoded from numbers to text?

Therefore, if A = 0 then 104 = KE and 3095 = DAJF which is... twice the length.

Is this the correct theory behind the statement that the ciphertext is twice the length of the plaintext?

Several issues:

(Typo now fixed) $g$ and $G$ where visually different, I do not see a reason why.
(Fixed by now using secret value where there was secret key) When enciphering, one does not need a secret key; the deciphering party is assumed to know the private key matching the public key, and keep it secret. The $k$ is the random secret nonce (number used once) drawn for encryption, not a "secret key". That's confirmed by $g^k\not\equiv y\pmod p$.
$y^k\cdot m\bmod p$ would be part of the ciphertext; something else is needed for successful decryption. Argument: $y^k\bmod p$ is essentially random for one not knowing $k$, thus so is $y^k\cdot m\bmod p$ for any particular $m$ coprime to $p$, thus $y^k\cdot m\bmod p$ can't allow recovering $m$ for one with no clue about $k$ (or something related).
Yes, that other component of the ciphertext is $g^k\bmod p$.
(My bad).
All $m$ with $1\le m<p$ are counted as having the same size. The ciphertext comprises two integers in $\Bbb Z_p^*$ while the plaintext is one, thus the ciphertext is twice as large as the plaintext. Cryptographers count the maximum size of message and cryptogram, rather than their actual size. As an aside they use bits or octets, rather than decimal digits, but the later is OK in the context of this exercise.
Non-negative integers strictly less than integer $p$ can all be expressed with $\lceil\log_b p\rceil$ digits in base $b$, where the notation $\lceil y\rceil$ is for $y$ rounded up to integer, and $\log_b(x)=\log(x)/\log(b)$; the base $b$ is $2$, $256$ or $10$ for bits, octets, or decimal digits.
We have $p-1=2\cdot59\cdot79$ when usually, in ElGamal, it is chosen $p$ prime with $(p-1)/2$ also prime, since that improves security against the Pohlig-Hellman discrete logarithm method. But since $p$ is way too small for security anyway, that' not a big deal. Or perhaps the next step is showing that attack at work to break the encryption; e.g. by recovering the private key from $y$, or recovering $k$ from $g^k\bmod p$.


Does preimage resistance and/or collision resistance imply the infeasiblility of finding fixed points in hash functions? For example, if $H$ is a secure cryptographic hash function, is it infeasible to find $x$ such that $H(x)=x$ or such that $H(H(x))=x$ ?

What about finding $x, y$, and $z$ such that $H(y||H(z||x))=x$ ?

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hash functions.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$

This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet it holds that $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$, is almost as easy and is left as an exercise to the reader.

Per comment: a good general purpose cryptographic hash function is essentially a random function, and wide, with no special case like in the above counterexamples. We have no efficient algorithm to exhibit a fixed point (if there is one, which has probability $1-1/e\approx63\%$) for such functions. Essentially, we must compute the function at $O(2^k)$ points where $k$ is the width. Therefore, there can't be a good general purpose cryptographic hash with a known fixed point. And that extends to all general purpose cryptographic hashes that I know, including those which collision-resistance or preimage-resistance is seriously broken.


RSA: least significant bit position in key How can I show that $C' = 2^e·C^* \bmod N$ when it is decrypted will add zero bits in the least significant bit position of the key?

I am not sure if the cause is multiplying by a ciphertext which would lead the key to be multiplied by it as well.

Because (if $C=P^e$ where $P$ is the plain text): $2^e C= (2P)^c \pmod{N}$ so multiplying the ciphertext by $2^e$ modifies the plain text by a multiplication of $2$, which is a bitshift to the left of $1$, so we get 1 new zero bit at the end. To get $m$ zero bits, we need to multiply by $2^{em}$ (modulo $N$), of course.


Linear Cryptanalysis - possible without plaintext? If Linear Cryptanalysis exploits the fact that the plaintext and ciphertext are not completely unrelated, is the attack possible without having access to the plaintext?

Yes, linear cryptanalysis may still be possible, depending upon the distribution on the plaintexts and the specifics of the block cipher.

For instance, suppose we know that the plaintext is English encoded in ASCII.  Then we know that the high bit of each 8-bit byte is zero.  We may also know some additional linear approximations that hold on the plaintext that hold with non-zero bias.  This may be enough to mount linear cryptanalysis, e.g., if you can find a linear characteristic for the whole cipher that only involves those bits of the plaintext (only the high bits of each byte) and not any other bits of the plaintext.

As I recall, there has been results showing that ciphertext-only linear cryptanalysis of DES is possible, assuming that the plaintexts are ASCII-encoded English text.  This result might even have been included in Matsui's original paper on linear cryptanalysis; I cannot remember.


How is it possible that these two encryption functions yield the same result? I opened this post in stackoverflow some time ago where I explained a problem I had about not finding a way that would allow to successfully get the result of a string encrypted with a "aes-256-cbc-hmac-sha256" algorithm.
As seen in the answer, the encrypted string is exactly the same as it had been encrypted with just a "aes-256-cbc" algorithm, I could get advantage of that to successfully do a proper decryption.
Out of curiosity, I'd like to know how something like that is possible. I don't know much about criptography, but, on general terms, I know how all the functions involved in the algorithm work... And, by no means, I see that they could offer the same result, as it happens.
Why are these two different functions yielding exactly the same result?

This is a problem created by the library. Either the HMAC algorithm is skipped entirely, or - more likely - the HMAC authentication tag is generated and then forgotten. The reason is likely the spotty to non-existent handing of authenticated ciphers in the OpenSSL command line and (likely) higher-level functions. The string is recognized by the cipher classes, but the authentication tag output is simply ignored.
The output is 64 Base64 characters without padding chars, corresponding to a $(64 / 4) * 3 = 48$ ciphertext in binary. The plaintext is 43 characters/bytes. There is no way that the ciphertext includes the authentication tag of 32 bytes (256 bits, the output size of SHA-256). No, the plaintext is just padded with an additional 5 bytes using PKCS#7 compatible padding and then encrypted... and that's it.
So sorry, no crypto magic happening here, just a bad implementation of a cryptographic library. To any OpenSSL devs out there: this should not be that hard to fix, right? Just whitelist the strings that you have tested, please.


Problem with Hash-DRBG's seedlen values (and others) In NIST-SP-800-90Ar1, the Hash-DRBG is instantiated with hash functions using strange values for seed length (seedlen) such as 440, 888.

How are these values derived? How to derive values for other hash functions?

440 and 888 are the maximal values of seed length, that, when concatenated with 1 octet, yields a input to SHA256 and SHA512 respectively, requiring only 1 invocation of the compression function.

These values are fixed in such way that, it precludes the use of other hash functions, even ones approved as SHA3.

However, if one wants, the above rule can be used to derive seedlen for other hash functions, although, this would have no official document backing it.

For example, the minimal padding length in all SHA3 functions (when used in byte-oriented environment), is 1 byte, so seedlen for SHA3 functions is

$$ 1600-\mathit{capacity}-16 $$

Also, there's problem with Hash-DRBG that's missed in the publication.

The document states that the hash function used should be "one-way", but in reality, to obtain secure DRBG instances, the underlaying primitive have to behave random, or else, distinguish attacks will be possible.


Are hash functions "intentionally" designed to be efficient? I am curious to know if the hash functions are intentionally designed to be fast, or it happens to be like this. This is very interesting to know because on the one hand, efficiency is not considered as a property to design a hash function. On the other hand, if they are not efficient, a lot of applications and protocols will be affected, e.g., the hash chain.

It seems your question is about design / choice criteria for hash functions, so let's go through all of them (or at least the more important ones).

Basic security. If your hash function fails to provide the basic security guarantees, e.g. 2nd and first pre-image resistance and collision resistance, there's no chance it's ever going to be used.
Advanced security. This is also a "must-have" for hash functions these days and includes things like "acts like a PRF" or "can be modeled by a random oracle".
Speed. If I have the choice between two hash functions that are equally secure for my purposes, I'm always gonna pick the faster one, unless there are other good reasons to pick another one.
Endorsements. As everywhere, if you have a good "marketing department" your product is gonna be widely used. This also holds true for hash functions which benefit massively from endorsements such as "SHA-3 finalist", "SHA-3" or endorsement by NIST, BSI, ...
Elegance. Many good hash function designs try to be simple but effective to ease analysis and give confidence that no "hidden problems" can be found because it's all "so simple".

To go a bit further into the speed side, you want your hash function to have a nice synergy with your hardware. E.g. Keccak has been designed to be fast once the gates for the the $\chi$ step will be integrated in the hardware (this is why hash competition have VHDL design requirement).


BIKE: Bit Flipping Key Encapsulation - Inverse encryption / decryption I'm trying to understand white paper about BIKE Asymmetric crypt.
And actually read about the inverse matrix that needs to be produced for decryption.
My concern is:
Can I actually encrypt data with private key and decrypt with public key instead too?
If so, there are 3 Versions of BIKE: "BIKE-1, BIKE-2, BIKE-3"
Which one will work?

I can't say for sure, but I don't think that will work for the following simple reason:
The secret key in BIKE is a sparse parity check matrix of an MDPC code $(h_0, h_1)$, and the public key is always dense.
The decryption of BIKE (in all versions) relies upon the sparsity of the parity check matrix of the secret key. If you were to swap the keys the bit-flipping decoder wouldn't work anymore - it's decoding failure rate increases linearly with the weight of the parity check matrix.
Hope I could help!


Computational requirements for breaking SHA-256? Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function):

preimage attacks to get $m$ knowing $H(m)$
second-preimage attacks to find some $m'\neq m$ knowing $m$ so that $H(m)=H(m')$
collision attacks to find $m_1,m_2\neq m_1$ for $H(m_1)=H(m_2)$

I wonder how much computational resources would in theory be required for performing each attack on SHA-256. I have little experience with complexity theory, but could not find much literature on this.

My approach was this: in general, there are $2^{256}$ possible hashes. Since there is no known structural weakness in SHA-2, brute-forcing a preimage is the only option and should take $2^{255}$ trials (half of the hash space). However most refer to $2^{256}$, is that because that means certain success rather than expected time needed?

A collision takes $2^{128}$ steps with a Birthday attack. I could not find figures for the second-preimage attack.

First of all, are my assumptions above correct? What would the complexity of the three attacks be?

I am also curious what "unit" a number like $2^{256}$ implies - is it something like floating-point operations that would be needed to run?

I am aware that SHA-256 is deemed secure given today's computational power. is it likely that increasing computer capacities (classical, not quantum computing) will become a threat to this over the next years?

First of all, are my assumptions above correct? What would the
complexity of the three attacks be? I am also curious what "unit" a
number like $2^{256}$ implies - is it something like floating-point
operations that would be needed to run?

Almost, this number is the number of times the primitive (in this case SHA-256) must be called to break the algorithm (e.g. find a preimage or collision).

I am aware that SHA-256 is deemed secure given today's computational
power. Is it likely that increasing computer capacities (classical,
not quantum computing) will become a threat to this over the next
years?

No, SHA-256 will not be broken because of computational power. When you attack a hash function using brute force, the computation will take millions of years. $2^{128}$ operations is just too large a number.
However, most people expect that SHA-2 will be broken in the next 100 years. That is how the first preimage/collision will be found. What this means (in the case of collisions) is that somebody devises a smart algorithm which can find a collision without needing to execute this large amount of operations. Recently, Marc Stevens et al published an attack on SHA-1 which only needs
$9\,223\,372\,036\,854\,775\,808 \approx 2^{63}$ operations. This number is small enough to be searched through by Google's awesome computing cluster (and consequently the first known SHA-1 collision has been found).


Where to store the file extension to retrieve it correctly after decryption I am using Java to write AES-256 to encrypt various files with different extension, the problem is, where am I suppose to store the file extension so the if the data is decrypted, the file extension would be restored ?

For example,

If I encrypt a "test.pdf" file, I will first read it as a byte array and then encrypt it using AES-256, but when the data is decrypted, I can manually save the decrypted data as "xyz.pdf", but this is because I know the original file extension was "pdf".

What If I don't know what was the extension of the original file before encryption,
If I save the extension inside the encrypted text, then It would only be decrypted with my AES algorithm and wouldn't be decrypted with any another AES-256 algorithm even if the user has a correct key.

So, Where Am I supposed to store the extension of a file?

If you are encrypting one file to one file, simply save the correct extension. Example: open test.pdf, encrypt the content, and save as test1.pdf, or test1.pdf.enc (so that you know that the file is encrypted and any pdf won't try to open it when you double click).

If you are encrypting more than one file together (and, in the end, you have one big chunk of data that contains more than one file inside), you're already having to deal with "which byte belongs to which file", and then storing the original filename is just part of this file manipulation.


Arbitrary width pseudorandom permutation An arbitrary width pseudorandom permutation seems like a very versatile secret-key cryptographic building block.  It allows for trivial (nonce-misuse-resistant!) authenticated encryption, among other things.

Are there any known constructions that are considered secure?  Are any of those efficient in practice?

There's XXTEA, whose block size is an arbitrary multiple of 64 bits, but it's broken.  There's the Hasty Pudding Cipher, an AES candidate, but it was not selected to be one of the AES finalists and has received relatively little attention.

Built out of a stream cipher (short key $\mapsto$ long output stream) and hash function (long message $\mapsto$ short hash), there are BEAR, LION, and LIONESS.  But you probably won't break any speed records with an authenticated encryption scheme built out of one of those, rather than out of the stream cipher and hash function directly.


Is public key ever used to encrypt data directly? In TLS, asymmetric encryption is used to agree on a symmetric key, which is used to encrypt/decrypt the data.
I want to ask if there is any scenario or system where the public / private key is directly used to encrypt and decrypt data.

TL,DR: It's technically possible, but not in well-designed systems.
No, public-key encryption is never used to encrypt end-user data directly, either in TLS or in any other sensible protocol. Public-key encryption has many drawbacks compared to symmetric encryption:

It's a lot slower. A lot slower.
It can only encrypt very small payloads (a few tens of bytes). To encrypt more data would require a mode of operation, which carries its own share of difficulty (modes for symmetric encryption don't necessarily work automatically with public-key encryption).
If done wrong (e.g. PKCS#1 v1.5), it's vulnerable to oracle attacks.
It's more complex to implement, and at more risk of side channel leaks.
A successful quantum computer as currently envisioned would break all current asymmetric cryptography, but would only have a minor effect on symmetric cryptography (requiring twice the key size).

Sensible protocols are hybrid: they use asymmetric cryptography to establish a session key, and then use symmetric cryptography with the session key. Encrypting the session key is not the best way to do this. Rather than generate a session key and use public-key encryption to encrypt it, it's better to use asymmetric cryptography to generate a random session key. This is usually called a key establishment method (KEM) (although terminology can vary). The basic type of two-party KEM is key agreement, where each side uses its own private key and the other side's public key to generate a session key, in such a way that both sides obtain the same session key. Diffie-Hellman is the classic key agreement protocol. There are also one-sided KEM, for example RSA-KEM has one side apply the public-key operation to a random number in the correct range, and the other side decrypts it with the private key.
Good protocols use signature and key establishment in preference to public-key encryption. Signature and key establishment use the public key in combination with data received from an untrusted peer and use the private key in combination with data produced locally. In contrast, public-key encryption uses the private key in combination with data received from an untrusted peer, which gives an attacker more direct access to the most sensitive part of the system.
TLS may or may not use public-key encryption, depending on the cipher suite.
Most TLS cipher suites use a key agreement method (Diffie-Hellman, usually on an elliptic curve nowadays) to allow the two parties to exchange a symmetric key, and the client checks a signature made by the server to make sure that it's connecting to the expected server. With ephemeral Diffie-Hellman (each side generates a new DH key on each connection), this has the benefit of providing forward secrecy: an attacker who records a TLS connection and later manages to compromise one of the parties will not be able to decrypt the connection, because that requires the knowledge of the ephemeral key.
There is a set of TLS cipher suites that use public-key encryption and not signature or
key agreement. You can spot them because they have “RSA” in their name, but not “(EC)DH(E)”. The client creates a symmetric key and encrypts it with the server's public key. In theory, this is secure: without the server's private key, an attacker cannot obtain the symmetric key. In practice, this method has historically been subject to many implementation flaws. And even with a perfect implementation, relying on public-key encryption lacks forward secrecy: if an attacker records traffic and later breaches a server, the attacker can use the server's private key to decrypt past connections. The most recent version of the TLS protocol (TLS 1.3) does not include any cipher suite based on public-key encryption.
RSA-KEM is not used in TLS.
Finally, to answer the literal question in the title, there are of course plenty of systems with badly designed cryptography out there. As we've seen, there are sensible (but not ideal) protocols that encrypt a session key. The asymmetric encryption mechanism doesn't care that what it's encrypting is a key, so it is possible to have a system that uses a public key to encrypt user data directly and that is functionally correct (i.e. what you decrypt with the private key is what was originally encrypted with the public key). If the size of the data to encrypt is small enough, the system even has a chance of being secure (i.e. the only way to decrypt data is to already have the private key). Due to the size limitation, this is effectively never done in sensible protocols.


What kind of data is appended to the message encrypted in AES128-CBC? I'm currently using wireshark to analyse TLSv1 traffic. I generate the traffic to an Apache (OpenSSL) using the following java (jdk 6) code :

        URL url = new URL(strUrl);
        HttpURLConnection httpc = (HttpURLConnection) url.openConnection();
        httpc.setRequestMethod("POST");
        httpc.setDoOutput(true);
        httpc.setFixedLengthStreamingMode(32);
        OutputStream out = httpc.getOutputStream();

        String request = "A";
        byte[] bytesRequest = new byte[1];
        bytesRequest[0] = Character.toString((char)Integer.parseInt(partsRequest[0])).getBytes("UTF-8")[0];
        out.write(bytesRequest);
        out.flush();
        out.close();

The chosen algorithm in the handshake is AES128_CBC_SHA.

So if I understand things correctly, the POST request is encrypted and sent, then we use the last cipherblock of this request as an IV for the message "A" to be encrypted.

However, when sniffing the traffic with Wireshark I noticed that the size of the encrypted data is of 32 bytes even if Wireshark decrypt it only as 1 byte :

So my question is : what is the nature of the appended data, padding, or info about the length of the message, or both ?

Also, I encrypted both 16 and 32 bytes and I respectively end up with 48 and 64 encrypted bytes, even though padding is not necessary (I'm using messages of the block size).

So my question is : what is the nature of the appended data, padding, or info about the length of the message, or both ?

With this ciphersuite, the encrypted data consists of the plaintext data, and the HMAC of the plaintext (and header and sequence number); this HMAC is 20 bytes long.

Hence, if you encrypt 1 byte, then you'll end up encrypting 21 bytes; with CBC mode, this gets padded up to 32 bytes; exactly what you see.  And, a 16 byte message becomes 36 bytes with the HMAC, hence 48 bytes after padding; and a 32 byte message becomes 52 bytes, which is 64 byes after padding.

One correction to a statement you made:

  even though padding is not necessary (I'm using messages of the block size).

Actually, even if the 20 byte HMAC wasn't added, you always have to add at least one byte of padding; if the prepadded message was a multiple of 16 bytes long, that means that you'll need to add a full 16 bytes of padding.  If you encrypt a 12 byte message (so it becomes 32 bytes after the HMAC), that becomes 48 bytes after padding; if padding was not added, then on decryption, there'd be no way to distinguish between "this decrypted message was precisely 32 bytes long", vs "this decrypted message was shorter than 32 bytes, and had padding added"


Does AES use different keys for each block of plaintext? If you have 4 16-byte blocks of plaintext to encrypt does each block have a different 128 bit original key? Or do they all use the same?

TL;DR no it doesn't use different keys for each block; the key stays the same. AES has been designed to be able to encrypt many blocks with the same key.

AES is a block cipher. As a block cipher it can only encrypt / decrypt (or permute) one block of plaintext / ciphertext at a time. How you encrypt 4 concatenated blocks of plaintext isn't specified by AES. So in that sense it is impossible to answer your question.

Generally the block cipher AES is however used in a block cipher mode of operation such as CBC. These modes of operation take an already keyed block cipher as parameter. So in a mode of operation the key stays the same. This also goes for the derived sub-keys or round keys that are calculated during initialization of the block cipher that performs the key schedule.

In principle you could create a mode that uses different keys for each block encrypt (probably using some kind of calculation to calculate each "block key" from a key seed). That would however require you calculate the key schedule for each block. Furthermore, it would likely allow related key attacks, to which at least AES-256 is susceptible.

Proposing such a mode during a crypto conference is probably not advisable.

If the 16 byte blocks are separate messages then it is of course also possible to use the same key. If you're not concerned about leaking information about equality of the plaintext then you can also simply use the block cipher directly.

The modes of operation specified for block ciphers such as CBC, GCM (and so on) also work for smaller messages. Note that you need to use an IV if you want to reuse the key for most modes of operation. Using an IV is required for modes of operation that provide CPA security.

If you want to use different keys then that's also possible, for instance by deriving keys from a master key using a KDF.


Is CTR really equally secure than CBC? Here is a typical cryptographic situation:
A secret key exists that is only known to a sender and a receiver of messages. As it is hard to replace that key, since you either need a secure channel for transmission or a way how the receiver can send something to the sender to perform a key exchange and both may not exist, a lot of different messages will be encrypted all with the same key. Note, however, that the messages exchanged will all be different. It's not impossible that two messages could start with the same couple of bytes or contain the same byte sequences somewhere within the messages but that would be pure coincident and is not generally expected to happen frequently.

Now when using CBC encryption, there is an IV and that IV is randomly chosen for every message exchanged. With a 128 bit block cipher, like AES, the IV has 128 bits as well, so the chances that two messages are encrypted with the same IV is only 1 to 2^128, which is rather tiny. And even if the same IV would have been used for two messages, does it really matter if the messages are entirely different in the beginning? After all the IV is XORed with the first 128 bit of the message first, so even for the same IV that operation has a different result if the first 16 byte of the message are different than the last message that had the same IV.

However, CBC is considered outdated by most people today, pretty much every paper about block cipher chaining recommends to only use CTR for new development, praising all it's advantages. Sure, CTR has a couple of nice features but is it really equally secure to CBC in a situation initially described?

CTR also uses an IV, yet that IV is split into two parts: A nonce and a counter. As the counter values are for sure repeating for different messages, since all counters start at zero for the first block of every new message, the only randomness comes from the nonce. Yet the nonce will be less than 128 bit because there must be room for the counter. All papers say, you must never use the same IV with the same key to encrypt two different data blocks but the nonce space of CTR is always for sure smaller than the IV space of CBC, so the chances for a collision are much higher, aren't they?

I've seen CTR implementation that split the IV in half, so there are 64 bit nonce and 64 bit counter. In that case the chances for a nonce collision are just 1 to 2^64 compared to 1 to 2^128 for the CBC case. While 2^64 is still a big number, it's a whole lot smaller than 2^128.

Thus won't using CTR force you to replace the key much more frequently, unless you want to risk the security of your encrypted data exchange? Is CTR really a suitable replacement for CBC in a situation as described above?

Aside from that, CTR doesn't seem compatible to itself. Every CBC implementation can decrypt data correctly that any CBC implementation has encrypted. That's because there are no open question on how CBC works, everything is standardized. The same cannot be said for CTR as different CTR implementation can use different ways to split the IV into nonce and counter. When I know that my messages will never have more than 2^20 blocks, I could use only a 20 bit counter and thus get a 108 bit nonce, yet this won't work if the other side expects a nonce to be exactly 64 bit long.

To make things even more complicated, instead of splitting the IV into two parts, one can also create the IV by adding nonce and counter together or XORing nonce and counter together, which avoids the issue with the IV space reduction, yet I have no idea what such a behavior means in regards to security of CTR. Also it will make the implementation incompatible to most existing CTR implementations.

Your analysis is mostly correct, yet it ignores the reasons CBC has lost favour. CBC requires padding. And we have seen multiple practical attacks on the padding.

Nounce reuse in CTR is indeed much worse than IV reuse in CBC (which is bad enough).

I've seen implementation where the sender sends a full block length nonce(e.g 128 bit) and how he split it up is up to sender. receiver need not verify the bottom part starts with an appropriate number of trailing zeros. In fact the protocol could work even if we start each message with a fully random nonce with no trailing zeros and increment it.


Storing values under different keys (e.g. during key rotation) If you are encrypting some secrets (database passwords, access tokens, etc).

When it comes to key rotation, you'll need to store those encrypted values twice, for a short period of time (under the old and new keys).

Could the encrypted secrets be stored in two files named after the hash of their keys? maybe sha256?

Or could those file names (if known) be used in a malicious way? perhaps making it easier to determine the key values?

An alternative would be to use the keys to encrypt a known plain-text value, and use that for the file names.

I'm currently considering using libsodium, and "IETF ChaCha20-Poly1305" (aead_chacha20poly1305_ietf), to encrypt the secrets.

Why I'm not using 'secrets.new' and 'secrets.old'...

This will be used for some websites, where the script running will simply be given a key to decrypt the secrets (via an environment variable), I'd like to avoid having to also say if it's the new or old key.

Secondly, lets assume the website also has this security vulnerability:

<?php

    $path = '/path/to/file/' . $_GET['file'];

    readfile($path);

?>

It might not be that obvious, but the attacker won't know what the file will be called if it's based on the key (you see a similar thing with the Firefox profile directory).

As a very rough implementation:

<?php

//--------------------------------------------------
// Functions

    function secrets_set($key, $secrets) {

        $nonce = random_bytes(SODIUM_CRYPTO_AEAD_CHACHA20POLY1305_IETF_NPUBBYTES);

        $encrypted = sodium_crypto_aead_chacha20poly1305_ietf_encrypt(
                json_encode($secrets),
                $nonce,
                $nonce,
                $key
            );

        $name = hash('sha256', $key);

        $path = SECRETS_FOLDER . '/' . $name . '-' . bin2hex($nonce);

        file_put_contents($path, $encrypted);

    }

    function secrets_get($key) {

        $name = hash('sha256', $key);

        $prefix = SECRETS_FOLDER . '/' . $name . '-';
        $path = NULL;
        $nonce = NULL;
        $secrets = NULL;

        foreach (glob($prefix . '*') as $match) {
            if (($pos = strrpos($match, '-')) !== false) {
                $path = $match;
                $nonce = hex2bin(substr($match, ($pos + 1)));
            }
        }

        if ($path) {

            $secrets = file_get_contents($path);

            $secrets = sodium_crypto_aead_chacha20poly1305_ietf_decrypt(
                        $secrets,
                        $nonce,
                        $nonce,
                        $key
                    );

            $secrets = json_decode($secrets, true);

        }

        return $secrets;

    }

//--------------------------------------------------
// Store

    $key1 = sodium_crypto_aead_chacha20poly1305_ietf_keygen();

    secrets_set($key1, [
            'database' => 'u8syTtAvNWJbhwMNdFdRsfxJY',
            'api_key1' => 'y9f82wZdkahEPsyjXQAmy6nPh',
            'api_key2' => 'YtMp4pHR9EbHbGJXgRiniQixU',
        ]);

//--------------------------------------------------
// Get

    print_r(secrets_get($key1));

//--------------------------------------------------
// Re-key

    $key2 = sodium_crypto_aead_chacha20poly1305_ietf_keygen();

    secrets_set($key2, secrets_get($key1));

    print_r(secrets_get($key1));
    print_r(secrets_get($key2));

    // When $key1 is no longer in use, delete the old file.

?>

ChaCha20 is a stream cipher, therefore, knowledge can be used. Let see what one can do.

  When it comes to key rotation, you'll need to store those encrypted values twice, for a short period of time (under the old and new keys).

This means that the attacker has a chance to see these $C_1 = P\oplus K_1$ and $C_2 = P\oplus K_2$. X-oring these two ciphertexts;

$$P\oplus K_1 \oplus P\oplus K_2 = K_1 \oplus K_2$$ results the x-or of the keys.

In other words, the attacker could get information about the X-or of new and old keys. As longs as the keys are select independently and uniformly from a good entropy source, this will give no information to the attacker.

Note that IV reuse under the same key will reveal information by crib dragging.

$$P_1\oplus K \oplus P_2\oplus K = P_1 \oplus P_2$$ this can ve exploited by crib-dragging.

  Could the encrypted secrets be stored in two files named after the hash of their keys? maybe sha256?

Using hash of the keys give additional information for the attacker. Today, or maybe in a foreseeable this cannot be exploited, however, don't do this. Just use the file name with .old .new extensions during the operation.

  Or could those file names (if known) be used in a malicious way? perhaps making it easier to determine the key values?

Already pointed above that the knowledge of the old and new file doesn't reveal the keys.

  An alternative would be to use the keys to encrypt a known plain-text value, and use that for the file names.

This is fine.


Is it safe to use the hash of the data as the key to encrypt them? Is it safe to use the hash of the data as the key to encrypt them?

That is, if I give one some encrypted data and tell them that the key that was used to encrypt them was the hash digest of the data before encrypting, will it be easier for them to decrypt them?

Edit as I can not reply to comments: The recipient will have the keys, that is no problem.

It's kind of pointless to use the hash over the data even if you only hand over the key to the receiver of the ciphertext.

First of all, it's insecure. Consider an empty or very simple message. In that case an attacker can guess the message, create the hash, and verify correctness by decrypting.

Second, it binds the key to the data of the message. You will have to refresh the key each time you change the message. The idea of symmetric ciphers is that you can reuse the key for different messages. This scheme is not as bad as a one-time pad where the key has to have the size of the message as well, but it is still very inefficient.

Creating a secure key for most symmetric ciphers isn't hard; you just take 128 to 256 bits of secure random data and use that as key. There is no need to make the key dependent on the plaintext message. If you communicate with another party then often key agreement (DH or ECDH) is performed to agree on a key instead. There are of course countless other methods of key establishment.

In case the key is reused then you would have to use a different IV for each message. This IV can however be included with the ciphertext; it doesn't need to remain secret.

Note that this answer assumes a cryptographically secure hash such as SHA-2 or SHA-3. It doesn't consider a keyed hash or PRF such as HMAC-SHA-2 or KMAC-SHA-3.


"Kernel attack" on MinRank -- why do we guess $\left\lceil \frac k n \right\rceil$ vectors? The kernel attack on MinRank is described here (page 5). My question refers to this line:

  Note that if $m = \left\lceil \frac k n \right\rceil$, the system essentially has only one solution $\lambda = (\lambda_1, \ldots, \lambda_k)$.

Why is this so? I understand that when $m = \left\lceil \frac k n \right\rceil$ the described system is never underdetermined, but how does this help? Any insight / further references?

So we have $k+1$ matrices $M_0, M_1, \ldots, M_k \in \mathbb{K}^{n\times{}n}$. We are trying to find weights $\mu_1, \dots, \mu_k$ such that the rank of the weighted sum of matrices is smaller than or equal to some target rank: $\mathsf{rank}(-M_0 + \sum_{i=1}^k\mu_iM_i) \leq r$.

The Courtois and Goubin strategy is to select $m$ random vectors $\mathbf{x}^{(i)} \in \mathbb{K}^n$ (for $i$ from $1$ to $m$) and hope they all lie in the kernel of some combination of the matrices. If these vectors do lie in the kernel of suck a weighted sum, we can then easily find those weights by solving for $\mu = (\mu_1,\ldots,\mu_k)$ the linear system
$ \left\{ (-M_0 + \sum_{j=1}^k\mu_jM_j)\mathbf{x}^{(i)} = \mathbf{0} \right\} $
for all
$ i \in \{1, \ldots, m\}$.

This linear system consists of $mn$ equations and $k$ variables. If $k = mn$, then we expect there to be one solution. If $k < mn$, then the system might well be over-determined and might not admit any solutions, whereas if $k > mn$ then we might find several solutions rather than a single one. We are aiming for the case in which the system has one solution, so we must choose $m$ so that $k \approx mn$ holds as well as possible. Further constraints on $m$ are that it is an integer -- so we must round up or down -- and that it is different from zero -- because otherwise we have no equations. So the natural choice is $m = \lceil {k \over n} \rceil$.


Is gfcombinefs - a filesystem for n-of-m Shamir secret sharing - fundamentally read-only? With a view on using a tool similar to fgcombinefs in cloud situations, I would need a writable n-of-m Shamir secret sharing filesystem.

As a matter of routine security, I do not want the cloud provider to be able to reconstruct real data from what I store on his hardware.

If the data stored on his hardware is fundamentally random, because it is just one share in a Shamir shared secret, there is no point for anybody to try to look for a key, because there isn't one. The attacker would simply need find the other n-1 shares, stored at other cloud providers elsewhere on the globe.

fgcombinefs seems to implement 99% of the job, but unfortunately, its Shamir filesystem is read-only.

When looking at the fuse operations behind fgcombinefs, you can see that both read and write are actually supported :

int(*   write_buf )(const char *, struct fuse_bufvec *buf,
   off_t off, struct fuse_file_info *)

int(*   read_buf )(const char *, struct fuse_bufvec **bufp,
   size_t size, off_t off, struct fuse_file_info *)

You can see that in the case of writing a block, fuse will ask you to effectively perform a write to the file named as in the first string argument const char *, at offset off_t off.  In the case of a read of a block in a file at a particular offset and a particular size, fuse will ask you to allocate a block, if needed, and return its address in bufp.

I would think that writing a Shamir block, amounts to first producing the m Shamir secret shares, and then writing them to the m underlying filesystems, while reading a Shamir block amounts to picking n filesystems from the m available, ask them to send the block, recombine the n secrets on the fly, and return the reconstituted block to the caller.

In these circumstances, I do not really understand why writing to a Shamir filesystem would fundamentally be unsupported?

However, if I overlooked an impossibility somewhere, I would be most grateful if someone pointed it out, because it would spare me the time wasted in trying to program something that would in fact be impossible. Is there fundamentally a reason why the author has made fgcombinefs read-only?

I am the author of gfcombinefs.

Instead of sharing your actual secret, I would suggest secret-sharing an immutable, securely-random bytestring, and using that bytestring as a symmetric encryption key. That way, you can use any standard encryption mechanism to change and re-encrypt your actual secret. That's what I now do instead of using gfcombinefs - I use the gfcombine tool to reconstitute a symmetric encryption key on a ramfs, and use it to decrypt an encrypted volume. This means I have the freedom to change the secret keys that are on the encrypted volume, back up the encrypted volume, and so on without needing to re-share anything (which is very inconvenient if you have written some of the shares to external media stored in a separate location, or to paper).

  In these circumstances, I do not really understand why writing to a Shamir filesystem would fundamentally be unsupported?

Three reasons:

I didn't need it when I wrote gfcombinefs, and I didn't implement what I didn't need :-)
I haven't done the mathematics to prove whether it would be safe
I would guess (although I have no proof for this assertion) that making it safe would require having all the shares online and modifiable at the same time

Another commenter wrote:

  AFAICT, it should be safe against attackers who only get one look at the shares, but it might leak information if the attacker can observe the same n′< n shares before and after the change

You are welcome to do whatever you want with gfcombinefs (bearing in mind that it has absolutely no warranty, and I never actually did a proper release of it). However, if it was my secret being shared, I would not be comfortable with doing this until I had a security model, and a mathematical proof that the proposed scheme met the security model.

I wrote a mathematical proof that libgfshare had the properties I believed it did (https://sources.debian.net/src/libgfshare/2.0.0-2/doc/theory.tex/) before starting to use libgfshare for anything I valued. I would suggest doing the same if you use it differently.


Is xgcd faster than Fermat for calculating $d$ in RSA? I want to calculate $d$ from $e$ when generating RSA keys.

What is faster?

Calculating $\operatorname{xgcd}(e,p)$ and $\operatorname{xgcd}(e,q)$ and CRT.
Or calculating $e^{p-2}\bmod p$ and $e^{q-2}\bmod q$ and CRT.

I'm having a hard time understanding how to calculate the complexity here.

The extended Euclidean algorithm ($\operatorname{xgcd}$), when applied to $p$ and $e<p$, uses at most $\lceil\log_\phi(\sqrt5(p+1))\rceil-2\in\mathcal O(\log p)$ divisions in $\mathbb Z$. (This is Knuth's corollary to Lamé's theorem.)
Using Fermat's little theorem and square-and-multiply exponentiation on $e$ modulo $p$ takes at most $2\cdot\lfloor\log_2(p-2)\rfloor\in\mathcal O(\log p)$ multiplications in $\mathbb F_p$.

Therefore, both methods are asymptotically equivalent. However, there are some practical benefits when using $\operatorname{xgcd}$:

The involved numbers' bit length decreases very quickly.
A division with remainder is generally cheaper than a multiplication followed by a modulo operation.


Why does SHA-1 have 80 rounds? Why does SHA-1 algorithm have exactly 80 rounds? Is it to reduce collisions? If yes, then why do SHA-2 and SHA-3 have a lower number of rounds?

Most hashes are built from permutations (either keyed permutations/block-ciphers, as in MD5, SHA-1 and SHA-2, or unkeyed permutations as in Keccak/SHA-3 and CubeHash). A permutation is a shuffling of the inputs. Once you have a good random permutation, you can easily build a hash from it. See Construction of One-way compression functions from block ciphers on wikipedia for details.

As an analogy you can think of shuffling cards by hand (except crypto uses between $2^{128}$ and $2^{512}$ cards).

A common strategy for shuffling is going through the deck several times, performing a bunch simple operation each time. Each time of going through the deck is called a "round".

Why do SHA-2 and SHA-3 have a smaller number of rounds?

For a round you can either choose to do more complex, and thus expensive operations which achieves more or simpler cheaper rounds which do less. SHA-1 has simpler rounds than SHA-2 and thus needs more of them to properly mix the values.

The art of designing a symmetric primitive that achieves as much mixing as possible with as cheap as possible operations. The SHA-2 and SHA-3 are better than SHA-1 in that regard.

Why have many rounds?

More rounds make cryptoanalytic attacks harder but do not help (much) against brute-force. In particular it increases resistance to a technique called differential cryptoanalysis, which is a popular technique for attacking hashes and block-ciphers.

Going back to the card shuffling analogy:

You can define features of a deck, such as two specific cards being placed directly after each other. After going through the deck once, that feature might be preserved with a relatively high probability like 10%. After going through the deck multiple times the probability of a feature surviving all of them drops exponentially. So the probability of a feature being present in the final state will approach the ideal probability quickly.

In cryptoanalysis you can define similar features called "differential characteristic". One round preserves this characteristic with a certain probability. For example if a characteristic survives one round with probability $10^{-3}$, it might survive 80 rounds with probability $10^{-3 \cdot 80}= 10^{-240}$.

If you have characteristics surviving all rounds with high enough probability, that can often be exploited for finding a collision or pre-image faster. A designer aims for enough rounds that exploiting these shuffling flaws is more expensive than doing a brute-force attack while choosing few enough rounds for good performance.

(There are a few inaccuracies in the above description, but I believe the general idea is correct.)

Why does SHA-1 have 80 rounds?

More rounds increase security against cryptoanalysis. But it also decreases performance. So it's necessary to find a compromise between security and performance. The SHA-1 designers chose 80 rounds.

In hindsight, they chose a too low value, since we have since found attacks against SHA-1 that find collisions faster than brute-force.


Why constrain the message lengths in indistinguishability in the presence of an eavesdropper? I need your help with a very basic concept in cryptography which I can't understand/prove on my own.

I'm trying to prove and understand why, under "indistinguishability in the presence
of an eavesdropper" encrpytion, it is required that the lengths of the messages output by the adversary satisfy $|m_0| = |m_1|$.

Just to make sure the reader understand exactly what's I'm talking about, the context of my question is page 6 of these lecture notes on Constructing a Computationally Secure Scheme Pseudorandomness (“Claim of indistinguishable encryptions in the presence of an eavesdropper”).

Well, the problem is that -- as long as your encryption algorithm accepts messages of arbitrary length -- it is impossible to hide the length of the encrypted message.

This is actually quite natural. Think about it, when I encrypt a 1000 bit message I simply need more bits to represent the ciphertext than when I encrypt only a single bit.

Therefore, if one of the messages is allowed to be longer than the other, it is in general quite easy to distinguish between the two cases, because in the one case the ciphertext will be longer.


Is this problem based on discrete polynomials modulo $(x^3-1)$ strong? We start working with the Ring $R=\left(\mathbb{Z}/p\mathbb{Z}\right)\left[x\right]/\left(x^{3}-1\right)$,
$p$ prime, i.e. degree two polynomials with coefficients modulo $p$
modulo $x^{3}-1$. As $x^{3}-1=\left(x-1\right)\left(x^{2}+x+1\right)$,
we choose a subset of $R$, $S\subset R$, and a public value, $z\in\mathbb{Z}/p\mathbb{Z},\ z\neq0$,
$P\in S,\ P\equiv-z\left(mod\ x-1\right)$.

We can define the transpose operation of elements of $S$ as swaping
the $x$ coefficient with the $x^{2}$one of the corresponding polynomial,
so $\left(ax^{2}+bx+c\right)^{T}=bx^{2}+ax+c$.

Now, we define a function $f:S\times S\mapsto S$, as $f\left(A,B\right)=\left(xA^{T}+z\right)\left(xB^{T}+z\right)-zx$.
It's null element is $-zx$ and $f$ is a closed map of $S$, so $A,B\in S,\ f\left(A,B\right)\in S$.

Next, we define a series as follows:

$A,B\in S,\ s_{0}=A,\ s_{1}=B,\ s_{n}=f\left(s_{n-2},s_{n-1}\right)$

And for a given element of the series,$s_{n}$, a value $r_{n}=f\left(s_{n},A\right)$

The question is

Taking into account that the function $f$ is not
associative, how difficult is, knowing $B$ and $r_{n}$, recover the
value of a secret $A$. As an example of sizes let's say $n=256,\ p\sim2^{128}$.

This problem can lead to a cryptosystem described in this two documents:

https://drive.google.com/open?id=1OGnFfooWASVCD1Iw_hVwvHYgqMGGE5nH

https://drive.google.com/open?id=1OeKh_ZJF-i7_KzWFRv8jodk3YkXe2qyv

Here's the isomorphism:

$ax^2 + bx + c$ (with $z$) maps to $ax^2 + (b + z - z')x + c$ (with $z'$)

The only nonobvious thing about this transform is that it preserves $f$, that is, that $f(A, B)$ (with $z$) is the element that maps to $f'(A', B')$ (with $z'$, and $f', A', B'$ are the mapped versions of $f, A, B$)

However, this is not hard to show; we notice that the constraints $ax^2 + bx + c = -z \pmod {x-1}$ is equivalent to $a + b + c = -z$.

With this in mind, if $A = ax^2 - (a+b+z)x + b$ (setting the linear term to the value it must be for it to be consistent with the constraint), and if $B = cx^2 - (c+d+z)x + d$, then $f(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z)x + (2ad+2bc+ac+bd)$

If we consider the mapped version of those two elements $A' = ax^2 - (a+b+z')x + b$ and $B' = cx^2 - (c+d+z')x + d$, then the mapped version of $f'$ would have $f'(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z')x + (2ad+2bc+ac+bd)$

We can see that the element $f(A, B)$ maps to the element $f'(A', B')$, hence the isomorphism is preserved.


Are any public key algos commutative? Are there any public key encryption algorithms that allows for arbitrary ordering of crypto operations (commutative). That is, given a plaintext $\text{message}_1$, the following operations work to doubly encrypt it:

$$\text{message}_2 = \operatorname{encrypt}(\text{message}_1, \text{pub}\_\text{key}_1)$$
$$\text{message}_3 = \operatorname{encrypt}(\text{message}_2, \text{pub}\_\text{key}_2)$$

Then to decrypt one would need to remove the encryption in LIFO order:

$$\text{message}_2 = \operatorname{decrypt}(\text{message}_3, \text{priv_key}_2)$$
$$\text{message}_1 = \operatorname{decrypt}(\text{message}_2, \text{priv_key}_1)$$

Is there a crypto method that allows me to also (implying commutativity) reverse the order in which the keys are applied in the decrypt operations to recover the original plaintext $\text{message}_1$? That is, I would need the following to work as well:

$$\text{message}_4 = decrypt(\text{message}_3, \text{priv_key}_1)$$
$$\text{message}_1 = decrypt(\text{message}_4, \text{priv_key}_2)$$

The classical ElGamal cryptosystem satisfies your requirements. Indeed, let us consider a group $\mathbb{G}$ of prime order $p$ and a generator $g \in \mathbb{G}$. Let $(h_1,h_2) = (g^{s_1},g^{s_2})$ be two public keys for two random secret keys $(s_1,s_2)$. To encrypt a message $m \in \mathbb{G}$ with the public key $h_1$, pick a random coin $r_1 \in \mathbb{Z}_p$ and send $C_1 = (g^{r_1}, mh_1^{r_1}) = (c,c')$. To re-encrypt it, it is sufficient to encrypt the second component $c'$ of the ciphertext $C_1$. So, pick a random coin $r_2$ and compute $C_2 = (c, g^{r_2}, c'h_2^{r_2}) = (\alpha,\beta,\gamma)$, which is a re-encryption of $C_1$ with the second public key $h_2$. Now, you can decrypt in reverse order: decrypt $C_2$ by computing $\gamma / \alpha^{s_1} = \delta = mh_2^{r_2}$, and decrypt the resulting ciphertext $(\beta, \delta)$ with $s_2$: $\beta/ \delta^{s_2} = m$.

However, re-encryption of a ciphertext is not compact: encrypting $n$ times a plaintext results in a ciphertext of size $O(n)$.

There are probably many other examples of commutative cryptosystems, and there has been some work on constructing various interesting cryptosystems with this property, but unless what you want is more complicated than just "commutative public key cryptosystem", the above examples are sufficient.


Is exposing a constant IV an easy target to attacks? I have multiple RFID tags which I want the data stored on them to only be read by certain users when scanned. What I did was basically to encrypt the data with a key using CBC mode, take the encrypted hex data and append it with the IV, and then put this whole string into the tag.

So, each tag will have a different IV but their data is encrypted by the same key.

Basically, Tag A is assigned with $IV_A$ and Tag B is assigned with $IV_B$, same for Tag C, D and so on. I would pre-encrypt the data on my computer, append the IV to the back of the encrypted data, and then transfer the whole string into the tags. The different data for each of the tags will all be encrypted with the same key. So, the data in Tag A would contain $EncryptedMsg_A+IV_A$. In Tag B, the data in it would look like $EncryptedMsg_B+IV_B$.

The IVs are appended in clear text behind the encrypted data. $IV_A$ will remain unchange as the IV of Tag A for as long as it is around. And $IV_B$ will remain unchange as the IV of Tag B too.

The users wouldn't be writing to the tag. They will only be reading from the tag.

However, the part where IV remain unchanged on each scan and exposed makes me feel uneasy about this method.

Will this method be sustainable to attackers? Should I have another key to encrypt the IV before appending to the encrypted data? Would it be stronger this way?

To use CBC mode, you'll want to get a new, randomly-generated IV before each message encryption.  As long as you do this, you shouldn't have to worry about issues like how many times the same ciphertext is read with the same IV.


Continuous stream of strong randomness from limited entropy? I need a continuous (infinite) strong random generator, but I've only got limited entropy as seed. I know there's already a contradiction there, but I'm looking for a practical approach.

Suppose I have a piece of 1024 bit strong random entropy (a one time constant for this particular stream), and a cryptographically secure hash function, say Sha512 or Sha3-512.

Would this generate a proper stream of random data:

Next block of random bits = hash( unix or system time || entropy || last block of random bits )

Fundamentally I know there is no more real entropy in this than the initial 1024 bits. Plus maybe one bit or so per round from the unix or system time (maybe a few more if we take microseconds) but that's very predictable.

Yet considering the hash to be a CSPRNG, I'd say the output would be totally unpredictable, and good enough for all reasonable purposes? Or am I overlooking something?

As long as the initial seed remains hidden, would this 'leak' or impose any security risks when using this stream of randomness to extract encryption keys, for example? (which are supposed to be independent)

As noted in the comments, simply using your initial entropy to seed a deterministic random bitstream generator, such as those specified in NIST SP 800-90A Rev.1, or as a key to any secure stream cipher or a block cipher in OFB / CTR mode, should be enough to generate a bitstream practically indistinguishable from random.

Actually, 1024 bits of seed entropy is overkill for that.  Even a 256-bit keyspace cannot be enumerated using known physics (yes, even quantum computing) and resources available to mankind, so the only way to break (i.e. distinguish from true randomness, without prior knowledge of the key) a DRBG with a 256-bit seed length is through cryptanalytic attacks that exploit some flaw in the generator — and adding more seed entropy generally doesn't help against attacks like that.  This is fortunate, since most standard DRBGs / ciphers don't actually accept a seed / key longer than 256 bits, or, if they do, they'll internally hash it down to a shorter internal state.

That said, if your chosen DRBG does not directly accept long keys, and if you're not 100% sure that your 1024-bit seed really has 1024 bits of entropy, you may still want to hash it down to 256 bits (using a secure cryptographic hash function), instead of simply truncating it, before feeding it to the DRBG.  Alternatively, you can simply use a hash-based DRBG (such as the Hash_DRBG or HMAC_DRBG constructions from SP 800-90A.1, or the SHAKE functions from SHA-3 / FIPS 202) that directly accepts an arbitrarily long seed, and automatically hashes it down to its internal state size.

In any case, without a better entropy source than system time, I would not bother with attempting to merge additional entropy into the PRNG state — or at least, not the way you're proposing to do it.  Specifically, your proposed method has a couple of serious weaknesses:

If the initial entropy is ever leaked, an attacker can fairly easily predict future outputs just by observing a block of output and guessing when the next output will be generated.  (The precise level of difficulty will depend on the precision of the clock input, and on the predictability of the usage patterns, but even in the best case it's unlikely to deter a serious attacker.)
In particular, by observing two output blocks separated by one unknown block, an attacker can both guess the middle block and verify their guess quite efficiently (most especially so if they can observe the two blocks within a short period of time).
Conversely, if the initial entropy is not leaked, mixing in the system time doesn't really provide any added value.  It does, however, destroy the determinism of the generator, which might be considered a drawback.
Also, if the seed entropy is leaked, and an attacker can observe two or more previously generated successive outputs of the generator, they may be able to learn when those outputs were generated, which could be information one might not wish to reveal.

If you do wish to incorporate additional entropy from the system time (or other low-density entropy sources), I'd suggest using a proper entropy pool design such as Fortuna, which is designed to recover from state compromises by accumulating entropy into multiple internal pools that are only used to reseed to PRNG once they've accumulated enough entropy to resist brute force guessing.


DH and PKI for KeyExchange My question is fairly simple. I have more than two nodes which needs to communicate very efficiently from computational point of view. One of the nodes can become a coordinator between the nodes. Nodes do have certificate and private keys. To let the nodes communicate with each other efficiently I plan to use a symmetric key therefore key-exchange must be done.

The scheme to key exchange that comes to mind is to share DH's prime and primitive root among all so every one can have the shared secret key after a ring communication. Of course to prevent MITM the parameters are encrypted with each party public key.

Another scheme that comes to mind is to let coordinator generate a secret key and distribute it to nodes using their public keys.

I tend to the 2nd scheme since it's easier to implement and needs less communication in handshake phase.

Would be a compromise to distribute the secret key encrypted with public keys? Or it's always recommended to use scheme like Diffe-Hellman to avoid explicitly sending the shared secret key even encrypted.

Key exchange is notoriously hard to get right, and I strongly recommend not to do your own (unless your security requirements are really minimal). For example, what you propose does not provide forward security, which is generally considered of great importance in key exchange protocols. The good news is that there is a paper doing exactly what you need; look here. I haven't looked at the details of it, but by the abstract it sounds very efficient (albeit, not as efficient as your proposal, but giving you provable security with properties like forward security as well).


How do you prove an encryption scheme is IND-CPA or IND-CCA? I know for proving a scheme is not IND-CPA or not IND-CCA you can construct an Adversary which has an unfair advantage in an experiment/game, but how would you prove a scheme is IND-CPA or IND-CCA?

As SEJPM said in his comment: one proceeds by contrapositive, first suppose that such an adversary with an unfair advantage exists and use that adversary to break a well known assumption, e.g.: the adversary can be used to factorise a large composite integer (as defined in RSA).

As of today, we have no efficient algorithm to factorise large composite integers, even after years of research spent trying to achieve this. So from this it is safe to assume that the problem is hard, and that no such adversary exists. The scheme is IND-CPA or IND-CCA secure, because if it was not, an adversary breaking the scheme will break this well known problem.

The next step is to proceed by transforming an instance of the well known problem (a composite integer to be factored) into an instance of the scheme, if the adversary is able to break the scheme with a non-negligible advantage, it will also inadvertently solve the hard problem, this is a contradiction as we have assumed the problem to be hard.