Minimal Hamming distance of SHA512 hashes at bit flip For $n\in\mathbb{N}$ let $\{0,1\}^n$ denote the set of $\{0,1\}$-vectors of length $n$. Let $\{0,1\}^* = \bigcup_{n\in\mathbb{N}}\{0,1\}^n$ denote the collection of all finite-length $\{0,1\}$-strings.
If $x,y\in \{0,1\}^n$ for some $n\in\mathbb{N}$, we let $$d_H(x,y) = \big|\big\{ i\in \{0,\ldots,n-1\}:x_i \neq y_i\big\}\big| \;\;\in \{0,\ldots,n\}$$
denote the Hamming distance between $x, y$.
Let $h:\{0,1\}^* \to \{0,1\}^{512}$ denote the cryptological hash function ${\sf SHA512}$.
Question. Is it known whether $$m_0 = \min\{d_H(h(x),h(y)): (\exists n\in\mathbb{N}(x,y\in \{0,1\}^n)) \land (d_H(x,y)=1)\}$$
is positive? Is a lower bound $\geq 2$ for $m_0$ known?

We strongly hope that $m_0=0$ as we wish for the SHA512 compression function to perform as a random oracle. Thus for example, if we were to pick a $2^{521}$ long string $s$ there are $2^{521}$ other strings whose Hamming distance from $s$ is 1. The coupon collecting estimate would return all possible outputs with high probability, including the value that matches $\mathrm{SHA512}(s)$. Thus for any fixed, really long string we hope that there is one bit that you can flip that doesn't change the final value.
We strongly hope not to be able to constructively demonstrate that $m_0=0$ as this would be an example of a hash collision. To demonstrate that $m_0=0$ non-constructively seems to require more mathematical structure than is provided in its design.
Interestingly, the related value
$$m_1=\mathrm{min}\{d_H(h(x),h(y)):(\exists n\in\mathbb N,(x,y\in \{0,1\}^n))\wedge (d_H(x,y)=2)\}$$
can be shown to be zero by the pigeon hole principle. We pick a string of length $2^{512}+1$ and compute the hashes of its one-bit flips. Two of these must match and are a pair of strings with Hamming distance 2.

ETA: @poncho points out that SHA512 is limited to inputs of length at most $2^{128}-1$(!) and so these long string arguments do not apply to the standard version of SHA512, only the abstraction of the question. For the probabilistic argument with the standardised version, then instead we consider all strings of length 522 and fix some bit position these provide $2^{521}$ pairs that differ in that bit position and whose differences should be statistically independent. We should anticipate a full set of differences including 0.
Although the pigeonhole principle no longer delivers $m_1$ it does deliver an upper bound of 10 flips of input to produce matching output. We consider a string of length $2^{127}$ and the set of inputs produced by 5 flips. There are more than $2^{512}+1$ of these and so again by pigeonhole there must be two with the same value. The Hamming distance between this pair is at most 10 by the triangle inequality applied to the Hamming metric.


What does $x^{1/e}$ mean in cryptography in this open butterfly structure? I am currently reading a research paper that introduces this thing called a butterfly structure.

I am confused about the structure of the open butterfly in this paper which has the equation $H^{\alpha}_{e}(x,y)=(R^{-1}_{R_y[e,\alpha](x)}(y),R_y[e,\alpha](x))$ where $R_k[e,\alpha](x)=(x+\alpha k)^e+k^e$ and a corresponding structure as seen below:

I am confused as to how the structure of the butterfly above, relates to the equation. Furthermore, I don't really understand what $x^{1/e}$ in the butterfly structure means. It would be great if someone could explain this. The paper is Cryptanalysis of a Theorem Decomposing the only Known solution to the big APN problem.

Squeamish Ossifrage is correct. This is the power map $x\rightarrow x^t$ where $te\equiv 1 \pmod{2^n-1}$ and the underlying field is $GF(2^n).$

The subject of power maps and when they give permutations with nice properties is quite well studied, and this is a paper along those lines.


Would using a hash of the site name salted with a master password be a secure password for all sites? I am considering creating an application that is able to work out a unique password for a site by hashing the url while using a secure master password as a salt (or technically pepper since it will always be the same?). I am incredibly inexperienced in the world of cryptology so if this is a stupid question then sorry for wasting your time (:

The aim of using salt is having a countermeasure against the Rainbow tables. In your case, we can think of as you are creating a password for each site by using a master password and the URL of the site as salt.

Normally, you will be secure against the rainbow tables. One, however, must consider the case that the master password is compromised. Then all of the sites are easily compromised since your URL is known and the hash algorithm is also known.

A better solution, first, use an off-line system to generate the password for each site using a KDF function ( as Bcrypt, Argon2, PBKDF2) using your master password. For the randomness in KDFs you can use the URL but add other random values, too. Now, save your master password as offline, or delete if you finished.

Then you can use these passwords directly. And, remember you will still need the salt and pepper in your websites against rainbow tables.


Is it secure to derive an AES key from a MAC? I'm working on a project where we need to encrypt a large number of files and store them on the cloud. And I'm wondering if the following process would be secure (we have a “Hardware Security Module” and an “encryption server” in a private data center, only the files will be in the cloud).

Since the volume of the files is too big to be encrypted in an HSM, my idea is to:

Have a 256 bit master encryption key in an HSM.
Derive an encryption key by generating a 256 bit random number and HMAC-SHA2-256 it with the master encryption key.
Take the rightmost 128 bits from the MAC and use that as an AES key.
Take the leftmost 128 bits from the MAC and use them as the IV.
Encrypt the content in an internal server.
Overwrite the memory where the derived AES key was stored.
Store some metadata of the file (including the 256bits random number from the 2nd step).

I would do something similar to generate a signing key:

Have 256bit master signing key in an HSM.
Derive a signing key by generating a 256 bit random number and HMAC-SHA2-256 it with the master signing key.
MAC the encrypted file with the derived signing key
Overwrite the memory where the derived signing key was stored.
Store some metadata of the file (including the 256bits random number from the 2nd step).

To decrypt the data, I would use the random number to re-derive the key. What I'm trying to achieve with this is a different key per file, plus we can rotate the master key every now and then for extra security. Plus, after a few years, when we don't need those files, we can delete the master key (apart from deleting the files from the cloud).

I know the process above is not 100% secure, as the derived key will exist outside the HSM, but we need to keep a balance between security and cost. If storing the plain random numbers is not secure, I could have an AES key in the hsm only to encrypt the random numbers.

The level of security / assumptions I'm happy to live with is:

If the HSM is compromised, all files are compromised (this quite an obvious one)
If the encryption server is compromised, an attacker has access to the plain text files before they are encrypted (so I don't even bother to think about the attacker stealing the AES keys as they are in memory).
An attacker stealing the database (with the random numbers) plus all the files, cannot decrypt the data.

(I hope these assumptions are sensible - please let me know if you disagree!)

It looks like, given your adversary model, things should be secure. HMAC as a randomness extractor has been shown to be good, especially when we can assume the hash function is collision resistant. That paper also has some results which tell how you could guard against the collision resistance being broken (basically use a hash function with larger output size). If SHA-256 is broken any time soon, however, we are all in a lot of trouble, so I wouldn't be too worried about that attack.


Sign a plaintext accepted by a secure function without revealing private key Imagine the following scenario: Alice is a well-respected chef. She is famous for reviewing recipes. Anyone can send her a recipe. If she likes it she'll add her famous line of approval to the end: "This is delicious, y'all". Cryptographically signed with her public key of course. Alice-approved recipes are universally delicious.

But let's be honest, cooking isn't that hard. Tasty food is pretty much just making adding a ton of salt, sugar, oil and MSG. Alice's seal of approval can be replicated by a computer program that makes sure the above are present in sufficient concentrations. Alice would like to kick-back and let the program do the hard work.

So, she hires an untrustworthy middleman, Bob. She hands Bob the computer program. Bob pretends to be Alice. Someone sends her a recipe, which gets forwarded to Bob. Bob runs the computer program, if the recipe passes, he adds her trademark seal and cryptographically signs it with her keys. However Alice only wants Bob to be able to sign recipes that pass. She wants to avoid a scenario where she has to trust Bob with access to her private keys.

Is there anyway to practically accomplish the above? As I understand, homographic encryption, garbled circuits and blind Turing machines can evaluate arbitrary computations. But current implementations are extremely inefficient for complex programs. The logic of the program itself doesn't need to be encrypted. The only thing Alice cares about is protecting her private keys, and restricting Bob to signing inputs that pass the function. Any ideas about whether this is feasible and what the best approach might be?

The cryptographic primitive you're looking for is known as functional signature: in a functional signature scheme, there is a standard signature and verification key pair, as well as an algorithm to derive functional signature and verification keys, for any function $f$. The signature scheme then allows to sign any message $m$ in the range of $f$. The notion was introduced in this paper (see also the papers that cite it on Google scholar, for more recent constructions).

To get a solution to your problem out of this, let me call $P$ the program that checks whether $m$ is a good recipe. Define $f$ as follow: $f(m)$ returns $m$ if $P(m) = 1$, and the symbol $\bot$ otherwise. Now, if Bob (who knows the signing key for this function $f$) can sign a recipe $m \neq \bot$, this means that $m$ is in the range of $f$, hence that $P(m)=1$.

From your scenario, I suppose that you additionally have a function-privacy requirement: $f$ should not be publicly known (otherwise anyone could always check whether a recipe is nice, without the help of Alice), hence the functional signature key should hide $f$. This is known as function-private functional signatures, and is also defined and constructed in the paper I mentioned above. Such a scheme can be constructed for any polytime-computable function, assuming one-way functions and succinct non-interactive zero-knowledge arguments. The latter is a strong assumption, but we now have relatively efficient constructions of such arguments for functions of reasonable size (although probably not standardised implementations) - for example, this one was published a few days ago on ePrint, and seems quite efficient.

Note that none of this would be "incredibly efficient", but still fairly feasible.


How random are commercial TRNGS I'm thinking about buying a USB TRNG. How do I evaluate its randomness? I'm sure some are better than others but which is which? Are thermal-noise better than radio-noise TRNGs?

Evaluating a TRNG device positively requires knowing its structure, both to evaluate the actual amount of entropy it produces, and the possibility to detect a field failure.

Some devices sold as TRNG are in fact a TRNG subsystem followed by a PRNG, which produces the output of the device. In that case, if the PRNG is any good, the output of the device may appear random even though the TRNG subsystem produces no or little entropy, opening the possibility of an attack (perhaps just by enumerating the possible outputs of the TRNG subsystem), especially for an attacker knowing enough about the PRNG.

To illustrate: consider an hypothetical Smart Card with an RNG amounting to a TRNG subsystem followed by an LFSR-based PRNG, which task is to hide any small imperfection of the TRNG subsystem. In case of total failure of the TRNG subsystem, perhaps induced by very cold temperature (as obtained non-destructively by evaporation of a liquefied gas poured on the card), it is easy to guess future output from past one (if the PRNG has few state bits, the output has a short period; even with many state bits, the full state is known after that many bits have been output, with knowledge of the LFSR feedback; even when that's unknown, Berlekamf-Massey allows an efficient attack). There might be less obvious failure modes at different temperatures. If the PRNG is fair (e.g. based on the ASG and enough state bits) but secret, only those in the know of the PRNG design are in a good position to detect the failure, or exploit it.

To avoid this, a modern Smart Card RNG may keep the same basic structure, but with hardware to detect total failure of the TRNG subsystem (e.g. when it outputs constant 0 or constant 1), with some access by the software to the output of the TRNG, to enable testing and certification. Any cryptographic TRNG should have some monitoring system able to detect its failures. In the case of a USB RNG, mere accidental under-voltage could cause the source to fail; and USB ports fuses, hubs and their power supply do fail! Monitoring is a must in contexts where an adversary is in a position induce failure. The monitoring system can be hardware or software, internal or external.

This is a requirement in the AIS31 scheme for common-criteria security evaluation of TRNG (index in German, linking to documents in English; see also how French authorities have been using AIS31 method, including some reservation in section 5). This the best such methodology I've used, although I find it much more complex than necessary to the point of being confusing, and not free from error especially in the examples. My advice if you want to assess by yourself the soundness of a TRNG (rather than delegate that to security certification) is to follow the principles behind AIS31, which I can loosely outline as:

the structure of the RNG must be known and it must guide the evaluation;
the TRNG hardware source must be modeled in some way;
there should be some access to the output of that TRNG hardware source, allowing to check experimentally that the model is sound;
some system must monitor and detect possible failures of the TRNG hardware source, and in that event prevent operation (such monitoring system typically uses the output of the TRNG hardware source);
the model of the TRNG hardware source must support the effectiveness of that monitoring system;
before actual use as key material, the output of the TRNG hardware source must be post-processed by a PRNG, preferably a cryptographically strong PRNG;
the model of the TRNG hardware source must support that comfortably more entropy is fed in the (CS)PRNG than is necessary for security of the output of the (CS)PRNG in any situation where the monitoring system allows operation;
the false alarm rate of the monitoring system should be functionally tolerable (that one tends to be hard to demonstrate).

With access to a raw bit stream produced by a TNRG hardware source, at a point amounting to the output of an analog comparator followed by sampling with a clock, one could do worse than experimentally evaluating the entropy in sub-samples of say 4 to 16 bits (depending on RAM resources and time allowance) by frequency counting, computing experimental entropy from that; doing this as monitoring, with some threshold comfortably below the experimental value; assuming the real entropy is a small fraction of what the threshold supports; and post-processing the whole output with a CSPRNG.

A note on thermal noise vs "radio noise" TRNG sources: I've never met the later, and suspect that it is hard to prove that an attacker can't beam some RF signal towards the TRNG source, strong enough to turn its output into a square wave under the attacker's control.

Thermal noise TRNGs are more classic. They are known to be susceptible to temperature variations; in theory, the colder the less entropy; but high temperatures can introduce undesirable effects in the detector following the source. This might need to be considered (it is very relevant in a Smart Card, not much to something hooked to a PC operated in a trusted environment).

My limited understanding of physics make me see thermal noise as having its origin in quantum noise. I'm equally confident in either as a source of unguessable bits for cryptographic purposes. In my opinion, what matters more than the quantum vs thermal origin of the noise is how it is extracted and converted to bits, and the robustness of that with respect to failure modes and external influence.

This is one area where CSPRNG post-processing helps: in a cryptographic context, it insures that an attacker must have near perfect control of the TRNG source to gain an advantage. As soon as about 160 bits (give or take a factor of two) of actual entropy has been fed into the CSPRNG (without the output being observable by the adversary meanwhile, as rightly pointed by @CodesInChaos), and baring any attack on its design or implementation, the output is indistinguishable from random for any practical purpose (that's even though any CSPRNG using finite memory and no more seeding has a finite period; we are considering computationally bounded adversaries).

The output of any TRNG can't be better than that! On the contrary, in my experience, the unconditioned output of a TRNG source is never free from some detectable bias. If a stream of bits of arbitrary length has odds of 0 vs 1 passing a basic chi-squared test (and especially when that stands taking the effect of temperature and device variation into consideration), this is strong indication that it is not the output of an unconditioned TRNG. And again, any post-processing of the TRNG source must be known and taken into account (in addition to the nature of the source) when assessing the TRNG, and especially the effectiveness of its monitoring.


Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box? This linear secret sharing scheme allows us to share a secret between n parties, such that only an honest majority can reconstruct it.

I understand that – because I do not allow the user to certify the authenticity of the shares nor the value they reconstruct (using for instance VSS or some kind of homomorphic MAC) – they are secure only on the semi-honest case. However, in my mind that problem is more related to integrity, because that even if the adversary sends an incorrect share, the output is unpredictable, and as far as my understanding goes, indistinguishable from randomness.

If that is the case, is there any way an active adversary can learn something by deviating from the protocol i.e., information about the private inputs of the honest parties? If that is so, what would it be?

Here is an active attack on the privacy of out-of-the-box SSS.  For this attack, we'll assume that the attacker (without a valid share) is allowed to participate (with $T-1$ friends with honest key shares), jointly use the protocol to recover a 'shared secret' (which might not be the real shared secret); we'll assume that this shared secret recovery process is done by some MPC-secure method so that the attacker learns nothing other than the final value.  We also assume that everyone's $x$ coordinate is public.

First off, the attacker picks a value $x_a$ which is an $x$ coordinate which is not the $x$-coordinate shared by anyone else.  If the dealer were to generate a share with that $x_a$ value, it would generate a $y$-coordinate that we'll call $y_a$; obviously, the attacker does not know this $y_a$ value.

Then, the attacker then gets a set of $T-1$ friends, and have them recover a shared secret value using their shares (and the attacker will contribute the value $(x_a, 0)$; (actually, a nonzero value for the $y$ coordinate would work, but make the explanation slightly more involved); they'll go through the SSS recovery process, and obtain a value which we'll denote as $S_0$.

If we call the real shared secret $S$, then what the attacker can do is derive a value $T_0$ (which depends on the $x$-coordinates of him and his friends), and derive the linear equation:

$$S = T_0 y_a + S_0$$

This is a linear equation in two unknowns ($S, y_a$), and $T_0 \ne 0$, and so the attacker cannot derive any information about $s$ from it.  This can also be derived from the security properties of SSS; the attacker and his $T-1$ friends only have $T-1$ valid shares, and so of course they cannot recover $S$.

What the attacker then does is get together a different set of $T-1$ friends (there can be some overlap, but there must be at least one difference), and do the same thing again (with the attacker using the same $(x_a, 0)$ share.  They do the same thing, deriving a 'shared secret' value $S_1$, and the attacker ends up with a second linear equation:

$$S = T_1 y_a + S_1$$

Now, if $T_0 \ne T_1$ (which is likely if the two sets of friends are distinct), the attacker has two linear equations in two unknowns; it's trivial to solve for $S$.


What is the motivation behind Key-policy Attribute-based Encryption? What is Attribute Based Encryption? has a nice explanation what both forms (Ciphertext-policy Attribute-based Encryption and Key-policy Attribute-based Encryption) are.

My question is: what is the motivation/analogy behind Key-policy Attribute-based Encryption?

CPABE can be regarded as a variant of Attribute-based Access Control (ABAC) which is a well understood technique. What would be the KPABE equivalent, if there is one?

My take for an example key policy

$$(\text{Student}\wedge\text{Course}_A)\vee\text{Staff}$$

would be that $\text{Student}\wedge\text{Course}_A$ and $\text{Staff}$ can be seen as roles (RBAC) which will be activated through the attributes in the ciphertext. Is this an accurate analogy? Can you come up with a better one?

I believe the answer cygnusv gave is not fully correct. If an object is tagged with "NUCLEAR, TOPSECRET" it can potentially be decrypted by someone not having the TOPSECRET attribute (or NUCLEAR attribute). Why? Because it all depends on the structure of the private keys in the system.

A private key could for example be: "NUCLEAR or SCIENCE LAB A". Thus it would suffice for the object to be tagged with NUCLEAR for this person to gain access.

This is also one of the reasons to why KP-ABE is "less intuitive" because the encryptor does not specify the relation between the attributes that are tagged. Instead it is the key authority (or just authority) which will decide how these attributes needs to be combined for access.


One ciphertext, multiple keys, multiple messages I recently came across following idea, does anyone know a name and if it is actually used?

  A wants to send B a message (A and B know both have a common secret
  key) and C wants to intercept it (without the knowledge of the key)

  Now we assume they have an encryption method that let's you define two
  distinct messages for two distinct keys that both are encoded in the
  same cyphertext.

  With this method A can send the secret message "it is raining
  tomorrow" encrypted with the secret key, but A can also include the
  message "it is not raining tomorrow" with another key.

  If C manages to intercept the message and manages to find one or both of the
  keys, they still don't know anything, as there are two contradicting
  messages. But since B knows which key was used, they can use the
  correct message.

If such an method exists, wouldn't it very secure, or are there any problems that come with it? The only problem I can think of is obiously the size of the cyphertext, and depending on the complexity of the messages you might have to find a lot of messages to completely "diffuse" the meaning.

Sorry for the probably not very fitting tags, I did not find any better ones, as this is just a relativel vague question.

This functionality is usually called deniable encryption. It is feasible for (innocuous/incriminating) pairs of a few messages.

Wikipedia:

  Deniable encryption makes it impossible to prove the existence of the plaintext message without the proper encryption key. This may be done by allowing an encrypted message to be decrypted to different sensible plaintexts, depending on the key used. This allows the sender to have plausible deniability if compelled to give up his or her encryption key. The notion of "deniable encryption" was used by Julian Assange and Ralf Weinmann in the Rubberhose filesystem and explored in detail in a paper by Ran Canetti, Cynthia Dwork, Moni Naor, and Rafail Ostrovsky in 1996.

There are related questions and answers, e.g., is-there-an-encryption-decryption-algorithm-that-can-give-two-different-outputs, and deniable-encryption-from-simple-primitives as well as a few others.


Do you need both client and server side support for TLS 1.3 record padding? When you enable record padding for a client, does a server need a specific option to support this? Or does the other end only need to support TLS 1.3 as well and can handle the padding automatically?

When you enable record padding for a client, does a server need a specific option to support this?

It shouldn't; record padding is a part of the RFC which is not listed as optional; I don't see anyone could claim to support TLS 1.3 without understanding record padding on decryption.


password generation: random length or max length In short:

Is it cryptographically stronger to have a known length password of the maximum length allowed, or a random length password somewhere in the range of the longest length possible?

Does the answer change depending on the max length?  For instance my credit union (still!) forces a maximum length of 10 characters.  Would it be better to utilize all 10 if an attacker knew that that was the length I used, or would it be better to randomly use a length of either 9 or 10.  What if my credit union allowed a length of 16?  Or a length of 255?

Having a random length makes very little total difference in the entropy of your password compared to the entropy you would get using just the maximum length allowed. This is because there are a lot more passwords of, say, length 10 than any shorter length (in fact, there are more 10-character passwords than any other shorter password). So if your attacker has the ability to brute force 10-character passwords, he can easily brute-force passwords from 1 to 10 characters with more or less the same amount of work.

In fact, many password cracking programs take advantage of this by going through the shorter passwords first, as checking them takes a negligible amount of time compared to checking all the longer ones, so if you chose a 9-character password in an effort to thwart your opponent, your password will probably take a fraction of the time a 10-character password would have taken. In other words, choosing a random length is a very bad move, always choose the longest possible length (up to some limit dictated by the software you use or your ability to manage that password).

To justify why they do this, let's get some numbers. For instance, assume a charset of 96 symbols (typical ASCII + special characters stuff). How many 10-character passwords are there?

Answer: $96^{10} \approx 6.64 \times 10^{19}$

Now how many passwords of length shorter than 10 are there:

Answer: $\sum_{k = 1}^9 96^k \approx 7 \times 10^{17}$

And so:

$$\frac{\text{Number of passwords length less than 10}}{\text{Number of 10-character passwords}} = \frac{7 \times 10^{17}}{6.64 \times 10^{19}} \approx 0.01$$

What does this mean? It means that if someone took, say, one year to search through all 10-character passwords, it would only take him about 4 days to search through all passwords of length 1 to 9. Clearly, that person might as well search them too if he isn't sure of the length, for very little additional cost. And he may as well do them first to spare himself a year of waiting in case you picked one of the shorter passwords.

You can do the math for other lengths and charsets, and you'll see that in general, it's not worth it.

To conclude, if an opponent has the ability to brute force passwords of length $l$, then picking a random password of length between $k$ and $l$ where $k < l$ offers very little additional protection, and may in fact decrease security as shorter passwords are generally searched first.


Do standalone Oblivious Transfer (OT) Protocols exist? Are there any Oblivious Transfer (OT) protocols that don’t rely on asymmetrical encryption, public-key encryption or key-exchange?

I’m starting to wonder, as all the OT protocols I know of (and can understand how it works), rely on such an encryption layer. Are there any out there which is somewhat-standalone and does not depend on the security of the scheme/protocol it uses underneath?

The term "stand alone" in secure computation typically refers to the case of a protocol being run once, and not to assumptions. In any case, what I assume you are really asking is what assumptions are needed for OT. You are indeed correct that OT is built from asymmetric assumptions, and this is actually inherent for black-box constructions. This was studied in The Relationship Between Public Key Encryption and Oblivious Transfer.


Why do we need asymmetric algorithms for key exchange? In SSL protocols, both symmetric and asymmetric algorithms are used. Why is it so? The symmetric algorithms are more secure and easier to implement. Why are asymmetric algorithms usually preferred in key exchange?

Say you encrypt a message with a key $k$.

With symmetric encryption (ie. symmetric ciphers), $k$ must be secret. The sender and recipient must agree (somehow) on $k$. No-one else can be allowed to find out $k$. Anyone else who finds out $k$, can decrypt all the messages encrypted with $k$. For that reason, symmetric ciphers are often called "secret key" ciphers - you have to keep the $k$s secret!
Conversely - somewhat against common sense - with asymmetric encryption (ie. asymmetric ciphers), the encryption key $k$ is not secret. The recipient (not sender) chooses a so-called "public key" $k$, and a so-called "private key" $p$. Then they publish $k$ for all to see - perhaps on their website - but keep $p$ secret. Senders use $k$ to encrypt their messages to that recipient. You'd think, why can't other people use $k$ to decrypt all those messages? The answer is, that with asymmetric encryption, the public key $k$ will only encrypt - it won't decrypt. Only the private key $p$ will decrypt. And the recipient keeps $p$ secret. Since $k$ is not only public - but has to be public for all of this to work - asymmetric ciphers are often called "public key" ciphers.

The critical difference is this. Say you want to send me a message:

With symmetric encryption, either (a) you choose a key, and send it securely to me, so I can decrypt the messsage with that key; or (b) I choose a key, and send it to you, so you can encrypt the message with that key. Either way, we need a secure communication channel, to get the key from one of us, to the other. But if we do have a secure communications channel, why  encrypt the message at all? Why not just send it via that secure channel? If that channel is secure, we don't need to encrypt the message at all. But if that channel isn't secure, we can not safely share the encryption key $k$! This is called the "key exchange problem".
With asymmetric encryption, we do not have that problem. I publish my public key for all to see. You encrypt your message with that key. Decrypting needs the private key. And only I have that! So we don't need a secure communication channel to exchange the encryption key.

In summary, symmetric encryption requires the sender and receiver to share a secret key. Achieving that safely, can be a real problem. Asymmetric encryption only requires the sender and receiver to share a public key. Achieving that safely, is much more straightforward.

Finally, as mikeazo said, asymmetric encryption is enormously slow, compared to symmetric encryption.

So, say you want to send me a very long message, using asymmetric encryption. Here's what you'd actually do:

(1) Pick a random key for use with a symmetric (fast) cipher. Encrypt your message using that (fast) cipher and key. Send me that encrypted message.

(2) Then use asymmetric (slow) encryption to encrypt the following message and send it to me:

 "Hi, I just sent you a message encrypted using the BLAH
  symmetric cipher with key ABCDE123456."

Now I (the recipient) use my private key to decrypt (2). This gives me the information necessary to decrypt (1) - voila! Only a small amount of information was encrypted using asymmetric (slow) encryption. The bulk of the data was encrypted using symmetric (fast) encryption. And none of this data needed a secure channel. You could publish all of this data on the front page of the New York Times, with no loss of security.


RSA-blind signatures vs. DSA-blind signatures I see that the RSA blind signature scheme tends to be implemented more often than others, e.g., DSA blind signatures. Isn't the RSA blind signature scheme a 'lesser' scheme, if you may, compared to DSA? DSA appears to be about 6x more performant and is not prone to attacks like timing attacks. The security of RSA scheme isn't even proven, right?

Thanks

Well, I think it is quite hard to give a really objective and complete answer to this question.

Personally, I think that why you may encounter RSA blind signatures quite often is due to it's simplicity. I am not quite sure
if you will see it often in practical implementation though, because there has been a patent (which as far as I remember expired quite recently). RSA blind signatures can be proven secure in the random oracle model under an interactive assumption (the one-more
RSA inversion assumption), see here. Some people may say that proving security under some interactive
 assumption is not really nice, but we do not have any better arguments for this scheme. A nice thing from a theoretical point of view, however,
 is that RSA blind signatures are round optimal, i.e., two move (one message to the signer and one back), and thus automatically concurrently secure, i.e., one
 does not need to care about attacks due to interleaving different signing sessions.

Schnorr type blind signatures (such as blind DSA signatures) are conceptually not that simple (although also not really complicated) and
always at least three move (and thus not round optimal). From a provable security point of view they can be proven secure in the random oracle model,
but as far as I know all reductions require the forking lemma and are thus not really tight. You have to decide on your own if you would rather live with interactive assumptions or loose reductions to the discrete log assumption.

If you are looking for practical blind signatures
in the discrete log setting, you may also look at BLS blind signatures, which are round optimal and
can be proven secure in the random oracle model under an interactive assumption (quite similar to that of the RSA blind signature scheme). However, they require gap Diffie Hellman groups, i.e., groups where the DDH is easy, and thus requires pairings.

From an implementation point of view I think it is hard to give a general answer as it really depends over which types of groups you
are going to instantiate blind signatures in the discrete log based setting.


Why is a hash of blocks - with index - weaker than hashing the entire thing? Let's say we want to sign message $M$ with RSA using a safe hash function.
However, instead of signing $\operatorname{hash}(M)$,
We split the message into 64-bit blocks (|| is concatenation):

$$M = {m_0}||{m_1}||{m_2}||{m_3}\,...$$

For each block we calculate:

$${h_i} = \operatorname{hash}({m_i}||i)$$

and then we calculate the total hash:

$$h = {h_1} \oplus {h_2} \oplus {h_3}\,...$$

and sign $h$ with RSA instead of $\operatorname{hash}(M)$.

Why is it weaker than signing $\operatorname{hash}(M)$?

I know that the order of the blocks cannot be modified because of the concatenation of $i$, and that I cannot add the same block twice because of that too.

I think the answer involves collision, birthday or brute-force attack which may be faster than performing those attacks against $\operatorname{hash}(M)$ but couldn't show that. Any ideas?

P.S: Homework question - hint is enough :)

Ok, here's a hint as to why this construct has essentially no cryptographical strength.

By using Gaussian Elimination, we can solve the below problem in $O(n^3)$ time (that is, very fast):

Given a target value $T$ and $n$ values $v_1, v_2, ..., v_n$ what bit vector $b_1, b_2, ..., b_n$ makes this happen:

$$\bigoplus_{i=1}^n b_i \cdot v_i = T$$

where $\cdot$ is multiplication (so $0 \cdot v_i = $ and $1 \cdot v_i = v_i$), and $\bigoplus$ is the exclusive-or.

If we were given a value $S$, how can the above observation be used to craft a message, that, when hashed by the method in question, generates the value $S$?

Further hint: suppose we were to arbitrarily select $n$ pairs of messages blocks $(m_1, m'_1)$, $(m_2, m'_2)$..., $(m_n, m'_n)$, and we set:

$u_i = Hash(m_i||i)$

$v_i = Hash(m_i||i) \oplus Hash(m'_i||i)$

$T = S \oplus \bigoplus_{i=1}^n u_i$

And we use Gaussian Elimination to find the bit vector $b_1, ... b_n$ with:

$$\bigoplus_{i=1}^n b_i \cdot v_i = T$$

How can we use the $v_i$ values to directly deduce the message that hashes to $S$?

(Practical note: often, there will be no such bit vector that satisfies the equation; this can be handled by including a few extra message block pairs (and hence $v_i$ values).


Is timing analysis attack the same as cache timing attack? I am working on an essay on timing attacks on DES but then i have seen resources mostly about cache timing attacks. so is timing analysis attack the same as cache timing?

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


How does the TLS cipher suite DHE-RSA-AES128-CCM8 work without hashing algorithm I came across cipher suites without hashing algorithm, when inspecting the mbedTLS (previously Polar SSL) TLS cipher suite list.

For example:

TLS-DHE-RSA-WITH-AES-128-CCM-8 (OpenSSL: DHE-RSA-AES128-CCM8)
TLS-DHE-RSA-WITH-AES-256-CCM-8 (OpenSSL: DHE-RSA-AES256-CCM8)

As stated in other questions, the hashing algorithm has applications in TLS, even with AEAD ciphers/modes of operation.

How do these TLS cipher suites work without hashing algorithm and how do they compare to their counterparts with a hashing algorithm, considering the security?

These Cipher Suites are defined in RFC 6655 and use TLS v1.2's default: SHA-256.

To quote it from the RFC:

  These ciphersuites make use of the default TLS 1.2 Pseudorandom
  Function (PRF), which uses HMAC with the SHA-256 hash function.

The default-ness of SHA-256 is probably inferred from the following parapgraph from RFC 5246:

  In this section, we define one PRF, based on HMAC.  This PRF with the
  SHA-256 hash function is used for all cipher suites defined in this
  document and in TLS documents published prior to this document when
  TLS 1.2 is negotiated.  New cipher suites MUST explicitly specify a
  PRF and, in general, SHOULD use the TLS PRF with SHA-256 or a
  stronger standard hash function.


Is it OK to encode data using key equal to data For some project, I need to store some short string in encrypted form. It would be ideal for the current purposes to encrypt it using itself.

# This would be the usual way:
result = AES_ENCRYPT(string, key)

# but I would like to do it this way:
result = AES_ENCRYPT(string, string)

The same string itself would be used as the key!

The 'string' is always some short text, like 20 characters of letters and numbers. This solution seems better to me than using any hash function, since hash could lead to collisions - different strings could potentially produce the same result, which is low probability, I know, but still not zero so I want to avoid that.

My question is, is my approach safe? Encoding the data using the data itself, does it lead to any security issue? Would it mean that it could be easier to decrypt the result, if the 'attacker' knows the fact it is produced by encrypting my way? Thank you.

Your scheme turns AES into a one way function. As you already found out from the comments this scheme doesn't preclude collisions. There is a good reason why hash functions have a larger output size than the block size of most block ciphers as the birthday problem is applicable for this newly build PRF and normal hash functions.

The chance of a collision is so low for SHA-2 that it is easily possible to prune some of the rightmost bytes output and still have a large security margin in case you need a smaller output. The number of hashes required a collision using SHA-256 is about $2^{128}$. I.e. that's about the same amount of tries as brute forcing AES-128. In the end you need to end up with at least double the amount of the required strength in bits.

Your key is a problem as well. You say you have 20 character of letters and numbers. That's not a good AES key. If you just encode it using ASCII you have a 20 byte key; 20 byte keys are not acceptable for AES as block cipher. So you can either thing of some weird encoding method, or you could use a KDF. But the KDF is likely made up by a block cipher or hash function...

Finally, a hash can take any size of input, and it has been designed to be a one way function. This is what it was designed for, there is simply no need for a block cipher here. If you have a need for the function to be irreversible you may want to use a password hash such as PBKDF2, to counter the lack of entropy in the input.


Can I open a file in plaintext (already decrypt) but the cipher doesn't change? I want to create an app that encrypts a file and saves it to the Dropbox. Thus, I open and edit this file, I want the file is already decrypted, but the encrypted file that stored in Dropbox still in cipher text. Whenever I update/edit this file, encrypted file that stored in Dropbox also update. Is this possible?

Yes, it's possible.

Let's assume that you have a text. It is possible for decrypt the text content from the ciphertext when opening the file. The content can be present in the memory without being written to disk. When you're done, it can be saved, which will encrypt the plaintext and write it to a file.

What you need to do:

Figure out the file format (this is probably symmetric, so don't forget random IVs and MACs/authentication tags).
Write either a standalone program, or a plugin for an existing program (e.g. LibreOffice). In particular

User interface,
file opening, parsing and decryption,
data serialization and encryption.


What exactly means to sample from the set of congruence classes? Say one is doing some cryptography around the set of congruence classes, namely: $$\mathbb{Z}/n\mathbb{Z} = \mathbb{Z}_n = \{[0]_n, [1]_m, \dots, [n-1]_n\}.$$
Sometimes we use to write $a \leftarrow_R \mathbb{Z}_n$ to denote that we are sampling an element from $\mathbb{Z}_n$. But, what exactly means to perform such a sampling? I imagine that it is the following

Shorthand for $[a]_n \leftarrow_R \mathbb{Z}_n$ plus $a \leftarrow [a]_n$, i.e., taking the representative of the class, where $0 \leq a <n$.

Is it like that? We typically use this sampled number as an exponent, so it would not make sense to sample an entire congruence class.
At the begginning I though that $a \leftarrow_R \mathbb{Z}_n$ was writing to avoid writing $[a]_n \leftarrow_R \mathbb{Z}_n$ too many times. But it would not make sense.
It is also often to see that $\mathbb{Z}_n = \{0, 1, \dots, n-1\}$. Is it a shorthand for its real meaning?

Sometimes we use to write $a \leftarrow_R \mathbb{Z}_n$ to denote that we are sampling an element from $\mathbb{Z}_n$. But, what exactly means to perform such a sampling?

When we talked about $\mathbb{Z}_n$ we usually consider the least residue system modulo $n$ that is the integers $\{0,1,\ldots,n-1\}$
When we write $a \stackrel r\gets \mathbb{Z}_n$ we usually mean possibly probabilistic process assignment, there are other variants.
When sampling uniformly one should be careful about the random source, simple taking modulus is dangerous and can be biased, discarding is required. Consider your random number generates random numbers in the range $[0,15]$ and you want to sample for $\mathbb Z_{13}$ than taking $\mod 13$ can create a bias since the 13 will map to 0, the 14 will map 1, and 15 will map to 2. Therefore their sampling is more than others, $2/16$ instead of $1/16$. Just discard the numbers $>12$ and get a new random number.
One can use outside of the least residue system like

asked for RSA recently that $e > \varphi(n)$ that will still represent an $e' = e  \bmod \varphi(n) $, or
one can get the private key $k$ in ECC longer than the order $n$ of the base point $G$. It is still useless since $[k]G = [k \bmod n]G$

But the devil in details;  sampling outside may carry some unintended side effects. Always check according to the context!
A further question;

Are we restricted to the least residue system?
Like the adversaries who can do whatever they want that suits their advantage, we can use it, too.

For example, to speed up the gcd we can allow negative remainders.
One may skip a modular reduction step that will cause the number not in the range $[0,n-1]$ and probably higher, Omura '90. In the end, the result must be in the least residue.

In some context, we require the residue as $(n/2,n/2]$ because it forms a ball around the origin and can help to better understand.

For instance, when we want to use ElGamal we write $g^x$, but what we are actually writing? $g^x$ or $g^{[x]_q}$.

First one, since we sample from $[2,q-1]$. When $g^{[x]_q}$ is written it means that the $[x]_q$ can be any of $x+kq$ wher $k \in \mathbb Z - \{0\}$.


Generic name for (?hash) functions of form $\{0,1\}^n \rightarrow \{0,1\}^{poly(n)}$ Consider a function $$f: \{0,1\}^n \rightarrow \{0,1\}^{poly(n)} $$

with the following properties:

hard to invert, i.e. given $f(x)$, hard to find $x$
hard to find a collision, i.e given $f(x)$, hard to find $x'$, such that $f(x') = f(x)$
indistinguishable from a random number i.e given $f(x)$ and $y \stackrel{R}{\leftarrow} \{0,1\}^{|f(x)|}$, hard to distinguish w.p. $>1/2$

So, what is the generic name for this type of functions?

(I could model them as them as ideal hash functions, if i did not have the requirement of $|f(x)| = poly(x)$, but with that requirement, is there a 'expansion function' for hashes? or Does PRGs have pre-image resistant property? or OWFs that satisfy the property of indistinguishability?)

I presume you are referring to hardcore, one-way functions (OWF's) with polynomial span?

There have been a flurry of publications in the past 12 months relating to these functions and their implied possibility or practicability.
The challenge with hardcore predicates has been in achieving polynomial span...

Bellare

  "The original conjecture by Goldreich and Levin only provided a hardcore predicate, meaning span one, and by extension logarithmic span."

Bellare gave a construction achieving polynomial hardcore predicate span for any OWF (injective or not) with polynomially bounded pre-image size (PPS), along with an added assumption of input obfuscation (iO).
Garg countered with an example of an arbitrary (?) OWF which does not yield hardcore bits, either with or without auxilliary inputs.
So in summary, there are competing claims as to the plausibility of OWF's with auxilliary input obfuscation.

If you are thinking more along the lines of iterative permutations or perfect hashing functions, you may find the specific characteristics of your definition are more completely addressed in an outline of my own algorithm, via my website:

unitambo.files.wordpress.com/2014/05/one-way-function1.pdf
(A more polished paper is pending.)

So, in answer to your question. The correct-est term I guess, would be; polynomial span, one-way functions with auxilliary input obfuscation.


Is there a recommendation or standard for using SCRYPT as an unbounded length KDF and not a fixed length authentication hash? How would I go about this? I don't want to roll my own but I do really want to use SCRYPT as a KDF for several algorithms, some of which require an output length longer than the SHA-256 hash. Otherwise with encryption algorithms like AES-256 it's the perfect size already.

Do I just manipulate the keylength of the second PBKDF2 output?
If I'm correct, this technically wouldn't be SCRYPT anymore but just a close variant?

Would it be at all practical to use the SCRYPT hashing algorithm as the PRF in HKDF or PBKDF2 output?

I understand how to use it as an authentication hash but as a full fledged KDF perhaps I don't have the right code and documentation is extremely unclear to me.

The signature for scrypt, straight from the source:

/**
 * crypto_scrypt(passwd, passwdlen, salt, saltlen, N, r, p, buf, buflen):
 * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r,
 * p, buflen) and write the result into buf.  The parameters r, p, and buflen
 * must satisfy r * p < 2^30 and buflen <= (2^32 - 1) * 32.  The parameter N
 * must be a power of 2 greater than 1.
 *
 * Return 0 on success; or -1 on error.
 */
int crypto_scrypt(const uint8_t *, size_t, const uint8_t *, size_t, uint64_t,
    uint32_t, uint32_t, uint8_t *, size_t);

The last argument (buflen) is the output size.  You just give it the value you want (and that satisfies the requirements in the comment).

Given how simple this answer is, I would guess there's some missing context.  Maybe you are using a third-party library that reimplements scrypt or links to the original, but does not provide this parameter for the caller to specify.  In that case, well, then you have some options:

Use a different library that provides the full range of options;
Try to get the library patched to support the full range of options;
Use a key-based key derivation function like HKDF-expand to expand the short scrypt output your library provides.


What goals is homomorphic encryption aiming to solve? As I understand from this article about homomorphic encryption, it
mainly aims to enhance the security of cloud computing. We should be able to encrypt data and send it to the cloud. After it is send, we should be able to make computation on the encrypted data and the result of this computation is an encrypted data too. If we decrypt the result of our computation, then we should get back the plain text version of the result.

The question is, why we assume it enhances the cloud computing? We could just encrypt data, send it to cloud. When we need to make computation, query these data to our computers and decrypt it, make computation, then send it back to the cloud if needed.

Homomorphic encryption in and of itself solves the problem of computation on encrypted data. For example, if I give you only the encryptions of $a$ and $b$ ($E(a),E(b)$) can you compute $E(ab)$ and $E(a+b)$. That is the problem that fully homomorphic encryption (FHE) solves. There are also partially homomorphic encryption methods that allow you to only compute one operation (e.g., Paillier and Elgamal).

Cloud computing is "the use of computing resources (hardware and software) that are delivered as a service over a network (typically the Internet)." So, you push your data to the cloud then tell the cloud what computation to perform. The cloud computes the result and sends the answer back to you. The benefit of FHE when applied to the cloud is that all of this can take place without the cloud learning your data. You upload encrypted data, the cloud performs the comptuations on that data, returns the result. That said, it appears that FHE alone is not sufficient for privacy-preserving cloud computing.

Of related interest, I'd suggest you look at In what ways does Full or Partial Homomorphic Encryption benefit the cloud?


Why does anyone use elliptic curves for a CSPRNG? I saw Martijn Grooten's talk on elliptic curves at BSides London this year, and it helped me understand how elliptic curve crypto works, especially in the case of Diffie-Hellman (ECDH). He also touched on the use of EC for random number generators (e.g. Dual_EC_DRBG) and why they can be flawed / backdoored.

This got me thinking: why do we even bother using EC for CSPRNGs? What drove us to even try? Surely block-cipher based CSPRNGs (e.g. AES-CTR) would be faster and more reliable, with no potential for "hidden number" backdoors? What is the key benefit that EC brings to the world of PRNGs, which outweighs their potential for weakness?

We, for the most part, don't bother with elliptic curve-based pseudorandom generators. DUAL_EC_DRBG was shoehorned into a NIST standard that also included a block cipher generator, CTR_DRBG, and two hash-based ones—Hash_DRBG and HMAC_DRBG—that are actually used in the field.

Number-theoretic generators, which include Blum-Blum-Shub, DUAL_EC_DRBG, and several others, tend to advertise provable security. What this means is that predicting the next bit reduces to solving a presumably hard problem, like integer factorization or the discrete logarithm problem. While this is appealing to mathematicians and theorists, this kind of generator tends to be very slow and hard to implement correctly, i.e., without leaking state information via a side-channel or buggy arithmetic.

Practitioners highly favor generators based on symmetric primitives that are much faster and easy to implement and reason about and—as a bonus—also happen to resist quantum computers, if those ever get built.


Why does openssl use SHA1 in ECC when I use secp384r1 curve I need a small clarification that why openssl using SHA1 in ECC when I am using secp384r1 curve, but in rfc they are saying we should use SHA2.

Thing here is am using nanoECC in my DTLS, nanoECC using SHA384 for secp384r1 but openssl is using SHA1. So which one to use, if openssl is wrong then how to set openssl to use SHA384 for secp384r1 curve.

I need a small clarification that why openssl using SHA1 in ECC when I am using secp384r1 curve, but in rfc they are saying we should use SHA2.

OpenSSL uses SHA-1 because RFC 4492 defines the use of ECC on SSL with SHA-1. It should also support SHA-384 as defined in RFC 5289.

Which hash algorithm is used in TLS depends on the cipher suite. For example:

TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA (uses SHA-1)
TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA384 (uses SHA-384)


Are ideal hashes possible to create? In a hash function, you map an input of arbitrary length to an output of finite length such that the relationship is one-to-one (or at least that's what you are trying to achieve).

Hence, isn't it impossible to have a perfect hashing algorithm? Aren't MD5, SHA-*, all flawed in this respect?

Is an "ideal hash" impossible to achieve?

Of course, since the domain of a hash function is infinite and its range is finite, it cannot possibly be injective, i.e. there is at least one hash with more than one string that is being mapped to it.
This is called the pigeonhole argument: if the domain of a function is larger than the set that it maps to, at least two values are mapped to the same thing. (In fact, one can even show quite easily that in the case of infinite domain v finite range there is one hash that has infinitely many input strings associated to it)

So injectivity, or “uniqueness”, if you will, is, of course, a goal one cannot possibly hope to achieve for a hash function. If that is what you call an “ideal hash function”, then that is doomed to fail.

So what can we hope to have in a hash function?
There are a number of properties that hash functions should have. A common way to define these properties is to state that certain problems concerning the hash function should be computatinally hard, such as:

Collision resistance: it should be difficult to find a collision of the hash function f, i.e. to obtain two different values x₁, x₂ such that f(x₁) = f(x₂)
Second-preimage resistance: for any value, it should be difficult to find another value with the same hash. Formally: for any x₁, it should be difficult to find an x₂ such that f(x₁) = f(x₂)
Preimage resistance: given a hash, it should be difficult to find a message that has that hash. Formally, given y and some x₁ with f(x₁)=y, it should be difficult to obtain x₂ with f(x₂)=y

(There is also the related notion of a universal one-way hash function, but I shall not explain it here.)

It can be seen that collision resistance implies second-preimage resistance and that again implies preimage resistance. Now, do SHA and MD5 have these properties? Well, nobody really knows. The problem in cryptography is that it is very difficult to prove that a cryptographic scheme is correct. There are many relative security results, i.e. “Scheme A is secure if some assumption holds”, but the only cryptographic scheme that is proven to be secure is the One Time Pad.

In particular, it is not even known whether things such as “safe” (practical, i.e. not OTP) ciphers, good hash functions and so on exist in the first place – essentially, if the (still unresolved) P = NP? question has a positive result, i.e. P = NP, all these ciphers and hash functions are basically worthless.

However, it is widely thought that P does, in fact, not equal NP. Cryptographic primitives such as hash functions and ciphers are designed by people who are very knowledgeable in this area and have to withstand many attempts to break them before they are tentatively declared probably secure.

To come back to MD5, there are a lot of papers that describe efficient attacks on MD5. MD5 is definitely not collision-resistant. SHA-2 still seems to be quite good. But generally, the natural progression is that as hash functions grow older, more flaws and corresponding new attacks are discovered and they are gradually replaced by new hash functions, which were developed with the lessons learnt from the flaws of the old ones in mind.

I just realised this post got a lot longer and more detailed than I had initially planned; nevertheless, I hope it answers your question.


How Secure is gpg Command Using Symmetric AES-256 From Being Cracked How secure is any data encrypted using the following command:

gpg -o *encrypted_output_file_name* --symmetric --cipher-algo AES256 *file_to_be_encrypted*

Can anyone depend on this to encrypt and archive personal content in a public store?

Please provide details as to which attacks it is vulnerable to, and describe better encryption alternatives if any exist.

GPG's AES-256 symmetric encryption is believed to be as secure as it is difficult to

guess the passphrase
or compromise the machine used to perform encryption and decryption.

Guessing the passphrase should be harder if one uses

gpg --s2k-mode 3 --s2k-count 65011712 --s2k-digest-algo SHA512 --s2k-cipher-algo AES256

or equivalently puts in the gpg.conf file:

s2k-mode 3
s2k-count 65011712
s2k-digest-algo SHA512
s2k-cipher-algo AES256

These options increase (to about the maximum possible per the OpenPGP format) the amount of processing to transform a passphrase into a key, hence the resistance to brute-force passphrase search. This is not a substitute to using a hard-to-guess passphrase, but does help significantly.

When encrypting to self, it still makes a lot of sense to use asymmetric encryption: that allows to encrypt without a passphrase, limiting its possible leak to decryption. I use this for automated backups in the cloud (with a different asymmetric key to sign the backups). I can confidently say that nothing on the machines doing the backups allows to decipher the backups.


Is that possible to use encryption higher than 256-bit? When browsing websites with Chrome sometimes I can see a green lock and encryption info inside. It says the connection with this website is 128-bit or 256-bit encrypted with TLS1.2. So I'm wondering that is that possible to use 512-bit or higher encryption on websites?

TLS does not support any cipher suite combination with a symmetric key size larger than 256 bits. Asymmetric key sizes are available up to 15360 bits, which correspond to a 256-bit symmetric security level.

RFC5246 lists the available cipher suite combinations for TLS 1.2

It should be noted that the symmetric security of TLS is not the weak point, and 128-bits should be more than secure enough for the next 30 years.


Is there much difference in a RSA-4096 over RSA-3072 for support/speed and security? I am in the process of created a signing certificate and i have an option of RSA-4096 or RSA-3072.
Is there much difference in security between the two? I know people say RSA-3072 should be good until 2030. But people may also prefer the high security.
But if it makes a big difference on speed, they may not.
So do you think it is worth using RSA-4096 for the next 10 years?

See here, they mention that there is not particularly good software support for RSA-3072.


AES Key Length vs Block Length This answer points out that certain key and block lengths were a requirement for the AES submissions:

  The candidate algorithm shall be capable of supporting key-block combinations with sizes of 128-128, 192-128, and 256-128 bits.

My question is this; how can having a key length that is greater than the block size enhance security?

If we look at ECB mode for simplicity, when the key length is equal to the block length we have a permutation relationship between the set of all plaintexts and the set of all ciphertexts.

Once you increase the key length beyond that, you start to introduce collisions. In fact, you only introduce collisions from then on don't you? Collisions in the sense that a key will create the same ciphertext-plantext relationship as another key.

This would lead me to believe that only part of the key-space is unique, and only that part of key-space needs to be brute-forced?

I know that I am clearly incorrect, I just don't understand why.

A block cipher is pretty much a substitution cipher. So let's look at a simple alphabetic substitution cipher. There are 26 different plaintexts and 26 different ciphertexts. The cipher is a permutation of these 26 values. But that does not mean there are 26 different permutations, it means that there are $26! \approx 2^{88.4}$ different permutations, which allows an 88-bit key without equivalent keys.

If you transfer this to an n bit block cipher, which has $2^n$ different inputs/outputs, then there are $(2^n)!$ different permutations, which is ridiculously large ($\approx 2^{2^{135}}$) for $n = 128$, much larger than the $2^{256}$ different permutations addressed by a 256 bit key.

So even a 256-bit key only uses a tiny fraction of the available permutations, and thus there are (probably) no equivalent keys if the cipher is ideal.


Which encryption method supports random reads? I have a file containing 16-bit samples and I want to encrypt it, but the problem is that I need to be able to read any random 16-bit value from the file, and be to able to decrypt it, without reading larger (or surrounding) blocks. Because else it would require huge modifications to the device and driver.

It doesnt need to be very strong encryption, so I thought about just XOR-ing each 16-bit value with a another (fixed) value. But thats not really secure once the plain-text is known. And there are many samples with the value '0' at the start of the stream, so it would be easy to deduce the secret XOR value just by looking to the startblock.

Is there a similar method, that is almost as efficient and low-memory, but offers a little more security than my example above? The encryption may only take a few CPU cycles because its for an embedded MCU, however the decryption will be done using very fast CPU's.

Any block cipher in CTR mode can be used to encrypt and decrypt data in arbitrary order.

Basically, to encrypt something in CTR mode, you use the block cipher to encrypt a simple sequence of values, like (1, 2, 3, 4, 5, etc.), and concatenate the results to produce a pseudorandom bitstream, and then XOR this "keystream" with the data you want to encrypt.  Since you can produce any block in the keystream at any time just by feeding the appropriate counter value into the block cipher, you can easily decrypt the data in any order.

(Yes, you can even decrypt pieces of data smaller than a single cipher block with CTR mode, even down to a single bit.  You do need to compute the keystream block by block, but you don't need an entire block of ciphertext to be able to decrypt it.  If reading the ciphertext is much slower than block cipher encryption, this may be a useful optimization, and you can always cache the keystream block in case you need it again.)

The work needed for CTR mode encryption is basically the same as for decryption, and depends on the block cipher you're using.  If you can find a usable AES implementation for your MCU, I'd recommend using it; it's a standard, widely used and well analyzed cipher.  As they say, nobody ever got fired for using AES.
If AES is too much for your MCU, you may want to look at specialized lightweight block ciphers like PRESENT instead.

Also note that CTR mode does not, by itself, protect message integrity — for that you need authenticated encryption.  However, many modern authenticated encryption modes, such as EAX, GCM and SIV, do essentially consist of CTR mode augmented by a message authentication scheme, and thus support all the features of CTR mode (including random-access decryption) once the data has been authenticated.  The authentication itself, however, normally requires reading and processing all the data, unless you choose to divide it into smaller segments and authenticate each segment separately.

Addendum: As CodesInChaos notes in the comments above, if the "file" you're encrypting might change, such that an attacker could observe several different ciphertexts corresponding to the same position in the file (encrypted with the same key and counter sequence), then CTR mode becomes quite vulnerable to attacks.

The reason is that, like with any other encryption scheme based on XORing the data with a fixed keystream, an attacker who can observe two distinct values encrypted with the same part of the keystream can recover the XOR of the plaintexts simply by XORing the ciphertexts.  If they can guess one of the plaintexts (say, because they know it's all zeros), this immediately reveals the other one.  For more information, see e.g. this earlier question.

That said, if the encryption is only done to transfer the file from the device to the host (i.e. the data is only encrypted "on demand" when it's requested by the host), it may be possible to solve this issue by constantly varying the key and/or the initial counter value, e.g. based on a running message counter or a high-resolution timestamp.

For example, assuming that you file is no longer than 64 GB, you could use the lowest 32 bits of the block cipher input for the counter (i.e. the position of the block in the keystream), the next 64 bits for a timestamp or a message counter (make sure it can never decrease, even if an attacker manipulates messages), and still (assuming a 128-bit block size like for AES) have 32 bits left over e.g. for a per-file unique nonce.  This would ensure that no part of the file is ever encrypted twice with the same keystream.

Also note that it's perfectly OK to apply this scheme as a second layer of encryption to transfer data that's already stored in encrypted form (possibly also using CTR mode, with a different key and/or initial counter value) on the device.  This could afford an extra measure of security against attacks involving physical disassembly of the device and direct reading of the stored data on it.


Proper implementation of AES-256-GCM with PHP OpenSSL I am really lost in this subject, I find it hard to get any reliable documentation on the subject that is a bit friendly for beginners like me. So I apologize in advance if this question would sound nonsensical.

Anyway, I am implementing encryption in a project using php openssl_encrypt. So far this is what I have:

// encrypt

$dataToEncrypt = 'Hello World';

$cypherMethod = 'AES-256-GCM';
$key = random_bytes(32);
$iv = random_bytes(openssl_cipher_iv_length($cypherMethod));

$encryptedString = openssl_encrypt($dataToEncrypt, $cypherMethod, $key, $options=0, $iv, $tag);

And then I store $encryptedString, $key, $iv, and $tag

// decrypt

$decryptedString = openssl_decrypt($encryptedString, $cypherMethod, $key, $options=0, $iv, $tag);

My questions are:

Is there anything wrong with my current implementation?
Should $key be randomly generated or should I use a single secret key for general use? I am asking this because in some examples I see around the web they are using text strings for the $key. If it is not required for the $key to be random, does it have any improvements to security if it is random?
Is the $tag the message authentication code (MAC)? In the PHP documentation it states:

  The authentication tag passed by reference when using AEAD cipher
  mode (GCM or CCM).

If $tag is the MAC, then does that mean that PHP openssl_decrypt is also handling the authentication process?

Thanks for any help!

This is a question for codereview.se or a PHP forum.  As an aside: if you're building a new protocol for your own application, rather than trying to interoperate with an existing application, you will almost certainly be better served by libsodium than by OpenSSL's byzantine API.  Even if you have to use older versions of PHP that don't have it as core, you can use sodium_compat from Paragon IE.

Note that AES-GCM tends to be vulnerable to timing attacks on AES and on GCM in software implementations, and has small limits on the number of messages that can be exchanged with random nonces.  So if you're not restricted to interoperation with an existing application, it may be safer to use libsodium's crypto_secretbox_xsalsa20poly1305, or if you have associated data as well, crypto_aead_xchacha20poly1305_ietf.  I would suggest a nonce-misuse-resistant scheme, but they are not widely available yet and the world hasn't standardized on one yet.
Your obligations for using AES-GCM are: (a) The key must be uniform random from the perspective of the attacker, and (b) the nonce (here confusingly called ‘IV’) must never be reused with the same key.  In exchange, AES-GCM guarantees an active adversary can't learn anything about message content (length and timing are not concealed) or forge messages not previously seen, even if they could adaptively learn the encryption of chosen messages.  If you break your side of this contract, then AES-GCM may provide no security to you.

You can't just set the key down alongside the ciphertext, of course: then the attacker knows what the key is, and it is no longer uniform random from the attacker's perspective.  In order for this to work, the peers have to know the key ahead of time.  Maybe it's a shared secret obtained by hashing the output of an authenticated Diffie–Hellman key agreement, $H(g^{ab})$; maybe it's a pre-shared secret you pulled out of /dev/urandom on your laptop and copied over an authentic channel to an application server.  If you have a password, rather than a uniform random string of 16 or 32 bytes, then you must use a password-based key derivation function such as scrypt or argon2 to derive a key from it.

You will have to study the documentation to figure out how to supply a 16- or 32-byte key.  To confirm your understanding, write an experiment of reproducing an AES-GCM test vector with your understanding of how to supply the bytes of a key exactly, and save that experiment as a unit test.

The peers have to agree on the nonce to use for each message, too.  In the best case, they exchange messages in order, or mostly in order; in that case, you can use message sequence number as a nonce.  If this is a bidirectional channel, make sure to use one key for each direction, or odd nonces in one direction but even nonces in the other direction, or similar.  If you use message sequence numbers, there is no meaningful limit on the number of messages you can use AES-GCM for.  (The limit is $2^{96}$.  Exercise: How many centuries are in $2^{96}$ picoseconds?)

If you can't use a message sequence number as a nonce, you can pick the nonce uniformly at random from $2^{96}$ possibilities (AES-GCM is defined to accept larger nonces, but hashes them into only $2^{96}$ internal possiblities), but random nonces severely limit the number of messages you can exchange—you should avoid using them for more than a billion messages or so, to be on the safe side.
I can't tell you about $tag because again it's a PHP programming question.  But it is good that you are paying attention to this, because there are some APIs that inexplicably have a separate step for verifying the authentication tag, which is probably what $tag is.  You must never touch message data before you verify the authentication tag.  Unauthenticated message data is pure evil—don't touch it!  In a sensible API, the AES-GCM decryption operation will throw an exception or return an error code if verification fails, before you can even touch the evil.

I'd suggest you triple-check your API documentation—but that's not enough, because OpenSSL's documentation is notoriously bad.  So write an experiment to flip a bit in a message before you try to decrypt it that confirms it fails, and save that experiment as a unit test.


How can we reason about the cryptographic capabilities of code-breaking agencies like the NSA or GCHQ? I have read in Applied Cryptography that the NSA is the largest hardware buyer and the largest mathematician employer in the world.

How can we reason about the symmetric ciphers cryptanalysis capabilities of code-breaking agencies like the NSA or GCHQ given that they have performed first class unpublished cryptographic research for the last ~40 years?
What sort of computational lower bounds can we establish on an attack against these ciphers given that these agencies may have unpublished and unknown cryptanalysis techniques of equivalent utility as differential cryptanalysis (we only know about differential cryptanalysis because someone outside the NSA/IBM rediscovered it)?

For example, could we have developed a good lower bound on the ease of finding collisions in md5 without knowledge of differential cryptanalysis?

This question is restricted to symmetric ciphers.

Applied Cryptography is book which is becoming, say, not-so-recent. NSA has quite a lot of budget, but not an infinite amount, and there are other organization, in particular big private corporation, which also have impressive means. Google or Apple, for instance, are companies with R&D activity in the area of cryptography, and who are able to potentially throw a billion dollars at a given problem (and they could probably do so with more administrative ease and flexibility than a federal agency).

Also, there has been quite some change in the area of public research on cryptography. In the early 1980s, there was a couple of conferences dedicated to cryptography; in 2011, there are more than one hundred ! The field has simply expanded, inflated, so much that no single organization, even the NSA or Microsoft or Apple, can claim employing a non-negligible proportion of the available brain resources. It is a recent change: from my own personal experience, inflation really began in earnest around 1995.

That's one thing that can be said about NSA abilities. They do not tell who they employ and what they work on; but we can estimate the probabilities of NSA having discovered advanced cryptanalytic techniques which have evaded the grasp of public academics. As Leibniz put it, discoveries are a product of ideas which are "floating around", and who will actually make the discovery is a random choice. In other words, if NSA employs 1% of the top cryptographers, then they will get 1% of the advances. Even if there is such as a thing as scientific capital (scientists work much more efficiently when they are in labs with many other scientists and a strong local tradition of working on the same subjects), it is still quite improbable that NSA is far ahead of everybody else.

Another point is about incentives. NSA is a budget sink-hole, but it has goals: namely, to protect the USA against their enemies (the rest of the World). When the NSA says that an algorithm is good (say, the AES), other US organization (both public and private) begin to use it. It is sure that NSA would like to be able to break encryption systems which are in widespread use; but, and (in my view) this is for them a much more important goal for NSA, they want the encryption that US organizations use to be unbreakable by their enemies. As such, it would make sense for NSA to promote an algorithm that they can break only if they have good reason to believe that only them can break it. NSA, like all secret services, knows what secret is: they keep their secrets, but they also assume that they do not know all about the secrets of their competitors. Correspondingly, there again, I find it implausible that NSA would know how to break AES, since they keep on brandishing it as "the solution" and there is not the slightest hint of a plan to define another symmetric encryption standard, if only as a backup.

So this is how I reason about the unknown capacities of secretive organization: I look at their resources, and I match their observable actions against their goals. Which leads to the following conclusion: if NSA can break AES, then either they have access to some non-Earth-based technology and science (a popular theme in movies, e.g. Men In Black), or they are not really trying to protect the organizations they are supposed to protect. Or both.

On the purely scientific plane, we have no proof that symmetric primitives really exist (in particular hash functions; but we do not know either if it is possible, in a Turing-said-it way, to have a symmetric cipher with an in-memory representation shorter than $\log n!$ bits: the amount of bits needed to represent a randomly selected permutation over $n$ bits). Right now we have candidates: defined block ciphers which we do not know how to break. And not block ciphers which we know cannot be broken. Therefore, there are no real "lower bounds" which would work against unknown cryptanalytic advances.


A good introduction to Cryptography Excuse me in advance for the generality of the question I am about to ask, I am not even sure if this is the place to ask... but here I go!

Let me start by mentioning a little about my academic background:

I recently finished my Mathematics BSc and I am starting an MSc in Mathematics on September. I did my Final degree thesis on Tannakian Categories and I have a good background in topics such as algebraic number theory, algebraic geometry (I have a good knowledge of scheme theory) and algebraic topology. When it comes to programming, I know C, C++, Python and R.

And here's the question:

I would like to find a good book/online course in order to learn a bit about Cryptography, most preferably following a deep mathematical approach, but combining it with programming in any of the latter languages, so that I can see an application. I don't mind learning another language, by the way :)

Thanks in advance!

i think “ Introduction to Modern Cryptography “ by Jonathan Katz and
Yehuda Lindell is a very good book for your requirements.
you could also try "Foundations of Cryptography” by Oded Goldreich.


Include TSA Certificate in Timestamp Request I'm currently working on Timestamping and stumbled upon a parameter fRequestCerts/requestSignerCertificates/certReq that according to the documentation (1, 2) tells a TSA to include the certificate that was used to sign the timestamp token in its response.

When fiddling with this parameter I noticed that Windows behaves differently when validating self-signed TSA certificates. More specifically, when the parameter is set to true Windows apparently treats self-signed TSA certificates as trustworthy. When the parameter is set to false Windows treats them as non-trustworthy.

Unfortunately I couldn't find any more detailed information about this matter. So my questions are:

Why exactly would I use this parameter?
How does it influence trust?

The behavior turned out to be a vulnerability. Details about it can be found here https://about.signpath.io/blog/2020/08/26/on-the-importance-of-trust-validation.html.


Relationship between the use of a mask and entropy This is part of an assignment and I'm not sure what conclusion I'm supposed to draw from the result.

We were supposed to generate two 1024 bytes words, one using an algorithm that randomly generate 0 and 1 (50%/50%) and one using an algorithm with a "secret" probability distribution. I'll call them word 1 and word 2 from now.

We were supposed to calculate the empirical entropy of each word bit per bit first, and then byte per byte.

I got the following results :

word 1 (bit per bit): 1.00

word 1 (byte per byte): 7.79

word 2 (bit per bit): 0.95

word 2 (byte per byte): 0.81

We where then supposed to generate a random 1024 bytes mask and apply it on each word, giving us word 1m and word 2m. The results are this time:

word 1m (bit per bit): 1.00

word 1m (byte per byte): 7.81

word 2m (bit per bit): 1.00

word 2m (byte per byte): 7.81

I'm not sure what those results mean! Of course I noticed the fact that the byte per byte empirical entropy of word 2 is low, which probably means that some specific bytes are appearing more often than other, but I don't know what happen for word 2m

Not sure I made myself very clear, don't hesitate to ask for clarifications. Thanks !

A uniform random source has maximum entropy: 1 bit per bit. It's fully unpredictable.

There's no way to measure the entropy of a source since you can only get a partial, finite view of it. If you see no pattern in the first $n$ bits, that doesn't prove that the source doesn't repeat every $n$ bits. Conversely, an ideal random source can return $n$ identical bits, it's just very unlikely (probability $2^{-n}$). So when you estimate the entropy of a uniform random source by sampling it, you can expect to get an entropy measure of about 1 bit per bit, whereas a non-random source usually has less (but only if your entropy estimation manages to catch the non-randomness).

You're getting 1 bit/bit and 7.79 ≈ 8 bit/byte (clearly not 7.79 byte/byte: it's a number between 0 and 1) as the entropy estimate for source 1 which is supposed to be uniformly random. This is within expected bounds.

You're getting 0.95 bit/bit and 0.81 bit/byte for source 2. This indicates that source 2 has pretty much equal numbers of 0's and 1's, but there's a very strong correlation between successive bits since grouping bytes together gives a low entropy estimate.

When you apply a uniformly random mask, the resulting combination becomes itself random. This is because every bit has a .5 chance of being flipped, so each 0 bit in the source has equal chances of being 0 or 1 in the combination, and each 1 bit in the source also has equal chances of being 0 or 1 in the combination. The entropy estimates that you get for source 1 with the random mask and for source 2 with the random mask are close to 1 bit/bit as expected.

Note that the mask is a xor, not an and. A bitwise and with a uniform random source would merely reduce the entropy by forcing about half the bits to 0.

This observation that an unpredictable mask xored with an arbitrary source results in an unpredictable combination is the basis of stream ciphers.


Attacking RSA signature verification that ignores padding I am looking at a RSA signature verification that is quite obviously flawed and am wondering if there's a way to exploit that flaw in practice.

Signature is generated using RSA with PKCS 1.5 padding, i.e. $S = M^d \mod N$, where $M$ is a padded message: $M = 00 \| 01 \| FFF ... F\|00\|m$ and $m$ is the raw message being signed, which is always a 64-char pseudo-random ASCII hex string (it's a hash value).

When verifying signature, however, there is no check for padding. Verification is done by computing $M = S^e \mod N$, converting M to a byte array and then simply looking for a substring $m$ in $M$.

Modulus $N$ is 2048 bits and public exponent $e = 65537$.

Attacker can obtain a limited number of valid signatures (of a padded message) but there's no direct control over what $m$ will get signed (it's a time-base hash value).

Do you see any way to forge signature of attacker-chosen $m$ so that it'd be accepted by this flawed verification procedure?

Thanks!

If you were using $e=3$, then there is a well known attack by Bleichenbacher that enables the trivial generation of a signature that passes verification. This attack was never published, but is described here. Note that this attack appeared in a real vulnerability in Kindle (and some versions of Android).

In any case, the attack does not work for $e=65536$. However, if your question is whether or not it's OK to use this, then it certainly is not. The existence of the $e=3$ attack should be enough to convince you of that. On the other hand, if your question is constructive to find an attack, then I don't know - but it's a great research question.


RSA 4096 bit key benchmark How can I benchmark RSA operations on my computer? I want to know about 4096-bit long keys on general computers. How many encryptions and decryptions are possible per second? All benchmarks I found only show 1024- and 2048-bit keys.

A "general computer" simply doesn't exist, test for yourself with this command:

openssl speed rsa

As an example here is the output on a Mac Pro 2007 withIntel Xeon 5130:

Doing 512 bit private rsa's for 10s: 67450 512 bit private RSA's in 9.95s
Doing 512 bit public rsa's for 10s: 961891 512 bit public RSA's in 9.94s
Doing 1024 bit private rsa's for 10s: 19914 1024 bit private RSA's in 9.93s
Doing 1024 bit public rsa's for 10s: 343029 1024 bit public RSA's in 9.98s
Doing 2048 bit private rsa's for 10s: 3101 2048 bit private RSA's in 10.00s
Doing 2048 bit public rsa's for 10s: 100363 2048 bit public RSA's in 10.00s
Doing 4096 bit private rsa's for 10s: 430 4096 bit private RSA's in 9.95s
Doing 4096 bit public rsa's for 10s: 27080 4096 bit public RSA's in 9.93s
OpenSSL 1.0.1 14 Mar 2012
built on: Tue Aug 21 05:18:48 UTC 2012
options:bn(64,64) rc4(16x,int) des(idx,cisc,16,int) aes(partial) blowfish(idx)
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4 -Wformat -Wformat-security -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_NO_TLS1_2_CLIENT -DOPENSSL_MAX_TLS1_2_CIPHER_LENGTH=50 -DMD32_REG_T=int -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM
                  sign    verify    sign/s verify/s
rsa  512 bits 0.000148s 0.000010s   6778.9  96769.7
rsa 1024 bits 0.000499s 0.000029s   2005.4  34371.6
rsa 2048 bits 0.003225s 0.000100s    310.1  10036.3
rsa 4096 bits 0.023140s 0.000367s     43.2   2727.1

And here is the same command on a slightly more up-to-date mobile (aka laptop) CPU (Intel i5 2540M)

Doing 512 bit private rsa's for 10s: 178265 512 bit private RSA's in 10.00s
Doing 512 bit public rsa's for 10s: 2244112 512 bit public RSA's in 10.01s
Doing 1024 bit private rsa's for 10s: 52008 1024 bit private RSA's in 10.00s
Doing 1024 bit public rsa's for 10s: 792898 1024 bit public RSA's in 10.01s
Doing 2048 bit private rsa's for 10s: 7216 2048 bit private RSA's in 10.00s
Doing 2048 bit public rsa's for 10s: 232383 2048 bit public RSA's in 10.01s
Doing 4096 bit private rsa's for 10s: 1012 4096 bit private RSA's in 10.01s
Doing 4096 bit public rsa's for 10s: 62854 4096 bit public RSA's in 10.01s
OpenSSL 1.0.1e 11 Feb 2013
built on: Mon Jul 15 12:44:45 UTC 2013
options:bn(64,64) rc4(16x,int) des(idx,cisc,16,int) aes(partial) blowfish(idx)
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4 -Wformat -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_NO_TLS1_2_CLIENT -DOPENSSL_MAX_TLS1_2_CIPHER_LENGTH=50 -DMD32_REG_T=int -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM
                  sign    verify    sign/s verify/s
rsa  512 bits 0.000056s 0.000004s  17826.5 224187.0
rsa 1024 bits 0.000192s 0.000013s   5200.8  79210.6
rsa 2048 bits 0.001386s 0.000043s    721.6  23215.1
rsa 4096 bits 0.009891s 0.000159s    101.1   6279.1


Subtle Crypto Algorithm Choice I need to encrypt some text in the browser to be stored server side. After a little research I decided to use the SubtleCrypto API. I created the the crypto key using the following code:
window.crypto.subtle
        .generateKey(
            {
                name: "RSA-OAEP",
                modulusLength: 4096,
                publicExponent: new Uint8Array([1, 0, 1]),
                hash: "SHA-256",
            },
            true,
            ["encrypt", "decrypt"]
        )

My initial testing was successful but later I discovered that any text longer than 446 bytes is failing. Which looks like to be expected according to this answer. I am no crypto expert so what should I do to encrypt larger amounts of data (low megabytes). Choose a different algorithm, or split the data in chunks etc?

RSA can not directly encrypt large data.
You need to generate a random key for a symmetric cipher (secure random), encrypt the large data with this key using a secure mode (e.g GCM).
encrypt the key with your RSA public key,
prepend encrypted key to encrypted data.
store.
This is just for understanding of what goes on, you should look for a library which does as much of this together as possible from a reputable source, start with libsodium which I believe has a pure JS implementation.


Can you exchange a shared key without any hardness assumptions? Imagine that P=NP, and one way functions don't exist. Can two people end up with a random shared key of arbitrary length, if every exchange is public? They have true RNGs, and know who they are talking to (we're not worried about mitm attacks).

There is also someone else sharing the channel, who has one time pads with both of them. The two people want to get their own one time pad, without the third person having it. They can obviously check afterwards if they have the same pad by sending random bits in it to each other.

It seems like there should be some way to have one person send a secure message to the third person (who shares a otp with him), and send that on and back with different layers added on each time, then unlayering afterwards, but I don't see exactly if it can work. A solution should make it that the two sides only end up with the same key if the middle person has no way of getting it.

The motivation for this was that CAs could act as middlemen for secure communication in a post-P=NP world, with every computer shipping with the CAs OTPs.

In cases where Alice and Bob are guaranteed to arrive at the same key, this is impossible: the function that takes Alice and Bob's private info as input, and produces the public transcript as output, must be a one-way function if the scheme is to be secure and if it always negotiates a shared key. If it sometimes fails, then you don't necessarily get a OWF; you get a function which can be turned into a OWF, but it's more complicated. Assuming that either Alice or Bob knows if it succeeded, you can make this construction work.

It should be pretty clear why the nonexistence of OWFs implies that you can, given a transcript, compute a possible set of private info for Alice and for Bob that gives that transcript. In comments, you suggested many inputs giving the same transcript but different keys. This is impossible if, after the protocol, either Alice or Bob knows if they successfully negotiated a key or not (and the other one doesn't think they know but actually have it wrong). In that case, any two inputs that lead to successful key exchange and produce the same transcript must negotiate the same key.

Each party has private information for any particular run; it's just whatever secret they had, plus the result of every single coin flip that happened during that run of the protocol. We can specify this in advance; if you need more coin flips than are in the private information, the algorithm just fails. Then at any step, whatever message is sent is a deterministic function of the transcript so far and the private information the sender has (all randomness got embedded in the private info). Also, include whatever check you're doing to verify key exchange worked in the protocol.

Suppose the set of private info $A_0,B_0$ and the set $A_1,B_1$ produced the same transcript. WLOG, Alice sent the first message each time. Consider what happens with $A_0,B_1$; we want it to be the same transcript as well. Alice sends the first message again; this is based only on $A_0$, so it's the same as the first message there. Now, suppose the first $k$ messages are the same in this new transcript as in $A_0,B_0$. Alice has exactly the same information as after the first $k$ messages in $A_0,B_0$, so she does the same thing (either doesn't send or sends the same message as there). Bob has exactly the same info as after $k$ messages in $A_1,B_1$, so does the same thing he did there. As the transcripts of $A_0,B_0$ and $A_1,B_1$ are the same, Bob did the same thing in the latter as in the former, so after message $k$, Alice and Bob behave the same as they did in $A_0,B_0$. So the first $k+1$ messages are the same if the first $k$ are. So, $A_0,B_1$ produces the same transcript as $A_0,B_0$.

Alice now computes a key from $A_0$ and the transcript. She can't know whether Bob had $B_0$ or $B_1$, so the key is the same. Likewise, Bob can't know if Alice had $A_0$ or $A_1$, so he produces the same key as $A_1,B_1$. If Alice and Bob know whether or not key exchange was successful, and Alice knew $A_0,B_0$ led to successful exchange, then she also knows $A_0,B_1$ did. That means the key from $A_0,B_0$ is that from $A_0,B_1$ is that from $A_1,B_1$. The only other option is that $A_0,B_1$ failed; in that case, Alice did not know it failed, so she doesn't ever know if her key exchange succeeded or failed.

The reason one party has to know if it succeeded or failed in this proof is that that's how we get that $A_0,B_1$ necessarily succeeded. It may be possible to prove that without someone having to know, but even without that, just extend the private info to contain the actual message being sent (e.g. if it's a one-way message, then Alice has it in her private info and the negotiated key is really the message itself). If the proof doesn't work because neither one knows, then that means neither Alice nor Bob knows whether or not Bob got Alice's message correctly, which is a bit of a problem.