Is a password cyphered by itself as secure as hash?

There is an important misconception on your part: in general cryptographic hashes such as MD5, SHA-1 or SHA-512 should not be used to directly hash a password. A password hash or PBKDF should be used. Examples are PBKDF2, bcrypt, scrypt and Argon2. These functions also take a salt and work factor to provide additional protection.

There are a few problems with your idea:

as noted in the comments, a cipher generally takes a key with one or more specific, pre-defined sizes;
a cipher would output a size as large or larger than the input which would leak the password size (and require VARBINARY in databases, larger buffer allocation etc.);
it is missing additional parameters such as a salt or iteration count to make it a password hash;
it would have almost the same performance as just hashing the password (it would offer no advantages, in other words).

No, there is likely little to no research as it would be dismissed out of hand. There was however a password hash competition quite recently where it could have been entered (and immediately dismissed).

Note that MD5 and SHA-1 have been broken and should generally not be used anymore.


What are the typical input lengths for KDFs?

As indicated, KDF's themselves can have any input size. But you can of course take a look at protocols where they are used.

First of all, HKDF is a Key Based KDF. So if it is used with a secret key (the "Input Key Material") you'd expect it to have enough security on its own. So that would be key sizes of 128 to 256 bit (or, more likely, just 128 or 256 bit).

KBKDF's are frequently used to create session keys after key agreement, for instance HKDF in TLS 1.3 (draft). In that case the entropy is first extracted from the given master secret. In that case the input of the KDF is simply the output of the key agreement protocol. Usually that's DH or ECDH.

For DH the output size is the same as the size of the prime (e.g. 1,024, 2,048, 3,072 or 4,096 bits). Note that some older algorithms may not include leftmost bytes if the calculated secret is one byte or more smaller than the modulus. In TLS 1.3 the size of the secret will be identical to the modulus size (I know, because I hinted that feature to the mailing list, to make it symmetric with ECDH, and probably leaks less information through side channels).

For ECDH the size is usually the size of the $x$ coordinate, which is encoded as the same length as the key size. Look up often used domain parameters to get an idea of what is possible there.

Of  course, the size of the Info field can be about anything. But usually it is a relatively short string, so you could just use 16 bytes or so to be on the safe side.

HKDF also may have a salt but that's a bit harder to guess, as I haven't seem it used yet. Salts normally are 64 or 128 bits, although a 256 bit salt is not unheard of.


Paid decryption scheme and possible attack surface

Knowing parts of the plaintext is commonly considered as one of the attackers capabilities when attacking a cryptographic scheme. So all the widely used schemes are resilient to that.

That means that for decent asymmetric encryption it will not help you.


First, it's important to understand that MPC is not possible for $t \geq n/2$ in the information-theoretic setting (where the adversary is computationally unbounded). In the computational setting, where the adversary is polynomial-time, it is possible to achieve MPC under cryptographic hardness assumptions.

Regarding your specific question, I assume you are referring to a case where we have a polynomial of degree $t$ to share a secret. Indeed, it is possible to share a secret securely for any $t\leq n$. However, the problem is that you need to be able to process that secret. So, if $t=3$ and $n=6$ and you have a degree-3 polynomial, then the first step of multiplication yields a polynomial of degree-6. In order to reconstruct the values, 7 points are needed for a degree-6 polynomial. However, there are only 6 parties and only 6 points. So, this cannot be done.

Of course, the above just says why this approach doesn't work. However, it's possible to prove that no approach can work, and I believe that this also appears in the book.


Hiding which cipher you are using means violating Kerckhoff's principle. That's actually an extremely common mistake. The problem is that such a cipher becomes very hard to analyze because you have to consider all the options for an attacker to learn parts of the system.

In general we don't analyze cipher designs on this website because it is too easy to come up with a random design which is probably broken but not totally obviously so. It wastes people's time to try and attack it. Cryptographers mostly don't care about new ciphers anyway. We already have good ciphers. Exceptions are made for very specific applications.


Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| ... ||F_{1…1}(x)$ a PRG?

Because the key-, input- and output-length of $F$ are equal, if the length of the seed $x$ is $n$, there are $2^n$ keys and so $G$ must compute $F$ $2^n$ times and output a string of length $n\cdot 2^n$. Hence, $G$ runs in time exponential in $n$, which means it can't be a pseudorandom generator because a pseudorandom generator is a deterministic polynomial-time algorithm.

(In addition, since a distinguisher runs in time polynomial in the length of $G(x)$, it runs in time exponential in the length of $x$, and brute force through all possible seeds is allowed.)


What is the use of pre-computed points in ECC?

Can someone help with an example?

Ok, here's a simple example; suppose we precompute a table that contained all the points of the form $(a \cdot 256^b) G$, for $0 < a < 256$ and where $b$ be within the scalar we intend to support.
For example, the table (if we support 2 byte scalars) would contain the points $\text{0x01}G, \text{0x02}G, …,\text{0xff}G, \text{0x0100}G, \text{0x0200}G, …, \text{0xff00}G$
Then, to compute the value $0x1234G$, we would look up $0x1200G$ in our table and the value $34G$, and then add them $0x1200G + 0x34G = 0x1234G$; we just computed the point multiplication with a single addition (and some table lookups); using a table without precomputation would use at least 13 point additions/doublings.
It should be obvious how this table can be extended to support longer scalars; if we support 32-byte scalars (appropriate for 256-bit curves), we can do any point multiplication using 31 additions (and a large table).
There are a number of ways to build the table (including methods with much smaller tables and not that much more computation required); I picked this example solely because it was easy to understand.

Also, once the pre-computed points are calculated, are these secrets?

Only if the base point is secret.  As this is most commonly used with the public curve generator point, there is usually no need.
Also, the tables/algorithms can be set up to run in constant time; however that is rather trickier.


Known text attack on Hash function (SHA 256 or SHA512)

Let consider $h = H(A\mathbin\|B\mathbin\|C)$ for SHA-256 or SHA-512 where both are MD-based cryptographic hash functions of NIST with

$A$ is 1000 bits
$B$ 16 bits, and
$C$ 283 bits

and we further assume that the attacker knows $h$ and $C$
Brute-force search
Definitely, the attacker cannot test the 1016-bit of unknown data to match the $h$. Bitcoin miners, the biggest known collective entity, can reach around $\approx 2^{93}$ This road is closed.
Prime-image attack
To find a pre-image normally we look for the first $a2^n$ input to find an input $x$ such that $h=H(x)$. For your case a little different.

Try random $a2^n$ values in the range $[2^{1299},2^{1300}]$. This has two problems;

It is infeasible
Even if the attackers have found one, the probability of result is equal to your data is $$\frac{2^{1299}}{2^{256}} = \frac{1}{2^{1043}}$$ for SHA-256, and $$\frac{2^{1299}}{2^{512}} = \frac{1}{2^{787}}$$ for SHA=512. Impractical, this road is closed, too.

And, we know that SHA-256 and SHA-512 are pre-image resistant, this road is also closed, too.
A simple counter-argument

If there is an attack on your case, that is one can extract $A$ and $B$ from $H(A\mathbin\|B\mathbin\|C)$ with the knowledge of $C$, Then we can use the length extension attacks on SHA-256 and SHA-512 to execute a pre-image. Simple, for a given $h'$ with $h' = SHA-256(x)$, execute a length extension $h'' = \operatorname{SHA-256}(x\mathbin\|C')$, then extract $X$ form $h''$ with the knowledge of $C'$. We don't have such any method.
In other words, extend the hash then find a pre-image. End of the path.

If you are looking for a secure way to hash with a key, the obvious method is the HMAC or you can use KMAC of SHA3.


Cracking a PRNG by observing ranks within groups of its output

Assuming $w=32$ (32-bit integers for internal state), $624 * 32 = 19968$ bits of information is found in the internal state. On the other hand, a maximum of $\lfloor\log_2(100!)\rfloor=524$ bits of information is revealed by each ranking of 100 outputs. $\lceil19968/524\rceil=39$ rankings of 100 outputs each would be the minimum information I would expect to need to identify the state. I do not, however, know of an algorithm to use the revealed ranking information to calculate the state.

You talk about "leaking" information and ask about a "cracking process". I hope you are not attempting to use a Mersenne Twister when a cryptographically secure pseudo-random number generator is needed.


Is it reasonable to assure that p-1 and q-1 aren't smooth?

Checking for smoothness can be computationally expensive, depending on the size of the "small" primes (there is no "natural" definition of "small", one has to define an arbitrary limit). Also, it is not really useful.

The need for non-smooth integers comes from the $p-1$ factorization method. Let $n = pq$ be a RSA modulus that we wish to factor. Now suppose that $x$ is an integer which is a multiple of $p-1$, but not $q-1$. For an integer $v$ relatively prime to $n$ (e.g. $v = 2$), this means that $v^x = 1 \mod p$ but $v^x \neq 1 \mod q$. By the Chinese Remainder Theorem, this implies that $w = v^x - 1 \mod n$ is a multiple of $p$ but not of $q$. A simple GCD computation between $w$ and $n$ then reveals $p$, a prime factor of $n$.

So the $p-1$ factorization method is about assuming that $p$ (or $q$) is such that $p-1$ is $B$-smooth for some limit $B$. Then things go thus:

Set $w \leftarrow 2$.
For all primes $r$ lower than $B$, compute $w \leftarrow w^{r^{z_r}} \mod n$, where $z_r = \lfloor \frac{\log B}{\log r} \rfloor$.
Compute the GCD of $w$ and $n$.

One way to see this method is the following: when we compute modulo $n$, by the CRT, we are actually computing modulo $p$ and modulo $q$ simultaneously. We do multiplications, so we work with two multiplicative groups, the non-zero integers modulo $p$ and the non-zero integers modulo $q$. The goal of the attacker is to find a multiple of the order of one of these two groups. The two groups have orders $p-1$ and $q-1$, respectively. If one of these two orders is $B$-smooth, the algorithm above will work with high probability (there are a few pathological cases where this does not work, due to the condition on $z_r$, but success probability is close to $1-(1/B)$).

This explains the prohibition against smooth $p-1$ and $q-1$. Note, though, that this depends on $B$: $B$ represents the effort that the attacker is ready to invest in the computation. A larger $B$ implies a more expensive attack, but also a more expensive test of non-smoothness, because the best known method for testing $B$-smoothness is trying to divide by all primes lower than $B$: this is somewhat faster than running the $p-1$ factorization method, but not by much. So to defeat an attacker ready to invest one month worth of computation with a dozen PC, we have to do ourselves a check which will take several hours one one PC.

Checking for smoothness is not useful because of the Elliptic Curve Method. ECM is an extension of the $p-1$ method. We again compute things modulo $n$, so that we are working, through the CRT, with two groups, one using integers modulo $p$, the other modulo $q$; and we still hope to hit a $x$ which is multiple of the order of one of the groups.

The groups, in ECM, are randomly chosen elliptic curves. The group law (usually denoted with an addition sign, but that's purely conventional) is weird but can be computed reasonably efficiently through a handful of operations modulo $n$. The interesting point is that when working with integers modulo $p$ (a prime), the order of an elliptic curve modulo $p$ is an integer $f = p+1-t$ where $t$ is called the "trace" and Hasse's theorem states that $|t| \leq 2\sqrt{p}$. So the order of a curve modulo $p$ is "close" to $p$, but still lies in a relatively large range surrounding $p$, and it so happens that a randomly chosen elliptic curve will have an order distributed fairly uniformly in that range.

So the ECM method works by selecting a random curve modulo $n$ (which implicitly selects two random sub-curves, one modulo $p$ and one modulo $q$), assuming that the order of one of these curves is $B$-smooth, and running the same algorithm than for the $p-1$ method, except that we use curve point additions instead of multiplications. If the algorithm fails (the final GCD yields 1), then we can start again with a new random curve.

The ECM method works as long as a randomly selected integer in the range around $p$ (of size $4\sqrt{p}$) has a non-negligible probability of being $B$-smooth from some value $B$ such that the "for all primes lower than $B$" step is computationally feasible. In other words, the RSA modulus will be secure only if the probability of a random integer of the size of $p$ (half the target size of the modulus) of being $B$-smooth is low enough.

Thus, due to ECM, we already rely on the non-smoothness of a random integer. It thus makes little sense to spend CPU cycles on checking $p-1$ specifically: even if we carefully avoid $p$ such that $p-1$ is $B$-smooth, this gains nothing about the probability of a random integer of the size of $p$ to be $B$-smooth. We still need that probability to be negligible, which is achieved by using large enough primes.

Probability of smoothness can be estimated with the de Bruijn function. But, given the discussion above, it is more practical to look at factorization records with ECM. Efficiency of ECM largely depends on the size of the smallest prime factor of the attacked integer -- that's the factor which the ECM finds. The largest factor ever found through ECM is close to $1.8*10^{73}$, i.e. a 244-bit integer. We can thus estimate that 244-bit integers have a probability of smoothness which is high enough for the ECM to work, but larger integers do not. For a 1024-bit RSA key, we use 512-bit prime factors, more than twice that record size. So we can say with some confidence that a random 512-bit integer is sufficiently non-smooth with overwhelming probability, thus "secure enough" for RSA. No need to test.


Best way to encrypt lots of private keys with the same passphrase

Confirm or refute my assumption that using same passphrase to encrypt
  millions of keys with PKCS #8 significantly weakens encryption
  strength. If Eve gets enough encrypted keys, she can decrypt them
  knowing that same passphrase was applied? Kind of "many times pad"
  attack?

It depends.
If you are using PKCS#8 encryption using the methods from PKCS#5 v1.5 (and not >v2.0), then you are using ciphers with very short key-lengths, like DES. This is obviously bad, as we can reasonably brute-force the keys (of interest).

However, PKCS#5 (which is the encryption specified by PKCS#8) should generate a new random salt for each container and use password based key derivation with this salt and some reasonable iteration paramter to arrive at a key / IV pair for the encryption. That is, all private keys would be encrypted using different keys derived from different salts and the same password.

So overall the encryption is not weak because you encrypt a lot of data, but because you use a weak encryption method (if you use the old v1 PKCS#5 standard).

  Suggest a better encryption methods which use same passphrase (or
  limited number of them).

Assuming the password is strong and not leaked, PKCS#5 v2.X should do the trick indeed. One might consider adding additional indirection though, that is use the password to derive a master secret (eg 256-bit) which is then fed to the PKCS#5 calls, so that you can easily change the password when it is eg leaked or people go, but they didn't take the derivation parameters / keys.


Why use CBC-MAC? Why not just apply hash function on the whole message?

A hash function is not a MAC, although you can turn it into a MAC (see e.g. HMAC).

The purpose of a MAC is message authenticity / integrity -- to prevent attackers (i.e. people who don't know the secret key) from modifying the message or forging fake messages.  A hash function trivially cannot fulfill the function of a MAC, because hash functions are unkeyed -- thus an attacker can always forge fake messages because they can calculate the digest of any message as easily as the legitimate parties.

With a MAC, such as CBC-MAC or HMAC, only the people who know the secret key can easily calculate the authentication 'Tag' for a given message, so if a message is sent accompanied by the correct Tag for that message then the receiver knows the message was almost certainly sent by someone who knew the key, and has not been altered (i.e. changed to a different message) in transit.


what is number of invertible matrix m*m on$ z_n$?

Assume you know the number of invertible $m \times m$ matrices over $\mathbb{Z}_{p^k}$ for $p$ prime. Call this number $N(p^k)$.

By the Chinese Remainder Theorem, $N(\prod_{i=1}^l p_i^{k_i}) = \prod_{i=1}^l N(p_i^{k_i})$ because a matrix is invertible iff every component in its CRT decomposition is invertible. For $m = 1$, $N$ is just the $\phi$ function.

Finding $N(p^k)$ is another matter.


AES S-Box: Possible options for constant to calculate S-Box values

Out of the 256 possible 8 bit additive constants for the AES S-box, 34 satisfy the requirement of there being no fixed points or opposite fixed points:

0x05, 0x07, 0x08, 0x15, 0x1D, 0x20, 0x30, 0x37, 0x38, 0x3B, 0x3D, 0x49,
0x52, 0x56, 0x5D, 0x63, 0x76, 0x89, 0x9C, 0xA2, 0xA9, 0xAD, 0xB6, 0xC2,
0xC4, 0xC7, 0xC8, 0xCF, 0xDF, 0xE2, 0xEA, 0xF7, 0xF8, 0xFA

To address the obvious follow-up question, no, I do not know why specifically the constant 0x63 was chosen from among these 34 options.

The only immediately apparent property of 0x63 that I could guess might have influenced the choice is that it has exactly four of its eight bits set; but that's still not enough to narrow down the choice completely, since 0x1D, 0x56, 0x9C, 0xA9 and 0xE2 also share this property.

Ps. To obtain the list above, the easiest way is to start with the normal AES S-box (which can be found in many sources, including Wikipedia) as a table of 256 bytes.  You can then bitwise XOR each byte in the table with the standard additive constant 0x63 to cancel it out and obtain the S-box as it would look with a zero constant.  Then you can just test all the 256 possible constants between 0 and 255 to see if XORing them with each of the table entries will yield any entries matching their index in the table or its bitwise negation.


Is the order of applying transformations in SP cryptosystems significant?

Let call the Substitution by $S$ and Permutation by $P$ in the Substitution Permutation Network (SPN). Let consider an SPN block cipher with $4$ rounds where $K$ represents the $\oplus$ round key.

With $S$ applied first

|KSP|KSP|KSP|KSP|

The last $P$ has no effect on security. The attackers simply discard it. So we can consider it like;

|KSP|KSP|KSP|KS|
With $P$ applied first

|KPS|KPS|KPS|KPS|

The initial permutation has no effect in the view of the attacker. Similarly, we can consider it with some changes in the key schedule.

|KS|KPS|KPS|KPS|

Now we can swap K and P that will require a change in the key schedule.

|KSP|KSP|KSP|KS|

That is turned into the simplified version of S applied first. Consequently, they did not differ.


How are certificate status obtained on browsers?

OCSP is not susceptible per se to MITM attacks, but it does have other problems:

Most browsers used to soft-fail, e.g., if they couldn't get the OCSP response for some reason, it allowed the connection to go through. So the attacker only needed to block the OCSP response.
Privacy issues: an attacker can see the OCSP query going through and can gain some information about your browsing.

This is solved by OCSP stapling, where the server is responsible for getting the OCSP response and sending it to the client (stapling). There is also the must-staple extension that makes stapling mandatory, otherwise a MITM attacker that stole the server private key could just not staple the OCSP response.


Zero knowledge proof for opening of Pedersen commit and discrete logarithm

It can be done with two Schnorr proofs, which can be interactive or noninteractive.

This is a simple way of proving knowledge of a discrete log; in the noninteractive version, to prove the knowledge of $x$ s.t. $a = g^x$ (assuming a public hash function $H$), the prover picks a random value $r$, computes $t = g^r$, $c = H(t)$, and then publishes $t$ and $s = r + cx$.  The verifier then checks whether $g^s = t a^c$

To prove the statement you want, you first publish a proof that you know $x$ s.t. $V = g^x$

The second proof is that you know $r$ s.t. $C V^{-1} = h^r$

The two combined is equivalent to the statement you are interested in.


I take your question to mean, how both historically and in the modern age one could construct a pen-and-paper cipher using the Chinese language.

As pointed out in the question, Chinese is a logographic language and therefore has a far greater number of characters than Phonetic systems. Historically this has cause Chinese codes not to be based around the script.

The following claims are taken from a forum discussion and translation of ancient Chinese codes for lack of a better source.

Nüshu script may not have been intended for secrecy but it functions as such since it was almost exclusively used and readable by educated Chinese women. It was phonetic and had a set of 700 characters. This suggests that one could use the phonetic attributes of the Chinese language as a basis for a reduced character set on top of which one could implement a code.
In an earlier form of secret sharing, messages were cut into strips and delivered by different couriers.

  The so called “阴书” was to write the document vertically and cut it into 3 sections. Sent 3 persons, and each person would hold one of the sections. They would depart at different times and using different paths. When the receiver received all 3 parts, he could get the whole thing of this secret document. If one of the messengers was captured by the enemies, the enemy would have difficulties to understand the secret document. As translated by the Chinese History Forum

The technique of phrases is something I don't entirely understand I think the method is essentially to use the phonetic sound from ciphertext logographic characters to transmit a secret message. In English "eyesight hat very eight seashores create rat table" or "I ha-ve a se-cre-re-t"

  “反切” (fan3 qie4) is a kind of phonetic system originated in ancient time to help document the pronunciation of Chinese language. The basic method for (fan3 qie4) is: Take the first word 上字 (shang4 zi4 - upper word) for its starting sound (or the consonant) and the second word (xia4 zi – lower word) for its ending sound (or the vowel). The tone would follow the ending sound. Therefore, a word is separated into two parts: 声母 (sheng mu3 – starting sound), 韵母 (yun4 mu3 – ending sound). Use the 声母 sheng mu adding a 韵母yun mu from another word to form the “反切” fan qie’s first word (or upper word). Use the 声母 sheng mu from another word adding a 韵母yun mu from this word to form the “反切” fan qie’s second word (or lower word). Use the lower word’s tone for the word’s tone. The first word’s starting sound and the second word’s ending sound is the pronunciation of the original word.  As translated by the Chinese History Forum

Code sticks were used in which each stick length represented a particular pre-agreed upon the message. These stick lengths could be transmitted using signal fires without actually having to physically send the stick. More generally this technique is equivalent to code books which were also used by the ancient Chinese.

  For example, one-inch stick means victory. 9 inches stick means the army has broken the enemy army and captured the enemy generals. 8 inches stick means the enemy’s city (cities) has surrendered. 7 inches stick means successfully resisted the enemy’s army and the enemy’s army was gone. 6 inches stick means the army should be alert and defend the place diligently. As translated by the Chinese History Forum

Grille ciphers have often been remarked as excellent pen and paper ciphers for Chinese.
While I can't find any historical reference to it, transposition ciphers seem completely compatible with the Chinese language. Although one would have to choose the words carefully because some meaning would leak out as whole words are transposed rather than letters.
A method of enciphering Chinese characters similar to rot16 would be to write different characters on top of each other in different colors of ink. The key would state which color at each position was the correct character. For instance, the key could be 'blue-red-red-black-green-blue'. One of the interesting features of such a scheme is that one could design the cipher text such that all possible keys encode an apparently valid and readable message.  One advantage of this scheme would also be that it is secure against colorblind adversaries.


As you noticed correctly, a hash function is kind-of computationally binding if you assume collision resistance. However, it is impossible to achieve perfect hiding property for hash functions, due to the potential loss of information.

Perfect hiding means, that a computationally unbound Alice COULD decomit any value:
I.e. Pedersen commitments $c = g^xh^r$ can be decommited to any value, if you know the discrete logarithm $log_g h$.

In your hash function you have no guarantee for this: for a fixed pair of commitment and K there might not be $h(N)$ to fulfill the computation. Even replacing $h(N)$ with just $N$ does not imply this property.

In general, a scheme can not be both perfectly hiding and perfectly binding, because they are opposing principles: If Alice was computationally unbound, hiding means she can decomit ANY value, and binding means she could still decomit ONLY the original value.


JOSE: JWE CEK Initialization Vector Position or Reuse

So the answer thanks to @kelalaka's comments is that X25519 doesn't need an iv. I was not using just X25519, but instead x25519-xsalsa20-poly1305 via TweetNaCl.js.
There isn't really a need to use x25519-xsalsa20-poly1305 to wrap the AES-256-GCM key, as the "xsalsa20 is a stream cipher and poly1305 is for mutual authentication".
Regarding JWE, there isn't a way to use x25519-xsalsa20-poly1305 with a JWE because JWE requires Authenticated Encryption Additional Data (AEAD) and salsa only has Authenticated Encryption (AE).
So my options with a JWE are to switch to just using x25519 + AES-256-GCM OR use just x25519-xsalsa20-poly1305 without using a JWE (or at least not a standards compliant one).


Nope, you can always restrict your message space to a subset of the message space for which the scheme is defined (which is the case here).

Note that in practice you will deal with messages relatively prime to $N$, i.e., from $\mathbb{Z}_N^*$, anyways (any message not coprime to $N$ - except zero - would allow you to factor $N$ - thus its very unlikely to hit such a message).


Why $e>n^{3/2}$ prevents Wiener's attack

In Wiener's attack $k$ is a small number ($k<d$). If we set $e^{'}=e+t\phi(n)$ for some large $t$ then $e^{'}$ can be used in place of $e$ for message encryption.Also the k became a big number and we can't using of Wiener's attack.For more detail you can see "Twenty Years of Attacks on the RSA Cryptosystem".


I solved the problem.
So for people who are hunting for the answer, you need to consider what mechs your HSM supports.
Every logic I had in the code was correct. The only problem was the mechanism that I used to derive the key was wrong. There are several mechs that are available to derive the key with, which was the hard part to figure out since it did not specify. I started with CKM_DES3_CBC_ENCRYPT_DATA as stated in the question, but turns out, I had to use CKM_DES2_DUKPT_DATA. And this mech was not defined in any wrapper libraries such as c# interlop pkcs11 library or the one I use, golang. Because this is a vendor defined mechanisms, I had to define it myself, and use it accordingly.

I hope this helps anyone in the future!


Can TLS session resumption work after client dropped connection & reconnected to server?

A TLS session can be resumed once both sides know of the session. The exchange of the necessary information (i.e. session identifier or session ticket) is done within the initial handshake. This means a session can already be re-used within other connections once this initial handshake is done.

How long the session information are kept and if they are discarded if a connection is closed uncleanly depends on the specific implementation and is unrelated to the cryptography itself.


Reversing SHA1 (don't know the correct term)

SHA-1's compression function (as well as MD5 and SHA-2) is build from a (custom-made) block cipher in the Davis-meyer construction. (These are the "invertible operations" you describe in the question.)

The basic idea is to use the message block as the key for the cipher to "encrypt" the previous state:

                    message block
                          |
                          ↓
                     .---------.
previous state ----> | Encrypt | ----> new state
                     '---------'

If this would be the only thing to do, then we actually could (knowing a block of the message and the new state) revert the cipher to calculate the previous state, just like you sketched in your question.

A compression function with this property is not what we call a "one-way" compression function, and would not be a good thing to use as a compression function for a hash function. Therefore this is not what is actually done, the Davis-meyer construction has one more step:

                    message block
                          |
                          ↓
                     .---------.
previous state ----> | Encrypt | --⊕---> new state
                 \   '---------'   ↑
                  \                /
                   \--------------/

This XORing of the "ciphertext" with the "plaintext" has the effect that we don't know the ciphertext output of the block cipher, and can't do our backtracing. This is actually enough to make the compression function one-way, if the block cipher is secure (for some formal notations of one-way and secure).

  If yes, for which other hash functions it will work too?

As explained, no hash function with your trackback property can be deemed secure, so we can conclude that no modern hash function should have this property.

  Would it work vice versa when A is known?

If A is known, you also know sha1(pad(A)), e.g. the state after hashing the first block, e.g. the input to the second block.

Looking at the diagram above, we now know both the plain text input as well as the cipher text output of the block cipher. From this deriving the (or any) used key is known as a known-plain text key retrieval attack (or chosen-plaintext, if the attacker can actually influence A and see hash(pad(A)||pad(B))). If the block cipher is any good, it should not feasible to retrieve any useful information about the key pad(B) (other than by trying examples, i.e. brute forcing).


Is timing analysis attack the same as cache timing attack?

No, cache timing attack is not the same thing as timing attack. The former is a subcategory of the later.

Timing attacks are about inferring information about confidential data (key, plaintext..) from measurement of a computation's execution time. Obviously, timing attacks are only possible when the execution time varies for some reason, and that reason has some corelation with confidential data.

Cache timing attack is a special form of timing attack where the cause of the measured variations of the execution time is operation of some cache (typically, cache memory in a CPU, even though a branching cache would also fit).

For terminally bad implementations of DES, it is conceivable that other causes of execution time variation correlated with confidential data exist, beyond a cache. Examples:

permutations implemented using if .. then
logical operations implemented using short-circuit Booleans

However no competent DES implementer would do such thing (other than deliberately to enable timing attack), leaving cache (memory) timing attack as practically the only kind of timing attack worth academic interest in the case of DES implementations.

In domains other than DES implementations, there are several other causes of timing variation beyond caches, and timing attack worth investigations, including:

comparisons (including, of DES-based MACs) made using memcmp, strcmp, or similar method that stop on the first difference found
at what point verification fails in a sequence of verifications, e.g. timing variation of Bleichenbacher's attack on RSA with PKCS#1 v1.5 padding
influence of the bit pattern in the exponent (resp. multiplier) in modular exponentiation (resp. group multiplication)
variations of duration of the multiplication instruction of a CPU as a function of the bit size of one of the operand
variations of duration of the division instruction of a CPU
if a subtraction of modulus occurs, or not, in a modular reduction


Asymmetric encryption is vastly inferior to symmetric encryption. That is, in all respects, except one -- being asymmetric. When that property is needed, there's no way around it, obviously.

Asymmetric encryption is much slower. It is much more susceptible to showing recognizable patterns of some kind given non-random input. You need much larger key sizes to provide an adequate level of protection, and the system is much more vulnerable in general with current and future technology (reasonably-sized quantum computers will basically mean instant death for RSA, but AES is pretty much "yeah, so what" in that respect).

That's the reason why asymmetric encryption is almost never used to encrypt bulk data.

Nothing prevents you from encrypting a terabyte of data with RSA using 2048 bit chunks, much like you encrypt a terabyte with AES in 128 bit chunks. Only just, it doesn't make sense to do that because it is several thousand times slower, and at the same time is much more insecure.


Is there an asymmetric scheme where keys form a graph and a message can only be decrypted across a certain degree of separation?

This looks like a new research to be done. I believe this is doable starting from graph characteristic polynomial as introduced at iacr 2008/363 and CECC 2009 (shameless). "Trusted" relationship would mean knowing secrets associated with neighbor nodes. Having secrets of trusted network of neighbors, sender would produce characteristic polynomial such that any trusted node can divide, that is, produce zero remainder polynomial. There might be a variant of ElGamal encryption designed from probabilistic test (Schwartz-Zippel) for zero remainder condition, which would likely complete this design. Considering (verifying) characteristic polynomials over a ring modulo random linear polynomial (no such ring at 363 preprint yet) might be a practical solution. Welcome.


Implementation of MiMC over Edward curve

Using the MiMC-hash function won't actually give you a hash function that outputs a point on the Edwards curve. The MiMC-hash function is based on a sponge-construction that uses the MiMC-permutation internally and is configurable for any $l$-bit output. It is designed for applications that profit from a low number of multiplications such as multi-party computation, zero-knowledge proof systems or SNARKs.

It seems you just want a hash function that takes an arbitrary input and outputs a point on a specific curve. In that case and depending on your specific requirements you could look the "try-and-increment" method described in section 3.3 here or at the methods described in this work.


Given this protocol, can you find some weakness?

One weakness with this protocol is that the compromise of a past symmetric key, which can often be assumed over some sufficiently large period of time, compromises all keys and messages sent after the time that key was first used.

edit:

If any $K_{ab}$ is compromised, a man in the middle attacker can resend message 4 corresponding to the compromised $K_{ab}$ and it will be accepted by $A$. The attacker can then impersonate $B$ communicating using the compromised key.


How to define the statistical distance between two probabilistic algorithms?

In general, total variation distance—which is the specific metric you're talking about, one of many that might be called ‘statistical distance’—of two random variables $P$ and $Q$ is defined by $$\sup_A |\Pr[A(P)] - \Pr[A(Q)]|,$$ taken over all random decision algorithms $A$.  For the computational version, we simply restrict $A$ to be, say, a cost-limited algorithm that examines only $q$ parts of the variable—if it is a bit string, examines only $q$ bits; if it is a function, queries it at only $q$ points.

If the support is finite, the total variation distance coincides with $$\frac 1 2 \sum_x |\Pr[P = x] - \Pr[Q = x]|,$$ taken over the common support of $P$ and $Q$.

This notion is the same whether $P$ and $Q$ are supported on coin flips, integers, functions, perfectly normal beasts, sets, Riemannian manifolds, probabilistic algorithms, or bit strings (for some of these, to be meaningful, you may have to replace ‘random decision algorithm’ by ‘measurable function’).

Once you set down what a decision algorithm can do with a probabilistic algorithm, the answer will fall out.  The usual notion formalizing probabilistic algorithms, as you observe, is just a deterministic function with parameters for all the coin flips it needs—of course, on some inputs and coin flips the algorithm may diverge, which we formally represent by ‘returning’ $\bot$.  As such, it's not substantively different from your keyed functions.


AES - the block cipher - can be used to process a large amount of data. In that sense it is possible to keep a single static key. How much data is specified in this answer by Thomas on the Security.SE site: around $2^{64}$ blocks of data or 250 millions of terabytes.

Generally would want to keep to $2^{32}$ blocks of random data though ("only" 64 GiB of data) to make sure that the chance of collision remains low. How much you can actually encrypt depends in the end on the mode of operation used. For CTR mode you can for instance encrypt 64 GiB with a random 96 bit nonce $2^{32}$ times with a ~ $1 \over 2^{64}$ chance of collision as the input of the block cipher isn't random.

If the use of AES with a static key is secure therefore depends not on the block cipher but how the block cipher is used: in other words, the protocol or protocols in which it is used. It may be insecure because the mode of operation introduces constraints that are voided by your protocol. It may not be secure because replay attacks are possible, oracles exist, the combination of cipher mode and MAC mode are vulnerable to attack, the list goes on...

AES does certainly leak information if the same input block is fed into it twice. If that's an issue depends - again - on the protocol. Your small algorithm could possibly be used to generate nonces so that the input to the AES cipher is always unique.

That using such a scheme can be relatively secure is shown by memory cards such as DESFire (which, funny enough, may also use AES). These cards are generally provided with one or more symmetric keys that are static during the lifetime of the product. Of course all the devices use derived keys that are tied to some unique identity of the card, otherwise extraction of one key would be enough to destroy the functionality of all of the cards.

Still, if the master key (from which the device keys are derived) is lost from which the other keys have been derived such schemes are certain to run into some form of trouble or another. It is very tricky to perform key  management on static keys, and such schemes are fraught with danger. This is why asymmetric keys are commonly used with a PKI scheme to ensure validity. For such schemes the controlling device doesn't need to hold a master key.

Sometimes devices are also provided with multiple keys (for multiple master keys) in advance. That way the device may still be used with a new master key if one becomes compromised. Needless to say, invalidating a master key on the devices and moving to the next one is tricky at best (if you can detect compromise in the first place), but you could possibly provide key rollover for your protocol.

Needless to say, using a static key makes it very vulnerable against side channel attacks on the implementation. Compare this for instance with a secure channel which needs to be reestablished using fresh session keys any time the MAC authentication tag is invalid. Those keys are probably invalidated before you can find out anything interesting about them.


Subtracting a point in elliptic curve cryptography?

The inverse of a point $P = (x_P,y_P)$ is its reflexion across the $x$-axis : $P' = (x_P,-y_P)$.

If you want to compute $Q-P$, just replace $y_P$ by $-y_P$ in the usual formula for point addition.


Can you help me understand the RSA Broadcast Attack?

Your solution works for Part 1 because (there) for each $i \neq j$ holds  $gcd(N_i,N_j) = 1$. In Part 2 $gcd(N_7, N_{13})$ is not equal to $1$.
$N_{13}$ is a product of two primes ($q = gcd(N_7, N_{13})$ and $p = N_{13}/q$).
Using that information you can recover the secret key $d$ (simply invert $e$ modulo $(p-1)(q-1)$ as during the key generation of RSA) and from that you can recover $m = C_{13}^d (mod\ N_{13})$. We did not use the broadcast attack in this case (I am not sure if you can make it work).


Stateless hash based public key cryptography?

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say).  Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message.  As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a collision is unlikely.

It takes some extra work to make this work.  In particular, if your tree used only hash functions, then to precompute the public key, you'd have to do $2^{80}$ work to populate the entire tree -- no good.  So, in fact we do a multi-level tree where the entries at one level are used to sign a subtree the next level down (signed, using Merkle-Winternitz signatures).

For more details on how to make this work, you can see, e.g.,  https://www.imperialviolet.org/2013/07/18/hashsig.html or https://www.cdc.informatik.tu-darmstadt.de/reports/reports/BDKOV07.pdf.

This does increase the size of signatures and the amount of computation needed a bit, but if you want a stateless scheme, it might be viable.


How does the encryption/decryption process work?

Diffie-Hellman does not generate public and private keys. It generates an agreed number in such a way that:

An eavesdropper cannot work out what number has been agreed upon.
A man in the middle can either know the agreed number which party $A$ is using and the agreed number which party $B$ is using, or ensure that the agreed number which party $A$ is using is the same as the agreed number which party $B$ is using, but not both.

No encryption is involved in Diffie-Hellman and Diffie-Hellman does not generate encryption keys.

Of course one of the main uses of an agreed number would be to do encryption with it – or rather, with a key derived from it. But that is nothing to do with Diffie-Hellman per se.

To that extent, your question is "How, given a number, do I turn it into an encryption key and use it?" – to which the answer is, "In any way you like".


Is there a formal language to define a cryptographic protocol?

Disclaimer: I use Coq on daily basis...

About the tools

As you are looking for a formal verification, I would advise you to take a look at Coq. Even though mainly used by Academics, it provides a logical framework and an interface to write formal and interactive proofs.

Based this language there exists some libraries dedicated to cryptographic proof :

CertiCrypt
EasyCrypt (tutorial)

Example of proof :

Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols
Formal certification of ElGamal encryption

PHD : Formal certification of game-based cryptographic proofs

Other formal tools (interactive provers) can be used such as Isabelle, Agda, Fstar and HOL.
And some more readings :

Computer Verification in Cryptography
Probabilistic Relational Verification for Cryptographic Implementations

As Mikeazo said, Cryptol might be an other possibility, but I can't say more on it.

About the formalizations

I would also suggest you to have a look at the $\pi$-calculus which is mainly used to explore the verification of concurrent programs, but could be applied in the case of protocols.

Because most of those proofs are game based, one of the notion applied in this case is probabilistic couplings.

Some interesting readings:

Introduction to Symbolic Verification Methods, David Basin, ETH Zurich
Computer-aided cryptographic proofs, Gilles Barthe, IMDEA
Human Errors in Security Protocols, David Basin, ETH Zurich

Given the nature of your project, I would strongly recommend you to have a look at the works of David Basin as they have a software that seems to do what you intend to work on (from what I recall).


MAC using a modified CBC mode of operation

This scheme is not worth the name MAC; it is horribly weak.

First and foremost, the tag/MAC is unchanged when two blocks of plaintext are exchanged (because of the commutativity and associativity of the $\oplus$ operation). If follows that from any message with at least two different blocks, we can make a different message for which we know the tag/MAC. This conclusively proves that this MAC is not secure, for any modern definition of security (which must include that a new message crafted by an adversary ignoring the key from other messages+MAC will pass verification with odds marginally above $2^{-n}$, where $n$ is the width of the MAC in bits).

Further, if we happen to know the tag/MAC of a message with two identical blocks, we can change these blocks to anything, and that will leave the MAC unchanged.

If the message length is allowed to vary, things get worse: the tag/MAC for the concatenation of messages is the XOR of the tag/MAC of the originals; and we can insert two identical blocks in a message leaving the tag/MAC unchanged.


Searchable Encryption with Substring Search

There are some works both theoretical and practical that they do solve your problem efficiently and in a secure way. By efficiently i mean the search efficiency is linear on the size of the searched substring. This is achieved by using auxiliary data structures known as suffix tree. Chase and Shen  follow this approach, by encrypting the suffix tree with symmetric primitives.

This work does not use any auxiliary data structure for efficiency. It encrypts consecutive n-grams and their positions.

A theoretical work follows another technique. By altering the subset sum problem to be easily solvable they issue subset sum instances to the cloud, and the cloud solves them polynomially and the solutions are the positions in the original string of the substring.

Stronger security guarantees with oblivious ram are presented here


Yes, there is a lot of difference, although it depends on how the software is produced and published as well.

With a hash you can just check if the file - as downloaded - is correct. For instance if you retrieve a file through a mirror or torrent then you might get a different file than you asked for. Validating the hash on a controlled site by the owner can then assure you that the file is correct. Of course you'd want a different hash than MD5 and SHA-1 is not secure anymore either - SHA-256 is often used instead. However, if an attacker can replace that hash then you're still vulnerable; all it takes is to compromise the site hosting the hash; anybody can calculate a hash over any file after all.

If there is a signature over the file, and you can trust the public key of the developer, then you can just verify the signature. An attacker cannot create a valid signature even if the hosting site of the signature is compromised. In general the key is kept secure with the developer team rather than the persons available for the hosting of the signature.

That's not to say that signatures are a panacea. Establishing the trust of the public key can be tricky and the security of the signing key or signature generation service may not be up to par. For instance, Microsoft authenticode keys have been misused in the past.


IND-CCA Security of a encryption scheme which is combination of two schemes

You should really specify how are they combined. If it is just composition, you should analyze the cases $S_1=\Pi_0\circ \Pi_1$ $S_2=\Pi_1\circ \Pi_0$, $S_3=\Pi_0\circ \Pi_0$ and $S_4=\Pi_1\circ \Pi_1$, where $\Pi_0$ is CCA and $\Pi_1$ is CPA. If you manage to prove a security type all four cases, you may establish rules for a general composition. However, you may also consider the meet in the middle case when composing if that is your definition of IND-CCA.


Playfair Cipher Confusion with one column encryption

TR would be replaced using rule 2 of the Wikipedia description:

  If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively (wrapping around to the left side of the row if a letter in the original pair was on the right side of the row).

So TR would become PS. See also step 10 of the example there.

Note that T and R are on the same row, not the same column.

You may want to use a larger key (i.e. one that includes more characters of the alphabet).


One way is to look at how many bits of the outputs are modified if you modify, say $t$ bits in the input. Actually, a function from $\{0,1\}^n$ to $\{0,1\}^m$ such that modifying $t$ bits in input modifies $m-t+1$ bits of output is said to achieve perfect diffusion.

Examples of functions with good diffusion are those associated with MDS matrices. For instance, the permutation layer of the AES is made of one such function (it is the "mixcolumn" part of the algorithm).


The primary problem with encrypt-then-sign (signing the ciphertext) relates to the difference between signing for the purpose of assigning responsibility vs for the purpose of taking credit.  Encrypt-then-sign is OK for the former but not for the latter.  The issue is quite subtle.

In particular, in your protocol, the recipient has no reason to believe the sender (signer) was ever aware of the contents of the plaintext.  The signer must have been aware of the contents of the ciphertext and approved signing the ciphertext, but this does not mean that the signer knows or created the original message.

For instance, suppose we're using this to log into a site.  Suppose Alice, who is a system administrator, is going to authenticate to Sam, who is a server.  Suppose that, to authenticate, Alice is going to use your scheme to send a copy of the root password to Sam (encrypted and then signed); if everything checks out, Sam will conclude that Alice knows the root password and should be granted full access to the server.  Sounds reasonable, right?  But now look what can go wrong.  Mallet can intercept Alice's encrypted-and-then-signed packet, strip off Alice's signature, append her own signature, and forward it to Sam.  Sam will receive it and everything will check out: Sam can see that this was signed by Mallet and decrypts to contain the correct root password, so Sam will conclude that Mallet should be granted full access to the server.  That's bad.

The reason why an attack is possible in the latter example is that Alice and Sam were using the signature as a basis for taking credit: Alice was trying to take credit for knowledge of the root password, and Sam was willing to accept the signature as evidence for that.  However, encrypt-then-sign does not provide a basis for allowing the sender to take credit for knowledge of the contents of the message.

So, whether this scheme is adequate will depend upon the particular application you have.  Many applications only need authentication for the purpose of assigning responsibility: if something goes wrong, we know who to hold responsible (or, we know whose account to charge or whose quota to decrement), and encrypt-then-sign is fine for that.  But a few applications (the password authentication example I mentioned; auctions; and some others) use authentication to additionally allow the parties to take credit for knowledge of a message.  For those applications, vanilla encrypt-then-sign can be problematic.

There are ways to fix encrypt-then-sign so it doesn't have this shortcoming.  See the research literature below for details.

For more details on all of this, including what can go wrong as well as how to avoid these problems, you can read the following detailed explanation in the research literature:

Prudent engineering practice for cryptographic protocols. Martin Abadi and Roger Needham.  See Section 5.2 (but the entire paper is fantastic and a classic).
Security Protocols and their Properties.  Martin Abadi.  See Section 5.


Although not really a question regarding cryptography, Sylow's theorems are quite boring for cyclic groups (or any commutative group):

$(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic and has order $p-1$
Theorem 1 gives you the existance of subgroups with order of every prime power divisor of $p-1$, where every element has a power of that prime as its order.
Theorem 2 on its own isn't all that useful, because conjugation of subgroups doesn't give you a different group in commutative groups: $g^{-1}Hg=g^{-1}gH=H$

Now the part you are asking about: The number of Sylow p-subgroups is fixed - it is $1$. Let's say we want a Sylow p-subgroup for prime $q$ (not to cause confusion with the group order $p-1$, and $q$ divides $p-1$). Theorem 2 states that Sylow groups are conjugate to each other, however conjugation always gives you the same subgroup. Assuming there are two Sylow p-subgroups, then theorem 2 would require them to be conjugate. However, that means those two subgroups are actually equivalent.


Including a "purpose" designation in a digital signature

A signature algorithm operates over a sequence of bits -- any sequence of bits. The meaning you may want to attach to these bits is totally none of the business of the signature algorithm. It is supposed to be handled at some other level.

Basically you want to attach some meta-data to the signed object, and have that meta-data signed as well. The usual solution is to compute the signature over a structure which encodes the meta-data and contains the target message as well. See, for instance, the CMS standard. When a "document" is signed, it is wrapped in a SignedData structure which contains "attributes", e.g. a "Content Type". The signature is computed over an encoding of (some of) the attributes, one of them containing a hash of the document itself.


Can the backdoor in Dual_EC_DRBG be used to create a public key stream cipher?

You can do something like what you are suggesting. But, the EC_Dual_DBRG also has biases in the stream and so you cannot use it without changes (e.g., truncating much more). However, this is based on the same operations as ElGamal.

The public key is set up exactly as proposed. Then, to encrypt a message $m$ of any length, do:

Choose a random $r\in\mathbb{Z}_q$, where $q$ is the order of the Elliptic curve group
Compute $U=r\cdot P$
Compute $k = H(r\cdot Q)$
Encrypt $m$ with $k$ using any symmetric encryption scheme you wish


What are the differences between a UHF (as used in cryptography) and a cryptographic hash function?

The usual definition for a hash function - to avoid hard coded collisions, i.e. trivial formal adversaries have a collision as part of their description and just output it- is as a pair of algorithms $(\operatorname{Gen},\operatorname{Hash})$. In this definition $\operatorname{Gen}$ typically picks a "key" for the hash function, which for the "keyless" ones can usually be seen as the details of the description, like the exact structure and constants.
The advantage of an adversary $\mathcal A$ against the collision resistance of a scheme $H$ is then defined using the following experiment:

$k\gets \operatorname{Gen}(1^\kappa)$
$(m,m')\gets\mathcal A(1^\kappa,k)$
$\mathbf{Adv}_H^{\text{CR}}(\mathcal A;\kappa)=\Pr[\operatorname{Hash}(k,m)=\operatorname{Hash}(k,m')\land m\neq m']$

A scheme is then called collision-resistant if for all polynomial-time adversaries $\mathcal A$ the advantage $\mathbf{Adv}_H^{\text{CR}}(\mathcal A;\kappa)$ is negligible in $\kappa$.
This definition essentially amounts to "give the adversary a full description of the scheme and then they win if they find a collision". The key serving the role of the definition of the hash function having only existed for so long in the real world, i.e. the key being given to the adversary the moment the hash function design was finalized.
Now for a UHF on the other hand the security definition is much weaker. The advantage of an adversary $\mathcal A$ against the universal hashing security of a scheme $H$ is then defined using the following experiment:

$(m,m')\gets\mathcal A(1^\kappa)$
$k\gets \operatorname{Gen}(1^\kappa)$
$\mathbf{Adv}_H^{\text{UHF}}(\mathcal A;\kappa)=\Pr[\operatorname{Hash}(k,m)=\operatorname{Hash}(k,m')\land m\neq m']$

A scheme is then called universal hashing secure if for all polynomial-time adversaries $\mathcal A$ the advantage $\mathbf{Adv}_H^{\text{UHF}}(\mathcal A;\kappa)$ is negligible in $\kappa$.
As you can see for the UHF security, the adversary doesn't get a full description of the scheme. They don't even get oracle access - i.e. they can't query values to get their hashes. So they have to come up with a collision that works for a non-negligible amount of instantiations ("keys") of $H$. Obviously this definition is much easier to satisfy. In cryptographic practice dedicated UHF schemes actually even break down in security if an adversary learns a single input-output pair, allowing an adversary to completely recover the key $k$ and produce collisions at will.


It is very similar to how we authenticate ourselves to a website. During registration, the website must store enough information to, at some time in the future, convince itself that the person trying to authenticate now is the same person who registered at some time in the past. For online services, this typically involves storing some function of the password. The online service also wants to make sure that the stored information is stored safely (i.e., unauthorized entities cannot get it) and authenticated (i.e., no unauthorized parties can change it). Otherwise authentication would fail.

With a PUF, it is almost the same. You register the PUF with the system by extracting $R$ and $P$ from $w$. $R$ and $P$ would then be stored in, for example, a database. When the PUF is used again to authenticate, the service would read $w'$, pull $P$ from the database and run the reproduction procedure to get $R'$. It could then pull $R$ from the database and see if $R==R'$. If so, authentication is successful and access is granted.

How you protect $R$ and $P$ from the generation phase is up to you. It also depends on how paranoid you are, how valuable the service is, your threat model, etc. For some, simply storing them in a database that (hopefully) only they have read access to is fine. Others might want to encrypt and sign the values.

It should be noted that $P$ is a public value. It does not need to be kept secret for the system to be secure. As you noted, however, if someone tampers with $P$, they could trick the system into authenticating the wrong party. Equivalently, if I change the hash stored in a database with login credentials, I can now become that user.

Active Attacker Update

Things become tricky when you allow your adversary to modify $P$. AFAIK, there are no guarantees that the attacker cannot modify $P$ in a devistating way (e.g., to publically reveal $R$). And I am not aware of any PUF research to mitigate the problem.

Fortunately PUFs and biometrics are very similar.

Both are a noisy source
Both require fuzzy extraction to be used to handle the noise

Given that, hopefully the following will at least help to solve the problem.

In "Robust and Reusable Fuzzy Extractors" by Boyen in the book "Security with Noisy Data", Boyen tackles a similar problem. From the chapter:

  Unfortunately, ordinary fuzzy extractors do not address the issue of an active adversary that can modify $P$ maliciously, either on the storage server or while in transit to the user.

I don't fully understand the details of the work yet, so I don't feel it wise to try and describe the algorithms and protocols.

NOTE: It looks like much of that chapter was taken from a paper by Boyen and some of his colleagues titled "Secure Remote Authentication using Biometric Data". I have not read the paper to confirm that all the detail you might be looking for is there, however.


Given the additive group $(G, +)$ with $|G| = p$ and generator $P$, what are the computations and exchanged messages for Diffie-Hellman?

I use order $p$ and assuming $p$ to be prime and the generator as $P$ (as it is used in context of elliptic curve groups - since you need additive groups where the DLP and the CDHP are hard - which is not the case for $\mathbb{Z}_n$).

Alice chooses random $a\in \mathbb{Z}_p^*$ and sends $A=aP$ (this means $P+\ldots+P$, $a$ times).
Bob chooses  $b\in \mathbb{Z}_p^*$ and sends $B=bP$.
Alice computes $K=aB=(ab)P$
Bob computes $K=bA=(ba)P=(ab)P$

Note that since I assume that we work on elliptic curve groups there is no reduction modulo the group order after the additive operation.


Proof that a encrypted file has the same content as an (existing) original

Retaining the 3DES encryption key would probably do it. Now simply use the same IV as before and encrypt the file; the IV is only random when it is initially chosen. Alice could also encrypt the key and store it together with the message.

You'd have to prove that you used the same key. That's no problem for larger messages in CBC mode where the possible plaintext is known, but for good measure, I'd include a MAC over the IV and ciphertext in the mail header.

Alternatively, and possibly better than using a MAC, is to transmit the random padding with the message and store the secret key. That way you can regenerate the wrapped key by pairing the padded key with a raw RSA operation, proving that it was that specific key you used.

It might be better in the sense that creating a covert channel is harder if all the information is shown to Mike. It has the drawback that it requires access to raw RSA operation, which may not be directly available to you.


possible MITM attack against servers that used to support weak DH?

TLSv1.1 doesn't have a different treatment of the key-exchange parameters than TLSv1.2 has. It's just a little less obvious.

Let's dig into TLSv1.1 specification.
On page 44 you'll find that ServerKeyExchange consists of ServerXXXParams params and Signature signed_params. Now on page 44 you'll actually find a definition of Signature. This definition signs sha_hash with or without md5_hash. Now look at the definition of sha_hash and md5_hash. It states that MD5(ClientHello.random + ServerHello.random + ServerParams) is the definition for md5_hash and that SHA(ClientHello.random + ServerHello.random + ServerParams) is the definition of sha_hash.

Now you've found the  random values you're looking for and hence this is the same methodology as in TLSv1.2, but there the signature is directly applied and arbitrary hash-functions can be used.


Need 32-bit mixing function that has perfect avalanche between octets

At first glance, the MixColumn step from AES (actually, a single column of that transform) sounds like precisely what you're looking for.  It is invertable (AES depends on that), and it does have the property that if one input octet changes, then all four output octets are guaranteed to change.

Most commonly, it's done by table lookup; however there's no reason it couldn't be done by inline code (and that inline code ought to fit in 256 bytes).


Is it theoretically possible to create an unbreakable cipher?

Some of us believe that it is possible to create ciphers and hash algorithms that are unbreakable (like when people said that we'd never run into an MD5 collision in the lifetime of the universe), but get broken in a couple of decades time (MD5 collision can be created on a modern PC in minutes).

MD5 or any other hash function is not proven to be secure. MD5 has already 128-bit output that has 64-bit collision security bound that was low even 2000s. As  "Attacks always get better; they never get worse" and we expect new attacks as time goes. Despite this, consider AES-128 still secure after 20 years. The only practical attack is the multi-target attacks that are applicable to all block-cipher. The easy mitigate is to use 256-bit key that is already the golden industry standard.

Sure, computing power increases and transistors double in count every year, but is a cipher really just a bodyguard that has a limited lifespan and dies when computing power increases? With quantum computing (I'll refer to it as QC) rapidly growing, many algorithms such as RSA and AES are becoming vulnerable.

Classical computer power is limited, there is no way for classical computers to break 256-bit block cipher just by brute-force. Even for AES-128, the collective powers of Bitcoin miners need around $2^{34}$ years to brute force 128-bit AES. As said before for 128-bit the multi-target attack is the real attack and not for 256-bit.
Shor's algorithm can break the RSA and some ECC. There is a secure ECC system like the Isogeny to be considered secure against QC.

I know, AES256 is safe against QC for now, but in the long run, it'll only get weaker and weaker until it is broken. But why (don't consider bruteforce because hashes take care of that)?

In the case of Block ciphers, the Grover can provide at most quadratic speed up and this is proven to be the lower bound. Therefore 256-bit block cipher is safe against Grover's algorithm.
Unless there is a new breakthrough result in QC, we can create a cipher safe against them. See NIST competition on post-quantum cryptography and target security level, or see the Ella Rose's answer on QC

The logic behind cryptography is math, and math is getting more complex (Calculus, modern math, etc). When DES was created, there was no Shor's algorithm or Grover's. As time went on, math advanced, as did technology, and thus Shor's and Grover's algorithms are created. These discoveries weaken ciphers like AES by not a lot, but when they pile up as time goes on, it greatly weakens them.

Is it just impossible to create a cryptographically secure cipher that is strongly rooted in math and designed so that no advance in QC/math will weaken it? If we gathered the world's best cryptographers, gave them telepath (just for example), and gave them 1 billion dollars to create a cipher, would it always be able to be cracked?

It is well-known that the One-Time Pad has information-theoretic security so that no one can break the cipher as long as it used correctly. The key needs to be generated uniformly randomly, the key size must be at least the message size, and the key never to be used again. Then you have the

key distribution problem that you need to solve if you want to communicate. That is a huge problem in the modern world.
key storage problem if you need to encrypt your files. It is the chicken-egg problem.

Therefore, the cryptographers for a long time concluded that instead of the informationally secure cipher, we should use a computationally secure cipher that is achievable with shorter keys. The cryptography is mature enough that we can calculate the security of a system in the foreseeable future. See keylength.com for such predictions.
On the plus side, we can use a key more than once with the help of nonce/IVs.
In today's Cryptography, the usual problem is not the cipher but the human factor;

The deliberately inserted backdoors, DUAL_EC_DRGB
incorrect implementations of PKCS#1 v.5 padding of RSA
leaking messages that are considered not harmful like in Padding Oracle attacks on the CBC mode.
The TPM's fail
Using low entropy to generate the system randoms,
Attack on Facebook's message Franking
are some of the examples.

Others (including me) think that it's impossible. I believe that it is near impossible to create an unbreakable cipher, but I don't quite understand why.

Unbreakable == no limit on the attacker's power then you turn back to Information Theoretically secure cipher as OTP and you will be fine!
Take AES, except for the side-channel attacks, it is secure. It is considered as PRP but no one has shown that is the case or not.
We consider the security against the attack model. If you say you have the unbreakable cipher then I can say my attack model is xkcd-538

Or should we say once you connect your PC to the internet is it no longer secure?
A nice read of Mitnick's book The Art of Deception: Controlling the Human Element of Security

I read this SE question and quickly came to the conclusion that it's a scam and just for views, but I'm sure many people believe it. I would like to know if ciphers can be unbreakable and if they can't be unbreakable, why they can't.

Prof. Lindell is already debunked that there. If people want to believe then we cannot do anything at all for them.
Sure, there will attack the ciphers that are faster than the brute-force and we act according to it.  AES-256 has attacks faster than 256-bit key search, however, these attacks are not practical.
We cannot prove that a cipher is unbreakable since we don't know all possible attacks. The Ideal-Cipher-Model is theoretic and one can create hash algorithms from an ideal-Cipher to be known secure but when instantiated they can be broken.
Theoretically, we can build an ideal cipher; for example, consider a 128-bit key and 128 bits block size. For each key, there are $2^n!$ possible permutation to select randomly and we need to select $2^{128}$ among them uniform randomly. We can represent each permutation with a table of $2^{128}$ rows and each row contains 128-bits of information. Therefore we need to store $2^{272}$ bits and if we generate each bit with random then this is not practical to generate and store. In the realization, this is neither practical in space, and there is the difficulty of secrecy and uniformity of the physical randomness. In contrast, modern cryptography easier to understand which helps to easy to analyze and control the security.
In short; we act on what we understand and analyze and control our assets according to the foreseeable future, not something that we cannot easily understand and analyze.


The decryption error occurs for the following reason.

In a classical NTRU decryption you compute

$c = e * f \pmod q \pmod p \\
\ \  = p r*h*f + m*f \pmod q \pmod p\\
\ \  = p r*g + m*f \pmod q \pmod p$

By construction $f = 1 \bmod p$. Therefore, if the all the coefficients of $(p r*g + m*f)$ are within the interval of $0$ and $q-1$, (or $-q/2$ and $q/2$, depending on how you define mod operation. Then you will have $c = m \bmod p$. On the other hand
if any coefficient is not within the interval, $\bmod q$   will cause a wraparound since in this case:

$p r*g + m*f \pmod q \pmod p \neq p r*g + m*f \pmod p
$

The current parameters for NTRU ensures that this wraparound does not happen
except for negligible probability, say $2^{-128}$, etc.

Now back to your re-randomization process, suppose

$e_1 = pr_1*h+m$ and $e_2 = e_1+pr_2$

When decrypting $e_2$, you will have

$c = e_2 * f \pmod q \pmod p \\
\ \ = p (r_1 +r_2)*h*f + m*f \pmod q \pmod p \\
\ \ =  p (r_1+r_2)*g + m*f \pmod q \pmod p
$

As you can see, you have grown the $r$ term and therefore you increase the
decryption error probability. You probably will be fine with a few re-randomizations since adding only a few of $r_i$ doesn't increase the $r$ term much. But eventually you will see a decryption error by repeatedly re-randomization.


Because the current answers may be a bit cryptic, I'll make a quick write-up of the solution of this one, as the asker has already figured out the solution and the way himself.

First thing to notice: $y_1=x_1\cdot h$ and $y_2=x_2\cdot h$, where $h$ is $g^{ak}$ where $a$ is the recipient's private key and $k$ is the ephemeral key of the message, it's assumed static for this. Let $p$ be the known modulus.

First note that $y_1-y_2=x_1\cdot h-x_2\cdot h=(x_1-x_2)\cdot h\pmod p$ and thus $(y_1-y_2)\cdot(x_1-x_2)^{-1}=h\pmod p$, where $x_1-x_2$ is known. Using this one can recover $x_1=y_1\cdot h^{-1}\pmod p$ and $x_2=y_2\cdot h^{-1}\pmod p$ using the extended euclidean algorithm.


Why can't we use a hash with no collision to compress data reliably?

Mathematically speaking, there is no such thing as a collision-free hash. Practically speaking, there is.

Cryptographic hash functions in good standing have no known collisions. That's one of their defining properties. They do have collisions, but there isn't enough computing power on Earth (if not in the whole universe) to find one, given current mathematical knowledge. A SHA-1 value is 160 bits, so we know that there exists a pair of 161-bit strings that have the same hash, but the best-known techniques to find one are out of range of current computing power (not out of range of imaginable computing power, though, which is why we're moving away from SHA-1).

Intuitively speaking, if it's hard to find collisions for a hash, the hash is hard to inverse. If there was a known algorithm to invert a hash, then at some point the algorithm would have to decide which of the possible preimages to go for, and we could run it with both decisions to find a collision.

It is possible to use a hash as a compression function. But since there is no way to calculate the original text from the hash, this compression method can only be used when the original text is available. Sounds useless? Not quite. In fact, that's one the basic reasons to use hashes! Cryptographic hashes are used when there are two storage or communication mechanisms, one that's secure but supports only a small volume of data, another that's insecure but supports a large volume of data. Store the hash on the small, secure storage and the actual data on the large, insecure storage. Then, when you need the file, retrieve the data, retrieve the hash, and check the hash. In this way, the secure storage mechanism uses the hash as a compression function; the decompression function makes use of the insecure storage, but guarantees the security of the outcome. (You'll not that something is lost, however: if the insecure storage is corrupted, this will be detected, but cannot be corrected. The “decompression” mechanism guarantees integrity (if you get the data back, it's the right data) but not availability (you might not be able to get the data back).)

Seen another way, a cryptographic hash can be used as a compression mechanism, but this requires that each time a new file is stored, the decompression function is somehow modified to remember the original file content. This is clearly impractical, but it is of theoretical interest — this basically describes a random oracle, which is a sort of idealized version of a cryptographic hash.

A perfect hash is a different kind of beast: it is mathematically collision-free, but it achieves that by restricting the possible inputs to a finite (usually small) subset of all possible inputs. The decompression function for a perfect hash is usually stored as a table from hash values to the corresponding original data (for example using an array if the hash values are small integers).


Shannon information entropy value of 64 bit data?

I guess that the question's data processing

Uses "64 bit binary value" as symbol of the plaintext.
Enciphers these  with a 64-bit block cipher in ECB mode, and considers the symbols in the encrypted data flow to be the individual outputs of that block cipher.
Assimilates the observed/actual frequency of a symbol $i$ in an experimental data set to the probability $p_i$ it has for the source of that data set. Which of course is an approximation (argument: if we repeat the experiment we'll likely get different frequencies, even if the source is unchanged, thus the probabilities unchanged).
Applies the formula $\displaystyle H\ =\ \sum_{i\text{ with }p_i\ne0}p_i\,\log_2\left(\frac1p_i\right)$ for the per-symbol Shannon entropy of a source of independent symbols of known probabilities $p_i$, even though nothing in the question supports that hypothesis of independence of the symbols produced by the source.

Assuming the above, reversibility of the transformation made on the symbols implies that encryption leaves $H$ exactly unchanged. The $p_i$ summed are the same, only for different $i$. The discrepancy between the reported 15.497477 before encryption and 15.0525 after could come from basing the computation of the second value on output that is not the encryption of the input used for the computation of the first value.
And independently, what's computed is something about the data (I don't know a proper name) produced by a source, but we have no assurance that it's a fair approximation of the Shannon entropy per symbol of the source. Knowing the data set length and the actual number of possible symbols (which depends heavily on how the input symbols are gathered, and what their physical source is) would help build an informed opinion on that.


Intuitive explanation of the $\varepsilon$ parameter in differential privacy

A colleague gave me the following explanation that I think makes a lot of intuitive sense, so I'm reproducing it here. Skip to the last paragraph it you don't care about the proof.
Suppose you're trying to track one individual user, and you're trying to figure out whether they're in the database. You have some prior knowledge about this: $\frac{P(in)}{P(out)}$ is how much more likely you think the user is in the database than isn't.
How does this change once you know the output $O$ of the algorithm? The posterior knowlege can be written as $\frac{P(in|O)}{P(out|O)}$. We can use Bayes' theorem to decompose it:
$$\frac{P(in|O)}{P(out|O)}=\frac{P(in)P(O|in)}{P(out)P(O|out)}=\frac{P(in)}{P(out)}\cdot \frac{P(O|in)}{P(O|out)}$$
If the algorithm is $\varepsilon$-differentially private, then it satisfies $e^{-\varepsilon}\le\frac{P(O|in)}{P(O|out)}\le e^{\varepsilon}$, since there's only one user different between the two scenarios. Using the previous formula, we get:
$$
e^{-\varepsilon} \cdot \frac{P(in)}{P(out)} \le
\frac{P(in|O)}{P(out|O)}
\le e^{\varepsilon} \cdot \frac{P(in)}{P(out)}
$$
This is essentially telling us that $e^\varepsilon$ is how much confidence we can gain about whether one user has been added/removed from the data, by looking at the output. When $\varepsilon=\log(2)$, we can gain a factor of $2$ in the knowledge we have: if we had no information at the beginning (say, $P(in)=P(out)=0.5$), now we might have information like $P(in|O)=2/3$ and $P(out|O)=1/3$, but not a bigger difference.
If you want to dive a bit deeper, I wrote a blog post to elaborate a bit on this reasoning and give a concrete example. I also explain how the formula above can be used to find bounds on the possible values of $P(in|O)$ depending on $P(in)$ and $\varepsilon$:


Why do the messages in IND-CPA have to be of same length

Here is an outline of such a distinguisher would work; if you submit a one byte plaintext, then the resulting ciphertext length will follow some probability distribution (with many ciphers, it will be one fixed length; we'll consider the more general case where it is probabilistic); for this probability distribution, we'll have some $N$ where the probability of the length being less than $N$ is $\ge 0.75$.

So, we submit two plaintexts; one consisting of 1 byte, and the other consisting of $N+1$ random bytes.  If the ciphertext corresponds to the short plaintext, the ciphertext will be of length $< N$ with probability $> 0.75$; if the ciphertext consists to the long plaintext, the ciphertext will be of length $< N$ with probability at most $\frac{1}{256}$ (can be shown by the pigeon-hole principle); hence just looking at the length of the ciphertext can serve as the distinguisher.

Obviously, one way to get around this approach would be to pad out all encrypted messages to a fixed length (and have an arbitrary length bound on plaintexts).  However, this sort of thing is expensive in practice; the leaking of the plaintext length is generally considered acceptable.


The difference of one byte before MixColumn will propagate to the whole column. The goal of this step is to mix the four bytes together to get another four bytes. Look at the definition and try it yourself.

Also, there is some nice property here. There are $256$ possible values for the XOR difference of the two bytes and since MixColumn is linear, the XOR difference of the two columns after applying MixColumn will be the same as applying MixColumn to the difference of the columns before. So there are only $256$ possible values for the entire difference of the two columns after MixColumn.

To make it clear: if $C_1$ and $C_2$ are the two columns that differ in only one of the four bytes, then there are $256$ values for $C_1 \oplus C_2$, and we have $\mathrm{MC}(C_1 \oplus C_2) = \mathrm{MC}(C_1) \oplus \mathrm{MC}(C_2)$, so only $256$ possible values for $\mathrm{MC}(C_1) \oplus \mathrm{MC}(C_2)$.

I think it's a nice property.


How to sell a piece of data through blockchain?

Etherium handles this. You need a trusted Escrow, If you don't trust a single third party you can use smart contracts to use the network as a distributed trusted third party.
You don't trust any single member of the network or even small conspiring groups you trust the network as whole.

With a smart contract you will provide a commitment on the data you wish to send(possibly a key allowing decrypting other data). You will supply a zero knowledge proof you hold a value matching the commitment as well as other proprerties(matches what you want to send).
Notice this assumes the buyer can verify the data he is buying.

The smart contract goes on the blockchain, and enforces the contract when one side provides publicly a value matching the commitment it can be verified by the contract and funds will be "transferred" on the ledger.

The contract is a program executed by multiple parties on the network, you pay them for their services. In etherium this is the cost of fuel.


How does encryption work in elliptic curve cryptography?

How are messages encrypted and decrypted?

Well, the easiest way to do public key encryption with ECC is to use ECIES.  In this system, Alice (the person doing the decryption) has a private key $a$ (which is an integer) and a public key $A = aG$ (which is an EC point); she publishes her public key $A$ to everyone, and keeps her private key secret.

Now, when Bob wants to pass a note to Alice, he first picks a random value $b$, and computes the points $bG$ and $bA$; he then gives the point $bA$ to a key derivation function $h$, which produces a set of symmetric keys; he then uses the symmetric keys to encrypt (and MAC) the message.  He then sends the values $bG$ and $\operatorname{Encrypt}_{h(bA)}(\text{note})$ to Alice.

When Alice recieves these two values, she first computes the point $a(bG)$, which is the same as $b(aG) = bA$; she then passes that point to the same key derivation function, which produces the same symmetric keys that Bob had.  She then decrypts the value $\operatorname{Encrypt}_{h(bA)}(\text{note})$, recovering the note (and verifying that it wasn't modified in transit by checking the MAC.

If you examine this, you can see what Alice and Bob are effectively doing is performing an Elliptic Curve Diffie-Hellman operation, and then using the shared secret to (symmetrically) encrypt a message.  This might seem like we're cheating a bit, however this meets the criteria for public key encryption (anyone with the public key can encrypt, only the holder of the private key can decrypt), and it also sidesteps the issue of translating the message into an elliptic curve point reversibly (which can be done, but it can be kludgy).

  How are the public and private keys determined?

That's easy; for just about any ECC method, the private key is a random integer $a$ between 1 and $n$ the order of the generator, and the public key is $aG$, the point multiplication of the private key and the generator (which is just a point on the curve that everyone agrees upon).  And, in case you haven't come across this in your studies, the order of the generator $n$ is the minimal value such that $nG$ is the "point at infinity"; when we select the curve, we make sure that this is a large prime.


Is there an efficient algorithm that allows to construct a cryptographically secure $n$-bit hash function based on two unkeyed $n$-bit permutations?

It is impossible to construct a collision-resistant hash function from one-way permutations, via a black-box construction. Thus, the answer in principle is no; such a construction is impossible. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? by Simon (Eurocrypt'98). This answer does not relate to heuristic constructions, but you cannot do this with a proof of security (unless it's not black box).

The question here actually relates to "ideal" permutations, and under such an assumption it may be different. (Although, I'm not sure what is meant by "public" ideal.) My answer referred to (non-ideal) one-way permutations.


Just use Shamir's Secret sharing: wiki link

It's designed by Adi Shamir, who is the "S" in RSA. It's fairly simple to use and there are no known weaknesses in it. While it doesn't split the data, splitting the key may work just as well (unless you absolutely must split the data.)


How do single use passwords work for an encrypted message

As hunter notes, the only people who can really say what LastPass actually does are those who work there.  However, as long as we only consider what they can and should do...

They don't really need to store a separate copy of your data for each one-time password.  Instead, all they need to store for each password is an encrypted copy of the key used to actually encrypt the data.

So, when you log in using a one-time password, the password is (presumably) passed through PBKDF2 to derive a "key-encryption key", which is then used to decrypt the actual key needed to decrypt the data.


The comments already have covered the two main points, but let me try to put it in the form of an answer. There are not (that we know) weak keys in AES, in the sense that you cannot formulate a routine $isWeak(key)$. However, there are weak ways to generate an AES key (i.e. bad randomness).

An AES key is just a bit string of length $n$. That means that there are $2^n$ possible keys. If the key is generated by a properly seeded CSPRNG, AES is (computationally) secure. If you don't know about the origins of the key, or it is generated by a less secure RNG (such as Java's Math.random), the key shouldn't be used.


Is there a consensus on what text encoding to use when hashing a string?

Hashing is done on binary, not text strings. It is the job of the character encoding to say what binary representation a string will have. After you represent the text using a particular encoding, then you can hash it. The hash process itself does not care at all about encoding, only binary.

There is no consensus as to what the binary representation a given string will be in every circumstance (i.e. how apple will look in binary), but there is a consensus as to what the hash itself uses as input, which is binary. Most strings use the same encoding (ASCII, UTF-8, etc), and since an encoding is needed to convert a string into a binary representation, the most common encodings will be used when hashing said string. This is not universal, of course. If you enter a string on a Japanese system into a hash function, you may get a different result due to it using Shift JIS or UTF-16, for example. Simply put, there is a consensus in what text encoding to use when encoding text, but it does not specify how that string will be used (e.g. passed to a hash).

Note also that many different text encoding formats are redundant for many characters. ASCII characters are represented as the same string of bits when they are encoded instead as UTF-8. The biggest difference is that UTF-8 is capable of encoding characters that ASCII cannot. Because virtually everyone is using either ASCII or UTF-8, the string apple will be the same in all of them.


Crack cryptographic hash functions using Toffoli gates?

Such a reversible circuit would have many additional output lanes. Since there are too many different values those can have(exponential in the number of extra lanes) you can't guess a complete output of such a circuit. Without a complete output of the circuit you can't reverse it. So your approach doesn't work.

If you could construct a reversible circuit with few additional output lanes, that'd break a hash-function. But there is no simple way construct such a circuit given a normal circuit.

  The Toffoli gate is universal; this means that for any boolean function f(x1, x2, ..., xm), there is a circuit consisting of Toffoli gates which takes x1, x2, ..., xm and some extra bits set to 0 or 1 and outputs x1, x2, ..., xm, f(x1, x2, ..., xm), and some extra bits (called garbage). Essentially, this means that one can use Toffoli gates to build systems that will perform any desired boolean function computation in a reversible manner.

Quoted from Wikipedia: Toffoli gate


Questions

  I'm just a bit confused about the nonce/IV in AES-CTR ... it seems the suggested way to go is have a 64bit random nonce, and use the last 64bits as the counter, "starting at 0".

No, that's just one way of creating a counter block.

Due to the birthday bound you would have about $2^{16}$ messages to have a chance of $1 \over 2^{48}$ that the nonce repeats. Or $2^{32}$ messages with a chance of $1 \over 2^{32}$. Your message size would be $2^{64}$ blocks.

  I'm just wondering why not PRNG initialize all 128bits? Still using a 'static' 64bit nonce and still with the least significant 64bits as the counter, but "IV"'d (set to a non-zero value). Am i missing something?

You're not missing something, that's just another way of doing things.

But this requires the user to generate 128 bits of randomness, and random numbers may not come that cheap - depending on the random number generator used. It would however be tricky to exactly define how many messages at what size (no known bounds), and you'd have to store the initial counter value to detect an overflow (to regenerate keys go into an error condition).

Your scheme could be useful to send many smaller messages in a system that cannot keep state such as a counter for the nonce.

  And in this example (https://tools.ietf.org/html/rfc3686) they clearly have a distinction with 1) a 32bit nonce, 2) a 64bit IV, and 3) a 32bit counter. In essence don't the nonce and IV essentially combine to form just one random use-only-once value? (ie. couldn't they just say "a 96bit nonce"?)

No, if you look at the definition you see that:

  The encryptor can generate the IV in any manner that ensures uniqueness.
     Common approaches to IV generation include incrementing a counter for
     each packet and linear feedback shift registers (LFSRs).

So the IV in the IPsec protocol is there for a different reason than the nonce, which is just there to prevent precomputation attacks (see below).

The IV does not need to be random, which allows for efficient calculation of the counter and a larger message space of $2^{64}$ messages if a counter is used.

  Also can the nonce be stored in plaintext alongside the ciphertext, or is it normally stored in some secured fashion, and if so how?

The nonce in IPsec is a random nonce, so it must be stored alongside the ciphertext (or at least linked to the ciphertext somehow, keeping it with the ciphertext is the most common method). It can be kept in plaintext and does not need to be secured.

IPsec case study

In the case of IPsec, the example in the question, the full counter block is defined using a specific scheme:

  Each PT block is XORed with a block of the key stream to generate the
     ciphertext, CT.  The AES encryption of each counter block results in
     128 bits of key stream.  The most significant 96 bits of the counter
     block are set to the nonce value, which is 32 bits, followed by the
     per-packet IV value, which is 64 bits.  The least significant 32 bits
     of the counter block are initially set to one.  This counter value is
     incremented by one to generate subsequent counter blocks, each
     resulting in another 128 bits of key stream.  The encryption of n
     plaintext blocks can be summarized as:

 CTRBLK := NONCE || IV || ONE
  FOR i := 1 to n-1 DO
    CT[i] := PT[i] XOR AES(CTRBLK)
    CTRBLK := CTRBLK + 1
  END
  CT[n] := PT[n] XOR TRUNC(AES(CTRBLK))

So IPSec allows $2^{64}$ packets to be encrypted if the sequence number is used for the IV, and it allows $2^{32} - 1$ counter for a maximum packet size of over 68GB (1 GB = 10 ^ 9 bytes). Fresh keys are required to be generated whenever the IPsec is restarted or after the encryption of $2^{64}$  packets. It is important to notice that these sizes are not influenced by the nonce.

The nonce is just there to prevent precomputation attacks against the key. This can be found in the security rationale, chapter 7:

  There are fairly generic precomputation attacks against all block
     cipher modes that allow a meet-in-the-middle attack against the key.
     These attacks require the creation and searching of huge tables of
     ciphertext associated with known plaintext and known keys.  Assuming
     that the memory and processor resources are available for a
     precomputation attack, then the theoretical strength of AES-CTR (and
     any other block cipher mode) is limited to 2^(n/2) bits, where n is
     the number of bits in the key.  The use of long keys is the best
     countermeasure to precomputation attacks.  Therefore, implementations
     that employ 128-bit AES keys should take precautions to make the
     precomputation attacks more difficult.  The unpredictable nonce value
     in the counter block significantly increases the size of the table
     that the attacker must compute to mount a successful attack.

So the IPsec has been defined in such a way that it requires a relatively small amount of randomness.

It provides clear bounds on the number of packets (messages) and packet size.

Finally it allows easy detection of overflow so that implementations can go into an error condition rather than to repeat a nonce, destroying confidentiality of the data in the packets.

Although the inclusion of a nonce to prevent precomputation attacks is probably superfluous (due to the large key sizes offered by AES) it may also offer some protection against implementations for which the generation of the IV is faulty.

Note that the CTR spec of IPsec does have its faults:

The name IV is generally used to indicate the initial counter block within cryptographic API's, which is confusing.
It says that "The same IV and key combination MUST NOT be used more than once.", but it should specify that this is specific to the IPsec packets, not the counter blocks.
It doesn't give any security hints in case the IV is generated by an LFSR (pseudo random value).


Considerations on using a single long-term key for file encryption

Is it sufficient to use a simple sequence number for each container and place it in the (authenticated) file header?

Yes, but making sure it is unique may be trickier than you think. Storing a counter is both error prone and it may hamper performance as well. What if you lose the .lock file (or similar) containing the number?

  Should I split the IV/nonce in a fixed and a sequential part (mentioned in RFC5116)?

If you want to, as long is it stays unique. This part of the standard seems particularly important if you've got multiple devices that each have their unique fixed ID. In that case the fixed ID can prevent the devices with coming up with the same nonce.

Personally I don't think you should use the same key in the first place. I don't consider RFC 5116 a strong standard and I would certainly not use it to draw cryptographic ideas from. Especially the part where the authentication tag is part of the ciphertext feels completely backwards to me (as it removes the online properties of AES-CTR that is used for most authenticated modes of encryption).

  Different approach?

Usually a symmetric key is generated for each file, which can then be wrapped by the master key. The advantage is that you can decrypt the data key and add other keys that may retrieve the data key. You may also be able to roll over to a new key that way. In other words, it simplifies key management. That kind of key management is harder to accomplish when using a KDF.

  But then again I could simply use the GUID as IV/nonce. Is there a benefit in creating individual key material for each container?

Yes, you'd be less vulnerable against catastrophic failure if the nonce ever repeats.

Be warned that you may want to protect against files being swapped as well.