Adding a number congruent to $0$ to ensure that the mod operation takes a constant number of instruction cycles I've been looking at the s2n implementation of HMAC, and in the `update' function (line 175), it says

/* Keep track of how much of the current hash block is full
     *
     * Why the 4294949760 constant in this code? 4294949760 is the highest 32-bit
     * value that is congruent to 0 modulo all of our HMAC block sizes, that is also
     * at least 16k smaller than 2^32. It therefore has no effect on the mathematical
     * result, and no valid record size can cause it to overflow.
     *
     * The value was found with the following python code;
     *
     * x = (2 ** 32) - (2 ** 14)
     * while True:
     *   if x % 40 | x % 48 | x % 64 | x % 128 == 0:
     *     break
     *   x -= 1
     * print x
     *
     * What it does do however is ensure that the mod operation takes a
     * constant number of instruction cycles, regardless of the size of the
     * input. On some platforms, including Intel, the operation can take a
     * smaller number of cycles if the input is "small".
     */

It then goes on to do

state->currently_in_hash_block += (4294949760 + size) % state->hash_block_size;
state->currently_in_hash_block %= state->block_size;

I don't understand why you would want to add a number that's congruent to zero modulo state->hash_block_size - what does it achieve? How does it guarantee a constant number of instruction cycles?

As the comment you quote notes:

  On some platforms, including Intel, the [modulo] operation can take a smaller number of cycles if the input is "small".

Is that really true, and what does that mean?  A bit of Googling led me to the Intel® 64 and IA-32 Architectures Optimization Reference Manual, which in table C-16 lists the throughput of the DIV instruction (which is used to compute both division and modulo) as "~20-26" cycles per instruction (~19-25 cycles on Ivy Bridge), with the following footnote:

  The throughput of “DIV/IDIV r32” varies with the number of significant digits in the input EDX:EAX and/or of the quotient of the division for a given size of significant bits in the divisor r32. The throughput decreases (increasing numerical value in cycles) with increasing number of significant bits in the input EDX:EAX or the output quotient. The latency of “DIV/IDIV r32” also varies with the significant bits of the input values. For a given set of input values, the latency is about the same as the throughput in cycles.

So what does that mean in plain English?

Integer division and modular reduction are not constant-time operations on Intel x86 CPUs.
The time taken to divide or reduce a number depends (mainly?) on the bit length of the number being divided or reduced.

Thus, the time needed to calculate x % y can leak information about the size of x.  However, we can minimize this leakage by instead calculating (x + c) % y, where c is a large constant multiple of y.  In particular, the constant c should be chosen so that:

the bit length of x + c is the same for all possible values of x,
the calculation of x + c cannot overflow for any possible value of x, and
of course, c needs to be divisible by the modulus y.

Depending on the range of possible x values, of course, it may not always be possible to find a constant c that would satisfy these requirements.

In the code you quote above, however, the constant 4294949760 appears to have been chosen as the largest value c that will not overflow a 32-bit unsigned register when added to any number 0 ≤ x < 214, and which is also an integer multiple of the possible moduli 40, 48, 64 and 128.  Given that 4294949760 ≥ 231, this also ensures that it satisfies the first condition: bitlength(4294949760 + x) = 32 for all 0 ≤ x < 214.


Is it meaningful to allow parties to use a non-uniform random tape in 2-party computation? Consider a trivial example where two semi-honest parties want to flip a biased coin. Since the sender is semi-honest, the sender can locally flip a biased coin and send it to the receiver. A natural question is: What does the sender's random tape look like in the above trivial real protocol?
I know that, in the 2-party computation literature, the random tape is assumed to be uniformly random. I am curious about the convention of such an assumption. Is it a mandatory requirement? Many thanks for your comments.

Most models I've come across have a truly random tape. You can use this trick - assume the tape to be uniformly random, but then the party reads a block (of certain size) of random bits and uses that to bias the coin.
For example, if you want the coin to output Heads by probability 0.75, read 2 random bits from the random tape and if they both are 1's, output Heads otherwise output Tails.


Do the session keys have the same value on both sides during TLS? I have two questions about the sessions keys generated during the last steps of the Handshake phase:

Do the "client write key" and the "server write key" have the same value, even though both keys are generated independently on both sides?

(Same question) Do the "client write MAC key" and the "server write MAC key" have also the same value?

General question: Do the client and server arrive at the same results while generating the session keys?

Do the "client write key" and the "server write key" have the same value, even though both keys are generated independently on both sides?

No, see the next answer.
For encryption keys this is less important as the message is MAC'ed anyway. However, within TLS 1.2 and before MAC-then-encrypt is used, which may expose some unwanted vulnerabilities. E.g. if the sender is vulnerable to oracle attacks, then you might use that to decrypt messages when the same key would be used. This shows that key separation is always a good idea, as padding oracle attacks were initially not envisioned.

(Same question) Do the "client write MAC key" and the "server write MAC key" have also the same value?

No, they are deliberately different so that you cannot have the senders have their own message being replayed back to them. Basically a KDF (the PRF in TLS 1.2 parlance) uses a different label for each key, which means that each derived key will only be dependent on the master key (using a one way function).

General question: Do the client and server arrive at the same results while generating the session keys?

Yes, that they do. But they simply end up with the same values for each specific key. The client and server derive identical master secrets, and then proceed to use the same labels for the specific keys. So both sides will have the "client write key", but the server will use it to decrypt the messages.


Could scrypt salts contribute to entropy if passwords & salts are only stored in human memory? I'm unsure of how exactly the salt is manipulated by scrypt and its potential contribution if any to overall password entropy if passwords & salts are stored only in human memory for a decentralized implementation.

For this implementation, a cryptocurrency login where the salt does not exist in any repository such as a user table because the resulting hash is the accountholder's signing key, a user would be responsible for generating a "username" as the salt and a password.  Both would be checked for minimum combined entropy such as naive entropy / 2 > 80 to push the user toward Diceware.  There are currently no other requirements.

The username approach was selected because of statistical evidence showing that their distributions possess more than 35 bits of entropy, but I do realize that this set is probably skewed because of users wanting taken names and settling for besthashcracker11 which of course will be impossible to enforce thereby reducing that number.

If that scheme is more vulnerable to the average user than the risk of a weak password/passphrase alone, should a single passphrase be broken arbitrarily into two parts?  If so, how?  What percentage should be the password, and what for the salt?

If salts do contribute to entropy for this implementation, how can total entropy be calculated as a function of password entropy and salt entropy if an attacker has no access to the passwords, salts, or resultant hashes?

Users can be expected to be almost totally anonymous to an attacker.

If you use a potentially guessable username as the salt, you should add a global salt that no other services or programs will be likely to use for scrypt. For example, a long random number. That ensures that attacking another user database does not simultaneously allow attacking your users' hashes.

However, if two users are allowed to choose the same username within your userbase, adding global salt is not enough. You need something unique per user to use as salt instead of or in addition to the username. If random numbers really are not possible, consider using email addresses, which should be unique. (Those naturally add no entropy.)


Selecting secret value in certificateless identity-based encryption In certificateless identity-based cryptography, selecting secret value $$x_i \in Z_p$$ and declaring public key of individual users such as $$Pub_i=g^{x_i}$$
$g$ is public parameter.
I think there will be some kind of collision in selecting secret value.
In security proof, they make assumption that secret value cannot be allowed to attackers. Is it enough?

I think there will be some kind of collision in selecting secret value.

What sort of collision could there be (that has a nontrivial probability of actually happening)?

If $p$ is the order of $g$, then $Pub_i = Pub_j$ only if $x_i = x_j$.  And, if $p$ is large (e.g. at least 256 bits), and we assume that $x_i, x_j$ are selected randomly and independently (that is, no one participant is allowed to peak at any of the other's secret, and they all have good entropy), then the probability of $x_i = x_j$ happening is $< 2^{-256}$, that is, mindboggling unlikely.

In fact, if we have, say 7 billion participants, and each one selects an $x_n$ randomly, the probability of there exists two different participants selecting the same value is $< 2^{-191}$, still mindboggling unlikely.

This does assume that the entropy of each participant is good; something that tends to be ignored in security proofs, but cannot be ignored when implementing the system.

  In security proof, they make assumption that secret value cannot be allowed to attackers. Is it enough?

They also assume (and they ought to make it explicit) that the discrete log problem is hard; that is, given the value $g^{x_i}$, it's hard to recover $x_i$.  If the group was small enough that someone would have a nontrivial probability of obtaining $x_i$, by guessing it (and computing $g^{x}$ to verify), well, that'd mean that the discrete log problem would be tractable.


How can I calculate the Rijndael SBox? I would like to implement the Rijndael subBytes() operation using calculation instead of tables, because I like to play with this on different wordsizes, as an academical exercice, to see what the table would look like.

The first part is a multiplicative inverse in the polynomial binary finite field, isn't it?
The $g: a \rightarrow b = a^{-1} \in \frac{\mathbb{F}_{2^8}[z]}{m(z)}$, right?

I can use Sage to calculate it, but I prefer to implement it by myself. I've tried with section 4.3.2 of the Rijndael's design book and I've look with others like cohen's book (its about curves but the binary field maths are explained), but I'm not finding something that convinces me because play with different word sizes would decay in an ugly set of if statements in the first case or my background is too pour to really get the others in the right way.

What would be the best way to attack an implementation of this?

I have another question with in this subBytes() and it's about the parameters in the affine transformation. In this sub-operation

$f: a \rightarrow b = r\times a+s$

where $r$ is a rotation matrix representation of the polynomial $z^7+z^6+z^5+z^4+1$ (that I'm not getting what's behind this matrix, or why/how this MDS (Maximum Separable Distance) are coming to the scene), and $s$ looks to be a vector representation of the polynomial $z^6+z^5+z+1$. I'm also confused because the book and the amended version 2 from 1999 uses different values on what I've called $r$ and $s$.

How were those $r$ and $s$ chosen?

To undo this $f$, $f^{-1}$ is using an $r^{-1}$ and $s^{-1}$ that, if I didn't made a mistake, are not the inverses calculated using the first operation.

Any clue about how they are calculated?

What you are looking to do can be done, but if you expect it to just work, you are mistaken.

Performing the calculation of the inverse here is the easy part, the hard part is the choice of affine transform polynomial and vector, as incorrect choice will lead to an insecure s-box.

Multiplicative Inverse

The most simple method of calculating the inverse is to build tables. You need to start by building antilog and log tables for the given field size and reduction polynomial.

The antilog table is built like this:

$Antilog(0) = 1$
   $Log(0) = 0$

$Antilog(i) = g \times Antilog(i-1)$
   $Log(Antilog(i)) = i$

for $i = 1$ to $2^{n-1}$, where $g$ is the generator of the table for a given $m$ (reduction polynomial), and addition and multiplication are done in $GF(2^n)$

The multiplicative inverse is then done using a lookup in these tables:

$b^{-1}(x)=Antilog(2^{n-1} - Log(b(x)))$

where $b(x)$ is the byte representation of the polynomial you want inverted, and subtraction is not in the field. $0^{-1}$ is mapped to $0$.

For Rijndael, $n$ is 8, $m$ is 0x11B, the smallest $g$ is 3.

Once the log and antilog tables are generated, you can either build a separate table for the inverse, or perform the double lookup to get it.

Affine Transformation

For the affine transform matrix multiplication, see my answer here for an implementation example. The bit indexes of the new affine transformation polynomial need to be placed into the correct locations of the rotational matrix.

The bit indexes of 0x1F do not match those of the polynomial representation, which is actually the right most row top to bottom. The 0x1F representation makes a software algorithm a little easier to write and debug, since the column index now matches a successive division by 2 of the input and taking the LSB. This could be done in the correct order using multiplication, but requires steps to prevent an overflow with specific data types (byte) in numerous programming languages. Creating a table for transformations by $r$ will be the quickest for testing.

The 0x1F representation is also used in many papers describing the Rijndael s-box or when presenting alternatives, so I tend to use it by default, while keeping in mind the polynomial is different.

The $r$ and $s$ values used in Rijndael do not seem to be optimal for avalanche properties, and seem to have been chosen without detailed analysis. $r^{-1}$ is the inverse of $r$, details here. $s^{-1} = r^{-1} \times s$.

Testing

When changing the width of the s-box, there are several important things at this point that need to be kept in mind. The choice of affine polynomial determines the avalanche properties of the s-box, and the vector determines if there are any fixed points. Avalanche properties are also determined by initial choice of $m$. See this paper for the effects of changing these:

S-boxes generated using Affine Transformation giving Maximum Avalanche Effect

Upon generation of a candidate s-box it needs to be tested to make sure it meets all relevant cryptographic properties. Test for avalanche first (with the first functional vector), and once you have found the best affine transform, run through all vectors. Additional testing should then be performed on the remaining s-boxes. Note the lack of vector testing in the first s-box generated in the above paper (table 4) which has a fixed point at 0x10. The Rijndael design criteria requires that fixed points do not exist; this restriction was imposed despite the fact no attacks which exploit fixed points were known.

For every 1 bit increase in $n$, the workload goes up substantially. Each s-box takes 2 to 3 times longer to generate, and you have have 4 times as many affine/vector combinations to test, and up to 8 times the workload for avalanche testing per combination. Additionally, if you test all choices of $m$ for best avalanche effect, that's another doubling on average. Memory required to store the tables also more than doubles.


CCA2-secure encryption based on LWE/Ring-LWE As I understand it, cryptosystems based on LWE/Ring-LWE are typically only IND-CPA, and fail to satisfy IND-CCA2.  In fact, it appears that chosen ciphertext attacks could allow secret key recovery (!).

What is the best known IND-CCA2 secure encryption algorithm based on (Ring-)LWE?  What about key exchange?

If you don't mind relying on random oracles, the simplest approach is to apply a generic transformation such as Fujisaki-Okamoto to the (Ring-)LWE based scheme you start from. See for example Peikert's PQCrypto'14 paper for a concrete instantiation, and the TCC 2016 paper of Targhi and Unruh for a proof of security of this type of transform in the quantum random oracle model.

Lattice-based CCA2-secure encryption in the standard model is usually obtained using lattice trapdoors. The state-of-the-art construction is due to Micciancio and Peikert (section 6.3 of this EUROCRYPT 2012 paper).


Can we ensure the security of a crypto-algorithm and -implementaton against acoustic cryptanalysis? Like people always say: “Attacks only get worse…” — which is why I'm asking early.
I have been reading the paper “RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis” published December 18, 2013 by Daniel Genkin, Adi Shamir, Eran Tromer.
Attack
In short, they discovered that it is possible to crack 4096-bit RSA encryption keys using a microphone to listen to high-pitch noises generated by internal computer components. In one of their setups, they only used a mobile phone which was placed 30 cm from a target laptop, with the phone's internal microphone pointing towards the laptop’s fan vents… successfully achieving a full key extraction in this conﬁguration and distance.

image source: https://www.cs.tau.ac.il/~tromer/acoustic/
The proof in that 57-page paper is hard enough to start thinking about related crypto-solutions. Especially since the paper mentions that rather simple hardware like parabolic microphones and laser vibrometers can be used for distant acquisition.

image source: https://www.cs.tau.ac.il/~tromer/acoustic/
Now, I know this audio-based key recovery attack is a new one (published December 18, duh) but there has been quite some research on hardware-related attacks in the past already — like measuring the electrical potential of a computer's chassis during encryption etc. — and beyond that, the crypto-community tends to search for a solution to every problem encountered. So, I can imagine that there might be something out there I'm not aware of, which might be fit enough to lift one or more security impacts of acoustic cryptanalysis; especially in the described case(s) of acoustic key recovery attacks.

image source: https://www.cs.tau.ac.il/~tromer/acoustic/
(Partial) Mitigation
Related to solutions, the paper's website  mentions

…software countermeasures…

but also notes

How vulnerable are other algorithms and cryptographic implementations?
We don't know. Our attack requires careful cryptographic analysis of the implementation, which so far has been conducted only for the GnuPG 1.x implementation of RSA.

and

Q9: How vulnerable is GnuPG now?
We have disclosed our attack to GnuPG developers under CVE-2013-4576, suggested suitable countermeasures, and worked with the developers to test them. New versions of GnuPG 1.x and of libgcrypt (which underlies GnuPG 2.x), containing these countermeasures and resistant to our current key-extraction attack, were released concurrently with the first public posting of these results. Some of the effects we found (including RSA key distinguishability) remain present.

(italic emphasis mine)
and last but not least the paper states on page 48 (as a conclusion at the end of it’s “Mitigation” section):

This too foils our key recovery attack (but not key distinguishing).

(italic emphasis mine)
Question
The paper and website obviously imply that a “key distinguishing” problem still exists and that it represents a potential attack vector. They also seem to imply that no general, one-fits-all solution to the problem does not exist at the time of writing. Especially not when thinking about non-RSA ciphers. Yet, chances are that there’s something out there I haven’t heard of yet.
Can we ensure the security of a crypto-algorithm and/or -scheme against acoustic cryptanalysis? Does any generally acknowledged crypto-scheme, crypto-solution, or crypto-protocol exist which would be able to provide cryptographic security/defense against the described and maybe even other acoustic cryptanalysis of (non-RSA) ciphers?
Simpler asked: What cryptographic measures enable us to ensure the security of a crypto-algorithm and/or -scheme against acoustic cryptanalysis and/or acoustic attacks?

The problem is a very old one going back at least as far as the late 1940's early 1950's and has been shown to exist with Quantum Key Exchange as well.

You need to think of it in terms of entropy down to heat pollution where a coherent signal energy steps down due to inefficiency via various transducers to what is basically thermal noise where the noise threshold is significantly above any residual coherent signal.

Most people incorrectly think that TEMPEST is all about EM energy, it's not. It's about any energy (EM, acoustic/mechanical conducted or radiated even gravity) in one or more Shannon channels which have bandwidth, noise and propagation delay giving rise to phase as well as amplitude effects. It's also about transducers which can be bidirectional (a DC Motor/Generator being such a beast, as are some types of microphone/speaker by moving coil or piezo effects).

Put simply, a capacitor is two metal plates with an insulated gap. When current flows into the plates a magnetic field is generated that will cause the plates to move fractionally in sympathy with the current. Also some insulators are dielectrics which have a piezo effect as the voltage rises the dielectric deforms mechanically. Both of these effects will cause the capacitors to emit sound. Likewise inductance effects designers of RF oscillators are well aware that mechanical vibration of the inductive component will cause the resulting output of the oscillator to be modulated, it's frequently called microphonics.

These basic physical effects cannot be prevented only reduced or mitigated. In EmSec you look to reduce the bandwidth of any signal path such that it is less than the information bandwidth and also at signal containment/absorption.

Theses mitigations when done properly all add significant cost to a product. Therefor in a price sensitive market such as PC manufacture anything that is not regulated will cause a race for the bottom. And even where there are regulations (EMC) the market will still look at avoidance rather than meeting the intent of the regulations. One such avoidance is "direct sequence spreading" of the PC master clocks/oscillators such that the energy in a spur/sprog is spread so that it's energy/Hz decreases and thus meets the regulatory masks. Unfortunately the energy is still there and still caries the signal information and only needs de-spreading to recover the signal information.

One solution to "singing caps" is high melt temperature wax or some hot melt glues they absorb the audio signals and reduce the effective channel bandwidth. Another partial solutions is 'sound absorbing foam' that also lets air flow through and the right selection of materials will significantly reduce the audio channel through fan and ventilation grills.

But as I noted all steps are "mitigations" not real "solutions", but may well be sufficiently effective in their own right if (and only if) implemented correctly.


Can a properly implemented ed25519 private key with public underlying data be cracked? If the underlying data is public albeit hashed with SHA-512, does that make a difference on the strength of ed25519?  Please quantify the extent.

Can ed25519 be cracked after a certain amount of known signatures?  If so, please quantify the conditions.

No, this does not weaken ed25519 in any way. Known plaintext will not have any effect on a signature algorithm, if it did it would make that algorithm completely useless.


RSA-4096 vs AES-256 for secure chat application? Which of these two methods suits better the implementation of a secure chat application? In this context, chat will be limited up to 150 letters for one message.
I would prefer RSA because what I know RSA is really secure if it is used for small text and also if I will use groups it is easy in RSA because of public key distribution. Specially for chat application where user can write very small letters message I don't know if AES will be good for security.
AES is better in performance specially if I will compare 256 bit vs 4096 bit. RSA will be slower for encrypt and decrypt. But my goal is to have strong secure chat and not super fast chat.
What would be the more apt method?
I will use this chat only for sending message, e.g. no attachments, etc.

RSA and AES do not oppose, and often are rightly used together in hybrid encryption. RSA can do things that AES can not, like allowing encryption to designated recipients, or allowing anyone to check that a message is not altered or from a different person than is apparent. Using AES or other form of symmetric encryption is a must when encrypting more than few hundred characters.

To choose a cryptosystem, you must first define your goals. Secure chat is not nearly precise enough. Confidentiality? Integrity? Proof of origin? Central registry of participants? How is registration and loss of keys handled?


What is the polynomial to use in the Massey-Omura cryptosystem? The Massey-Omura cryptosystem uses "multiplication over the finite field $GF(2^n)$. I'm just starting understand the idea of multiplying polynomials and I've searched for online calculators to use for this. Thing is, all of these calculators request that I enter some sort of polynomial modulus and I don't know which one the cryptosystem uses.

Actually, it doesn't matter (as long as the polynomial is prime, of course).

For any $n$, there's only one finite field $GF(2^n)$, however there are a number of ways of mapping those elements to bit patterns.  We call that mapping a representation; one method of generating such a representation is to use a prime polynomial of degree $n+1$.

Now, between any two representations of $GF(2^n)$, there will be a mapping that converts values in one representation into values in the other; if both representations are sane (by which I mean that they perform addition by bit-wise exclusive-or of the representation), then this mapping will be linear (and hence, cheap to compute).

In Massey-Omura, the sides exchange the representations of the field elements $m^a$, $m^{ab}$, $m^b$; if there was a representation that makes this exchange weak, then the attacker could convert these three elements into that weak representation, find the value $m$ in that weak representation, and then map it back into the original representation, breaking MO in the supposedly strong representation.  Hence, no representation is any stronger or weaker than any other -- the choice of representation is strictly a practical matter.

In fact, if you go to the patent, Massey and Omura suggest using a normal representation (which is an alternative to a polynomial representation); in normal representations, the operation of squaring is cheap, and they believe that this will make computing exponentiation cheaper overall.  Again, this is a practical consideration -- it has no impact on security.

I will leave off with one security issue: people have recently made significant progress in computing discrete logs over $GF(p^m)$ for small $p$ (and 2 is as small as we can get), and smooth $m$.  Because of this, it would appear to be wise to select a prime value of $n$; that way, these recent results do not apply.


Questions about the double ratchet mechanism in Signal I am trying to understand the threats the double ratchet system is trying to prevent against.

The threats mentioned in the paper do not quite make sense to me. May be someone can explain where I am wrong?

For the DH ratchet the paper says --

  An eavesdropper who briefly compromises one of the parties might learn the value of a current ratchet private key, but that private key will eventually be replaced with an uncompromised one. At that point, the Diffie-Hellman calculation between ratchet key pairs will define a DH output unknown to the attacker.

But practically speaking how does an attacker "briefly" compromise one of the parties? An attacker either has compromised a party or not. If the user is compromised at time T during a communication, isn't it true that the device is considered compromised for all time > T? If so why is the above assertion in the paper good?

For the Symmetric key ratchet --

  The KDF inputs for the sending and receiving chains are constant, so these chains don’t provide break-in recovery. The sending and receiving chains just ensure that each message is encrypted with a unique key that can be deleted after encryption or decryption.

Here again if the user or device is compromised at a time T computing all future keys is trivial, isn't it?

So what is the system providing in addition to forward secrecy? Just in terms of forward secrecy, this is obviously adding per message PFS. So this is great, I just don't understand the other assertions as I listed above.

An eavesdropper who briefly compromises one of the parties might learn the value of a current ratchet private key, but that private key will eventually be replaced with an uncompromised one. At that point, the Diffie-Hellman calculation between ratchet key pairs will define a DH output unknown to the attacker.

This brief compromise is a of the current ratchet private key, one of the keys which I believe are called 'medium-term' in the DH paper (or at least in this security analysis. This means that the compromised key is only able to decrypt the current message, or messages in the current session before the key is ratcheted forward.

This is part of how signal provides both forward and future secrecy - the medium-term key for this session cannot decrypt any past messages, and as soon as the key is refreshed it won't be able to decrypt any future messages.

  If the user is compromised at time T during a communication, isn't it true that the device is considered compromised for all time > T? If so why is the above assertion in the paper good?

This would be true if the long-term key was compromised as well as a medium term key, but in fact signal protocol also uses ephemeral public keys which are stored on the signal servers and also replaced every so often, meaning that theoretically even if a session's medium term and ephemeral private keys were compromised, future sessions would still be secure.

didn't go into too much detail but can dig into the paper and explain a bit more if you would like. Does this help?


Why was there a need to create CP-ABE when KP-ABE already exist? This is more of a good to know question, but looking online and in this forum I couldn't find an answer to this question. Was there some major reason why CP-ABE was created when KP-ABE already exist? I am new to this field so I apologise before hand if I offend anyone with this question.

I think you may find the founding paper of CP-ABE pretty informative on that regard: in "Ciphertext-Policy Attribute-Based Encryption" by Bethencourt et al. you can read the following:

  In key-policy attribute based encryption, ciphertexts are associated with sets of descriptive attributes, and users’ keys are associated with policies
  (the reverse of our situation). We stress that in key policy ABE, the encryptor exerts no control over who has access to the data she encrypts, except by her choice of descriptive attributes for the data. Rather, she must trust that the key-issuer issues the appropriate keys to grant or deny access to the appropriate users. [... ] In our setting, the encryptor must be able to intelligently decide who should or should not have access to the data that she encrypts.

It's basically two different methods to achieve the same kind of goal, ie "Attribute Base Encrpytion".

You may further find this answer pretty useful and that question may also help you.


Is it safe to distribute different portions of the same data encrypted with different AES keys? Assume I have a block of data consisting of three segments A, B and C. With "segments" I mean a particular section of a bit stream, so if the whole binary data was simply 00 01 02 ... FF, A might be 00 ... 5C, B could be 5D ... 72 and C would then be 73 ... FF.

K1 and K2 are 128 bit AES keys that were securely exchanged such that Alice has K1 and Bob has K2.

Alice gets data segments ABC encrypted with K1.
Bob gets only data segment B encrypted with K2.

My question is: if Bob got to know Alice's full cipher text for ABC (that was encrypted with K1), what could he deduce from the information he already has? Are there any circumstances under which Bob could decrypt segments A and/or C as well?

This is question is very similar to Vulnerabilities if encrypting the same data with 2 different keys, but not quite; I'm not asking about what Eve can deduce, but Bob.

I'm fairly new to encryption, and it was my understanding that AES is mostly XOR operations. For strict XOR operations, I think if you know any two a, b or c where a ^ b = c, you can calculate the third variable using XOR on the other two, as I think this was how parity bits for RAID systems work.

I keep finding hints as to AES is not just XOR, like How is XOR used for encryption? which in turn links to Why do block ciphers need a non-linear component (like an S-box)?. But I'm not sure I'm understanding the implications of the answers given there.

I think what the answers to those questions say is that for AES, K1 and K2 are just used to continuously generate a pseudo random bit stream, and only that is then XOR'ed with the data. So all Bob could deduce was the pseudo random bit stream section that has been used for Alice's B, but the generator function is such that this doesn't give Bob a clue about K1 or the bits generated earlier for A or later for C.

Is this universally true? Or, as I have seen often mentioned, are there limitations as to how many bits B may have to keep a 128 bit K1, A and C reasonably secret from Bob?

We assume that Bob knows B and Enc(K1, ABC) but doesn't know K1, A or C. Then the only information Bob can learn about ABC is the length of AC (not even the length of A and C individually). If Bob knows Enc(K1, M), Bob can't even tell whether B is a substring of M. This is assuming that Enc is any sensible symmetric cipher, including AES-CBC (with a random IV), AES-CTR (with a initial counter value that doesn't overlap any counter value used for another input with the same key), AES-GCM (with a non-repeated nonce), AES-CCM (with a non-repeated nonce), etc.

AES itself is a permutation on 128-bit blocks, not a way to encrypt a message. involves some xor operations internally, but this is not a xor between the message and something else. There is no simple arithmetic relation involving related inputs and related outputs, otherwise we'd consider it to be completely broken. Given AES_Enc(K, A) and AES_Enc(K, B) where A and B are 128-bit strings, the only thing you can deduce about A and B is whether they're equal or not (A = B if and only if AES_Enc(K, A) = AES_Enc(K, B)).

There are ways to encrypt a message that involve xoring the message with a keystream which is produced using AES as a building block: ciphertext = plaintext ⊕ keystream. AES-CTR is a relatively simple one, where the keystream is built by encrypting successive values. Suppose you have the encryption of two messages with the same key:

ciphertext1 = plaintext1 ⊕ keystream1
ciphertext2 = plaintext2 ⊕ keystream2

keystream1 and keystream2 are indistinguishable from random to someone who doesn't know the key. Therefore ciphertext1 and ciphertext2 are also indistinguishable from random. Any relationship between the plaintexts is completely hidden by this random data, and not visible as a relationship between the ciphertexts.

Badly used modes of operation, for example using a non-random IV, can cause keystream1 and keystream2 to be related in some way. But that's due to badly using the encryption mechanism. The standard mechanisms themselves don't have such weaknesses.

Note that this assumes that Bob doesn't know the key. If Bob knows some part of K1, all bets are off. Never reveal part of a secret key.


How would Private-key Cryptography be if we use quadratic polynomials as OWF's? I am aware that one-way functions (OWF's) are the core of many of the primitives in symmetric crypto, in the sense that many cryptographic primitives in the private-key setting can be constructed from these.

On the other hand, in Multivariate Public-key Cryptography the goal is to find trapdoor functions of the form $F = (f_1(x_1,\ldots,x_n),\ldots,f_m(x_1,\ldots,x_n))$ where each $f_i$ is a quadratic multivariate polynomial over a finite field (say $\mathbb F_2$). However, the main assumption and motivation for this is that

  A uniform function of the form $F = (f_1(x_1,\ldots,x_n),\ldots,f_m(x_1,\ldots,x_n))$ where each $f_i$ is a quadratic multivariate polynomial over a finite field is a one-way function.

Given this and the initial discussion, we would have already a symmetric world from multivariate polynomials, without additional effort. Have someone looked at these primitives? how would they be? evaluating at polynomials is extremely efficient but, would these primitives be efficient as well? If so, why aren't these already deployed?

You might look at the stream cipher QUAD invented by Berbain, Gilbert, and Patarin.

It uses the complexity of a multivariate quadratic map as the basis for its security. A drawback of this and other multivariate quadratic map crypto systems is the space needed to store a large random quadratic map.


An efficient SPEKE protocol with curve25519 SPEKE is a very simple and elegant PAKE protocol.
I think one of the reasons why PACE was invented and is now the ICAO protocol is that SPEKE was patented. Fortunately, the SPEKE patent expired in March 2017 and therefore we can now freely use it.

In SPEKE, one needs to hash a password into an elliptic curve. That can be done by hashing into the x-coordinate and the calculate the corresponding y-coordinate. The tricky part is that not every x-coordinate has an y-coordinate in the base field. So, the following or a related method is used.

Search an integer value $c$ starting from zero, such that  $\operatorname{Hash}(\pi \mathbin\| c)$ is an appropriate x-coordinate on the curve.
Calculate the corresponding y-coordinate.

With curve25519 we can simplify both steps, because

Every x-coordinate is defined
y-coordinates are not necessary

SPEKE with curve25519

\begin{array}{lcr}
\mathit{Terminal} & & \mathit{Passport} \\
s = \operatorname{Hash}(\pi) & &  s = \operatorname{Hash}(\pi) \\
x' \xleftarrow{$} \{0,1\}^{252} & & y' \xleftarrow{$} \{0,1\}^{252}\\
x \leftarrow x' \mathbin\| (000)_b & & y \leftarrow y' \mathbin\| (000)_b\\
h_x = s^x & \xrightarrow{\quad h_x\quad} &  h_y = s^y \\
z \leftarrow h_y^x & \xleftarrow{\quad h_y\quad}  & z \leftarrow h_x^y  \\
\end{array}

One small issue is that it can be detected if the x-coordinate lives on the base curve or on its twist. That means, one loses 1 bit of entropy from the password. I think one can live with that small loss.

Does that make sense regarding security and efficiency?

Updated according to comments from Thomas and poncho.

One small issue is that it can be detected if the x-coordinate lives on the base curve or on its twist.

There's not a small issue; this allows a passive attacker to halve his dictionary by listening into a single exchange.

That is, if $s$ is on the curve, then so will be $s^x$; if $s$ is on the twist, so will be $s^x$.

So, what the attacker can do is listen in, and see if the exchanged $s^x$ and $s^y$ values are on the curve or not.  If they are, he can discard the half of his password dictionary that would place $s$ on the twist.  If they aren't, he can discard the half of his dictionary that places $s$ on the curve.

SPEKE can be done security based on X25519; however you can't just select $s$ arbitrarily; you have to make sure that it's consistently on the curve (or on the twist).


How can ECDSA signatures be shortened (to be used as a product key)? So I made my own serial key generation software, using ECDSA, for use in my own applications and it works great so far! To keep the serial key short enough I use a 128 bit EC curve. My final signature (which I use as the product key) ends up containing two BigIntegers, 128-bit each, so the final key ends up being 32 bytes long. This is an ok solution and I can get my final key down to about 50 characters (not counting any delimiters like dashes) by doing some custom base conversion to convert this into a readable string.

Now I found a software called ellipter where the key for a 128 bit key strength only ends up being 30 characters (if you look at the screenshots on their page). Is this even possible? Or are they using a 64-bit curve? I can't understand how they do it. I would love to get my keys shorter also but I can't see how it can be possible?

The web site of https://ellipter.com says, they are using encryption.


Hermitian curves introductory references Could you give me some reference to start on Hermitian Curves. Some papers or textbooks would be perfect, and please mention if it's math inclined or comp.sci. inclined.

I've only seen hermitian curves in coding theory but if you know of applications of these curves to cryptography please let me know.

"Algebraic Geometry Codes: Basic Notions" by Tsfasman, Vladut, and Nogin is a textbook that is available as a PDF. Discussion of Hermitian curves begins on page 167.

I haven't read it and no very little about coding theory. It was the reference a friend provided in his dissertation, which included constructing universal hash functions from Hermitian curves.


Factorization problem Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$?

Note that, either $a$ or $b$ can be reused to compute another $X'$ which is also public.

Edited: (more details)

Let's say Alice chooses two random numbers $a, b\in Z^∗_q$ and computes $X=a\cdot b$. Alice publishes $X$. What is the complexity of Bob to guess (or compute) $a$ and $b$ from the known $X$ and $Z^∗_q$?

Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$?

If the multiplication is done within $Z_q^*$, then it's easy - pick an arbitrary nonzero $a$ and compute $b = a^{-1}X$; you're done.  You can compute $a^{-1}$ by either the Extended Euclidean method, or by using $a^{-1} = a^{p-2}$

This will find a $(a, b)$ pair that satisfies the equation.  If you're looking for the unique one that someone else had in mind, well, you're out of luck - there are $q-1$ pairs that satisfy the equation, and with no other information, there is no way to determine which is the correct one.


How to attack the Two Time Pad? I encrypt 2 random keys with the same 'one' time pad. You can get both encrypted keys. You don't know anything besides the size.

Is there a way to attack the two time pad in this scenario?

And what if I would encrypt 1000 random keys. is there a way to attack the 'one' time pad?

PS. I have read a lot of posts about plain text attacks and language analysis which both certainly don't apply here.

At least, doing the goof of reusing the OTP makes one vulnerable to disclosure of any of the key, which trivially reveals all the others.

For the rest, the consequences depends heavilly on what the keys are intended for. If the keys are intended for a block cipher that is secure including under related-key attack (as AES almost is), then there is not consequence beyond the aforementioned.

But in other cases the goof can be damaging, even disastrous. Simple example of the worse: the two random keys enciphered under two-times Pad are really random half-keys, intended to be held separately and combined by XOR to form a full key when needed (which is a simple and most common form of secret sharing with 2-out-of-2 parameterization); with the goof, the full key is the XOR of the ciphertexts for the two half-keys, thus is compromised, even though the individual half-keys remain confidential.

There is a spectrum in-between if the keys are for ciphers with poor security, especially under related-key attacks. In particular, if there are many keys enciphered under many-times pad, the goof allows the attacker to effortlessly pinpoint a key pair with much lower Hamming distance than average, and that pair might become the basis of a cryptanalysis (e.g. from ciphertexts for known plaintexts enciphered under both keys).


How does this affine cipher work? I have a question about how I need to solve the following:

A sentence has been changed to ASCII and then encrypted with the formula $E(x) = ax + b \bmod 256256$. All I know is that the first 4 letters are: W I S K

This is the encrypted message:

 064066 158368 092525 143358 099354 141643 110102 051667 024006 190286 133343

How do I go about solving this? I first tried to program a brute force but I actually want to understand how to solve it. I tried working with the extended euclidean algorithm as well, but didn't get far.

W is 87 in ASCII, so
$$
87a+b\equiv064066\pmod{256256}.
$$

I is 73 in ASCII, so
$$
73a+b\equiv158368\pmod{256256}.
$$

Subtracting, you get
$$
14a\equiv-94302\equiv161954\pmod{256256}.
$$

Unfortunately 14 is not coprime to 256256, so you'll need to use other letters to figure this out. Once you get an equation of the form
$$
ma\equiv n\pmod{256256}
$$
you can solve for $a\pmod{256256}$ and then substitute to find $b\pmod{256256}.$

(In fact, you already have enough to solve with trial and error, but it's nicer to avoid that.)


How does Gilbert, MacWilliams, and Sloane's solution to “perfect integrity” work? Gilbert, MacWilliams, and Sloane defined a solution to "perfect integrity" in Codes Which Detect Deception, unconditionally secure message authentication, not vulnerable to any cryptanalysis on its own even by an adversary with unbounded computational power, provided you have a key chosen uniformly at random the same length as the message. It sounds counter-intuitive that a MAC could have perfect integrity, any hash function can be broken with enough computational power. How does their solution have "perfect integrity"?

Let $r, s$ be uniform random nonnegative integers below $2^{130} - 5$, shared by Alice and Bob but kept secret from the adversary Mallory.  If Alice wants to send a single message $m \in \{0,1\}$ to Bob (this is a yes-or-no message—only two possible messages, with no secrecy of the message, the simplest scenario imaginable), she can compute the authenticator or authentication tag or MAC $$t = (r \cdot m + s) \bmod (2^{130} - 5)$$ along with $m$.  Suppose Mallory intercepts $(m, t)$, and wants to find $(m', t')$ for $m' \ne m$—that is, Mallory wants to find another message/authenticator pair whose message is any message other than $m$, in order to fool Bob.  Bob will accept the forgery $(m', t'$) only if $$t' = (r \cdot m' + s) \bmod (2^{130} - 5).$$  No matter what the real message $m$ and the real authenticator $t$ are, and no matter what forgery $m'$ and $t'$ Mallory attempts, and no matter how much computation Mallory can do, the probability that Mallory's forgery attempt succeeds—i.e., the probability that Bob accepts Mallory's forgery—is at most $1/(2^{130} - 5)$.  Why?

Consider Mallory's perspective: they don't know the real key; they only know a real message $m$ and its real authenticator $t$.  For any particular message $m$ and authenticator $t$, there are $2^{130} - 5$ different pairs of values $(r, s)$ satisfying $t = (r \cdot m + s) \bmod (2^{130} - 5)$: for each possible $r$ there is exactly one $s$ satisfying the equation, namely $s = (t - r \cdot m) \bmod (2^{130} - 5)$.  But only one of those $(r, s)$ pairs also satisfies $t' = (r \cdot m' + s) \bmod (2^{130} - 5)$ for any $m' \ne m$ and $t'$ (see below for more formal proof).

So—no matter what computation Mallory does!—given only $m$, $t$, and the knowledge that $t = (r \cdot m + s) \bmod (2^{130} - 5)$, Mallory can't narrow the candidate keys $(r, s)$ down to fewer than $2^{130} - 5$ possibilities, all with the same probability $1/(2^{130} - 5)$.  And since Mallory doesn't know which of the $2^{130} - 5$ values of $(r, s)$ Alice and Bob are actually using, Mallory has no hope of finding any $m'$ and $t'$ that will fool Bob, by satisfying $t' = r \cdot m' + s$, with probability higher than $1/(2^{130} - 5)$.

And this bound on forgery probability is the best you can hope for when there are $2^{130} - 5$ distinct authenticators on any given message: for any attempted forgery, the adversary could guess what the right authenticator is uniformly at random with probability $1/(2^{130} - 5)$.  In general, as long as there are only $n$ times as many possible authenticated messages as there are messages, whether the authenticator is tacked onto the end or the message is otherwise transformed to authenticate it, the best bound on forgery probability you can hope for is $1/n$.

I don't recommend the term ‘perfect integrity’, which is value-laden and ripe for confusion, but attaining this bound is the most reasonable interpretation of the term, and the theorem that the GMS authenticator attains this bound is unconditional in a specific technical sense.

We can write this a little more formally in the language of fields.  Since $p = 2^{130} - 5$ is a prime number, the integers modulo $p$ form a field, sometimes called $\mathbb Z/p\mathbb Z$ or $\mathbb F_p$.  If we understand the arithmetic to be done modulo $p$, we can write these equations in the event of a forgery a little more simply as

\begin{align*}
  t &= r m + s, \tag{$*$} \\
  t' &= r m' + s. \tag{$**$}
\end{align*}

Mallory knows $m$ and $t$, and assumes the equation $(*)$ is true—i.e., that Alice is computing the authenticator correctly.  Mallory succeeds at forgery in the event that the equation $(**)$ is also true, given that $(*)$ is true—that is, Mallory's forgery probability is the conditional probability

\begin{equation*}
  \Pr[\text{forgery} \mid \text{message/authenticator}]
  = \Pr[t' = r m' + s \mid t = r m + s].
\end{equation*}

We can rearrange this a little bit to eliminate the independent random variable $s$ by observing that $s = t - r m$, so we're interested in the probability that $t' = r m' + t - r m$, or equivalently $r = \frac{t' - t}{m' - m}$, since $m' \ne m$ and we're working in a field in which we can divide by any nonzero element.  In other words,

\begin{equation*}
  \Pr[t' = r m' + s \mid t = r m + s]
  = \Pr[r = {\textstyle\frac{t' - t}{m' - m}}].
\end{equation*}

Since $r$ was a random variable with uniform distribution among $2^{130} - 5$ possibilities, and $m$, $m'$, $t$, and $t'$ were arbitrary (i.e., there's a for all quantifier here—the reasoning works for all values of $m$, $m'$, $t$, and $t'$, except when $m = m'$), we can conclude, irrespective of Mallory's computational powers,

\begin{equation*}
  \Pr[\text{forgery} \mid \text{message/authenticator}]
  = \Pr[r = {\textstyle\frac{t' - t}{m' - m}}]
  = 1/(2^{130} - 5).
\end{equation*}

This bound on forgery probability applies even if Mallory gets to choose the original message $m$ in an attempt to make the task of forging the authenticator for a different $m'$ even easier.

This one-time authenticator is the basis for one of the most popular message authentication codes on the planet, Poly1305, widely used in the authenticated cipher ChaCha/Poly1305 by TLS and in the related authenticated cipher crypto_secretbox_xsalsa20poly1305.  I left out many practical details:

extending it to longer messages by interpreting the 128-bit chunks of a message $m$ as a polynomial $m_1 x^\ell + m_2 x^{\ell - 1} + \dotsb + m_\ell x$ over $\mathbb F_{2^{130} - 5}$ and evaluating it at the point $r$;
restricting the space of the evaluation points $r \in \mathbb F_{2^{130} - 5}$ for efficient software implementation; and
extending it to many messages by deriving $r$ and $s$ pseudorandomly with ChaCha or XSalsa20 for each message.

With these practical details sorted out, the forgery probability is still no more than $8\ell/2^{106}$ where $\ell$ is the number of 128-bit blocks in a message, plus whatever advantage the adversary can get by attacking the pseudorandom key derivation.

This might look very different from the Gilbert–MacWilliams–Sloane paper (paywall-free).  But actually, it is precisely (an instance of) the scheme described by Gilbert, MacWilliams, and Sloane, just without the language of projective space from algebraic geometry.

The geometric picture of the GMS scheme is that:

a $\text{message}$ is a line (drawn in solid black) through the origin that hits the equator (drawn in grey at $z = 0$),
a $\color{blue}{\text{key}}$ is a line (dashed blue) through the origin that doesn't hit the equator, and
an $\color{red}{\text{authenticated message}}$ is a line (dotted red) through the origin perpendicular to both message and key.

For any fixed message, every corresponding authenticated message under any key passes through the great circle perpendicular to that message (solid black)—but to know which line through that great circle requires knowledge of the key.  For any fixed key, every authenticated message under that key passes through the great circle perpendicular to that key (dashed blue)—but knowing one line through that great circle doesn't help to find any other line through that great circle for a forgery because there are many great circles that the authenticated message passes through and any one of them could correspond to the true key.

How do we compute this, though?  We won't actually work in real projective space; we'll work in the projective plane of a finite field, which is a little trickier to draw but easier to compute with, from algebraic geometry.

Fix a prime power $q$ and consider the finite field $k = \operatorname{GF}(q)$ of $q$ elements.  The projective plane $\mathbb P^2(k)$ over $k$ is (by one of several equivalent constructions) the set of lines in $k^3$ through the origin, with each line typically represented by any nonzero point on that line—the projective coordinates $(x : y : z)$ represent the same line as $(\lambda x : \lambda y : \lambda z)$ for any nonzero $\lambda \in k$, as long as $x, y, z \in k$ are not all zero.  (This rules out ‘$(0 : 0 : 0)$’ as a point on the projective plane.)  There are $q^2 + q + 1$ points on the projective plane, which can be counted in various different ways—for example, $q^2$ points of the form $(x : y : 1)$, $q$ points of the form $(x : 1 : 0)$, and the remaining point $(1 : 0 : 0)$.

In the GMS one-time authenticator, a message is a point $(1 : s : 0)$ on the ‘equator’ for some $s \in k$, and a key is a point $(i : j : 1)$ off the ‘equator’ for some $i, j \in k$ chosen uniformly at random.  An authenticated message is a line in the projective plane through the message and the key—equivalently, the set of all lines in $k^3$ through the origin that intersect the great circle on the unit sphere between the points where the message and key intersect the unit sphere (the dotted red circle in the diagram above).

Now, as the set of all lines in $k^3$ through a particular great circle on the unit sphere, a ‘line’ in projective space $\mathbb P^2(k)$ corresponds to a plane in the enclosing space $k^3$, so we can characterize it by a normal vector $L \in k^3$ to that plane: that is, the plane representing a projective line is the space of all vectors $v \in k^3$ perpendicular to $L$ so that $L \cdot v = 0$.  Any such normal vector $L = (x, y, z)$ is perpendicular to both $(1, s, 0)$ and $(i, j, 1)$, so it must solve the linear system

\begin{align*}
  0 &= L \cdot (1, s, 0) = x + y s, \tag{$\dagger$} \\
  0 &= L \cdot (i, j, 1) = x i + y j + z. \tag{$\ddagger$}
\end{align*}

Note, of course, that if $(x, y, z)$ is a solution then so is $(\lambda x, \lambda y, \lambda z)$ for any nonzero $\lambda \in k$.  Hence we can also view an authenticated message as a projective point which is ‘perpendicular’ to both $(1 : s : 0)$ and $(i : j : 1)$; such a point is given by $(-s : 1 : c)$ where $$s i - j = c,$$ which is Eq. $(17)$ of the paper.  (Eq. $(\dagger)$ implies $x = -y s$, and Eq. $(\ddagger)$ implies $z = y s i - y j$; dividing the coordinates by $y$ gives the form $$(x : y : z) = (x/y : y/y : z/y) = (-s : 1 : c)$$ for $c = z/y = s i - j$.)

Of course, rather than drawing out doodles of lines and planes on a napkin, we can represent a message by the element $s \in \operatorname{GF}(q)$ alone, a key by a pair of elements $i, j \in \operatorname{GF}(q)$, and an authenticator by an element $c \in \operatorname{GF}(q)$, and then encode those in bit strings to transmit on a conventional medium like ethernet.  And if you pick $q = 2^{130} - 5$, you wind up with exactly the scheme this post started with.  The correspondence with the GMS notation is:

\begin{equation*}
\begin{array}{r|c|c}
\text{role} & \text{this post} & \text{GMS} \\
\hline
\text{prime power modulus} & 2^{130} - 5 & q \\
\text{message} & m & s \\
\text{key} & (r, s) & (i, -j) \\
\text{authentication tag} & t & c \\
\text{authentication equation} & t = rm + s & si - j = c
\end{array}
\end{equation*}

Appendix: Asymptote code for the diagram

import three;

size(10cm, 0);

triple msg = (1, 4, 0);         // (1 : s : 0)
triple key = (1/2, 1/5, 1);     // (i : j : 1)
real tag = ypart(msg)*xpart(key) - ypart(key);
triple authmsg =                // (-s : 1 : si - j)
  (-ypart(msg), 1, tag);

void
drawaxis(triple A, string text, align align)
{
  Label L = Label(text, position=EndPoint, align=align);
  draw(O--1.5A, arrow=Arrow3(TeXHead2), L=L);
}

drawaxis(X, "$x$", align=W);
drawaxis(Y, "$y$", align=E);
drawaxis(Z, "$z$", align=N);

draw(circle(c=O, r=1, normal=Z), p=gray(0.5));

draw(1.5 unit(msg) -- 1.5 unit(-msg), arrow=Arrows3, p=black,
  L=Label("\noindent msg:\\$(1 : s : 0)$", position=BeginPoint, align=SE));
dot(unit(msg), p=black);
dot(unit(-msg), p=black);

draw(1.5 unit(key) -- 1.5 unit(-key), arrow=Arrows3, p=blue + dashed,
  L=Label("\noindent key:\\$(i : j : 1)$", position=BeginPoint, align=NW));
dot(unit(key), p=blue);
dot(unit(-key), p=blue);

draw(1.5 unit(authmsg) -- 1.5 unit(-authmsg), arrow=Arrows3, p=red + dotted,
  L=Label("\noindent auth msg:\\$(-s : 1 : c)$", position=EndPoint, align=S));
dot(unit(authmsg), p=red);
dot(unit(-authmsg), p=red);

draw(circle(c=O, r=1, normal=msg), p=black);
draw(circle(c=O, r=1, normal=key), p=blue + dashed);
draw(circle(c=O, r=1, normal=authmsg), p=red + dotted);
draw(
  0.2 unit(key) -- 0.2 (unit(key) + unit(-authmsg))
    -- 0.2 unit(-authmsg),
  p=gray(0.5));
draw(
  0.2 unit(msg) -- 0.2 (unit(msg) + unit(-authmsg))
    -- 0.2 unit(-authmsg),
  p=gray(0.5));

draw(unitsphere,
     surfacepen=material(white + opacity(0.5), ambientpen=white));


Generate secp256k1 ECC key pair with libsodium I'm new to crypto and I want to generate a key pair, in C, which would be the equivalent of openssl ecparam -name secp256k1 -genkey -out ec-priv.pem.
I love libsodium API but I can't find how (if ever) to generate a key pair that is an EC key. I was expecting to get a 32-byte private key, and a 64 byte (+0x04) public key.
Is it something that is not offered by the high-level libsodium API?

Your question has been asked on the GitHub, too:

Is there some way with sodium/libsodium to make all crypto_sign_* methods use SECp256k1?

And the answer was given as

No, there isn't, and there never will be.
Libsodium is an opinionated API. You get one good algorithm for every use case. Fewer knobs and levers + more secure constructions = less crypto vulns in software that consumes the API.
For public key cryptography, you get ECDH and EdDSA over Curve25519. No Weierstrass or Koblitz curves.


ASCII to same-length ASCII encryption? I need to encrypt an ASCII string [a-zA-Z0-9:] to an ASCII [a-zA-Z0-9] string of the same length. It doesn't have to be unbreakable, it's sufficient that it won't be readable at the first sight.
The purpose is to encrypt my WiFi hotspot name with a key so that only my friends holding the key can decrypt a message from the hotspot name.

I might need XOR encryption that will guarantee that the output will be ASCII.
Or I can simply have a numeric key and add the corresponding key number to each ASCII code of the char of the hotspot name.

What would you suggest?

I need to encrypt an ASCII string [a-zA-Z0-9:] to an ASCII [a-zA-Z0-9]
  string of the same length.

The pigeonhole principle can be used to explain why it is not possible to encrypt every 15-character string from some set of sixty-three characters into an encrypted 15-character string from a set of sixty-two characters.

  I need to encrypt an ASCII string [a-zA-Z0-9:] to an ASCII [a-zA-Z0-9]
  string; it's OK if the encrypted string is slightly longer.

There are a huge variety of ways to do this.
Off the top of my head, I might consider:

replace each ":" in the plaintext with "_"
decode the plaintext string from "base64url" encoding into a series of octets (which probably include some unprintable octets)
encrypt the series of octets using practically any implementation of practically any encryption algorithm, using the secret key that you have (somehow) distributed.
encode the ciphertext octets using any "base32" encoding.
The result is ciphertext that only uses 32 printable ASCII characters, but is slightly longer -- six-fifths the size of the original text if you pick a "length preserving" algorithms, somewhat longer if you pick an algorithm like salted AES encryption with an authentication code.

  I need to encrypt an ASCII string [ A-Za-z0-9-_ ]
  to an ASCII [ A-Za-z0-9-_ ]
  string of the same length.

Forcing the ciphertext to be exactly the same length as the plaintext makes a system less secure than one that has room for an initialization vector, an authentication code, etc.

Ah, the "base64url" character set.
With a character set that is a power of 2,
you can use pretty much any implementation of any "length preserving" algorithm, including the Vernam XOR one-time-pad cipher you mentioned and the Vernam modular addition one-time pad.

To encode a string using a Vernam XOR one-time pad, pull a fresh never-been-used page from your one-time pad.
For each character in your message: decode the character into a 6-bit number 0..63,
XOR that character with the corresponding 6 bits from your one-time pad,
then encode the resulting number (which will also be in the range 0..63),
to the corresponding character in the 64-character set.
Then eat or burn that page from your one-time pad, forcing you to use a different page for your next message.
Other encryption algorithms don't require you to consume your secret key, and so are often easier in practice.

  I need to encrypt an ASCII string [A-Za-z0-9] to an ASCII [A-Za-z0-9]
  string of the same length. I need all these characters in the plaintext, and I can't use any other characters or punctuation in the ciphertext.

Forcing the ciphertext to be exactly the same length as the plaintext makes a system less secure than one that has room for an initialization vector, an authentication code, etc.

Ah, format-preserving encryption with a 62-character set.
Most encryption algorithms -- including Vernam XOR -- don't work with such a restriction.
However, a few stream ciphers including modular addition one-time pad can handle such a character set.

To encode a string using a Vernam modular addition one-time pad, pull a fresh never-been-used page from your one-time pad (or generate the next derived block from your stream cipher).
If your keyblock has been generated by throwing a pair of dice or flipping an array of 6 coins, cross out and ignore any values of 62 or greater,
so we have values 0..61 of equal probability.

For each character in your message: decode the character into a number 0..61,
add that character to the corresponding number 0..61 from your derived block --
subtracting 62 if the result is too big, so the final result is in the range 0..61.
Then encode the final result to the corresponding character in the 62-character set.
Then eat or burn that page from your one-time pad, forcing you to use a different page for your next message.
Other encryption algorithms don't require you to consume your secret key, and so are often easier in practice.

(The GROMARK and Gronsfeld ciphers resemble Vernam modular addition, except using a smaller range of values of 0..9 rather than 0..25 or 0..61, and so are less secure but much easier to use).

(The ROT13 cipher is even easier to use, but provides practically no cryptographic security).

p.s.:
Isn't a SSID typically 32 characters?


Why isn't outputting only a portion of the hash state a simple defense against length extension attacks? As I understand length extension attacks, they depend on the coincidental property of most cryptographic hash functions that the hash value is exactly the hash function state after hashing the last block of data. This enables an attacker to initialize their own hash function with the state as it "left off".

This being the case, why are hash functions simply not defined as outputting the n-byte prefix of their state (i.e. for a 256-bit hash, maintain 512 bits of state)? I'm assuming there's a fundamental reason this isn't done, but I haven't been able to find any literature specifically addressing it.

Contrary to your assumption, this is done, and it is secure: For instance, the hash functions SHA-224 and SHA-384 are basically the same algorithms as SHA-256 and SHA-512! The only differences are in the initial values for the Merkle-Damgård construction used internally and, of course, in that only the first $224$ or $384$ bits of the resulting hash are output. These hash functions are resistant against length-extension attacks since an attacker would have to guess the remaining (too many) bits of the internal state. (Note that the choice of different initial values is irrelevant to this issue, so just truncating SHA-256 or SHA-512 also yields length-extension-resistant hashes.)

As another almost-example: In some sense, Keccak/SHA3's first $r$ output bits are simply a prefix of the internal state after consumption of the last block, while the rest of the state is kept secret (and possibly used to compute more output bits, which are again prefixes of the internal state, through repeated application of a so-called "sponge function"). With this construction one can argue, and in fact this is advertised as a feature of Keccak, that the keyed hash $\operatorname{Keccak}(\mathit{key}\mathbin\Vert\mathit{data})$ yields a secure MAC, while the same construction for Merkle-Damgård hashes is vulnerable to length-extension attacks.


Does the Blake3 hash have identities, due to its merkle tree structure? I've read that the Blake3 hash uses a Merkle Tree.
Does it follow that there are identities such as:
b3sum("This is ") xor b3sum("a test.") == b3sum("This is a test.")

The example above does not work, perhaps because the block size is not eight bytes.
Are there any real Blake3 identities of a similar form?

No, any simple identity like that would violate the cryptographic properties that BLAKE3 aims to have. Finding these cases is supposed to require a brute force search.
BLAKE3 is a Merkle tree, but it isn't constructed by XORing things together. Instead, parent nodes in the tree are constructed by concatenating the hashes ("chaining values") of each child, and then calling the compression function again with that concatenation as the input. Other important details are that the compression function domain-separates chunk/leaf outputs from parent node outputs, and that it domain-separates the root node from non-root nodes. (As an aside, it also domain-separates each chunk/leaf based on its index. That's not necessary for the security property we're talking about here, but it accomplishes other things. See section 7.5 of the BLAKE3 paper.) Putting all that together, it should be difficult to find any relationship between the BLAKE3 hashes of any two distinct inputs.


Is the "Hash Tree" described in this paper the same as a Merkle Hash Tree? I'm implementing an algorithm from a paper, and part of it calls for using a "hash tree". Since I'd never heard of that data structure I looked it up on Wikipedia. It turns out that the name hash tree is ambiguous and can be used to refer to three different types of data structures. They are:

Hashed Array Tree
Hash tree (persistent data structure), an implementation strategy for sets and maps
Merkle Tree

After reading about each type of data structure, I'm pretty sure that the paper is using a Merkle tree, but I want to get a second opinion. The only thing that makes me doubt that it might be a Merkle Tree is that it seems like I can find lots of examples of it being used in Cryptography and I only see it mentioned a few times in the data mining papers that I'm reading.

The paper in question is Fast Algorithms for Mining Association Rules and the specific section that I'm referring to can be found on page 4 in section 2.1.2.

I've quoted a section of the relevant text below.

  Candidate itemsets Ck are stored in a hashtree. A node of the hash-tree
  either contains a list of itemsets (a leaf node) or a hash table an (interior node). In an interior node each bucket of the hash table points to another node. The root of the hash-tree is defined to be at depth 1.  An interior node at depth d points to nodes at depth d+1. Itemsets are stored in the leaves. When we add an itemset c we start from the root and
  go down the tree until we reach a leaf. At an interior node at depth d we decide which branch to follow by applying a hash function to the dth item of the itemset. All nodes are initially created as leaf nodes. When the number of itemsets in a leaf node exceeds a specified threshold the leaf node is converted to an interior node.

It should also be noted that this particular data structure is mentioned in other data mining papers that are based off of the apriori algorithm such as in this paper on cyclic association rules. Since it is a data structure that is used often, I'd like to read more about is than simply two paragraphs in a few papers.

It turns out that the Hash Tree mentioned in the paper is pretty much the same as a Merkle Hash Tree. For further clarification see pages 344 & 345: https://www-users.cs.umn.edu/~kumar/dmbook/ch6.pdf.


Multiplication by 2 in the Rijndael Galois field I was studying the mix column transformation in AES and working through an example.

$[\mathtt{02}]\cdot[\mathtt{87}]$ - this multiplication works fine in the polynomial form modulo $x^8+x^4+x^3+x+1$. The polynomial answer to this is $x^4+x^2+1$ which is $\mathtt{0001 0101}$. But if you try to work this in bits, the answer you get is $\mathtt{0001 0100}$. (Multiplying by $2$ is the same as a left shift by $1$ followed by XOR with $\mathtt{00011011}$ if the MSB was $1$ before the shift).

Why is there a difference? Obviously, there shouldn't be a difference... Where am i going wrong?

I suspect you got the shift wrong.

Anything shifted left by 1 has an lsbit of 0; if you xor in 010101 (which you do in this case, as the initial value had a 1 msbit), well, 010101 has a 1 lsbit, and the xor of the two must have a 1 lsbit; your result had a 0 lsbit.

Perhaps you're doing a left circular shift (moving bit 7 to bit 0), rather than a left shift (which places a 0 into bit 0)


Generating HMAC-SHA256 - is this procedure secure enough? I have 256-bit value (call it "{Secret Value}") and I would like to compute HMAC-SHA256 digest of this value to check its integrity, and second requirement is to  minimize need of another artifacts for this process.

I have an idea that do not need any other artifact but {Secret Value}:

Compute PBKDF2 key from {Secret Value}, and as a salt use first 64 bits of my {Secret Value}
Key computed in step 1 use as key for HMAC-SHA256 and as value use {Secret Value}

Another option in step 1 is compute another PBKDF2 key for salt value from {Secret Value}.

I need to create this integrity digest to check if {Security Value} comming from user is the same as value I have in database.

Is this approach secure enough?

If you do this like that you won't guarantee the authenticity of your message, only its integrity, as you say you want to... but then if you only need to check integrity, you would be fine with a simpler SHA256.

But FWIW, HMAC is like a wrapper around a secure hash function adding a key, so if you remove the key, you end up with a secure hash function, plus some sequin, if I dare say so.

So, I wouldn't say it is secure per se, unless I knew what problem you are trying to solve, but this way to go will provide you with integrity while using a somewhat more complicated method than usual. (Which is generally not recommended.)

EDIT to address Artegon's comment:
If you really want to use HMAC for your purpose (which is to compare a client value with a value in the server database), you can do so with a challenge-response mechanism, you can use for example the SCRAM one which will use PBKDF2 and HMAC, like you do, but in a way that guarantee that the secret is not leaked and the authenticity of the parties is assured even in case of a MITM.

Otherwise you can devise one which is weak to MITM attack by simply doing the HMAC of the challenge using the secret value as HMAC key... (But you should do so only if you know for sure your channel is secured against MITM attack thanks to public key crypto/a shared secret/etc, otherwise you have to first establish a secure channel, e.g. using your shard secret value to do so... But then you could as well use SCRAM, since it already exists and is good.)


How do you test randomness? Suppose I receive a list of 1 million coinflips, and I want to know how likely it is that the list was randomly generated.

My first thought would be to count the number of heads and tails, which should be evenly distributed (around 500.000). But suppose the distribution looks normal, its still possible the list contains patterns or repititions. For example, the first half of the list may be the heads, and the last half the tails. In real random data, that would be highly unlikely.

So how do you calculate the 'randomness' of this list?

You can never actually prove that it was generated randomly or pseudorandomly. You can only prove with high probability that it wasn't. Calculating the number of heads and tails is one way. Another is calculating runs of consecutive heads or tails. There is a suite of statistical tests from NIST in their FIPS 140-2 document which is a good place to start.

Having said that, for cryptographic purposes you really need to be sure that you are using a secure random number generator and there aren't any tests you can apply to the data itself to sufficiently guarantee that it is secure enough.


Is ChaCha20 alone sufficient for securing data-at-rest? I wonder if ChaCha20 alone is sufficient for securing files stored on a disk or should Poly1305 should be used along with it? AFAIK, Poly1305 is used to secure the authentication channel, but for securing data-at-rest, the key can be read from the OS's keystore, which (typically) is fairly secure - correct?

If so, does that mean ChaCha20 alone is good enough?

Thanks

You really don't want to use ChaCha20 alone in (nearly) any situation.

What ChaCha20 does for you is to prevent attackers from (passively) reading your data, which is good. But ChaCha is a so-called stream cipher which works by XOR'ing a pseudorandom pad with the message (your file at rest). However it is for this very way of working that ChaCha doesn't prevent attackers from (actively) reading your data if you allow them to decrypt anything but the stored cipher text.

If an adversary now gets hands-on your drive / file he can manipulate the file. For example assume it's your next day's financial transaction plan. An attacker who knows where the account ID of the receiver lies and knows who should receive the transaction can flip the bits at that position in a way that his bank account is the target.

Poly1305 is designed to prevent this kind of attack by assuring that the data hasn't changed without knowledge of the key. Assuming the key for Poly1305 is unknown to the attacker he can't correctly update the authentication tag. If he now changes a single bit of the cipher text the verification will fail and you'll notice that somebody has changed your file, protecting you from a malformed operation ( / transaction).

TL;DR: ChaCha20 protects your file from being (passively) read, but not from being manipulated, which may easily cause severe attacks. So you really want to use Poly1305 in addition to ChaCha20.


What are rounds in the context of ciphers? Another recent question on security margin included in its answer the discussion of how many rounds are broken so far. What is the definition of a round?

Many block ciphers are defined by specifying a round and then running that specification multiple times. For example, in AES, a round consists of the operations SubBytes, ShiftRows, MixColumns, AddRoundKey. That is one round and, to get AES, you run that multiple times (plus some setup and some post-processing).

Thus a round is defined by each cipher and typically consists of a number of building blocks that are composed together to create a function that is run multiple times.


A problem exists with the security proof in the secure AND example in the malicious model Imagine that the malicious adversary in the real world uses $Y = 0$ as its input, therefore he computes the output as ($X$ && $y=0$) = $0$. We can conclude that the real view in the real world is as:

Real view: $X, Y = 0$ and $output = 0$

Real World

Now, imagine the simulator wants to simulate the real world’s view in the ideal world. In order to simulate $x$ (honest party’s input), the simulator must send $1$ to the trusted party and then receives $x$ from it. Thus the simulator succeeded to simulate $X$, but now the simulator computes the output as
 $X$ && $(Y = 1)$ = $X$, which is not the equal of the output in the real view $X$ && $0$ = $0$. Thus the simulator cannot simulate the output in the ideal model.

Ideal World

Definition 2.3.1 in the malicious model

The definition says that for every adversary A for the real model must exist a simulator S for the ideal model. Considering this definition, I could find an adversary (who sends $y = 0$ in the real world) that there is no any simulator for it, so the protocol is not secure in the malicious model. In the Lindell’s book-page 27 (the below proof), it is said that this protocol is secure!!! I am so confused. (I found a scenario where the protocol is not secure).

Proof of the protocol

If I understand correctly, you consider an adversary $\mathcal A$ corrupting $P_2$ in the real world, and which ignores $P_2$'s input $y$ and just outputs $0$ regardless of the value $x$ sent by $P_1$, is that right? And you claim that this adversary is not simulatable.

Well, of course this adversary is simulatable: the simulator sends whatever to the trusted party, receives whatever, and outputs $0$.

The proof, by the way, shows more: it shows how to construct a simulator for any adversary, as follows. In the real world, the adversary receives $x$, performs whatever computation based on $x$, $y$, and its auxiliary output $z$, and outputs the result. The simulator sends $1$ to the trusted party, receives $x$, performs the same computation as the real-world adversary, and outputs its result.


Encrypted file and decrypted hash What is the risk of storing an MD5 (or similar) hash of a decrypted file alongside the encrypted version of the same file.

Obviously if someone were to attempt a brute force attack against the file having the hash would provide an end condition for the attack.  Does providing the hash make reversing the encryption easier in some other way?

What is the risk of storing an MD5 (or similar) hash of a decrypted file alongside the encrypted version of the same file.

Note that MD5 is not considered secure anymore, especially with regards to hashing or signing files. Please consider SHA-2 or SHA-3 for your hashing needs.

Otherwise, you're answering yourself below.

  Obviously if someone were to attempt a brute force attack against the file having the hash would provide an end condition for the attack.

Indeed, and that's the main problem.

  Does providing the hash make reversing the encryption easier in some other way?

No, because the hash - even MD5 - is not reversible, so it doesn't leak any other information. Cryptographically secure hashes are one way functions. You can only brute force them.

Note that storing a hash in the same location only provides protection against errors. An attacker may e.g. brute force the plaintext, change a single bit in by e.g. changing the CTR-encrypted ciphertext and recalculate the hash.

Storing a signature over the plaintext data makes a whole lot more sense. Or, if you want to always store the files encrypted and do not want to leak information, store a signature over ciphertext.


What is the probability to produce a collision under two different hash functions? Given 2 (weak) hash functions, namely MD5 and SHA1

The fact that there exists 2 different inputs that will result in the same output under both hashing functions is explained in "Can there be two hash functions without common collisions?"

I would like to quantify the probability of this type of inputs to be forged.
Namely:

MD5(x) = MD5(y)
whilst
SHA1(x) = SHA1(y)

So if I keep the two hashes of a file, how much harder is it to forge another file that yield the same hashes rather than either of those individually ?

I expect it to be more than the added probability of each, but by how much (order of magnitude) ?

A "simple" answer (but somewhat wrong) would be the following: define function $H$ which is the concatenation of MD5 and SHA-1; i.e. on input $x$, $H(x)$ will be the 288-bit string consisting of MD5($x$) (128 bits) followed by SHA-1($x$) (160 bits). If you have distinct two messages $x$ and $y$ such that MD5($x$) = MD5($y$) and SHA-1($x$) = SHA-1($y$), then, by definition, $x$ and $y$ are a colliding pair for $H$. Since $H$ has a 288-bit output, finding a collision for $H$ requires an average effort of, at most, $2^{144}$ invocations, since that's the best you can expect from a "perfect" hash function.

What's wrong in the paragraph above is that the $H$ function, as described above, is far from the "perfect" state. In 2004, Joux published (Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions) an attack that works on "iterated" hash functions such as MD5 and SHA-1, which shows that even if MD5 and SHA-1 were both ideally strong (given their output size), the concatenation would not be stronger than the strongest of the two. In other words, even without leveraging known attacks on MD5 and SHA-1, a collision on the concatenated hash function $H$ can be found in about $2^{80}$ invocations. This work was generalized in 2006 by Hoch and Shamir (Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions).

Now, both MD5 and SHA-1 have known structural attacks. In an answer to a previous question on that subject, @poncho explains how to use the known attacks on SHA-1 (with cost $2^{61}$) to make a simultaneous MD5+SHA-1 collision in effort $2^{67}$. Amusingly, this does not leverage any specific weakness of MD5; it would also work for a perfect 128-bit hash function instead of MD5.


What are the costs of generating master key for symmetric ciphers? I recently read that generating large master keys for symmetric ciphers is very expensive. But what exactly do they cost? Any references would be much appreciated. I have checked NIST but actual costs seem hard to find.

The cost for generating master keys is not very expensive. It just requires secure random bit string of the same size as the key. Compare this with RSA, where a random prime needs to be generated. This may require repeated calls to the random number generator; you'd expect at least the same number of random bits for the RSA key size. Generally the largest symmetric keys are about 256 bits - far lower than the key size of even moderately secure RSA key pairs.

Now it completely depends on your requirements on the secure random number how much this will cost. If you require your master keys to be build directly upon (whitened) entropy then this may be a very expensive process if your entropy sources are slow. If you're OK with pseudo random numbers or if you have fast entropy sources, it will probably not be slow.

So it depends on the requirements and the implementation of the underlying RNG. I've seen several instances of Linux completely halt when large amount of data is retrieved from the (blocking) /dev/random. Usually it is possible to configure use of /dev/urandom instead. And usually this is as secure.


Diffie–Hellman Ephemerality Nomenclature Below is a short excerpt of available DH cipher suites available on a machine.

I understand EDH is ephemeral DH, and that ECDH is for Elliptic-Curve DH which is computationally faster.  ECDHE is both of those aspects together.  The confusing bit how there are EDH cipher suites and DHE suites.  The wikipedia article says both acronyms can be used to describe Ephemeral Diffie-Hellman suites, but it also mentions that DHE can stand for "Diffie-Hellman Exchange" which would have no ephemerality.  I am very interested in Perfect Forward Secrecy for my application and it is vital that I only use a suite with brief ephemerality.  How can I be sure which is which?

ECDHE-RSA-AES256-GCM-SHA384
ECDHE-ECDSA-AES256-GCM-SHA384
DHE-RSA-AES256-SHA
DHE-DSS-AES256-SHA
ECDH-RSA-AES256-SHA
ECDH-ECDSA-AES256-SHA
ECDHE-RSA-DES-CBC3-SHA
ECDHE-ECDSA-DES-CBC3-SHA
EDH-RSA-DES-CBC3-SHA
EDH-DSS-DES-CBC3-SHA
ECDH-RSA-DES-CBC3-SHA
ECDH-ECDSA-DES-CBC3-SHA
ECDHE-RSA-AES128-GCM-SHA256
ECDHE-ECDSA-AES128-GCM-SHA256
DHE-DSS-AES128-GCM-SHA256
DHE-RSA-AES128-SHA256
ECDH-RSA-AES128-GCM-SHA256
ECDH-ECDSA-AES128-GCM-SHA256
ECDHE-RSA-RC4-SHA
ECDHE-ECDSA-RC4-SHA
ECDH-RSA-RC4-SHA
ECDH-ECDSA-RC4-SHA
EDH-RSA-DES-CBC-SHA
EDH-DSS-DES-CBC-SHA
EXP-EDH-RSA-DES-CBC-SHA
EXP-EDH-DSS-DES-CBC-SHA

Agreeing with @otus but adding more background and context than I think belongs in comments:

This is an OpenSSL question though you don't say so; all other SSL/TLS software I've looked at uses the RFC spellings DHE ECDHE DH_anon ECDH_anon, but OpenSSL was written yonks ago with EDH in some places (mostly the ones dating before ECC was introduced and there was no ECDH to confuse with EDH) and ADH and AECDH in all. You may not have observed the latter two because all unauthenticated suites are disabled by default and very rarely used. So far the devs have been reluctant to "fix" spelling because that could break config files, scripts, calling applications, etc. Especially since OpenSSL cipherstrings are so arcane there seems to be a whole stratum of websites confidently ordaining "the single good way to configure ciphers in openssl or $thing_using_openssl", nearly all of them different and many of them long out of date or completely wrong.

If you look at the cipher details with openssl ciphers -v [$cipherstring] you will see which key-exchange and authentication methods (and also data cipher and MAC) are used for a given ciphersuite. In recent versions if you use -V (cap vee) it also shows the code value sent on the wire, which you can match to the RFCs to be 100% certain it is really the same thing.

A few months ago there was discussion on the maillist about accepting the standard spellings while still preferring the OpenSSL ones. See
http://rt.openssl.org/Ticket/Display.html?id=3203 (guest/guest for readonly access);
it appears this made it into 1.0.2, currently in beta.

1.0.2 is also planned to add the NON-ephemeral (and non-EC) DH suites. It's not clear if anyone wants or ever used them -- I've certainly never seen any public CA offer DH certs. (Integer DH keys have slightly different encoding than DSA and thus need a different cert, whereas one EC key & cert can be used for either ECDH and ECDSA depending on KeyUsage and technically can be used for both although it is not considered best practice to use one key of any type for multiple purposes.) Adding to otus' correct statement about static-ECDH, static-DH also will not provide PFS.

A more glaring (but non-DH) spelling difference is that OpenSSL names entirely omit "RSA" for plain-RSA key-exchange (not something authenticated by RSA). Also it varies spelling of 3DES. E.g. standard TLS_RSA_WITH_3DES_EDE_CBC_SHA is OpenSSL DES-CBC3-SHA. (Technically EDE is redundant because EEE, the alternative originally considered, was rejected, but putting the 3 after CBC suggests "inner" CBC mode which also was considered but rejected in favor of "outer".)


$P \ne NP$: a proof relating complexity theory to block ciphers I started thinking about P vs NP after reading another question on this stack exchange. Here I propose a proof that relates P vs NP to the existence of a secure block cipher in the elf model.
Let's say I have a (normal) Turing machine and I want to model a nondeterministic machine with it. According to certain models, a nondeterministic Turing machine can branch at each decision to multiple instances of itself. If I have an input $N$ of $n$ bits, let's say I must make a decision for each of $n$ bits: that's $2^n$ possible branches, operating in parallel. Since  a normal Turing machine must loop through every state of $N$, operating on each independently, wouldn't that mean $P \ne NP$ since I can construct a problem in $NP$ which requires me to operate on all possible $N$.
If we consider a an ideal block cipher we can say there exists a construction which requires you to operate on every possible input (consider the elf model). In the elf model, one must either form a lookup table of the entire mapping ($2^b$ blocks where $b$ is the block size) or iterate on every possible block. Therefore, if there exists a secure mode of operating on multiple blocks in the elf model, there must exist a problem in $NP$ which cannot be performed without iterating over every possible $N$. Since secure modes of operations are known to exist (if a secure block cipher exists), and the elf model proves a secure block cipher exists, this would prove $P \ne NP$.
If I can create a cipher which requires me to solve a cipher with a smaller block size (a perfect block cipher), I can force the decision to depend on every input bit, making the security rely only on obtaining perfect diffusion among the possible states, which many ciphers do already. This way I can create a secure block cipher from another secure block cipher, of smaller block size. Effectively, every SP-network is proof that $P \ne NP$.
Is this valid, or is there anything I'm missing? Is there anything unclear about my reasoning?

and the elf model proves a secure block cipher exists

It is worth mentioning that lower bounds in computationally limited settings do not "lift" [1] to lower bounds in computationally stronger settings. For example, there are lower bounds of $\Omega(\sqrt{|G|})$ on DL in the generic group model. This does not prove that DL is hard in "real life" though (and in fact, finite-field discrete log has $o(\sqrt{|G|})$ algorithms).
Secure block ciphers are not known to exist unconditionally. I don't know if your post precisely says this anywhere (this is the impression I get of the insight of your post though), but a proof that a secure block cipher exists immediately proves that $\mathsf{P}\neq \mathsf{NP}$.
This is because:

Secure Block ciphers are Pseudo-Random Permutations (PRPs)
PRPs imply One-Way Functions (is this HILL89? Idk its one of those old results)
The existence of One-Way Functions directly shows $\mathsf{P}\neq\mathsf{NP}$ (the problem of inverting a poly-time computable function is easily shown to be in $\mathsf{NP}$. The function being one-way means this can't be done in $\mathsf{P}$, and therefore we've found an $\mathsf{NP}$ language which is not in $\mathsf{P}$.

[1] There are areas of complexity theory which try to do exactly this though. Look up "lifting theorems" in communication complexity in particular, where lower bounds in weak models (generally things like decision trees) are "lifted" to lower bounds (for slightly different problems generally) in stronger models. This all being said, I do not expect lifting theorems to be useful for your application.


Recombination thresholds in degree reduction of multiplied Shamir shares Shamir's secret sharing can be considered multiplicatively homomorphic, if one is aware of the fact that multiplying two shares of a (n,t)-threshold shared secret yields a share of the same secret, but over a (n, 2t)-threshold sharing.

To overcome this, there is a secure degree reduction protocol, which is already explained in this question. My follow-up question tackles an unexplained point in that question's accepted answer:

The subsharings ($\sigma_3(x)$ to $\sigma_5(x)$ in the referenced answer) are polynomials of degree 1, i.e. 2 shares are needed for proper recombination.

However, trying this using two arbitrary shares for interpolation fails.
At the end of this question I paste a short Python script using VIFF that shows the misbehavior. When using a threshold of 2 (needing 3 shares) for
recombining the subshares, then the final shares can be arbitrarily recombined using only two shares, as expected from the secure degree reduction protocol.

How comes that you need a larger number of subshares than the degree of the corresponding polynomials for proper recombination?

In the following the Python snippet (note that there is a 1/11 chance that the lower threshold accidentially works):

from viff import shamir
from viff.field import GF

# Zp(x) gives an object that corresponds to x mod 11 and allows for multiplication
# I.e., Zp(3) * Zp(5) == Zp(15) == Zp(4)
Zp = GF(11)

# Share 5 and 2 among 3 players with threshold 1 (>= 2 shares needed)
t = 1
sh1 = (shamir.share(Zp(5), t, 3))
sh2 = (shamir.share(Zp(2), t, 3))

# Multiply shares, implies shares for 5*2 = 10, but threshold is 2
multiplied_shares = [ (Zp(i+1), sh1[i][1] * sh2[i][1]) for i in xrange(0, 3) ]
print('Recombination ' + ('works' if shamir.recombine(multiplied_shares[0:2*t+1]) == Zp(10) else 'does not work'))

# Create subshares of the multiplied shares, using threshold 1 (*)
sh3 = shamir.share(multiplied_shares[0][1], t, 3)
sh4 = shamir.share(multiplied_shares[1][1], t, 3)
sh5 = shamir.share(multiplied_shares[2][1], t, 3)

# Distribute the subshares
p1_shares = [ (Zp(1), sh3[0][1]), (Zp(2), sh4[0][1]), (Zp(3), sh5[0][1]) ]
p2_shares = [ (Zp(1), sh3[1][1]), (Zp(2), sh4[1][1]), (Zp(3), sh5[1][1]) ]
p3_shares = [ (Zp(1), sh3[2][1]), (Zp(2), sh4[2][1]), (Zp(3), sh5[2][1]) ]

# Try to recombine subshares using threshold 1 fails despite sharing (*) above
p1_final1 = shamir.recombine(p1_shares[0:t+1])
p2_final1 = shamir.recombine(p2_shares[0:t+1])
p3_final1 = shamir.recombine(p3_shares[0:t+1])
final_shares1 = [ (Zp(1), p1_final1), (Zp(2), p2_final1), (Zp(3), p3_final1) ]
final1 = shamir.recombine(final_shares1[0:t+1])
print(str(final1) + ' is ' + ('' if final1 == Zp(10) else 'NOT ') + 'correct')

# However, recombining subshares using threshold 2 works
p1_final2 = shamir.recombine(p1_shares[0:2*t+1])
p2_final2 = shamir.recombine(p2_shares[0:2*t+1])
p3_final2 = shamir.recombine(p3_shares[0:2*t+1])
final_shares2 = [ (Zp(1), p1_final2), (Zp(2), p2_final2), (Zp(3), p3_final2) ]
final2 = shamir.recombine(final_shares2[0:t+1])
print(str(final2) + ' is ' + ('' if final2 == Zp(10) else 'NOT ') + 'correct')

This is the correct behavior. Since the degree of the multiplication sharing is $2t$, it will take $2t+1$ shares of either it directly or the subshares. If done on the subshares, the resulting sharing is of degree $t$.

Shamir secret sharing is commutative with respect to polynomial evaluation.

Let $\sigma_1^t$ be the polynomial for sharing $s$ with degree $t$. So, multiplying shares generated by $\sigma_1^t$ and $\sigma_2^t$ (which shares some $s'$), we get a share of $\sigma_3^{2t}$, which shares $ss'$. To reconstruct $ss'$ it would take $2t+1$ shares.

In the degree reduction step, we create subshares with a threshold of $t$, or $\sigma_4^{t}\circ\sigma_3^{2t}$, in other words, we have a degree $t$ sharing of a degree $2t$ share. Due to commutativity, we can rearrange things to get $\sigma_3^{2t}\circ\sigma_4^{t}$, then apply the inverse operation $(\sigma_3^{2t})^{-1}$, to get $(\sigma_3^{2t})^{-1}\circ\sigma_3^{2t}\circ\sigma_4^{t}$, which gives you $\sigma_4^{t}$.

So I have probably thoroughly abused notation, but hopefully that makes sense. You are doing the inverse operation on a $2t$ degree sharing in order to get back to the degree $t$ sharing.

Some consequences of this are 1) in MPC we assume that everyone will participate in the protocol. If one party refuses to participate, the degree reduction won't work. 2) This is used to establish the theoretic upper bound on information theoretic honest-but-curious MPC protocols.


Does a cipher exist with the following properties? The key can unlock the ciphertext in polytime (measured in length of key + cipher).
a. Given the key + ciphertext as input, if you cannot unlock it in some fixed number of steps (relative to input size (key + cipher)) you reject.

b. No one can break your cipher in under this ^ number of steps without a valid key (not the average case--worse case)
The length of the ciphertext is no more than polynomially longer than the key.

Could you be looking for a password hashing KDF function with a secret parameter (a.k.a. pepper)?

With the correct password, the verification succeeds in a flash; without it, you can neither find the password, nor the keys derived from it.

Also, since it's not data/message encryption, the input and output are "short".

Of course, what appears to meet the description could still fail to provide the functionality that you want, so you have to rethink from the start to determine what security service(s) you want.

E.g.

confidentiality,
integrity protection,
authenticity guarantee,
non-repudiation,
recipient exclusion,
proof-of-work.