Can homomorphic decryption of DES be practical?

Every algorithm that can be modeled as a Boolean circuit can be homomorphically encrypted. DES/3DES can surely be modeled by a Boolean circuit.

The question is if it is practical to use DES/3DES for homomorphic encryption. I don't think so.


Updating values authenticated by Merkle Tree

What do you mean that you keep the root of the merkle tree locally? Is the merkle tree signed?

If i understand what you are saying correctly, then the server can choose not to display to the public the changes you have made and keep presenting the merkle tree for the values before you updated them.

Even if you sign the merkle tree the server can still do that. However it cannot arbitrarily change the files. Only use old values.


Times of nested algorithms in proofs of security

The equation $t'=t+n\cdot t_c$ is an estimation to put an upper limit on $t'$. It might be possible that an attacker $A'$ can use a different, more efficient algorithm. But since the attack will work with using $A$, there exists an attacker $A'$ with at most $t'$. This means it's actually not an equation, but an inequality $t' \leq t + n \cdot t_c$. And then the next step is just a standard transformation to get $t'  - n \cdot t_c \leq t$.

Edit:
Actually, this assumes that $A'$ only has to run $A$ once. There are also reductions which run $A$ multiple times. If you are only looking for asymptotical complexity, it doesn't change much, tho. Running a polynomial time algorithm polynomial many times is still polynomial overall.

Edit2:
Concerning your example, there are a couple of misunderstandings of of the these times. First, in a reduction we use $A$ mostly as a blackbox. We can observe the queries (e.g. if we assume an oracle for that, which can be accessed by both $A$ and $A'$). But we make no assumptions about these times. Saying that $A'$ takes 1 unit of time for a calculation and $A$ needing 1 unit of time for a query (and possibly some internal computations)  is an assumption about their correlation we should not make.

And then there is the question what we actually use from the attacker $A$. Usually we do not only use their queries, but their results. And that happens at the time $A$ is finished, which is $t$. Then $A'$ can do its final transformation of results or do some more complex computations, which is not necessarily instant (e.g. solving a large linear system or doing $k$ exponentiations, etc.). If you assume this to be instant, then $t=t'$ for exactly this attack. But that doesn't mean that this is the fastest attack (if you assume $A'$ to be the "best" attacker, $t'$ might be lower), or if those computations are not instant, then $t'$ might be greater.


File integrity checking: why use a hash tree instead of a hash list?

Looks like the question itself needs some correction. My characterization of what happens in "file sharing" was too simplistic, and adding detail to it explains the matter.

eDonkey/eMule in the 00's did use Tiger Tree Hashes, which are a kind of Merkle trees.

But by then, looks like BitTorrent's torrent files only contained a simple list of hashes corresponding to the blocks of the torrented file. The number of blocks was fixed, but their size could be adjusted. This made for big torrent files, which stressed web servers; but minimizing torrent file size forced big file blocks in the torrent, which was also bad.

So around 2009, BEP 30 introduced a way to reduce the size of the torrent files AND to reduce the size of the hashed file blocks: the new style of torrent file contains only the root of a Merkle tree (so its size is minimal, relieving the web server), and the tree is created internally by seeders. The pieces of the tree needed for each block transmission are sent in-band, making it self-contained and verifiable with the root.

The key point is that the tree is not transmitted by itself, but generated by seeders and transmitted piecewise as needed. This piecewise transmission probably generates a lot of redundancy, but this redundancy is in the P2P protocol, so this inefficiency is much less important than the relief to the web server.

A hash list as the one I described in the question might be workable as a substitute of the tree, but would cause even greater inefficiency in the protocol, and would need storage of the whole list of hashes (linear to the size of the torrented file) even if the client is not interested in some blocks.


No, since finding $a$ allows offline checking of passwords. $\:$ No, although I can't back this part up.


This question can be summarized: the attacker found a $d$ that did not satisfy $e \cdot d \equiv 1 \pmod{ \phi(n) }$, but it works; what's going on.
It turns out that $e \cdot d \equiv 1 \pmod{ \phi(n) }$ is not necessary (it is sufficient).
The necessary and sufficient conditions are:
$$e \cdot d \equiv 1 \pmod{p-1}$$
$$e \cdot d \equiv 1 \pmod{q-1}$$
If both of these hold, then $d$ will always work [1]; conversely if $d$ always works, then both of these hold.
These two conditions can be summarized as a single relation:
$$e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$$
This $\text{lcm}(p-1, q-1)$ modulus is known as the Carmichael function of $n$.
In the specific example you have, $\text{lcm}(p-1, q-1) = 60$, and we have $7 \cdot 43 \equiv 1 \pmod{60}$, and hence $d = 7$ works

[1]: Assuming $p, q$ are distinct primes.


How to perform the initial permutations 64-Bit DES to derive $K$?

I want to know how to use initial permutation to derive $K$ using permuted choice 1 and permute choice 2

You start with the DES key $K$, usually expressed as 8 bytes. That's 64 bits. DES number these bits from 1 to 64, starting with high-order bit on the first byte in reading order, moving to lower-order bit, then after the 8th bit of a byte moving to the next byte in reading order, so that bit 42 is the second-highest-order bit of to the 6th byte in reading order, testable by binary AND of that byte with 40h.

From these bits 64 bits of $K$ it is extracted two 28-bit quantities $C_0$ and $D_0$ by picking bits per table $PC1$. The top (resp. bottom) of this table gives the bit numbers in $K$ of the bits forming $C_0$ (resp. $D_0$). You'll notice that $PC1$ contains no multiple of 8, meaning that the low-order bit of each byte of $K$ is ignored. This deliberately weakens DES.

Bits of $C_0$ are numbered 1 to 28, and bits of $D_0$ are numbered 29 to 56, in reading order of $PC1$.

For the first round of encryption, from $C_0\mathbin\|D_0$ it is extracted eight 6-bit quantities (the subkeys 1 to 8 for the first round) by picking bits per table $PC2$, which lines gives the bit numbers in $C_0\mathbin\|D_0$ of the bits forming each 6-bit quantities. Eight bits of $C_0\mathbin\|D_0$ are left aside, but will be used in the next round, after some rotation of $C_0$ (resp. $D_0$) yielding $C_1$ (resp. $D_1$).


Why does NIST SP 800 `KDF in Counter Mode' specification require a PRF rather than a PRP?

The basic goal—not really explicated by the standard—of these KDF constructions is to turn an unstructured-input short-output PRF $f$ into a structured-input long-output PRF $\operatorname{KDF-}\!f$, whose PRF-advantage has some standard reduction to the PRF-advantage of $f$.

If the label, context, counter, etc., are all short enough, you could instantiate it with a PRP instead of a PRF for $f$, and you would incur the standard PRP-for-PRF cost on security bounds.  It is likely that with CMAC, you don't pay that cost—though I haven't done the analysis to be sure.


What is this called: encrypt $X$ with key $E$, decrypt $X$ with key $D$?

As correctly pointed out in the comments: The term is asymmetric cryptography, also known as public-key cryptography.

How do we know that it's asymmetric encryption?

In symmetric encryption the encryption key and decryption key are identical, meaning you can decrypt data with the same key that it has been encrypted with.

On the other hand, in asymmetric encryption the encryption key and decryption key are different from one another ($K_{Enc} \ne K_{Dec}$) and in your example it's stated:

  The encrypted data cannot be decrypted with key $E$.

How to create $E$ from $D$

This can be achieved with the following procedure:

Create a key $K$ with a key derivation function by using your password. You can think of this function as a key-stretching-function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format. This is important to get an input which is "random enough" for step 2.

PBKDF2 is a noteworthy here. To increase the difficulty of a potential attack a cryptographic salt is added to the password.

You can now use this created key $K$ as a seed for a PRNG (pseudo random number generator). Important here is the word pseudo, which means that given the same seed it will always return the same created number.
The PRNG is used for a key-pair-generation-algorithm, which then returns the public-key $K_{Public}$ (in your example $E$ for encryption) and the private-key $K_{Private}$ (in your example $D$ for decryption).
You can now use this generated keys for any asymmetric cryptography methods, some well known examples are:

ECDH (Elliptic-Curve-Diffie-Hellman).
RSA

Important: I left out that you would have to use different key-pair-generation-algorithms, depending on which asymmetric cryptographic scheme you would use.

This procedure would work theoretically, but is very expensive from a computational view as you're only using asymmetric encryption. In practice this problem is solved by implementing a hybrid cryptosystem:

  A hybrid cryptosystem is one which combines the convenience of a public-key cryptosystem with the efficiency of a symmetric-key cryptosystem.

A noteworthy example of this would be ECIES (Elliptic Curve Integrated Encryption Scheme), where the security is based on the Diffie–Hellman problem. This scheme allows two parties to create a (random) session key, which allows symmetric encryption.


Is PGP's way of maintaining email security optimal?

Yes, PGP's sketch as in the question is sound by today's textbooks on cryptography, and reasonable from a computer security standpoint. Applying digital signature then encryption (critically: including on the signature) does provide data integrity and confidentiality for the message.

PGP's way of doing things has the characteristic that one able to decipher the message can turn it into a cleartext message signed by Alice, that anyone (knowing and trusting Alice's public key) can verify. In many cases, that's a feature.

It can occasionally become a weakness when PGP is misused. Assume Alice sends a message to Mallory like "I love you", signed by Alice, encrypted to Mallory; Mallory can decipher the message, and forward it to Bob, still signed by Alice, perhaps even re-encrypted to Bob; Bob, if he does not understand what PGP signature really means, can be tricked into thinking Alice cares for him. That's also Alice's fault: she should have signed a more context-free message, like "I love you Mallory" (and be more selective). More examples here (which takes the debatable position this is a defect in PGP).

There's also the argument, legitimately made by some computer security material, that with sign-then-encrypt as in PGP, the receiver deciphers something unauthenticated, and that can allow exploitation of software bugs in the decryption, or after. In the context of PGP, that argument does not hold: PGP is designed to support unauthenticated enciphered messages; and one legitimately wants to be able to read messages that one is not able to authenticate, for lack of the alleged signer's trusted public key.

Update: this answer is only about the soundness of the overall structure of the PGP format as described in the question; I do not touch "optimality", for lack of a definition; nor try to examine the detailed PGP formats and implementations (which are not state of the art), as discussed in that other answer.


Keep this fact.

By linear algebra, we can know that $M'_{1} \times M=M'_{2}$.

Let $\beta _i$ be a row of $M'_{1}$ which is correspond to $M'_2$ 's $[0,\ldots,0]$ row

and let  $\beta_i=[\beta_{0,i},\beta_{1,i},\ldots,\beta_{2^n-1,i}]$

Then we can know that $\beta_{i} \times M=[0,\ldots,0] $ by above fact.

So, if we define $b_i(x)=\beta_{0,i}x^0 \oplus \beta_{1,i}x^1 \oplus \cdot\cdot\cdot \oplus \beta_{2^n-1,i}x^{2^n-1}$.

Then,

\begin{align}
b_i(x)\oplus b_i(S(x))= & \bigoplus_{u\in\mathbb{F}_2^n}\beta_{u,i}\big(x^u \oplus S(x)^u\big)\\
= & \bigoplus_{u\in\mathbb{F}_2^n} \beta_{u,i}\big(\bigoplus_{v\in\mathbb{F}_2^n} \lambda_{u,v}x^v \big)\\
= & \bigoplus_{u\in\mathbb{F}_2^n}\big(\bigoplus_{v\in\mathbb{F}_2^n}\beta_{u,i}\lambda_{u,v}\big)x^v\\
=& 0
\end{align}

We can apply this formula similarly to the case of $[1,0,\ldots,0]$.


"Practical" operations supported by functional encryption?

I think you are confusing functional encryption and homomorphic encryption.

In a functional encryption scheme, using a secret key for some function $f$ on a ciphertext $c$ which is an encryption of $m$ allows you to get $f(m)$ in clear.
In an homomorphic encryption scheme, you can run some operation on ciphertexts, and get an encryption of the result, for example in multiplicatively homomorphic encryption, $c_1c_2$ encrypts $m_1m_2$ if $c_i$ encrypted $m_i$.

If you want some answers about homomorphic encryption, there exists homomorphic encryption for addition and multiplication, and somewhat fully homomorphic encryption, which supports both of these operation, but there is a noise growing with each operation that reduces the probability of decryption each time an operation is run -this is only a small problem because given the number of operation you want to make, you can set the parameters of your scheme according to that.

If you want answers about functional encryption, recents works follow two paths:

Ineficient, theoretical functional encryption for all circuits. Which is really interesting for science but is really not practical for the moment.
Predicate encryption, which is all-or-nothing decryption based on an attribute given in the ciphertext and an attribute of each secret key. There should be practical particular predicate encryption such as Attribute Based Encryption or Identity Based Encryption.

If you want practical scheme that give partial information on the message with depending on the key you have, I don't know of many, but I have a paper that will be presented at PKC15 about Simple Functional Encryption Scheme for Inner Product, this scheme enables you to decrypt $<x.y>$ given a $ct_x$ and $sk_y$.


In what mode does Signal applies cryptography over voice and data?

The double ratchet is used to derive symmetric key material. Then
it uses AES-256 in CTR mode for encryption and HMAC-SHA-256 for authentication. Also check the source code.


It was (like @mikeazo) said an encoding issue.
See the answer linked in the OP for an updated answer from @mikeazo.

This is what the code became:

from hashlib import md5

s1 = 'd131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70'

h1 = md5(bytes.fromhex(s1))
print(h1.hexdigest())


Make AES CBC more secure by destroying each block?

Does it add "more security" [...] flipping a bit (or two) of each AES block and store information about the flips alongside with the key and IV in the RSA encrypted part (so that the recipient can decrypt properly)?

This would essentially be a stream cipher applied to the ciphertext, as a stream cipher encrypts by unpredictably deciding for each bit whether it should be flipped or not.

So this additional scheme can be seen as a custom stream cipher and will most likely add very little security beyond the existing encryption.

  Background of the question is the idea that an attacker, who "sees" the AES encrypted file, needs maybe more time and computing power to run a brute force attack because even when he has the right key and IV the decryption would fail because the blocks are all invalid?

CBC has no notion of "invalid decryption" (beyond padding errors) and so the adversary would have to decide based on the "deciphered" contents whether the decryption was ok or not.


Why when I perform RSA 5 times do I get my original input back out?

I read the question as:

  Why is it that often, iterating RSA encryption just a few times cycles back to the original value, when the public modulus is $N$ is small?

With $N$ square-free and $\gcd(e,\varphi(n))=1$, textbook RSA encryption
$$\begin{align}E: [0,N)&\to[0,N)\\
x&\mapsto x^e\bmod N\end{align}$$
is a bijection, equivalently a permutation of the set $[0,N)$.

By the pigeonhole principle, cycling any permutation of a finite set will loop back to the starting point after a number of iterations bounded by the set size $N$. It is easy to show that for a random permutation and a random starting point, probability of cycling on or before $i$ steps is exactly $i/N$.

But if for example we take $e=37$ and $n=13333=67\cdot199$ then indeed we observe that starting from most $x$ we cycle after just $5$ iterations (and for some $x$, e.g. $x=937$, that's down to $1$). This calls for explanation.

Restricting to $N=p\,q$, define $E_p(x)=E(x)\bmod p=x^e\bmod p$, and $E_q(x)=E(x)\bmod q=x^e\bmod q$. By the Chinese Remainder Theorem, the cycle length of $E$ starting from $x$ is the Least Common Multiple of the cycle length of $E_p$ starting from $x\bmod p$, and the cycle length of $E_q$ starting from $x\bmod q$.

When cycling $E_p$ for $k$ iterations starting from $x$, we reach $\displaystyle x^{\left(e^k\bmod\left(p-1\right)\right)}\bmod p$ (by Fermat's little theorem). It follows that whatever the starting $x$, we always are back (though not necessarily first back) to the starting point after making a number of iterations equal to the order of $e$ in the multiplicative group $\Bbb Z_{p-1}^*$ (notice that $\gcd(e,\varphi(n)=1$ insures $\gcd(e,p-1)=1$ and thus that $e$ belongs to that group).

In our example $e=37$, $p=67$, $q=199$, and it happens that $e^5\bmod(p-1)=1$ and $e^5\bmod(q-1)=1$, hence both $E_p$ and $E_q$ cycle after $5$ steps (or just $1$, depending on $x$), and $E$ inherits that property.

But why are short cycle relatively common for moderate $N$?

Define the decomposition of $p-1$ (resp. $q-1$) into prime factors to be $p-1=\prod p_i^{\alpha_i}$ (resp. $q-1=\prod q_i^{\beta_i}$). The order of any element of $\Bbb Z_{p-1}^*$ divides the Least Common Multiple of the $(p_i-1)\,p_i^{\alpha_i-1}$. Thus when iterating $E$, we always are back (though not necessarily first back) to the starting point after making a number of steps equal to the Least Common Multiple $\ell(N)$ of the $(p_i-1)\,p_i^{\alpha_i-1}$ and $(q_i-1)\,q_i^{\beta_i-1}$. I'm still trying to track the name of this $\ell(N)=\operatorname{lcm}(\lambda(p-1),\lambda(q-1))$ (where $\lambda$ is the Carmichael function used for computing the lowest possible private exponent $d=e^{-1}\bmod\lambda(N)$ in RSA, but here applied to $p-1$ and $q-1$).

Even without a name, it can be computed and graphed.

The $p_i-1$ and $q_i-1$ are composite (or $1$), which increases the potential for common factors. Due to this effect, $\ell(N)$ often ends up with sizably less bits than $N$. For a particular $e$, some further factors of $\ell(N)$ may disappear. This explains the phenomenon.

In our example $p-1=66=2\cdot3\cdot11$, $q-1=198=2\cdot3^2\cdot11$, thus $\lambda(p-1)=2\cdot5$, $\lambda(q-1)=2\cdot3\cdot5$, hence $\ell(N)=2\cdot3\cdot5=30$, and for any $e$ the maximum cycle length must be a divisor of that. It happens that the choice of $e$ further reduces that maximum cycle length to $5$.

Being more rigorous is possible. But a convincing meta-argument that we need not worry for cycles in RSA encryption from a security perspective when $N$ is in the thousands bits, is that if we could, that would be a great way to factor $N$; but experience shows that's not.

More precisely: if we could find one $x$ and compute enough $x_{i+1}=E(x_i)$ starting from $x_0=x$ that we reach¹ $x_k=x$ for $k>1$, then computing $\gcd(N,x-x_i)$ would² have factored $N$ much before: when $i$ reached the point when $E_p$ or $E_q$ first cycled. That's a passable factoring algorithm, but³ it's less efficient than GNFS or ECM, and even Pollard's rho.

Reference: Ronald L. Rivest, Robert D. Silverman, Are ’Strong’ primes needed for RSA?.

¹ Thus deciphering $x$ by taking $x_{k-1}$. That would be a threat to RSA encryption: the so-called cycling attack.

² With overwhelming likelihood, since there's no reason³ $E_p$ and $E_q$ first cycle simultaneously.

³ Under heuristic grounds well verified in experimental factorization.


Appropriate scrypt parameters when generating an scrypt hash

$r$ determines the sequential read size. This should only be changed if you have custom hardware that has a memory subsystem with different characteristics. It takes time to pull data from main memory, and the sequential read size allows the memory latency and CPU processing to be well-balanced on your system. Treat it like a constant unless you know what you're doing. Too large and your hash could be weaker than you expect as it allows an attacker to use a slower, cheaper memory system; too small and your computer will process it inefficiently. May be any positive number. $16$ is probably good today. Also note that $r = 1$ disables a mixing step.

$N$, with $r$, determines the memory block size and hashing iterations ($128\cdot N\cdot r$ bytes, $2\cdot N\cdot r$ rounds of hashing). This is the one you change, and you should make it as big as your usage can handle. Some implementations of the scrypt algorithm only allow powers of $2$, but could be any value greater than or equal to $2$ theoretically.

$p$ determines the number of parallelizable iterations. It allows you to increase hashing power over $N$ alone. Best if you are memory restricted and can't increase $N$ more, or if you want to use multiple processors to compute more hashes in the same time (if you can afford $p$-times more bytes). But you should prefer larger $N$ over larger $p$ in general, as $N$ is responsible for the memory-hardness that makes scrypt unique. May be any positive number.

There are maximum limits to these numbers, but they almost don't need to be worried about because the memory requirements would be astronomical.

Sadly there isn't a lot of discussion or analysis of the parameters, and even fewer about $r$, leading to many misconceptions.


Mitigating private key loss for the average non-technical user

Splitting your key by just splitting into partial strings (doesn't matter if it's every 3. symbol or consecutive symbols) is a terrible idea, because you hand out actual information about your key - to them and to everyone who compromises their system.

For RSA this is actually a real problem, because partial knowledge of the private key makes Coppersmith's attack possible. In the original attack the known bits had to be either the least or most significant bits, but the attack has been refined quite a bit. For example, Reconstructing RSA Private Keys from Random Key Bits by Heninger and Schacham (2009) just need a fraction of $0.27$ random bits of the private key and a small exponent. In that paper the related work section gives a good overview over previous works.

As a refinement for the splitting:
I suggest looking into secret sharing schemes (e.g. Shamir's secret sharing), so that at least no one with less than 3 shares can't recover any information about the key. But still, the security of your key becomes dependent of the other parties keeping your key secure and not be malicious. And of course you need a stragety to change your key and update their shares. Reasons for this might be that you want to change the list of trusted persons, one of them lost all the date on their computer, etc.

In general, the dependency on their security is a practical issue: If you use proper implementaions of current state-of-the-art encryption schemes, it is much more likely that key management and storage contains a security weakness than the actual encryption.

Regarding the last part: If you worry about one friend loosing his data at the same time as you (roughly the same time, before you could redo the splitting process), secret sharing schemes can be set up so that you need $k$ out of $n$ shares to recover the key. And it doesn't matter which $k$ of those $n$ shares you use.


Bitwise method of generating r for RSA-KEM

Here are a few options.  I include modular reduction and rejection sampling because I suspect they are less costly than you worry.

What you suggested, roughly: Pick $r$ uniformly in $\{0, 1, 2, \dots, 2^{\lfloor\log_2 n\rfloor} - 1\}$.

If there were an IND-CCA2 or NM-CCA2 adversary with success probability $p$ against RSA-KEM with $r$ uniform in $\{0, 1, 2, \dots, n - 1\}$, the success probability of the same adversary can't be more than $2p$ since we're removing less than half the possible space of $r$.  If $2p$ was too high, then $p$ was almost certainly too high already.  If you set the high byte to zero, as you suggested, then you remove more of the output space and it's $256p$ instead of just $2p$.

Theoretical concern: The standard security reduction to the RSA problem[1], which demonstrates how to turn an IND-CCA2 attacker into a procedure to compute $e^{\mathit{th}}$ roots modulo $n$, would no longer apply, because a little under half the space is guaranteed not to be covered.  It's a little hard to imagine that the general RSA problem is hard, but becomes easy if you restrict it to this domain; however, the more space you eliminate, the more irrelevant the reduction becomes to justifying the security, so better to set the high bit to zero than to set the high byte to zero as you suggested.
Modular reduction: Pick $r$ uniformly in $\{0, 1, 2, \dots, 2^{\lfloor\log_2 n\rfloor + k} - 1\}$ where $k$ is, say, 64, or 256 if you're paranoid or $\lfloor\log_2 n\rfloor$ if you're really paranoid, and reduce modulo $n$.

You don't need a general purpose division routine: You can easily reduce $r$ modulo $n$ in constant time with Barrett reduction using only two multiplications and a subtraction, if you precompute $2^{\lceil\log_2 n\rceil}/n$ (with bit-by-bit long division in constant time if $n$ is ever secret), as long as $r < n^2$.

This doesn't give a uniform distribution, but it's awfully close—much closer than option (1), if for no other reason than that it doesn't completely exclude any of $\mathbb Z/n\mathbb Z$ like (1) does.  (Exercise for the reader: Quantify the modulo bias in, say, total variation distance—this puts a similar bound on the advantage of an IND-CCA2 or NM-CCA2 adversary vs. a true uniform distribution.)
Rejection sampling: Pick $r$ uniformly in $\{0, 1, 2, \dots, 2^{\lceil\log_2 n\rceil} - 1\}$, and start over if $r \geq n$.

Since $2^{\lceil\log_2 n\rceil}/2 < n < 2^{\lceil\log_2 n\rceil}$, the number of trials is geometrically distributed with probability $p < 1/2$; the expected number of trials is just over 1 and well below 2.  You will obviously never see more than 128 trials—for a 4096-bit RSA modulus, you need to generate much less than 4096 KB of data.

This guarantees a uniform distribution for $r$ in $\{0, 1, 2, \dots, n - 1\}$.


Why a Unitary Matrix in Quantum Cryptography?

Short (unhelpful?) answer: the transformation are unitary, because quantum physics says all transformations on quantum states are unitary. So your question boils down to “Why are unitaries the only allowed transformations?”.

For two reasons:

Quantum mechanics restricts the allowed transformation on quantum states to  be linear, transforming the vector $|ψ\rangle$ to $V|ψ\rangle$, where V is a matrix. I have no obvious intuition on why the transformation have to be linear$^\dagger$, except that

it gives an elegant and simple mathematical theory;
attempts at constructing nonlinear quantum mechanics have all lead to problematic consequences, e.g. in causality.

Once you accept the linearity of the transformation $V$, the unitarity comes from the conservation of the norm of  $|φ\rangle$, since this norm corresponds to the sum of probabilities of the different measurement results, which is therefore $1$. We have then, for all $|φ\rangle$,
\begin{align*}
\langle φ|φ \rangle &=1 & \langle φ|V^\dagger V|φ\rangle=1.
\end{align*}
Since it is true for all $|φ\rangle$, it implies that the eigenvalues of the Hermitian operator $V^\dagger V$ are all $1$, that is $ V^\dagger V=\mathbb I$: in words, $V$ is unitary. Another (maybe mor intuitive) explanation of this is that unitaries are the only matrices preserving the the scalar products $\langle φ|ψ\rangle$, which measures the distinguisability of states $|φ\rangle$ and $|\psi\rangle$.

$\dagger$: if anyone knows an intuitive explanation of the linearity of QM, I’d love to read it!


Is Polly cracker non-circuit approach?

Polly Cracker is non-circuit.

  Can we construct fully homomorphic encryption scheme based on non-circuit approach?

The best info for this I could find comes from a recent paper proposing a non-circuit approach due to Xiao, et al..

They identify a number of non-circuit systems, but go on to say that "they all either have been broken or lack conclusive security evidence."

They then propose a symmetric system which reduces to the problem of factoring.

So it seems that the answer is yes, one can be constructed. It is still an active area of research, however, and I personally wouldn't use the proposed systems yet.

Now, what I am exactly not quite sure of is what non-circuit means? In the paper I reference, they state:

  The main works on homomorphic encryption algorithms are circuit based. They develop the encryption schemes and computation algorithms considering a single bit plaintext. All operations on various operand types can then be achieved by constructing the corresponding circuits.

So is a circuit approach simply that the cryto algorithms assume a single bit plaintext? If that is the case, then there are many, many more FHE systems which are "non-circuit". In fact, the BGV system does not require single bit plaintexts. So perhaps I am missing something in the circuit vs non-circuit discussion.


What are the known weaknesses in AES and is it being considered for upgrade or replacement?

The two main weaknesses where AES shows its age are the 128bit blocksize and the fact that AES 192 and 256 have far less security margin than the pure key size would suggest (some reasons for that here).

Besides that the concept of a block cipher with modes begins to be regarded as risky (authentication, padding, nonces) and more higher level primitives should be used in APIs (newer approaches like NaCl secretbox).

So from a crypto community standpoint it shows its age but is still time proofen and not broken. Especially since alternatives enjoy less general acceptance (especially if compliance voodoo is required).

I would argue long term archives cannot escape the voodoo argument for now, so they do rely on AES (at least in western geographies).

I think a successor will provide more than 128bit block size (or state), start with large key sizes and support efficient authenticated methods and maybe some support for parallelisation. It will hopefully define a approved family of modes/parameters in favor of free composition of primitives.


Decryption that is easy for humans and hard/impossible for computers

My opinion is that in order to design a cipher that is easier to decrypt by a human than by a competently programmed computer, the only working option is making the ciphertext or key unavailable to the computer due to some input limitation (like, the ciphertext or key is 3D-engraved in plexiglass, and the computer has no 3D vision); but that could be circumvented by an upgrade of the computer. With the relevant data available, no matter if we consider decryption with or without the key (the question is ambiguous about that), decryption is data processing, and properly programmed computers tend to vastly outperform humans at that.

Update: there are areas where the visual capabilities of the human brain (or possibly capabilities pertaining to other senses like audition) make humans somewhat competitive with computer programs; like finding a good move at the game of Go or Chess, an approximate solution to the Traveling Salesman Problem, or identifying some flaws in a pseudo random generator. I challenge that it allows constructing a cipher as asked, for two reasons:

For identification of flawed RNG, and arguably the TSP, there is evidence that humans perform significantly worse than computer programs primarily and competently designed for speed at the price of some error rate or non-optimality. Even for games, computer programs exist that beat the best humans with heavy hardware, and 99% of humans with a mere PC.
In tasks where humans are even mildly competitive with proper computer programs, humans tend to find only approximate solutions, and different humans will often find different solutions. It is hard to turn such capability into reliably deciphering a ciphertext, as necessary to answer the question.


Can I find a specific SHA512 for an partially-known string?

What you are describing is a second-preimage attack on SHA-512, and you will find it quite infeasible, requiring an expected $2^{512}$ hash computations.

Now, consider your friend's position.

SHA-512 is a one-way function, and knowing part of the plaintext does not help reverse it to recover the whole plaintext from the hash.

Instead, a brute-force approach is necessary. Your friend will calculate hashes of all possible inputs matching the condition you tell  him (ending with "ing"). Once he finds a match, he will conclude that he has found your string.

What does your friend know about your string? Its length? The set of characters you might use? The fact that you posted it on stackexchange? Your best hope is that your friend will not find your string, because if he does, you will be unable to lie and present another string with the same hash.


It has to do with the alignment between the size of cipher the key and the size of a round key. Since a 256-bit key is twice the size of a round key, the nonlinearity of the key schedule would be aligned to every other block, and that is bad.

Here is an example of the round keys generated by the key schedule for a key (hex bytes) of value 0000000000000000000000000000000000000000000000000000000000000001:

00  00000000 00000000 00000000 00000000
01  00000000 00000000 00000000 01000000
02  637c6362 637c6362 637c6362 637c6362
03  fb10fbaa fb10fbaa fb10fbaa fa10fbaa
04  cf51a96f ac2dca0d cf51a96f ac2dca0d
05  6ac88f7d 91d874d7 6ac88f7d 90d874d7
06  c131c8f9 6d1c02f4 a24dab9b 0e606196
07  c11860ed 50c0143a 3a089b47 aad0ef90
08  a19db82e cc81bada 6ecc1141 60ac70d7
09  118931e3 414925d9 7b41be9e d191510e
10  0aa339ef c6228335 a8ee9274 c842e2a3
11  f9a5a9e9 b8ec8c30 c3ad32ae 123c63a0
12  ea6ad234 2c485101 84a6c375 4ce421d6
13  d0cc541f 6820d82f ab8dea81 b9b18921
14  173c1ad3 3b744bd2 bfd288a7 f336a971

And here is what happens when you take out the extra SubBytes:

00  00000000 00000000 00000000 00000000
01  00000000 00000000 00000000 01000000
02  637c6362 637c6362 637c6362 637c6362
03  637c6362 637c6362 637c6362 627c6362
04  c9d6739b aaaa10f9 c9d6739b aaaa10f9
05  c9d6739b aaaa10f9 c9d6739b abaa10f9
06  50b4df55 fa1ecfac 33c8bc37 9962acce
07  50b4df55 fa1ecfac 33c8bc37 9862acce
08  dbf275cc 21ecba60 12240657 8b46aa99
09  dbf275cc 21ecba60 12240657 8a46aa99
10  358c2f70 14609510 06449347 8d0239de
11  56f04c12 771cf672 6538f025 ef7e5abc
12  5053dcee 443349fe 4277dab9 cf75e367
13  9985af75 ee995907 8ba1a922 64dff39e
14  5b1042a3 1f230b5d 5d54d1e4 92213283

It can be seen as far as round 9 the round keys are still extremely linear, and because the sbox application is performed every other round key, 3 of the 4 subkeys for the round keys are identical to a neighboring round key up to the 9th round, and the 4th only differs by a 4 bit maximum.


One time pad (OTP) perfect secrecy with different key space

It cannot be perfectly secret : if $C = M \oplus K$ is your encrypted message, all the possible values of $M$ do not happen with equal probability. Indeed, the case $M = C$ (corresponding to $K = 0$) is twice less liquely to happen. You cannot have $H(M) = H(M|C)$; if e.g. $M$ is drawn uniformly at random, the distribution of $M$ given $C$ is clearly not the uniform distribution.

  What's the probability of constraints 1? If we can find also we can say that given scheme is perfectly secret or not.

The probability distribution of $M$ given $C$ is $1/2(1/2^n + 1/(2^n-1))$ for every $M \neq C$, and $1/2^{n+1}$ for $M = C$. Hence the distribution of $M$ given $C$ is clearly not uniform.


What is the purpose of placing the most significant byte first?

$24$ expressed as a 16-byte hexadecimal number is
$$00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;00\;18$$
The most significant byte is the leftmost. $00011000_2$ comes last, not first.

It makes no difference to the security of the algorithm whether the most significant byte comes first or last. What is important is that everybody agrees on this point.


What happens to NORX if the same (key, nonce, header data) triple is reused

It depends on the attack model. In certain (realistic!) attack models, such as the one used for the BEAST and related attacks on TLS, security breaks down further—it becomes possible to decrypt messages in a byte-by-byte fashion!

This is not specific to NORX; any online authenticated encryption scheme will be vulnerable to the CPSS attack if misused repeatedly, though supposedly "misuse-resistant" modes do not lose security instantly (unlike e.g. AES-GCM). Modes that resist this kind of misuse necessarily need to perform two passes over the message, rendering them offline (i.e., the entire message must be accessible during encryption).


Would asymmetric cryptography be feasible in World War II?

Sure, you can do Diffie-Hellman or RSA by hand if you have to.
And you don't need the bit length we use today with powerful adversaries.
I'm not an expert on WW2 computational machines but I won't be surprised if something to do modular exponentiation could be built using WW2 technology given sufficient motivation.
A modern cryptographer in WW2 could make truly unbreakable ciphers. With authentication, key exchange, good randomness, and all the good stuff we have now.


How should short term keys (keys stored in RAM or volatile memory) be described by PKCS#11?

Is the proper way to distinguish between keys that are more temporary/stored in volatile memory and those stored in non-volatile memory to label them "session objects" or "token objects" using the CKA_TOKEN attribute?

Yes, temporary keys are indeed session objects.

  Or is there another attribute or property in the spec that I am missing?

No there is no other property that I know of. Just setting CKA_TOKEN to false should do the trick.

  If a power-off event occurs for a device, is it valid to consider that to be an event which closes the session and allows session objects to be destroyed?

Absolutely. I'd be very annoyed if a FIPS or Common Criteria verified product would not invalidate sessions on reboot (or, more likely, automatically remove all sessions on power off).

When the power is off the token may be transported to Siberia without the device noticing this. Clearly this should be reason to invalidate a session.

Destruction of keys when they are no longer needed are strong requirements both for FIPS and Common Criteria.


Why does the Node crypto library do Diffie Hellman this way?

My understanding of Diffie Hellman is that both parties only ever need to generate a single random number, not a public/private key.

That is not correct.

Wikipedia’s entry covers it pretty well. Once two parties have agreed upon a domain (the (g, p) pair) each member generates their own private key. Their shared secret is equal to

(g ^ (a * b)) % p

where a is Alice’s private key and b is Bob’s. Of course, each side can do this calculation without the other party revealing their private key.


Double discrete logarithm on elliptic curve

However, in the case of elliptic curves, $h^x$ is interpreted as the point
  $h$ added to itself $x$ times, resulting in curve point, $[x]h$

That is incorrect; as you had stated previously:

  $h \in \mathbb{Z}_p^*$ is an element of order $q$.

That is, $h$ is not a point on the elliptic curve; instead, it is a member of a finite field, and so $h^x$ is interpreted as $h$ multiplied to itself $x$ times (using the field multiplication operation).

  The folklore is that any cryptographic scheme based on a modular multiplicative group can be translated to an additive curve group.

One has to be careful; there are schemes such as SRTP that really rely on a modular field (rather than a modular group).

However, even in those cases where things can translate nicely (which are actually most of them; exceptions are comparatively rare), you do have to remember that, while the actual group operation (modular multiplication) translates into point addition, the operations on the exponents (which are done modulo $p-1$ in the modular case) translate to integer operations modulo $q$ in the Elliptic Curve case.


AWS is complicated, and most of the details are not in scope for this site.

  We will need to store AWS credentials in plain text on servers (our server as well as client's) to call KMS, how is it better than storing the secret key itself? (Given that we could share the secret key once, say in a registration successful email)

You said clients might not be on EC2, which I interpret to imply that your servers will be.  AWS is designed so that EC2 instances can authenticate with services like KMS without you having to store secrets in them—rather, EC2 can issue ephemeral credentials to your instances when it creates them.

That doesn't however by itself solve how to make sure that your EC2 instances and your clients will be able to share a secret key, or whether that's a good idea in the first place for your problem space. I think you need to find an AWS consultant and possibly a cryptographic engineer.

  Secret key will be transferred over the wire as plain text to be encrypted and after decryption by KMS, is this a safe practice?

The connection to KMS is encrypted.


What value for a Rfc2898 (PKBDF2) is overkill?

what value or iteration count is enough?

So in NIST SP 800-63B a baseline of 10,000 iterations is recommended. Going below that is a really bad idea.

Now of course the actual guidance is "do as many iterations as you can afford", which usually amounts to "do as many as your users are willing to wait for". If 65,000 already take 1 second and your users will complain enough about that to go for a different application lower the value. If they're patiently waiting 5 seconds, go for the iteration count that takes 5 seconds.


Can I replace DH by a post-quantum key exchange in IBAKE for post-quantum identity-based authenticated key exchange?

The security proof for the original IBAKE protocol is found in IBAKE: Identity-Based Authenticated Key Exchange Protocol.  The IBAKE scheme described there uses an Identity Based Key Exchange to authenticate an ephemeral elliptic curve Diffie-Hellman key exchange.  The scheme uses two different elliptic curves one for the ephemeral elliptic curve Diffie-Hellman exchange (ECDHE) and a pairing friendly curve to serve as the basis for the Identity Based Key Exchange.  The security proof requires that the ephemeral key exchange be secure but it does not rely on any particulars of the ephemeral key exchange being used.  Therefore on could replace the quantum vulnerable ECDHE with a quantum secure key exchange like
SIDH or New Hope and the proof of security of the protocol will still hold.

Using SIDH instead of a Lattice Based Key exchange would keep the protocol packet sizes within a few hundreds of bits of the original IBAKE scheme.  Using and ephemeral SIDH (SIDHE) in place of ECDHE in IBAKE would lengthen the useful lifetime of IBAKE until an adversary actually has a quantum computer because the SIDHE exchange would protect against the well know "store then break" attack.


Public key encryption and message integrity

If someone tampers with the message in between a. what kind of tampering can be performed and b. wouldn't the decryption process fail since the message ought to be malformed due to the tampering?

That depends on the format. In general, yes, tampering is detected. That may even be the reason that the protocol is insecure, as it could lead to padding oracle attacks.

Note that an attacker can also simply encrypt a different message as encryption doesn't add integrity or authenticity, and the public key is commonly considered, well, public.

  c. Does asymmetric encryption like RSA ensure message integrity without hashing the message with an HMAC? or is hashing necessary only when utilizing symmetric encryption?

No. Generally the message is first signed and then encrypted. If a symmetric key is already shared the parties might as well encrypt with it - or with a key derived from it.

If a symmetric key is wrapped (encrypted) and sent, you need to verify that the secret key has been agreed upon successfully - as explained in the next section.

  For example at initiation time of the TLS handshake when the client encrypts with the server's public key the symmetric key that's going to be used for the rest of the transaction, does it also uses hashing?

No, but as the symmetric key is later used for a HMAC over the previously communicated messages, it doesn't matter if the symmetric key was changed. If it was, the authentication tag calculated using HMAC value will be incorrect and the handshake will fail.


Hashing a password with SHA256 on the client then bcrypt on the server

A problem with your proposed solution is that the digest of the password is now "password equivalent". So, what does hashing it before sending it gain you?

That said, I don't think either of your concerns are concerning (or should be concerning). For the first, see this. If anything, most passwords will have less than 256 bits of entropy anyways. For mixing hashes, see this and this.

A better solution would be to use SRP for which a javascript version already exists.

That said, you are aware of the problems with doing crypto in javascript, right?


Comparable or partially homomorphic public key derivation for signatures?

If I understand you correctly, you want that given $\mathit{pk}, \mathit{pk}'$, one can publicly decide whether or not $\mathit{sk} < \mathit{sk}'$ (lexicographically) for the corresponding secret keys.

Such a signature scheme would inherently be insecure.
This is because given your public key $\mathit{pk}^*$, anyone would be able to run a binary search to find the underlying secret key $\mathit{sk}^*$.

For example, the attacker could choose $\mathit{sk} = 10000000$, compute the corresponding $\mathit{pk}$ and then run the lexicographic comparison on $\mathit{pk}$ and $\mathit{pk}^*$ to find out whether or not your key $\mathit{sk}^*$ starts with a 1. If so, checking whether $\mathit{sk}^*$ is still lexicographically larger than $11000000$ can be done similarly and reveals the next bit, etc.

After $n$ comparisons (assuming n-bit secrets), the secret key is revealed. Of course, this also generalizes to larger alphabets.


Length of key: symmetric vs asymmetric algorithms

Point 1: If two symmetric algorithms with no attacks better than brute force but different key lengths are to be compared, then simply comparing the key lengths tells you which is stronger. A larger key is stronger. Note that keys larger than 256 bits are typically slower and provide no practical increase in security (as in, even with quantum computers they'll take centuries to brute-force). Note that the "no attacks better than brute force" is the key here, FEAL-NX with a 128-bit key is thoroughly broken and far less secure than AES with a 128-bit key.

Point 2: The security of asymmetric algorithms is less related to key length because there are attacks better than brute force for all existing asymmetric algorithms. For a trivial example RSA uses large prime numbers, which must be odd, and thus one can skip the even numbers when performing trial division, thus dividing the brute force search time in half. The actual improvements on brute force search are more complicated and vary significantly from algorithm to algorithm.

Point 3: As symmetric and asymmetric ciphers are totally different things with different purposes it's like comparing the cargo capacity of a freight train with that of a container ship. The same units (mass or volume) are used, but they do very different things and can't simply be exchanged. Trains don't float.


Is it possible to alter the plaintext message without altering the ciphertext?

Yes, but typically not in any controlled way.
Essentially you're asking whether two different encryption parameterisations map to the same ciphertext space and that is precisely what most cryptosystems do.
Let's take AES-ECB as an example. Suppose that I have a key $k_0$ and a plaintext $P_0$ and a ciphertext $C=\mathrm{AES}_{\mathrm Enc}(k_0,P_0)$. Now I can pick any other key $k_1$ and compute $P_1\mathrm{AES}_{\mathrm Dec}(k_1,C)$ and lo and behold $C=\mathrm{AES}_{\mathrm Enc}(k_1,P_1)$. However $P_1$ is almost certainly gibberish. To try and control $P_1$ is to say I have a matched plain and cipher and want to find the corresponding key. This is intended to be hard.
To take a public key example, let's consider El Gamal on an arbitrary additive group $\langle G\rangle$. Pick a private key $a$ and public key $A=aG$ and off we go. For a plaintext message $M_0$ some one chooses a random $r$ and sends $(R,C)=(rG,rA+M_0)$. Now choose any other private key $b$ which would have corresponding public key $B=bG$ and we decrypt $(R,C)$ using this key to get $C-rB$ which we call $M_1$. Note that $M_1=M_0+r(B-A)$ so to select $M_1$ I need to know $r$ which would involve solving a discrete logarithm.
There is one cryptosystem where the alternative plaintext can be pretty much completely specified and that is the one-time pad. It's a straightforward exercise to show that any OTP cryptogram can be written as any plaintext message of the same length enciphered with a different OTP which differs from the original OTP by the difference of the messages.


Which symmetric algorithm should I use for storing files in untrusted servers?

Just a note: AES is not a encryption scheme, it is technically just a block cipher; though it is a fine one.

To create a cipher you need to use it in a mode like counter mode.

To obtain chosen ciphetext security (which is the usual aim) you should use an authenticated encryption scheme such as Galois/Counter Mode.

As usual, don't try make it yourself, use a premade secure library.


Count elements with a given order in the multiplicative group $n=pq$ (RSA)

It's not hard to compute, the number of elements with order precisely $r$ is:
$$F_{p-1, q-1}( \phi(r))$$
where $F$ is this function:
If the prime factorization of $r = r_1^{e_1} r_2^{e_2} ... r_n^{e_n}$ then
$$F_{p-1, q-1}(r) = F_{p-1, q-1}(r_1^{e_1}) \cdot F_{p-1, q-1}(r_2^{e_2}) \cdot ... \cdot F_{p-1, q-1}(r_n^{e_n})$$
If $s$ is prime and $e>0$, then $F_{p-1, q-1}(s^e)$ depends on $\gcd( s^e, p-1) = s^a$ and $\gcd( s^e, q-1) = s^b$
If $a, b < e$, then $F_{p-1, q-1}(s^e) = 0$ (i.e. there are no elements with that order)
If $a=e, b < e$, then $F_{p-1, q-1}(s^e) = s^b$
If $b=e, a< e$, then $F_{p-1, q-1}(s^e) = s^a$
If $a=b=e$, then $F_{p-1, q-1}(s^e) = s^e + s^{e-1}$
This allows us to compute the number of elements in all cases.


Number of cycles in cipher feedback mode (CFB)

In CFB-mode you effectively have a data-dependent stream cipher and you'll need $\lceil\frac{l}n\rceil$ block cipher calls or "cycles" as you call them to process the full message, where $l$ is the mesage length (in bits), $n$ the block size (in bits) and $\lceil\cdot\rceil$ is the ceiling function.
However, you get the encryption of the $i$-th plaintext block after the $i$-th "cycle" or block cipher call. This can be seen if you look at the formal definition of the CFB-mode which reads (in this case):
$$c_i=p_i\oplus E_K(c_{i-1}),\quad c_0=IV$$

where $c_i$ is the $i$-th ciphertext block, $p_i$ is the $i$-th plaintext block, $\oplus$ is bitwise XOR and IV is an initialization vector.


The EAX mode of operation is defined for 128 bit block ciphers. It consists of a combination of CTR mode for confidentiality and OMAC for authentication and nonce derivation. CTR mode does not require padding, but OMAC does, since it is based on CBC-MAC, when the length of the plain text is not a multiple of 128 bits.

Hence, such specifications might mean one of two things.

It means that standard OMAC padding is implied and doesn't have to be specified twice.
It means that the plain text will always be an integer multiple of 128 bits, meaning that the OMAC padding algorithm would never have to be invoked.

Hence, if the API doesn't require you to explicitly specify the OMAC padding specified in the EAX paper, NoPadding will comply with the security claims in the EAX paper.

That said, in some cases there are additional security requirements for hiding the length of the plain text, by padding each message to a fixed length, but that falls outside of the scope of EAX, as well as most (all) other AEAD modes as well.


Yes, EME is a wideblock cipher. Theorem 1 (in Section 4, top of page 5) states that EME is secure as a wideblock (tweakable) cipher under the assumption that AES (or whatever blockcipher you use) is secure.

Specifically, to someone who doesn't know the key, EME will look like a set of random, independent permutations (one for each tweak). This is true even if the attacker can both encrypt and decrypt whatever they wish. This in turn implies that all the bits get scrambled upon decryption if a single ciphertext bit is corrupted. (The definition at the bottom of page two captures these ideas, and then Theorem 1 states that EME meets this definition).


Tamarin-prover issue on a basic Diffie-Hellman Exchange

Did you try asking this on the Tamarin google group? I'm guessing that's the right place to ask such a question and get a good answer.
Though from a first glance, I would guess that the empty trace (or any trace in which no Secret fact occurs) satisfies your second lemma, and this is thus entirely expected behavior.
Intuitively, your second lemma states: there exists a trace, such that (if a Secret fact occurs in it, then the adversary knows the secret). This trivially holds for any trace without a Secret fact, and thus the lemma indeed holds.
Or, put differently, your second lemma is not the negation of the first lemma.


Why does PGP still use the Fermat primality test? What if it hits one of the Carmichael numbers？

It is a choice of the designers of PGP to stick to Fermat test. There are some nice talk since 1994

sci.crypt: 1994 - Why Fermat test for PGP primes

Critique of PGP Key Generation

and PGP Attack FAQ: The asymmetric cipher

The quote from the last;

The Carmichael Numbers
Unfortunately, there are some numbers which are not prime and which do satisfy the equation $b^{n-1} \bmod n$. These integers are known as the Carmichael Numbers, and they are quite rare. The reason for this is that a Carmichael Number must not be divisable by the square of any prime and must be the product of at least three primes). The first three Carmichael Numbers are: 561, 1105, and 1729. They are so rare, in fact, there are only 255 of them less than $10^9$. The chance of PGP generating a Carmichael Number is less than 1 in $10^{50}$.

So, even there are other alternatives to Fermat Test, they still use it.
Here the oeis/A002997 for the  Carmichael numbers;

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461

If it hits a Carmichael number then it will factor into smaller primes like $512461 =31 \cdot 61 \cdot 271$. But it can still work as a normal RSA and fool us.
Once a fast probable prime obtained then one can use proof methods instead of AKS. We may consider this as modern sieving.

1993, Atkin and Morain, Elliptic Curve and Primality Proving which can also provide a primality certificate for rapid verification which is not possible with AKS in which the number itself considered as the self-certificate for its primality.
1983,1984, Adleman–Pomerance–Rumely primality test

If you want to use the AKS then use the faster variant of AKS test. And note that AKS  is a slow and deterministic primality-proving algorithm. Here a quote from DanaJ's great answer in Math.SE Fastest way to find if a given number is prime

Anyone who suggests actually using AKS in practice has never actually run it on numbers larger than 10,000 and should be ignored.


Need for 3 rounds in Luby Rackoff theorem

The simple answer is that fewer than 3 rounds can be easily distinguished from a random permutation. The 2-round Luby-Rackoff cipher on $2n$ bits, using random functions $f_i$ mapping $n$ bits to $n$ bits, consists of
$$
F(L, R) = (A, B),
$$
where $A = L \oplus f_1(R)$ and $B = R \oplus f_2(L \oplus f_1(R))$.

Now consider an attacker that wants to distinguish $F$ from a random permutation. First they send some arbitrary $(L_1, R_1)$ to the oracle, and get back $(A_1, B_1)$.

Next they send $(L_2, R_1)$, which results in $(A_2, B_2)$. Verifying that $A_1 \oplus A_2$ = $L_1 \oplus f_1(R_1) \oplus L_2 \oplus f_1(R_1)$ = $L_1 \oplus L_2$, the attacker is now pretty sure this is the Luby-Rackoff cipher.

What happens at 3 rounds is that no such distinguisher (querying only in the forward direction, of course!) is now possible. The proof relies on showing that collisions on the internal variables $A_i, B_i$ are necessary to mount any distinguisher, and then shows that those collisions are rare, in that you need approximately $2^{n/2}$ oracle queries to obtain one.


creating PKCS8 private keys with a PBMAC1 hash

Your link (2898) is actually PKCS5 which defines those two encryption schemes (with predefined cases for 1) and the MAC scheme. PKCS8 uses the ASN.1-flexible way (AlgorithmIdentifier) to identify the encryptionAlgorithm, but for specific values references the older PKCS5 v1.5 which had only the scheme now called PBES1 and PBKDF1. OpenSSL also supports the PBES2/PBKDF2 schemes from PKCS5 v2 and the PBE schemes defined in PKCS12 (see below).
PKCS8 does not support a separate authentication algorithm. All defined PBES1 and PBES2 schemes and most pkcs12PBE ones do use CBC mode with padding, which provides some protection against accidental corruption but not tampering.

PKCS12 is now the more common and arguably better way of transporting privatekeys plus usually related certificate(s). It does have a PBMAC on the whole container (technically optional but usually present) and PBE on the KeyBag and CertBag items in the container; even though certificates shouldn't need to be secret, by convention (or just custom) the CertBag is encrypted with weak 40-bit encryption, although OpenSSL has an undocumented option -certpbe none to leave it clear. PKCS12 originally referred to the older PKCS5 (effectively PBES1/PBKDF1) and added its own PBE/PBKDF scheme again with several predefined cases, plus its own PBMAC scheme. PKCS12 v1.1 changes this to prefer PBES2/PBKDF2 from newer PKCS5 for encryption while still documenting its own PBE schemes in Appendix C for backward compatibility, and still using its own PBMAC scheme.

If I had to speculate why the need for integrity protection wasn't appreciated at first, it might be that by 1990 most industry experience had been with wrapping symmetric keys, mostly for transport -- rarely storage, which was in special hardware instead -- and that customarily used a manually verified Key Check Value.


Importance of random number generation in Schnorr's signature

Note that the signature is $(s,e)$ where $s=k-xe$. If you can learn $k$ since it is predictable, then you can learn the secret signing key by computing $x = (s-k)/e$. Note that even without a concrete attack, the proof of security completely breaks down if the value $k$ is not chosen randomly.

Having said this, it is possible to change the scheme to be deterministic by including a random key $K$ for a PRF as part of the secret key and then generating the randomness needed to sign $M$ by computing $PRF_K(M)$. This actually is a good idea especially for DSA/ECDSA since repeating randomness there is a disaster
The proof that this is good in general is not difficult (a reduction to the PRF).


Simplified Key Wrapping to Achieve Only Confidentiality?

Your proposal is malleable, so in particular, confidentiality does not hold against a chosen-W' attack, which is the key-wrap analogue of a chosen-ciphertext attack. $\:$ Also, the fact that your

proposal concatenates s with p suggests that H can probably be evaluated too quickly.

Although that may be typical, it shouldn't be, since the time needed to try passwords

in a known way scales linearly with the time needed to evaluate the password hash.

This answer gives some better password-based key derivation functions.

The "best reason that it is better for key wrapping" is that AES is hopefully non-malleable.

(Note that AES should replace xor, rather than replacing H.)


How to prove that someone encrypted a specific (large) chunk of data

I may be interpreting your question incorrectly, but it sounds to me like you are asking if Caroline can prove (in court or whatever) that she can only gain access to some secret $S$ if both Alice and Bob collaborate in revealing it to her.  Unfortunately as you have currently set up the question, I don't think that is possible, because your question establishes that Alice knows the secret $S$ before any encryption is applied (it's "her data", as you put it).  Hence, it is always possible for Alice to simply tell Caroline $S$, regardless of whether Bob collaborates.

But, if we modify the set-up a bit, it is possible to prove what you want.  We need to assume that neither Alice nor Bob knows $S$, and in addition we need a trusted third party and a secret sharing scheme.  Only the trusted third party, Tim, starts off knowing $S$, and he can be trusted to a) not leak any information about $S$ to anyone at any point, and b) to reliably carry out the following three steps:

Tim generates a pad $P$ - a random string of bits equal to the length of $S$.
Tim establishes a secure channel with Alice (using e.g. secure public key exchange and PKI methods to prevent Man In the Middle attacks), and sends her the string $P \oplus S$.
Tim similarly establishes a different secure channel with Bob, and securely sends him $P$.

At this point, Tim has split the secret into two 'shares', and Alice and Bob only know what their own share looks like (i.e. random nonsense).

Alice and Bob then each encrypt their own share using authenticated encryption (e.g. AES-GCM) and their own secret keys.
Alice and Bob now send Caroline the encrypted shares.

This way, no one (aside from Tim) can know what $S$ is unless both Alice and Bob  reveal their shares (e.g. by sharing their keys with Caroline).  Knowing only one share gives you zero information about $S$ (besides the length), and as such if either Bob or Alice don't reveal their share then $S$ is safe.

As to any concerns about ensuring that Alice and Bob do their part (i.e. properly encrypt their shares) and don't simply forward their shares unencrypted to Caroline, I would note that simply forwarding the unencrypted shares to Caroline is equivalent to encrypting the shares but then revealing the keys to her -- so long as either Alice or Bob does their part properly Caroline cannot know $S$. It takes collaborative effort / incompetence by both Alice and Bob for $S$ to be revealed. If we cannot trust that at least one of the two will keep their key secret and properly run their part of the protocol then no scheme will succeed (so my scheme is not unique in that respect). But given my described scheme, one person doing their part properly is sufficient to keep Caroline provably in the dark.


Why don't block ciphers consist of a simple XOR operation with key like Stream ciphers?

If the construction of stream ciphers is already secure why does the construction of block cipher involve pseudo permutations and complex operations that makes block ciphers less faster?

A stream cipher consists of more than just a single XOR operation. They first have to spend time generating the key stream from the key and nonce/seed. They actually use many of the same operations and take about the same amount of time as a block cipher does to do so.

For example, Salsa20 is a stream cipher that uses addition, rotation, and XOR to generate the key stream.

After the key stream is generated, it is combined with the message via XOR.

The stream cipher is only secure if the key stream is unpredictable. The complexity and time goes into making the output unpredictable.

  Is a construction of a block cipher defined as just Xor-ing a block of bytes with a block of key bytes (removing all permutations and other operations) not secure?

Yes, such a construction is insecure. Suppose that the adversary knows a single plaintext message. They can simply subtract out the known message to retrieve the key, which allows them to subtract out the key from any other ciphertext to recover the plaintext message.

$c \leftarrow m \oplus key\\
key \leftarrow c \oplus m$

Unless your messages are the output of a random number generator and have 8-bits per byte of entropy, then they are susceptible to a known plaintext attack. Any meaningful message will not have 8-bits/byte of entropy, and so you have to assume that the adversary already knows the plaintext messages when designing a cipher.

Additionally, assume that you have two messages $m_1$ and $m_2$ that differ by only a single bit. When you XOR the key into them, the only difference in the resultant ciphertexts is at the place where the messages differed by one bit. A block cipher should produce a random permutation of message blocks, and this is clearly non-random behavior. A block cipher needs to spend time creating diffusion, where flipping a single input bit flips approximately half of the output bits.


Skipping over the OAEP details, considering only the probability that a random ciphertext will have a valid all-zero pad.

For a $t$ bit pad, the random probability is $1/2^t$. Brute forcing 512 bytes or $512\times8$ bits will result in on average $2^{512\times8}/2^t$ valid padding. Assuming a $128$-bit zero pad this is$\dots$

$$3.069183e1194$$

As you said this is impossible. Information theoretically we know the message is one of the $2^{512\times8}/2^t$. If you have any additional structure of the message, you may reduce the candidates further.

Another way to look at this is the birthday bound. Where it'll take on average $2^{t/2}$ random samples to find a valid padding.


My question is how is this attack avoided in FHE (fully homomorphic encryption) which allows arbitrary computations (e.g adding and comparing) on ciphertexts.

We don't give attackers access to such Oracles.  Such an Oracle would allow an attacker to decrypt (as you've noted), and so cannot be computed without help of the private key (or so we hope, otherwise the encryption method is broken).  So, unless the attacker gets some help from someone with the private key, he cannot perform this attack (and, if the attacker does get insider help, that insider could just decrypt the text, and hand the decrypted text to the attacker).

Note that this is not specific to homomorphic encryption; for any public key encryption method, an Oracle that will determinize a ciphertext will allow the attacker to test values (by the attacker determinizing the challenge ciphertext, make a guess as to the plaintext, encrypting it, determinizing that encryption, and seeing if it matches the challenge ciphertext).


Supersingular vs non-singular (Same or different)

Every elliptic curve is non-singular. Some elliptic curves are supersingular.

A quote from "The Arithmetic of Elliptic Curves" by Silverman, Remark V.3.2.2:

  Do not confuse the notions of singularity and supersingularity. A supersingular elliptic curve is, by definition, an elliptic curve, so it is nonsingular. The origin of the potentially confusing terminology is as follows. Historically, elliptic curves defined over $\mathbb{C}$ whose endomorphism rings are larger than $\mathbb{Z}$ were called singular, where "singular" was used in the sense of "unusual" or "rare". However, in this sense, all elliptic curves defined over $\bar{\mathbb{F}}_p$ are singular! The endomorphism rings of most elliptic curves over $\bar{\mathbb{F}}_p$ are order in imaginary quadratic fields. It is only the rare and unusual curve whose endomorphism ring is an order in a quaternion algebra, whence the term "supersingular".


Is it possible that two distinct RSA moduli share both of their prime factors?

Here's the scenario that this caveat in the documentation worries about:

Suppose you had three modulii:

$M_1 = p \times q$

$M_2 = p \times r$

$M_3 = q \times s$

Then, when the program outputs the GCD of $M_1$, it'll output $p \times q = M_1$. It'd do this even though the above has enough information to factor $M_1$ efficiently.

It does this because it actually outputs $GCD( M_1, M_2M_3)$; because both factors of $M_1$ appear in $M_2M_3$, both factors appear in the output.

This is certainly possible; as for how likely it is, well, that rather depends on the details within exact RSA generation algorithm.  I personally would be surprised, though; most RSA generation algorithms pick one prime, and then pick the other (and run into problems because entropy was lousy when they picked the first prime, and then got better when it picked the second).  The primes it picks depends on the internal state (and the entropy).  For the first primes to match, we need to assume that the initial entropy was lousy (however, it got better when picking the second prime); this is plausible.  However, in order to share the second prime, then two runs must have distinct states when picking the first prime, and then somehow fall into exactly the same state when picking the second. That seems rather implausible (although not impossible) to me.


This problem was studied under the name of private set-intersection cardinality (PSI-CA) by De Cristofaro et al. They give protocols for the two-party case both in the honest-but-curious and malicious setting, and the complexity grows only linearly in the size of the sets. A result for the multi-party case was given by Egert et al. using Bloom Filters.

In case you are interested in only testing whether two sets are disjoint without revealing anything else then the problem has been studied by Kiayias and Mitrofanova and under the name private intersection predicate evaluation.


How much (home PC) CPU time is required to generate a prime number of a given size?

By the prime number theorem, the average (asymptotic) distance from a prime $p$ to the next prime is $\log p $. So, on average, one must test $\log p$ integers for primality before finding the next prime. However, $\log p$ grows very, very slowly: even for 1024-bit numbers, $\log p \approx 710$.

Primality testing is well-understood, and very fast algorithms exist. For example, per AKS primality test, there exists a deterministic primality test with runtime $\tilde{O}(\log^6 p)$. Since we would have to run this test for (on average) $\log p$ integers, the runtime ends up becoming $\tilde{O}(\log^7 p)$. That's if you want an asymptotically-fast, deterministic test; in practice something like Miller-Rabin will do better, with a runtime of $\tilde{O}(k\cdot\log^3 p)$.

I guess the answer is "not much CPU time at all," but how much exactly depends on the CPU, memory speed, algorithm chosen, system load/usage, ... etc. All of those messy details are abstracted away with the use of Big-O notation (as above), so I think that's a more useful viewpoint.


How can a derived key be verified to be the right key?

It depends on the protocol, there is not one way of handling this.

If a symmetric cipher does not provide integrity protection or message authenticity (through a MAC calculation) then it may well be that the decrypted plaintext is not correct.

Usually we try and use an authenticated cipher like GCM to avoid such problems. In that case the verification of the authentication tag fails and the file is not decrypted.

If the ciphertext is large it may be a good idea to create a separate MAC over some known information and include it with the ciphertext. That way the validity of the key can be determined without having to decrypt the entire message. It may also help detecting that e.g. the decrypted file isn't fully present in it's original form. It seems wasteful to perform the full verification of the ciphertext in case a wrong password is provided, and it makes no sense to have more security for large files as for small files in case an adversary tries to find the password.

Note that above trick is basically an enhanced version of a Key Check Value, and the usefulness of KCV is debatable. There is no good way of distinguishing between a bad password and an altered ciphertext. Even if you include an additional MAC with the ciphertext, then that MAC value may be altered as well.

Obviously providing a signature over the ciphertext may also work. You must make sure that the public key of the sender is trusted by the receiver, otherwise signature verification is useless. Do note however that other trusted parties - if any - could remove the signature and sign the file themselves.


Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

Entropy and bias are not the same.
Yes, total entropy is additive so as you suggest 7 bits of badrand() produce a total of 1.064 bits of entropy. So? How would you use that?  In cryptography we aim to use some source to produce a stream of independently and identically distributed random bits.
Assume a plaintext ($p$) of octets XORed with an octet keystream ($k$) to generate ciphertext ($c$) as $c = p \oplus k$. Where would you get 8 bits of $k$ from?  We would need to use up at least $\frac{8}{0.152} \approx 53$ bits from badrand(). So the issue becomes how do you transform 53 bits into 8 to be usable as an unbiased keystream?
We could use a randomness extractor such as a 2 universal hash function. That can be as simple as vector multiplication. The maths (Leftover Hash Lemma) governing the transformation tells us that the output bias $\epsilon_{hash} = 2^{-(sn - k)/2}$. In your case, $\epsilon_{hash} = 2^{-(0.152 \times 53 - 8)/2} = 0.98$. Not much improvement over the raw bit stream! The maths only works if $n$ is increased to >849 which then gives you a small enough bias for $k$ to be cryptographically useful.
As stated in the linked paper, there is a large entropy loss as an unavoidable(?) consequence of the transformation. The loss can be reduced and the extraction made more efficient, but nothing comes entirely for free.

Speaking of entropy loss: The most important factor that can reduce the entropy loss is the output size of the extractor function. Your example uses 8 bits. So the entropy loss is just over 99%. That's bad. Imagine using SHA-512 instead of an 8 column wide vector extractor. You'd hash 4211 bits to produce 512. The loss is now 88%.


Is it ever safe to use encryption with compression?

I think that the answer to this question is a bit more involved than it first seems. The reason is that the compression attacks work when different lengths after compression reveal information about the plaintext. This is of course a huge problem. However, you have to ask the question without compression as well: when does the plaintext size leak information.

In practice, the plaintext size leaks information in many settings, and it's very problematic. A very nice paper that deals with this is called Side-Channel Leaks in Web Applications: a Reality Today, a Challenge Tomorrow (it appears at IEEE S&P 2010).

So, this question arises when using compression and when not using compression in exactly the same way. If you have a lot of control over your application, then you can pad to a fixed length (if this is feasible regarding efficiency). This is indeed harder to do when using compression since you typically don't have a fixed useful upper-bound on the post-compression length. If you did have such an upper bound, then you could compress and then pad.

In many cases, the actual values being encrypted are not known ahead of time and the person designing that part of the application knows nothing about security. Then you are in trouble whether you are using compression or not.

In summary, length leakage is a real problem that is way too ignored. The use of compression in some cases makes it worse (like in the CRIME and BREACH scenario), and in some cases it's the same problem as without compression. It depends on the application and you have to do the analysis.

(Just to answer the specific question: if you are saving 42% by using compression, try to estimate the maximum foreseeable size after compression and pad to that; you may very well still save 25-35%.)


I will keep the same notations as in the paper mentioned above.

First, your substitution for $H^{(0)}$ is correct but you could stop to
\begin{align*}
T_1^{(1)} = H^{(0)}\boxplus \Sigma_1(E^{(0)}) \boxplus Ch(E^{(0)}, F^{(0)}, G^{(0)}) \boxplus K_1 \boxplus W_1
\end{align*}
since all values except $H^{(0)}$ are known from previous DPAs.

Regarding $C^{(0)}$, it is a little less straightforward. We have
\begin{align*}
T_2^{(1)} &= \Sigma_0(A^{(0)}) \boxplus Maj(A^{(0)}, B^{(0)}, C^{(0)})\\
&= \Sigma_0(A^{(0)}) \boxplus \big[(A^{(0)} \wedge B^{(0)}) \oplus (A^{(0)} \wedge C^{(0)}) \oplus(B^{(0)} \wedge C^{(0)})\big]
\end{align*}
which results in
\begin{align*}
\big[T_2^{(1)} \boxminus \Sigma_0(A^{(0)})\big] \oplus (A^{(0)} \wedge B^{(0)})&=  (A^{(0)} \wedge C^{(0)}) \oplus(B^{(0)} \wedge C^{(0)}) \,.
\end{align*}
Unfortunately, as bitwise AND operator is not invertible, we don't get $C^{(0)}$ directly. Still, $C^{(0)}$ is the only unknown variable making a bruteforce attack on this 32-bit variable easy in practice.


The goal of a MDC is to provide integrity guarantees. That is, given the value $h(x)$, it should be possible to check whether $x$ has been tampered with. The attack scenario you are describing requires authenticity guarantees, i.e., you want to be able to detect whether the tuple is actually from Alice. To achieve this, there are many possible solutions. One simple example would be to require an additional signature from Alice on the tuple (this is for the setting where Bob will need to verify the authenticity and the integrity of the tuple). In case you only require private verification, i.e., Alice stores the data somewhere and when retrieving them again wants to verify authenticity and integrity, you could simply use a message authentication code (MAC).

To your question: in many practical scenarios the hash is delivered by some other means. Yet, in many cases you also have no (cryptographic) authenticity guarantees. Take, for example, the hashes which are provided when you download files. In case you are using plain HTTP you also only can verify whether the downloaded file fits the hash, but you can not verify whether the page you are viewing is actually the page it should be.


Example of CHI Square test on Caesar Cipher?

I'll assume that the objective is to assert if the distribution of the $f'_i/n'$ is sufficiently similar with the distribution of the $f_i/n$ to support that a substitution cipher (including Caesar cipher) with the same permutation table and same frequency of plaintext characters could be used in both case.

If $n \gg n'$, $f_i \gg 5$ and $f'_i \ge 5$ for each $i$, we can use the first sample as reference; the expected $f'_i$ is $n'·f_i/n$, and the usual Chi-squared test is now to compute (update: formula and condition fixed)

$$X = \sum_{i = 1}^k \frac{(f'_i-n'·f_i/n)^2}{n'·f_i/n} = \sum_{i = 1}^k \frac{(n·f'_i-n'·f_i)^2}{n·n'·f_i}$$

which should be distributed as a Chi-squared variable with $k-1$ degree of liberty under the null hypothesis. We can reject the null hypothesis (substitution cipher with same permutation table and frequency of plaintext characters, assumed independent) if $X$ is bigger than found in a table for Chi-squared confidence test. E.g. for $k$ = 27 and $X$ > 38.9, we reject the null hypothesis with confidence level 95%. CAUTION: we have disregarded the fact that letters in the plaintext are not independent, and this will tend to make $X$ bigger than predicted by the null hypothesis.

If some $f'_i$ (or $f_i$) are too small, an option is to aggregate the smaller ones into a single value (and reduce $k$ accordingly).

If fail to find a reference on what to do when $n$ and $n'$ are of the same order of magnitude.


We need to get back to Matsui's notations.

X is represented as X[31]....  X[0]

K is represented as K[47]......K[0]

In X[15] ⨁ F5(X,K)[7,18,24,29] = K[22]

X[15] is actually the round input before expansion E and is therefore the 4th bit of SBOX 5 with input bits of S5 being x[5]x[4]x[3]x[2]x[1]x[0]. X[15] = x[4] in practise and the key bit is the 23rd from right to left, hence K[22] because the first one is K[0].

Then F5(X,K) = P(S5(X, K)), for which we sum up the 4 output bits. The bits straight out of S5 are Y[15], Y[14], Y[13] and Y[12], with Y = Y[31]......Y[0] using Matsui's notation, Y is mine.

If we apply P to Y,  P(Y[15]Y[14]Y[13]Y[12]) is the permuted output of S5 (that would be P(Y[17]Y[18]Y[19]Y[20]) in a "normal DES" representation from left to right) and becomes Z[24]Z[18]Z[7]Z[29] before expansion for the next round.

Hence the result:
X[15] ⨁ Z[24] ⨁ Z[18] ⨁ Z[7] ⨁ Z[29] = K[22] or

X[15] ⨁ Z[7] ⨁ Z[18] ⨁ Z[24] ⨁ Z[29] = K[22] as presented by Matsui.

Note 1: X is the input of round R before expansion, Z is the input of round R+1 before expansion

Note 2: it looks like Matsui used the processor's bit order as opposed to standard DES notations

Kiss


OMAC/CMAC constant for different block sizes

The identification of the lexicographically first irreducible degree-b binary polynomial with the minimal number of ones can be implemented by testing reducibility (second algorithm) of those

polynomials in order until you get to the first irreducible polynomial in that order.

Alternatively, you could look them up.

The constant itself is then derived from the polynomial by discarding the leading (block size) term and evaluating the remainder for $x = 2$.

e.g. for 256-bit block size:

first polynomial is $x^{256} + x^{10} + x^5 + x^2 + 1$
Note this is is 256,10,5,2 in the linked report, which discards the $+1$ term.
discarding first term and evaluating for $x = 2$ gives $2^{10} + 2^5 + 2^2 + 1 = 0x425$


Taking $p$ and $q$ to be the same value in paillier cryptosystem

Irrespective of the math, you CANNOT take $p=q$ since in this case the scheme is completely insecure. You must choose random, independent primes $p$ and $q$.


Will current encryption always remain secure? Is there mathematical proof?

"Will such security always remain secure?"

No. $\:$ In particular, quantum computers will break RSA and elliptic curves.

Has it been mathematically proved that these algorithms can not be cracked, or is it a possibility?

It is a possibility, since a very-practical algorithm for the Boolean satisfiability problem
would be enough to break essentially all complexity-based cryptography.

(There might still be a secure complexity-based proof-of-work system,

although it would need a super-constant number of rounds of interaction.)

If so, how likely is it that cracking the RSA via a

mathematical weakness will be possible in the near future?

Does Shor's algorithm constitute "a mathematical weakness" in RSA?


Why do we need in RSA the modulus to be product of 2 primes?

RSA would still "work" with such $N$, but isn't secure for $N$ that are easily factored. If you know the factorization of $N$ (which is trivial for prime $N$s) you can calculate the private key from the public key. This totally breaks the desired security properties of RSA.

The essential equation for RSA is that $m^{\phi(N)+1}= m \mod N $ for all $m$. This works for all $N$, but only for some $N$ it's hard to calculate $\phi(N)$. When using RSA we require $\phi(N)$ being hard to calculate, since once you know $\phi(N)$ you can get $d$ from $e$ by solving $e \cdot d = 1 \mod \phi(N)$ using the extended Euclidean algorithm (just like what you do when legitimately creating the key-pair).

If $N$ has more than two factors, but at least two of those are large and hard to guess, it's still secure. But almost nobody uses this RSA variation.


Disjunctive zero knowledge proof of equality of committed values

What's special about your question is the "global" use of generators $g,h$ for all the commitments. This allows for a nice shortcut, leading to some potential savings.

Asking for a proof that $x=x'$ for given $C=g^x h^y$ and $C'=g^{x'} h^{y'}$ only makes sense if we actually demand a proof of knowledge of all four exponents as well. Now, the interesting thing is that if some party already proved knowledge of the four exponents, it suffices to prove knowledge of $z=\log_h (C/C')$ to establish that $x=x'$. This latter proof can be done using the Schnorr protocol.

The basic assumption for Pedersen commitments is that nobody knows $\log_g h$, otherwise one cannot even speak about the exponents for a given commitment. So, given all these proofs it follows that we can write $C=g^x h^y=C' h^z=g^{x'} h^{y'+z}$, hence that $x=x'$ must hold (and $y=y'+z$).

The proof that you are asking for then boils down to the OR-composition of two Schnorr proofs, which is pretty efficient. This idea can be applied more generally, and was in fact the basis for an efficient construction of list signatures (see Lemma~1 in List Signature Schemes).

If knowledge of the four exponents has not been proved yet, it is more efficient to prove everything in one go using EQ-composition combined with OR-composition.
Assuming that $x_1=x'_1$, we use an EQ-proof for $C_1,C'_1$ and a simulation of an EQ-proof for $C_2,C'_2$. This yields the following $\Sigma$-protocol:

Prover sends announcement $(a_1,a'_1,a_2,a'_2)\leftarrow(g^{u_1} h^{v_1}, g^{u_1} h^{v'_1}, g^{r_2} h^{s_2} C_2^{-c_2}, g^{r_2} h^{s'_2} C_2'^{-c_2})$ with $u_1,v_1,v'_1,c_2,r_2,s_2,s'_2\in_R\mathbb{Z}_n$.
Verifier sends challenge $c\in_R\mathbb{Z}_n$.
Prover sets $c_1\leftarrow_n c-c_2$ and $(r_1,s_1,s'_1)\leftarrow_n (u_1+c_1\,x_1, v_1+c_1\,y_1,v'_1+c_1\,y'_1)$, and sends response  $(c_1,r_1,s_1,s'_1,r_2,s_2,s'_2)$. Verifier sets $c_2 \leftarrow_n c - c_1$ and accepts if all of $g^{r_1} h^{s_1} = a_1 C_1^{c_1}$, $g^{r_1} h^{s'_1} = a'_1 C_1'^{c_1}$,  $g^{r_2} h^{s_2} = a_2 C_2^{c_2}$, and $g^{r_2} h^{s'_2} = a'_2 C_2'^{c_2}$ hold.


Memory hardness of key derivation function through XOR-ring multiple matrix values

Collisions are not much of a concern, since you have to compute them to know they happen, and assuming your values are a typical hash size (256+ bits) they will never happen randomly anyway. But yes, having identical computation that use the same data is wasteful if you don't store the intermediate values.

However, the main problem your function has is that the XORs can be computed ahead of time for multiple iterations of the second loop. For example, here:

Computing 1 ^ 15 ^ 17 ^ 31 AND 7 ^ 9 ^ 23 ^ 25
Computing 2 ^ 14 ^ 18 ^ 30 AND 6 ^ 10 ^ 22 ^ 26

The attacker can compute both of these by going through the matrix once and only maintain four values where they XOR the appropriate elements of the matrix. In fact, they can choose exactly the amount of memory they do have and calculate that many iterations' worth of XORs in one go. (Concatenation would be better than XOR since it would take more space. But it would still be less than the whole matrix, so trade-offs would be possible.)

The way scrypt and other memory hard hashes accomplish their memory-hardness is by having a large state that they update instead of just reading. Your two loops where one generates and one "collects" the data will always let the attacker store only parts of the matrix and recalculate as needed. If the second loop took many passes over the data while also changing the matrix, it would no longer be as easy since calculating any dropped values again would take longer and longer the further along the algorithm is.


can session key be be used as digital signature?

No.  Let || be concatenation, let [E',D'] be any symmetric encryption scheme,

and then let [E,D] be given by    E(k,x)  =  0 || E'(k,x)    and

D(k,empty_string) = empty_string    and    D(k,0||c) = D'(k,c)    and  D'(k,1||c) = c .

The efficiency and correctness conditions for [E,D] are trivial.  Since E can be simulated

from E' by just prepending a zero to each ciphertext, [E,D] will be IND-CPA if [E',D'] is.

However, with [E,D], one can trivially break {m}k as an authentication

scheme by just outputting something that starts with 1.


The only reason I can imagine why one would prefer CFB over OFB or CTR is error propagation. Another reason may be technical issues with the relieability of the transmission line.

This comes from the fact that if you flip a single bit in an OFB ciphertext then you only get the same bit flipped in the underlying plaintext. But if you flip a single bit in CFB mode, you get the bit flipped in the plaintext and get the following block to decrypt to gibberish. So there's a larger chance of you detecting a manipulation of the ciphertext because the effect on the plaintext is bigger.

However the above reason stems from the dark ages of cryptography, where authenticated encryption was usually done ad-hoc or not at all, so people actually relied on these error propagation properties. These days, using anything but CTR is pointless, because CTR allows very nicely for SIMD parallelization and error propagation as a property is kinda irrelevant because the authentication tag will catch any modifications.


Trying to understand textbook exercise question regrading RSA

I will assume that Alice uses $D' = E^{-1}(\varphi(N) - 1)$ with $E^{-1}$ the inverse of $E$ modulo $\lambda(N)$.
The question uses a very specific definition of $D'$, which requires the assumption that $E$ divides $\varphi(N) - 1$. But since such an $E$ is necessarily coprime to $\varphi(N)$, it is a special case of the more general definition of $D'$ provided above.

So we must find some number $E'$ such that
$$E' E^{-1}(\varphi(N) - 1) \equiv 1 \pmod {\lambda(N)}$$
Now note that $E' = -E$ is a solution because $\varphi(N) \equiv 0 \pmod{\lambda(N)}$, so we have

$$m^{-ED'} \equiv 1 \pmod N$$.

So given $c = m^{E}$, compute $c^{-D'}$ to obtain $m$ again. Either you first take the inverse, or you just use $\lambda(N) - D'$ as the exponent.


The proposed system seems to be as follows:

At generation, Alice selects odd $e>2$ and random large primes $p$ and $q$ with $\gcd(p-1,e)=1=\gcd(q-1,e)$; computes $n\gets p\,q$; chooses random $s_0$ in $[1,n)$; and publishes $(n,e,s_0)$. She computes and keeps secret $\lambda(n)\gets(p-1)(q-1)/\gcd(p-1,q-1)$ and $d\gets e^{-1}\bmod\lambda(n)$.
For successive times $t\in\Bbb N^*$, Alice computes $s_t\gets{s_{t-1}}^d\bmod n$ and publishes $s_t$ at time $t$.
For $t\in\Bbb N^*$, anyone with knowledge of $(n,e,s_{t-1})$, e.g. Bob, can check an alleged $s_t$, by verifying that $0<s_t<n$ and ${s_t}^e\bmod n=s_{t-1}$. Alternatively, $s_t$ can be verified from $(n,e,s_0)$ by verifying that $0<s_t<n$ and ${s_t}^{(e^t)}\bmod n=s_0$.
By convention, $k_t=H(s_t)$ where $H$ is some 128-bit PRF, e.g. the low-order 128 bits of SHA-256.

Anyone with knowledge and trust of $(n,e,s_0)$ and knowledge of $s_{t'}$, e.g. Bob, can compute and trust $k_t$ for $0\le t\le t'$.
The intention is that it would be infeasible to derive $k_t$ for $t>t'$. That holds, with some degree of reduction to the RSA problem. Some arguments:

Given how it is generated, it is overwhelmingly likely that $s_0$ is coprime to both $p$ and $q$. Assuming that, it follows that for fixed $t$, each $s_t$ is uniformly random in $\Bbb Z_n^*$.
Knowledge of $s_{t'}$ subsumes knowledge of earlier $s_i$ with $i<t'$.
Finding $s_t$ from $s_{t'}$ for $t>t'$ is solving the RSA problem for public exponent $e^{t-t'}$, or equivalently public exponent $e^{t-t'}\bmod\lambda(n)$, which itself takes quite random-like values in $\Bbb Z_{\lambda(n)}^*$.


Key generation algorithm based on bytes in a drive

Useful: No. Secure: No.

The most pertinent part of your question is the title which I'd slightly correct to "Key generation algorithm based on file lengths in a drive".  It is here at the start that you've made invalid assumptions. There are others later on too though.

A random cryptographic key is essentially entropy, which you can read as uncertainty.  So from a high level, key = entropy = uncertainty.  The file structure on a typical machine is fairly well specified, whether it's a proper *nix machine or one of those other ones. If the machine is newly created (especially as a virtual image or embedded), the file layout may be identical between machine instances.  So any key derived from the file system (lengths or contents thereof) will be highly predicable.  There for insecure.  You have confused complexity with uncertainty.  The file system is certainly complex, but think of all of those free AOL CDs that ended up as coasters.  If you had run your algorithm across the newly installed AOL directory, all of the generated keys would be identical across any machine you'd just installed on. All of you  10 million digit concatenations would have been identical, or very nearly identical.

The second error is the key length.  As a security student, you'll come across typical acceptable key sizes.  No one will even require more than 256 bits of key security. There are mathematical proofs of this limit.  Your attempt at creating an extra long key is meaningless. A lot of cryptographic primitives are designed around the 256 bit size.  What were you attempting to use a 10 million byte key for, as there is no legitimate function to absorb such a key? [You're not thinking one time pad are you?]

With respect, you're probably quite new to cryptography on the basis of this question. There is no effective improvement that can be made to this algorithm without a much more extensive understanding of the nature of a cryptographic key and it's relationship to entropy.

You are though ultimately correct in realising that a key can be generated from the chaotic churn inside a modern computer environment.  Chaos principles can be applied to a file system and there is true entropy but it requires a much greater understanding of the principles before you can extract it safely.


is accessing elements of an array in secret order vulnerable to timing attack?

Being vulnerable to specific timing attack isn't property of construction, but of it's implementation. It isn't hard to imagine a microprocesor that always takes X time to access a byte of memory. Such implementation likely won't be vulnerable to timing attack (but probably will to variety of other, like power analysis). But also some high-level languages can reorganize your data in way which will make analysis far easier, even when you shuffle.

So from now on let's assume modern PC class CPU and a compiler that compiles to native code (assembly). In such case, compilers will very likely make data appear in memory how we see it in table (for optimization purposes).

Modern CPUs cache access to ram on more than one level. Usually cache line has 64bytes. Since all of your data likely won't fit into single cache line, it will likely take different amount of time to access depending where that data is. So it will leak some data about index. It doesn't change anything if you do a double-dereference - it will still leak information about index.

But it doesn't automatically mean that it has to be vulnerable. Some RSA libraries (like OpenSSL) won't have this trouble, because they interleave their data, so that each piece of secret lies on next cache line. This way CPU will always access same cache lines, without timing dependency on index. This of course will also result in performance decrease and isn't likely to be done by compiler.

So having that out of the way, assuming normal memory organization (for speed, not for resistance), your scheme probably is still vulnerable, but shuffling will likely prevent most attacks. Your key will leak because of shuffling, and with enough patience it will be possible to retrieve key and then learn index. Such attack is unlikely to happen, but the cost of shuffling data is very big. So best idea is to follow established protocol for such problems (RSA is well known for having this problem so I suggest looking in that direction).


What exactly is Let's encrypts chain.pem file?

When requesting a certificate one sends a Certificate Signing Request, containing the information to be signed by a CA, to that CA. The CA responds with the resulting certificate and the chain of certificates back to a root. That chain is the CA's certificate, any intermediate CA certificate(s) that signed the CA, (possibly multiple levels), and the root certificate that signed the top-level intermediate CA certificate (if that's not the same as the CA's certificate in question). In Let's Encrypt's case, there's only the CA certificate and the Root in this chain.
The CA knows everything in the chain because they in turn had requested their certificate from an intermediate CA or root, and they know who they requested it from. So they know the certificate of the intermediate or root, and can include it. Likewise back up the chain.
Root CAs have self-signed certificates. There's no other entity in their certificate chain. These certificates get imported as trusted root certificates by browser vendors (and other entities dealing with the TLS CA system), allowing verification of certificate chains starting at these roots.
Since every time anyone (including a CA) requests a certificate they get back the entire chain it's trivial for a CA to send the chain along with the resulting certificate from a request. Also, certificates are public and all major CAs publish the certificates they issue in "certificate transparency logs", so even without the chain one could (in theory) look up the certificates for each signing entity.