Example of calculating a primitive root for large prime? I am trying to figure out how to calculate primitive root $w$ for a prime.
Following what I read, I generated my prime to be 'safe prime', $p=qr+1$.
I know $q$ (also prime) and $r$. Let's assume, for example: $q=11$, $r=8$ and $p=89$. Both $p$ and $q$ are prime, as needed.

I now find $w$ by choosing random number $h\mod p$ , take for example $h=41$:
$$w=h^r\mod p\\w=41^8\mod 89=32$$

However, $32$ is not a primitive root for $89$. I know I am probably get something wrong, please help me find my mistake.

Thank you for your time!

The first question to ask is "are you looking to find a primitive root (that is, a value $g$ such that $g^x \bmod p$ takes on all possible values in $\mathbb{Z}_p^*$), or are you looking to find a generator to the subgroup of order $q$?

Depending on what you are trying to do, either may make sense.  If you are trying to get a subgroup for a DLog-based cryptosystem, the second may be what you want.  On the other hand, sometimes we really want a primitive root.

The procedure you gave is a fine way to find a generator to the subgroup (assuming that you include a check that the value $w$ you get is not 1); however it is guaranteed not to give you a primitive root.

If you really want a primitive root, there are a couple of obvious possibilities:

One is to pick a random value, and check if it happens to be a primitive root (which happens often enough to make this practical).  This is easy if you know the factorization of $p-1$; that is, $x$ is a primitive root if, for all prime factors $s$ of $p-1$, we have $x^{(p-1)/s} \not\equiv 1 \pmod p$
We can also do it be construction; for example, if $(p-1)/2$ is also prime (that is, $r=2$ in your formulation), and $p \equiv 3 \pmod 8$, then $w=2$ will always be a primitive root.

BTW: common usage nowadays is that a "safe prime" is a prime $p$ where $(p-1)/2$ is also prime (also known as a Sophie Germain prime).  It used to have other meanings associated with it as well; however it's been a while since I've heard those other meanings used.  Using the term now with a meaning other than what is common is likely to confuse people.  If you need to use a different meaning, I'd suggest using different terminology.


Expected Polynomial time Simulator in Interactive ZKP I was reading the Zero knowledge property for Interactive Proofs. It said that for the proof to be zero knowledge, there should exist a simulator that runs in expected polynomial time for all verifiers, such that the simulator can generate a distribution which is identical to the view of the Verifier.
What was the need of formalizing this property with such a simulator?
Is it formalized with a simulator that runs in polynomial time, which has access to the random bits of Verifier, and which generates the Verifier's view only using the input to the proof and the verifier's random bits? This formulation seems much more intuitive to me.
Moreover, it also gives me a better idea as to why we allow the simulator to generate the random public string in NIZKP.
I am also confused as to how exactly the simulator is allowed to interact with the Verifier.

Simulator does not have access to random bits of Verifier. Expected polynomial time means expected value (expectation from probability theory) of running time is polynomial in problem size. Simulator is a kind of replacement of Prover, exchanging messages in exactly the same way.

Introducing your own definitions is ok, but you will be proving probably another statement (different protocol property) with your definition.


What makes the quadratic residuosity problem hard? The quadratic residuosity problem is the problem of determining whether, for given $r$, $m$, $\exists a.a^2\equiv r\mod m$.

This problem's believed to be hard to solve in general (e.g. an efficient general solution to finding $a$ would allow you to factorise semiprimes efficiently). However, there are many special cases where the problem is easy (e.g. when $r$ and $m$ are both odd primes, determining whether or not $a$ exists can be solved in constant time), and I'm interested in avoiding those special cases.

I'm looking at the decision problem version of quadratic residuosity – that is, to determine whether $a$ exists at all (the attacker doesn't need to be able to work out what its value is). What restrictions are needed on $r$ and $m$ in order to prevent any of the known algorithms for solving the problem efficiently for being usable?

I don't know a full answer to this question (which is why I asked it!), but here's what I've been able to determine so far…

Most of the known solutions and partial solutions to the quadratic residuosity problem are based on the prime factors of $m$. In particular, quadratic residuosity is efficient to check for prime $m$, and a number is a quadratic residue modulo $m$ if it's a quadratic residue modulo every prime factor of $m$, so one important criterion is that the factorisation of $m$ is not known by an adversary. As mentioned to the comments in the question, finding semiprimes that are hard to factorise is a well-known problem, given their use in RSA.

When it comes to the decision problem version of quadratic residuosity, there's also an important criterion on the value of $r$: an efficient algorithm (based on the Jacobi symbol) exists to know whether $a$ is a quadratic residue modulo an odd or even number of prime factors of $m$. If an adversary either knows or can guess the number of prime factors of $m$ (e.g. they know that $m$ is likely to be a semiprime), then around half the possible values of $r$ will be efficiently determinable as quadratic non-residues of $m$ (because they need to be a quadratic residue to every prime factor of $m$, and yet the number of prime factors of $m$ that they are quadratic residues to has a different parity). The conclusion is that $r$ must be chosen to be a quadratic non-residue to an even number of prime factors of $m$ (e.g. if $m$ is a semiprime $pq$, then $r$ must be a quadratic residue to either both of $p$ and $q$, or else neither).

$4n+1$ primes and $4n+3$ primes generally interact with quadratic residuosity problems in different ways, so it's possible that there's a security difference between the two different types of prime. (For example, it is of course easy to intentionally generate a quadratic residue $r$ for every prime factor of any given $m$, even without knowing its factorisation, simply by squaring a random $a$; when using the product of two $4n+3$ primes, it's also easy to intentionally generate a quadratic non-residue for every prime factor.) For Blum Blum Shub, a CSPRNG based on the quadratic residuosity problem, there's a requirement to use the product of two $4n+3$ primes as $m$ (and also to keep $\textrm{gcd}(p-1,q-1)$ small). These requirements appear to be specific to the algorithm in question, in order to ensure that the CSPRNG's period is large, and thus might not be required for the problem more generally; however, more effort has likely been put into breaking the quadratic residuosity problem in this case than in cases with no cryptographic applications, so it may make sense to use such values to benefit from the additional scrutiny they may have been given.

It's also, of course, important to avoid trivial cases, e.g. you wouldn't want to pick $r=0$. One highly important case to avoid seems to be $\textrm{gcd}(r,m)\neq 1$ (both because it makes quadratic residuosity easier to directly calculate, and for the more obvious reason that it reveals a factor of $m$). Apart from that, a random $r$ (that's been verified to have the correct Jacobi symbol, i.e. to be a quadratic non-residue of an even number of factors of $m$) will come up at a random point in a brute-force search for quadratic residuosity, so is likely to be secure.

It's probably worth avoiding the smallest values of $a$ because it's possible to, e.g., efficiently search all the values $0\leq a<\sqrt{m}$ in a single calculation, thus the gain from discarding small $a$ is probably larger than the loss from giving a brute-forcing adversary a smaller search space (even if the adversary knows how many values have been discarded, and thus can start their search higher); however, this is something I'm not sure on, and the optimal number of values of $a$ to discard is unclear. Similarly, it may be worth avoiding values $r$ for which $-r=a^2$ for small $a$ (because the quadratic residuosities of $r$ and $-r$ are related).


Are modes of operation algorithms practical? I took a cryptography class back in college, and now that I am working my 1st career one of the things currently on my plate is coming up with an algorithm to encrypt data before it's placed on the server (In this case it's pretty sensitive info). I remember different modes of operation from that class like cipher block chaining and things of the like. I know that some of them are pretty hard to crack, but since they are so commonly known is it even practical to consider using something like that as an encryption method considering the algorithms for encryption and decryption are commonly known (from a security perspective)?

I know that some of them are pretty hard to crack, but since they are so commonly known is it even practical to consider using something like that as an encryption method considering the algorithms for encryption and decryption are commonly known (from a security perspective)?

In fact, this is exactly what we want.

Schneier's law

  Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break.

That is why it is crucial that the algorithms be made public. If the only information I keep secret from you is a relatively short key (128-bits isn't much), and you still cannot break the cipher, then one could argue that the cipher is stronger than one where you have to keep a few megabytes (the source code) protected.


Adversary Two Stages I am read this paragraph and I have a doubt.

  "An adversary to PKC $\Pi$ is given by two probabilistic polynomial
  time algorithms, $A = (A1; A2)$. In the first stage, the "find"
  stage, the adversary analyzes the public key and tries to determine
  which plaintexts, when encrypted, are vulnerable to attack. This is
  the job of $A1$. In the second stage, the "guess" stage, the adversary
  $(A2)$ will be presented with a challenge ciphertext $y$, an
  encryption of one of the plaintexts he found in stage 1."

What is the "new" in use the challenge ciphertext $y$ if I know the its plaintext?  How I will be able to make attack?

It's hard to be sure without seeing a bit more context, but the paragraph you quoted looks like it's part of a definition of IND-CPA security (ciphertext indistinguishability under a chosen-plaintext attack) for public-key ciphers.
Here's the corresponding definition from the Wikipedia article I linked to above:

"For a probabilistic asymmetric key encryption algorithm, indistinguishability under chosen plaintext attack (IND-CPA) is defined by the following game between an adversary and a challenger. For schemes based on computational security, the adversary is modeled by a probabilistic polynomial time Turing machine, meaning that it must complete the game and output a guess within a polynomial number of time steps. In this definition $E(PK, M)$ represents the encryption of a message $M$ under the key $PK$:

The challenger generates a key pair $PK, SK$ based on some security parameter $k$ (e.g., a key size in bits), and publishes $PK$ to the adversary. The challenger retains $SK$.
The adversary may perform a polynomially bounded number of encryptions or other operations.
Eventually, the adversary submits two distinct chosen plaintexts $M_0, M_1$ to the challenger.
The challenger selects a bit $b \in \{0, 1\}$ uniformly at random, and sends the challenge ciphertext $C = E(PK, M_b)$ back to the adversary.
The adversary is free to perform any number of additional computations or encryptions. Finally, it outputs a guess for the value of $b$.

A cryptosystem is indistinguishable under chosen plaintext attack if every probabilistic polynomial time adversary has only a negligible "advantage" over random guessing. An adversary is said to have a negligible "advantage" if it wins the above game with probability $\tfrac12 + \epsilon(k)$, where $\epsilon(k)$ is a negligible function in the security parameter $k$, that is for every (nonzero) polynomial function $\mathrm{poly}()$ there exists $k_0$ such that $|\epsilon(k)| < \left|\tfrac{1}{\mathrm{poly}(k)}\right|$ for all $k > k_0$."

Unlike the definition you quoted, the Wikipedia version doesn't explicitly represent the adversary as two polynomial-time algorithms $A1$ and $A2$, but it does note that the total computational time used by the adversary must be polynomial, which amounts to the same thing.
What the Wikipedia version does note explicitly, however, is that the adversary is supposed to choose (at least) two potentially vulnerable plaintexts, of which the challenger then encrypts one and sends it back to the adversary, who then tries to guess which of the plaintexts it corresponds to.  The Wikipedia article also notes that the reason this isn't trivial is because the same plaintext can encrypt to many different ciphertexts:

"Although the adversary knows $M_0, M_1$ and $PK$, the probabilistic nature of $E$ means that the encryption of $M_b$ will be only one of many valid ciphertexts, and therefore encrypting $M_0, M_1$ and comparing the resulting ciphertexts with the challenge ciphertext does not afford any non-negligible advantage to the adversary."


Just a super basic question - Does the key create the algorithm? I don't understand how the key gives you the algorithm, in other words I am having trouble understanding how the key works in symmetric encryption. My book says:

  "Symmetric encryption transforms plaintext into ciphertext using a secret key and an encryption algorithm"

So what does the secret key do, is it like  a password to give you access to the actual encryption? Also my book says:

  "Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key"

It says "generated with the secret key", so the key creates the algorithm?

The key does not create the algorithm.

The algorithm is a fixed, publicly known set of steps. Clearly, a fixed, publicly known set of steps is not capable of encrypting anything.

So we include some secret information into the steps in the form of a key. A key for a symmetric encryption algorithm is a random sequence of bits that is kept secret. The knowledge of this secret random sequence of bits is what enables one to perform the encryption/decryption steps - and what prevents anyone else from doing the same.

For example, the AES algorithm uses the following steps:

Add key
Add constant
Mix Columns
Substitute bytes

The Add key step is the same instruction for everyone who uses the algorithm, but the data that the instruction operates on is different for everyone because of the key.

This may be the source of the confusion. There are two things going on in an encryption algorithm:

The instructions, or steps that are applied
The data, which are the bits of information that the instructions operate upon

The instructions (the algorithm) are fixed and publicly known. The key is data, and it provides the source of secrecy that enables one to compute the encryption/decryption operation. The plaintext and ciphertext are also data, which are operated upon by the instructions in conjunction with the key.


Is this password-cracking challenge possible? Taking a graduate computer security class, part of our current assignment is to crack 50 Unix md5crypt password hashes, due on Thursday, October 8th (in eight days.) I've managed to crack 49 out of the 50 passwords using hashcat, but the last password seems borderline impossible within the time given to us.
The hash for this password is $1$gT$qN6H47wSbSr4TaWFkuo/c.
The restraints on this password (given through hints from the professor) are as follows:

The plaintext is 8 characters long
The first character and last two characters are lowercase
There are two numeric characters, and the rest of the password consists of only uppercase and lowercase letters (no symbols).

The best approach I could come up with was using a mask attack with the mask ?l?2?2?2?2?2?l?l, where ?2 = ?l?u?d, but this would take a maximum of 20 days on my single desktop machine, far too long to be able to complete the assignment.
I could potentially try to assume that characters 1-5 (inclusive) are not lowercase, which allows us to use the same mask with ?2 = ?u?d, which cuts the max crack time to 1 day 13 hours. Certainly within the realm of possibility, but that's only in the case that my assumption is correct.
To be clear, this last password apparently isn't required for full credit, but at this point, I'm just curious to see how it could be cracked as fast as possible.
Is this crack possible within the remaining 8 days we're given, or is our professor setting us up to fail without giving us any further hints? Are there any other novel approaches I could take to crack this password faster?

Coming back to answer this since I see someone is wondering if I was able to do it.
The professor, seemingly realizing that this assignment wasn't possible in the time given, gave another hint that made this doable.

The plaintext is 8 characters long
The first character and last two characters are lowercase
There are two digits, and the rest of the password consists of only uppercase and lowercase letters (no symbols).
The second character is a digit

Using these criteria, there are only 12 possible arrangements for the remaining characters (characters three, four, five, and six, which contain a digit, two uppercase letters, and a lowercase letter.)
I made a list of the following masks in an .hcmask file, ran it through hashcat, and the crack now only took roughly eight hours.
?l?d?d?l?u?u?l?l
?l?d?d?u?l?u?l?l
?l?d?d?u?u?l?l?l

?l?d?l?d?u?u?l?l
?l?d?u?d?l?u?l?l
?l?d?u?d?u?l?l?l

?l?d?l?u?d?u?l?l
?l?d?u?l?d?u?l?l
?l?d?u?u?d?l?l?l

?l?d?l?u?u?d?l?l
?l?d?u?l?u?d?l?l
?l?d?u?u?l?d?l?l

The password ended up being cracked successfully: e3IDq9wv


Simple xor cipher extension Probably the simplest cipher is the xor cipher with a single integer. One can extend this to use more than one integer by several means. I'm wondering if there is any benefit to doing more than this:

Let $x_n$ be the $n$th data byte to encrypt and $p_k$ be the data stream (password or whatever) to encrypt with and $p_k$ is cylical.

Then the "standard" way of doing the encryption is

$$\large y_n = x_n \small\oplus\large\; p_k$$

But for certain functions $f,g,h$

$$\large y_n = x_{h(n)} \small\oplus\large\; f(p_{g(k,n)},n)$$

is invertible.

My question is:

  Without knowing what formula and functions are used, would such a method make it much more difficult to "crack" an encryption? (Basically is there any real benefit to using a more complex formula. Ofcourse, if anyone has any theoretical insight in how these modifications "enhance" the encryption then by all means ;) My guess is that it is too difficult, mathematically, to understand in general. For example, if invertibility exists and f,g, and h have certain properties, do we end up with a more secure encryption than the standard xor cipher(which is easily attacked using frequency analysis)?)

Assume $f,g$ and $h$ are the best possible functions in whatever way is needed.

What I have noticed is that such complex formula seem to increase the "randomness" of the output over the standard method.

It would seem that if $f,g$ and $h$ are completely known to the cracker then it is equivalent to simply using a different $p_k$ and $x_n$ and equivalent to the standard method.

If the keystream $p$ is as long as the plaintext $x$ (and is not reused), then $y_n := x_n \oplus p_n$ is a one-time pad, which is theoretically unbreakable, and thus needs no further strengthening.

On the other hand, if $p$ is shorter than $x$, then what you have is basically equivalent to a Vigenère cipher, which is known to be quite weak.  Thus, any additional obfuscation may well improve it, although it's still unlikely to produce a truly secure cipher.

It should be noted that your construction is almost general enough to encompass arbitrary synchronous stream ciphers, which are of the form $y_n := x_n \oplus f(p, n)$.  The only difference is that stream ciphers are generally designed (with good reason) so that each byte (or bit) of the output of $f$ depends essentially on the entire key $p$.


Does knowing multiple hash of the same content make it more likely to generate original plain text? Say I'm trying to brute force the original plain text of an SHA256 hash, does knowing the RIPEMD160 hash of the same text help? In other words, does providing access to hash values of the same text generated by multiple algorithms decrease security?

No, there is no security decrease in this case. While there could be some hypothetical constructions that might leak the preimage if two images are known, this is definitely not the case for existing hash functions, which are all quite different from each other.

An example of such a weak pair of hash functions could be two versions of MD5: one with 63 rounds, and another one with 64 rounds. Then the two hashes would reveal partial information about the preimage.


Security issues with computing parallel hashes? One issue with most hash algorithms like SHA-256 is that it is inherently serial.  You can't effectively use SIMD to parallelize a single SHA-256 calculation.

However, you can calculate multiple SHA-256 hashes in parallel efficiently, because you can keep each algorithm in a lane of the SIMD registers.

Take SSE as an example: each register has four 32-bit lanes.  Computing SHA-256 four times in parallel makes sense.  We can define a new hash algorithm for computing the hash of a single file as slicing the input into four pieces, computing the hash of each of the four pieces (in parallel), then produce the final result by hashing the final four sub-hashes together.  Obviously, this would be a new hash function, not matching a normal SHA-256.

Are there security problems with such a design that wouldn't exist with a normal hash algorithm?

Are there security problems with such a design that wouldn't exist with a normal hash algorithm?

At least not for collision resistance.

Suppose you could come up with a collision for the composite construction $H_p$ based on the hash function $H$. Then you'd have two inputs $x\neq x'$ such that $H_p(x)=H_p(x')$. Then either there is a collision on the final hash invocation and we can reconstruct the relevant inputs following the description of $H_p$. Alternatively all the inputs to the final invocation are equal between $x,x'$ and then the slices that differ produced a collision in $H$ which we can reconstruct.

So every collision for $H_p$ implies a collision for $H$, but because we assume $H$ to be collision-resistant there is no efficiently findable collision for $H_p$.


Whitebox AES: why not steal the whole whitebox? If I understand correctly, Whitebox AES is a way of transforming decryption code to make impossible to recover the decryption key, even if you have access to the code.
But what's stopping someone from just separating the entire whitebox decryption function from your program and using it inside their program? They won't have the key, but they'll be able to decrypt any data and use it for whatever they want.

This is answered in the Whitebox AES paper. I've quoted the relevant section, which occurs on the second page:

A natural question is: if an attacker has access to executing decryption soft-ware itself, why worry about preventing secret-key extraction --- the attacker
could simply use the software and platform at hand to decrypt ciphertext or
access plaintext. The answer (see also section 2.2) is that our techniques are
targeted mainly at software-based cryptographic content protection for Internet
media, rather than at more traditional communications security. In such applications, the damage is relatively small if an attacker can make continued use
of an already-compromised platform, but cannot extract keying material allowing software protection goals to be bypassed on other machines, or publish keys
or software sub-components allowing `global cracks' to defeat security measures
across large user-bases of installed software. Our solutions can also be combined
with other software protection approaches, such as node-locking techniques tying
software use to specific hardware devices.

Their argument is essentially that key extraction can allow you to completely break DRM for all users in a way that "stealing the whitebox" would not. I believe famous DRM breaks (say against the PS3) involved key extraction, so their claim may have been justified by history.


The second row of the second table gives you the values of $g^e\pmod{11}$ for $0 \le e \le 10$. Notice that $2^{10}\pmod{11} \equiv 2^{0}\pmod{11}$. This means that $2^{10}$ raised to any power is congruent to $1\pmod{11}$.

With that in mind, it shouldn't be hard to see that $2^{2652557887263}\pmod{11} \equiv 2^3\pmod{11}$. So the answer is $8$.

P.S. I suspect your question may be slightly off-topic for this site, hence the down votes.


X509 certificates: Two Algorithm Identifiers? I'm wondering why there are two Algorithm Identifiers in a X509 certificate. One is in the "to be signed" part and the other one is at the end right before the actual signature.

Are they used for the same purpose? Do they have to be the same? Can implementations choose which of these two fields they evaluate?

I'm assuming you're talking about these two fields:

signature
signatureAlgorithm

following the names defined in RFC 5280 section 4.1. And section 4.1.1.2 then goes on to state (for signatureAlgorithm):

  This field MUST contain the same algorithm identifier as the signature field in the sequence tbsCertificate (Section 4.1.2.3).

So, yes, they have to be the same.


What is the purpose of update() in popular hash APIs? E.g., in Python's hashlib, update() basically merges in string buffer functionality into the object. Several other digest APIs I've seen have this pattern.

Considering this adds functionality that arguably doesn't belong here, why is this pattern popular?

Being able to generate hashes incrementally (by presenting parts of the string being hashed) is there for basically two reasons:

It's commonly useful in practice.  Quite often, we don't have the entire string in one contiguous segment; instead, we often have parts laying around separately.  For one simple example of this, consider the
HMAC
function; the inner hash is some preprocessed keying material, followed by the message being MAC'ed.  We could create a temporary buffer consisting of the HMAC inner key ("ipad") and the message, but why?
It's actually easy to do with our current hash function (including SHA-1, all the SHA-2 versions and SHA-3).  You appear to think that the Python hashlib library copies the parts of the message being hashed into a buffer, and then runs the hash on the entire buffer.  That's extremely unlikely to be how they implement it; instead, it is easy (with a small amount of side memory) to have the hash process the message in pieces.

So, the answer is: they provide this functionality because people find it useful, and its easy for the library to do.


I'm trying to understand which cryptographic algorithm is this I'm reversing a cryptographic algorithm. This is part of the encryption function translated to python (starting from assembly code):

cleartext = [ 0x24,0x11,0x33,0x63,0xbc,0x59,0x07,0x5b,0x96,0x4b,0x07,0x15,0x2d,0x23,0x4b,0x70 ]
clearlen = 16

# Init the dictionary
cdict = [ 0 ] * 256
for i in range(256):
  cdict[i] = i

v1 = 0
# Load the dictionary
for i in range(256):
  v1 += (cleartext[ i % clearlen ] + cdict[i])
  v1 = v1 & 0xFF
  v2 = cdict[v1] ^ cdict[i]
  cdict[i] = v2
  v3 = cdict[v1] ^ v2
  cdict[v1] = v3
  cdict[i] ^= v3

Then this array of 256 bytes is used to extract clearlen bytes which are XORed with a key. I didn't translate it to python yet.

I was trying to understand if this was a known cryptographic algorithm, or it is completely custom. So far I was not able to identify it. Do you?

That would appear to be RC4, which is a well known (if not well trusted) cryptographical algorithm, original designed by Ron Rivest.

The part you quoted is the Key Setup Algorithm, which is run before you actually encrypt/decrypt anything.  The part which is written in an unusual (but correct) way is the last 5 lines, which does a swap of cdict[i] and cdict[v1] - more typically, it is written with just 2 reads and 2 writes and two temp variables in the obvious fashion; for some reason they decided to use some 'clever' logic with xors (and two temp variables, 4 reads, 3 writes).


How can I encrypt more than 128 bits of data with AES? To my understanding a state is a $4 \times 4$ byte array used to store the plaintext. That equates to $128$ bits of data.

To encrypt more than $128$ bits of data do I need to setup multiple of these states in order to encrypt all the data and perform the algorithm on those states? Or is there another method?

No, the state of the AES is the internal state of the block cipher. It is not used to store the plaintext message. After a block encrypt the state of the block cipher isn't required anymore. Generally only the subkeys are kept so they don't have to be recalculated using the key schedule anymore.

AES, being a block cipher, is not a generic / secure cipher in itself. To use it as a cipher you need to use a mode of operation. The mode of operation is independent of the block cipher itself, although it of course does depend on some parameter such as the block size. The best known mode of operation to create confidentiality is probably CBC. However you will get much more security when using an authenticated mode of operation such as GCM mode.

Now the CBC mode and GCM implementations also require state, and this state needs to be kept up to date. For CBC this is at least a block of plaintext as it is impossible to encrypt partial blocks. For GCM it is possible to encrypt partial blocks because it uses counter mode underneath. However, you would still have to store the intermediate results required to calculate the authentication tag (usually stored at the end of the ciphertext) and at least one block for the key stream used to encrypt.

As the input / output of a block cipher is one block, and since there must be some kind of vector to link the blocks into one message, you should expect around two blocks of memory for the state, not including the subkeys. That's not that much and probably insignificant compared to the other memory requirements (in-memory tables) required for a fast software implementation of the cipher itself.


What is PCT_SSL_CIPHER_TYPE_1ST_HALF? I'm writing a tool to do security posture assessments of SSL/TLS services, and ran into an interesting result. I ran through all defined cipher suites to test which could be negotiated (like sslscan does) and found that an unusual PCT-related cipher suite, PCT_SSL_CIPHER_TYPE_1ST_HALF (0x830004) appeared to be accepted by a number of sites.

I'm aware of PCT as a precursor-of-sorts to TLS, alongside early SSL implementations, but I can't find any information as to what PCT_SSL_CIPHER_TYPE_1ST_HALF is, or why modern SSL/TLS stacks would ever negotiate it successfully.

What is this suite? Why can I negotiate it?

As usual, I ask a question after a couple of days of research, then immediately realise the answer: I'm doing it wrong.

My definitions included the following "suites":

SSL2_RC4_128_WITH_MD5   0x010080
SSL2_RC4_128_EXPORT40_WITH_MD5  0x020080
SSL2_RC2_CBC_128_CBC_WITH_MD5   0x030080
SSL2_RC2_CBC_128_CBC_WITH_MD5   0x040080
SSL2_IDEA_128_CBC_WITH_MD5  0x050080
SSL2_DES_64_CBC_WITH_MD5    0x060040
SSL2_DES_192_EDE3_CBC_WITH_MD5  0x0700C0
SSL2_RC4_64_WITH_MD5    0x080080
CT_SSL_CERT_TYPE    0x800001
PCT_SSL_CERT_TYPE   0x800003
PCT_SSL_HASH_TYPE   0x810001
PCT_SSL_HASH_TYPE   0x810003
PCT_SSL_EXCH_TYPE   0x820001
PCT_SSL_CIPHER_TYPE_1ST_HALF    0x830004
PCT_SSL_CIPHER_TYPE_2ND_HALF_40     0x842840
PCT_SSL_CIPHER_TYPE_2ND_HALF_128    0x848040
PCT_SSL_COMPAT  0x8F8001

TLS has a cipher suite specifier length of 16 bits. My code, when given these 24-bit identifiers, ignores the high 8 bits. This means I'm really scanning for 0x0080 a few times, 0x0040, 0x00C0, 0x0001, 0x0003, 0x0004 (*), 0x2840, 0x8040, and 0x8001.

Since 0x0004 is RSA_WITH_RC4_128_MD5, and the target server supports that suite, my code was incorrectly reporting that PCT_SSL_CIPHER_TYPE_1ST_HALF was enabled. It just happened to coincide. Other values did not align with enabled cipher suites, so that's the only one that cropped up.

I've now removed these definitions since they're erroneous for SSL/TLS.

Silly me!


With RSA or ECC, if I encrypt my private key with my public key, is there a way to recover my private key? Is there an algorithmic, mathematical, technical or implementation "hack" to recover the private key or is it definitively encrypted without any particular mathematical property, like any message M?

Although there is an answer here saying "no" for usual definitions, I want to strongly warn that there is no rigorous basis for that. Specifically, it is true that there is no known way of recovering a private key from an encryption of it with its associated public key. However, there is also no proof whatsoever that it isn't possible. Security of this kind is called "circular security" and there has been researching understanding it. In general, it is possible to achieve this in the random oracle model (quite easily - since the random oracle breaks the mathematical connection between the keys). Specifically, the encryption ${\sf enc}'_{pk}(m) = ({\sf enc}_{pk}(r), H(r) \oplus m)$ is circular secure when $H$ is modelled as a random oracle (meaning that it's secure when taking $m=sk$ or the like), as shown by Camenisch-Lysyanskaya in their EUROCRYPT 2001 paper titled An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation. However, in general, there are no reductions from the security of the encryption scheme in general to the case of encrypting the private key, and one should be careful.


How to forge Schnorr signatures if you can guess the challenge Underlying the Schnorr signature is an identification protocol:  let $G$ be a cyclic group where discrete log is "hard" and choose $g$ as a generator of $G$.  Now have Alice pick a random (secret) exponent $s$ and publish $v=g^s$.

To identify herself to Bob, it goes like this:

Alice chooses a random exponent $r$ and sends $g^r$ (commits $r$)
Bob sends random exponent $e$ (challenge $e$)
Alice sends $r + se$
Bob makes sure $g^r = g^{r + se}v^{-e}$

That's all well and good, but what if a cheating prover can guess $e$?  Then how does he fool Bob?

In the other answers, you'll find how to simulate a proof if you know $e$. This answer is meant to provide some "color commentary" on the other answers. It is a companion piece.

Notation

In step 1, Alice sends $g^r$. Call this value $a=g^r$.
In step 3, Alice sends $r+se$. Call this value $b=r+se$.
In step 1-3, one value is sent in each step: {$a,e,b$}. We'll call these three values a transcript for public key $v$.
In step 4, with the new notation, Bob checks: $a=g^bv^{-e}$.

Basic question

With this notation, it may be easier to see how knowing $e$ can help. Generate a random $b$ and then compute $a$ so that the equation holds and {$a,e,b$} will accept.

Another thing to note

Other answers noted that since you choose $a$ directly, you do not really know an $r$ such that $a=g^r$ (by the discrete log problem). This is one thing that distinguishes a true proof from a simulated one.

A second thing to note, which is very important, is that to simulate a proof, you start by computing (choosing) $b$ and then you compute $a$ using $b$ and $e$. In a real execution, you compute everything in order.

The only way to forge?

The other answers have shown a way to simulate the proof. Is it the only way?

For example, is it possible to choose an $a$ value knowing $e$ and then compute the right $b$ to make {$a,e,b$} accept (short of knowing $s$)? The answer is no.

Pretend you have a black box that could do this: it takes {$a,e$} as input and returns the proper $b$ without knowing $s$. If such as box existed, you could query {$a,e_1$) and get $b_1$, and then query {$a,e_2$} with the same $a$ and different $e$, and get $b_2$. However one can verify that this is sufficient to compute $s$: in fact, $s=\frac{b_1-b_2}{e_1-e_2}$.  So there is a contradiction: the box doesn't know $s$ by definition and yet it does "know" $s$ (in the sense that it can compute it). Therefore, by contradiction, such a box cannot exist, and neither can a forgery {$a,e,b$} where $a$ and $e$ are chosen.

Enforcing only true transcripts

If we put all of the above together, it basically says that if {$a,e,b$} accepts, it must have either been computed by someone who truly knows $s$, or it was computed backward by choosing/knowing $b$ and $e$ before computing $a$.

Can we eliminate the second case? One way is to be Bob. Another might be to be there in person to see that $a$ is sent before $e$: however do you really know that Alice doesn't know $e$? Can you really be sure?

The answer is yes.

If you can ensure $a$ is computed before $e$, then we are done. A simple technique (called Fiat-Shamir) is to set $e=\mathcal{H}(a)$, where $\mathcal{H}$ is a hash function (technically a random oracle). If you choose/know $e$ first, you cannot find an $a$ that will hash to it (by preimage-resistance).


Deriving user keys from ID The "normal idea" is to generate a key per user, send them to the users (securely, of course), and store them in a database.

But what if I use a keyed hash (like Blake2b) with a server key and then hash the user ID to generate the user key to avoid the need to hold a database of randomly generated keys? Is it secure? If not, why and how can you attack it?

But what if I use a keyed hash (like Blake2b) with a server key and
  then hash the user ID to generate the user key to avoid the need to
  hold a database of randomly generated keys?

Let's make some assumptions: the user IDs are unique and Blake2b with a keyed input acts like a PRF and you supply a long-enough key, all of which are reasonable. Then for any given (userID,hash) pair you can't learn anything about the other pairs (if you're computationally bounded).

There are a couple of potential issues with this though:

The user can't choose their credentials themselves, users may dislike this.
It is potentially easier to exfiltrate a short secret than a large amount of data (like in a database).
You must ensure that the userID is always given in the exact same encoding to the hash function.
If the credential gets compromised on the user end, the user also has to change the userID or you have to change the master key
Key roll-over gets harder as every client needs to log-in to receive their updated access token

There's an upside to this sort of scheme though: If you want to, you can put the secret inside a HSM and use HMAC-SHA256 instead of Blake2b and mitigate the key exfiltration risk


What is considered a "weak key" in AES? I need to construct an AES key from an array of bytes (in Java), but I first I have to check if the key created from these bytes would be weak.

Java can check for weakness for DES, but not for AES. What are the criteria for an AES key to be considered weak?

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

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


AES S-Box: How is value for 01 mapped to 7c? If irreducible polynomial $m(x) = x^8+x^4+x^3+x+1$ is chosen, or even for any other value, the multiplicative inverse will not exist for $01$, as $0000 0001$ will perfectly divide $m(x) = 100011011$ leaving remainder zero.

So then how it the value for $01$ mapped to $7c$ in AES S-box?

$00000001$ is its own inverse in the Rijndael field, because polynomial multiplication by itself gets $00000001$ and is unchanged by the modulo operation.  This will always be true in any ring, as noted in a comment above.

However, the specification of the Rijndael S-box is that after taking the inverse of the number in the Galois field, you have to multiply the result by a matrix then add (XOR) a constant: the "affine transformation".  That is what makes 0x01 map to 0x7C.

Note that for the purposes of the Rijndael S-box, zero's inverse in the field is considered to be zero.  The affine transformation is applied to zero, getting the expected 0x63.


Individual bits of Textbook RSA This question relates to the underlying RSA assumption. Forgetting about the fact that Textbook RSA is deterministic, I am curious about the assumed strength of the RSA problem.

Does RSA hide all bits of the message, or are there some bits that can be easily revealed. Concretely,

$$m^e \space \bmod \space N$$

Can any part of $m$ be learned(with significant probability) without learning the secret key, and if so how?

Under the assumption that $m$ is unknown to the adversary, and random in $[0,N-1]$, then to the best of our knowledge, $m^e\bmod N$ does not reveal anything about any bit of $m$ to an adversary unable to factor $N$.

Update: in the above, "bit of $m$" is in the sense of binary digit of $m$ (for some integer $k≥0$, the value of $⌊m/2^k⌋\bmod 2$), not tiny amount of information. Revealing $m^e\bmod N$ does reveal information abut $m$; most notably the adversary knows the Jacobi symbol $\left(\frac m N\right)$ since that's also $\left(\frac{m^e\bmod N}N\right)$; and can test if an $x$ with $0≤x<N$ is $m$, by checking if $x^e\bmod N$ is $m^e\bmod N$.


Elliptic Curve Encryption Ciphertext Size I'd like to know how much bigger is the ciphertext when encrypting a message using ECC encrytpion? ECIES (or ElGamal)

Ok, I sum it up.

In ECIES, which is a hybrid encryption scheme, the ciphertext size is one point of the curve + the size of the encrypted message (size of the message + small overhead of padding for the symmetric cipher) + the tag length of the used MAC. As CodesInChaos pointed out, if you work on a 256 bit curve (giving 128 bit security), then using point compression this will amount to 32 byte (and 64 otherwise) for the elliptic curve point and as he mentioned in addition to the ciphertext and the MAC some little overhead for the format.

A Note on ElGamal (as in the original Question):
ElGamal is not really useful for larger messages and when using ElGamal in the elliptic curve setting hashed ElGamal should be your choice (as you avoid cumbersome mapping of messages to points on the curve). You could also use a hybrid version of ElGamal to achieve a hybrid cryptosystem like ECIES does.

But ECIES is standardized and provides better security (IND-CCA) as the ElGamal versions (only IND-CPA).


Is this OTP scheme safe? I have a message $m_1$ and I want to encrypt it by XORing it with two keys $k_1$ and $k_2$:

$$c_1 = m_1 \oplus k_1 \oplus k_2$$

So far so good.

Now I was wondering if I could create a "fake" result with a different message $m_2$:

$$c_2 = m_2 \oplus k_1 \oplus k_2$$

This way, if I'm forced to hand over $c_1$, I can give $c_2$ instead and $m_2$ will be reconstructed (instead of $m_1$). I know OTP keys shouldn't be reused, so maybe this can't be called OTP (or can it?).

So the question is: Is this safe? Can $m_1$ be reconstructed from anything different than $k_1$, $k_2$, and $c_1$? Eg: $c_2$, $c_1$, and $k_2$. Don't consider $m_1$ and $m_2$ as options since they are gone after the encryption, they aren't stored anywhere.

Note 1: The messages and keys have a fixed length, about 150 characters, which isn't a lot. This doesn't give enough material for cryptanalysis, right?

Note 2: Each key is going to be given to a different party; that's why I don't combine $k_1$ and $k_2$ into a single key.

If you have $c_2$ and $m_2$ you can reconstruct the used key by

$$k' = m_2 \oplus c_2$$

Now I have the key to decrypt $c_1$.

Also know that using multiple keys for OTP does not increase the security as the resulting key is

$$k'' = k_2 \oplus k_3$$


Why aren't 4096-bit RSA PGP key blocks $\lceil\frac{4096}{6}\rceil=683$ base64 characters long? If a 4096-bit RSA PGP key is considered sufficiently long for most purposes, why are so many key blocks around 3000 base64 characters in length? Why aren't $\lceil\frac{4096}{6}\rceil=683$  base64 characters enough?

Base64 uses $64=2^6$ characters, and hence can encode at most 6 bits per character.  Hence, the correct calculation would be at least $\frac{4096}{6} = 682 \frac{2}{3} $ characters (or 683, we really can't have fractional characters)

As far as why PGP keys are longer than that, well, that's because they're carrying around a lot more information than just the raw RSA key.


Does this algorithm have a name? (Distance between letters) This came to mind the other day and I'm wanting to know if there is a name for the following algorithm (I'm not sure if "cipher" is the right word for it):

Take two consecutive letters at a time (not just one).
Perform the A1Z26 cipher on each letter to get their position in the alphabet as numbers.
Take the difference between those numbers obtained in the previous step.
Convert the difference back into a letter through A1Z26 in reverse. If the difference is positive, use a capital letter. If the difference is negative, use a lowercase letter. If you encounter two of the same letter in a row (difference is 0), convert them to the letter Z, since there is no "0th" letter of the alphabet, and Z would otherwise go unused since we're taking differences (the maximum difference possible would be Z - A -> 26 - 1 = 25 -> Y). Z is always capitalized.
Repeat until you reach the last letter, in which case you "wrap" back around from the last letter to the first.

"Hello world", for example, becomes "CgZcG HcFHs"

H, e -> 8 - 5 = 3 -> C
e, l -> 5 - 12 = -7 -> g
l, l -> 12 - 12 = 0 -> Z
l, o -> 12 - 15 = -3 -> c
o, H -> 15 - 8 = 7 -> G
w, o -> 23 - 15 = 8 -> H
o, r -> 15 - 18 = -3 -> c
r, l -> 18 - 12 = 6 -> F
l, d -> 12 - 4 = 8 -> H
d, W -> 4 - 23 = -19 -> s

Is there a name for this method, or a similar algorithm? What are other examples of algorithms working on not the individual letters themselves, but mathematical operations between 2+ letters?

This answer is expanding on @mentallurg's comment.
One of the important properties of a cipher is that you can decrypt. More precisely that there is an algorithm that takes in the cipher text and the private key and produces the correct plaintext. (Your scheme does not have a key, which is a separate problem with calling it a cipher).
So let's take your ciphertext "CgZcG HcFHs" and try decrypting it.
C = 3
g = -7
Z = 0
c = -3
G = 7

H = 8
c = -3
F = 6
H = 8
s = -19

So I know the distance between the fist and second letter is 3, but I don't know what the first letter actually is. If I knew the first letter then the rest would be uniquely determined. If your alphabet is [a-zA-Z] then there are 52 different plaintexts that would have produced this ciphertext, and the decryption algorithm has no way to know which of the 52 was the intended plaintext.


Why, or when, to use an Initialization Vector? i'm trying to figure out when an Intialization Vector (IV) should be used.

There are anecdotal reports that WEP was broken because of weak IV's. It's also claimed that if two pieces of plaintext are encrypted with the same Key+IV, then it's trivial to recover the plaintext.

To test this, i've encrypted two pieces of equal length plaintext using the same IV and Key. i am using AES, which has a 128-bit block size (16 bytes), so i will make my sample plaintexts less than 16 bytes.

Ciphertext1: ba 81 1b c3 d1 6b ee bd 0a 87 23 33 04 90 5d 8a
Ciphertext2: b0 80 01 ed e8 2c 6c 60 17 b7 5d 60 37 9a e8 3d

Now the theory is that C1 ⊻ C2 = P1 ⊻ P2:

So i calculate Ciphertext1 xor Ciphertext2:

Ciphertext1: ba 81 1b c3 d1 6b ee bd 0a 87 23 33 04 90 5d 8a
Ciphertext2: b0 80 01 ed e8 2c 6c 60 17 b7 5d 60 37 9a e8 3d
XOR:         0A 01 1A 2E 39 47 82 DD 1D 30 7E 53 33 0A B5 B7

Now, for comparison, the XOR of the two (15 byte) plaintexts together is:

Plaintext  XOR: 03 0C 1E 1F 1B 49 4E 57 28 07 15 01 53 17 18
Ciphertext XOR: AE 2C 0B F7 19 39 FA D6 0B 16 F4 59 1D EA D5 67

Which are not the same.

What causes an encryption algorithm to be weak if a specific key is used?

Pseudo sample code, using WinCrypt API:

hProvider = CryptAcquireContext(null, null, PROV_RSA_AES, CRYPT_VERIFYCONTEXT);
hKey = CryptImportKey(hProvider, keyData, sizeof(keyData), null, 0);

encryptedLength = CryptEncrypt(hKey, null, true, 0, plaintextData, plainLength);

CryptDestroyKey(hKey);
CryptReleaseContext(hProvider, 0);

In other words, in the words of MSDN:

  If keys are generated for symmetric block ciphers, the key, by default, is set up in cipher block chaining (CBC) mode with an initialization vector of zero.

i am using an IV of all zeros, in CBC mode. Edit: But since there is only one block being encrypted, there is no "chaining" to be had; so the result is the came as Electronic Cookbook (ECB).

AES (as any block cipher) strifes to be indistinguishable from a random permutation, so any property like $C_1 \oplus C_2 = P_1 \oplus P_2$ would be quite bad.

This property (with $K$ as the "key stream bits") is valid for synchronous stream ciphers, including the one time pad and stream cipher modes of block ciphers (CTR, OFB, and for the first block also CFB), but not for those modes of operation who actually put the plaintext through the cipher, like CBC.

This is why you should never reuse the same key with the same initialization vector for stream ciphers (or reuse the same key at all for stream ciphers which don't have an initialization vector).

For CBC, the effect of such a misuse is just that identical plaintexts (or actually identical starting plaintext blocks) give identical ciphertexts (identical starting ciphertext blocks). This is still something one doesn't want, so you should use a fresh random IV for each message even for CBC mode.

If you can't do this, encrypting a random block before the real data has the same effect.

But we have a similar property if we take the initialization vector into account.

CBC mode works (for the first block) like this:

$$C = Enc_k(IV \oplus P)$$

So, if we don't fix the initialization vector, but chose it according to the plain text (or chose the plain text according to the IV), we can get two $(IV, P)$ pairs which will give the same ciphertext.

Or the other way around:
If we have two Pairs $(IV, P)$ and $(IV', P')$ such that $C = C'$, then we know that $IV \oplus P = IV' \oplus P'$. Written differently, $IV \oplus IV' = P \oplus P'$ and also $P = IV \oplus IV' \oplus P'$ (assuming $P$ was the original, unknown plaintext, and $(IV', P')$ were a later, crafted pair).

This is the basis of the BEAST chosen plaintext attack against CBC, when the next initialization vector is known before the attacker choses his plaintext block. (Note that this attack can be extended to all blocks, not just the first one.)

So make sure you create your random IV only after you did get (at least the first block of) the actual message to encrypt, if you are implementing an online encryption protocol like TLS. (With a random IV, the chance that the XOR with any plaintext block is the same as something encrypted before is neglible.)

The "one block CBC with zero initialization vector" version is the same as ECB, and has the same problems: identical plaintexts give identical ciphertexts. Normally you don't want this, as it is not semantically secure.


SRP with random, but constant private-value b In RFC5054, the SRP6a algorithm states that the client and the server should generate random ephemeral private values $a$ and $b$ respectively which are used for further derivation in the handshake and in the generation of the shared-key. For a persistent TLS connection, it obviously makes sense to generate a new random $b$ value each time a client connects.

Edited for clarity: However, I would like to use SRP in a stateless authentication handshake over multiple HTTP requests. The first request would be the client sending its $I$ to the server, and it would receive ($N$, $g$, $s$, $B$) in return. The client would the calculate $A$ and make another request to confirm its identity. Since the second request may hit a different server, this implies that the private $b$ would have to be shared across all servers. The simple solution is a constant value shared by all servers.

Aside from replayability, does choosing a random but constant $b$ value across all servers have any other security implications? Should I definitely not do this? Would silly tricks, like a varying time-windowed values derived from a constant $b$ be a better choice?

My instinct tells me this is roughly fine, in the same way that we use random-but-constant secrets to secure, e.g. session cookies, but I want to understand the implications.

To be clear, I'm only using this for authentication purposes so that the server never sees the user's password, and depending on TLS for forward secrecy of subsequent communications. I realize I could also, for example, bcrypt the user's password before sending it to the server to achieve similar goals, but thought it might be better to use a degraded version SRP instead.

If you use a $g^b$ value between sessions, you allow an attacker to test multiple passwords for the second session; this invalidates the security goal for SRP.

Here is how the attack looks like:

For the first session, the attacker logs in using a password he does know.  The server sends the value $B = kv + g^b$; the attacker knows $k$ (that's derived from common data), he knows $v$ (that's derived from the password he knows), and so can recover $g^b$

For the second session, the attacker listens into a login that uses a password he does not know.  Again, the server sends the value $B = k'v' + g^b$ (where $k', v'$ are different values for this session), as he now knows $g^b$ (and can derive $k'$, he can recover $v'$; he can then go through his dictionary, and test the various passwords against $v'$.


Why is the P-521 elliptic curve not in Suite B if AES-256 is? In the NSA's document, "The Case for Elliptic Curve Cryptography" (archived), we have

+---------------+-------------------------+-----------------+
| Symmetric Key | RSA and Diffie-Hellman  | Elliptic Curve  |
| Size (bits)   |      Key Size (bits)    | Key Size (bits) |
+---------------+-------------------------+-----------------+
|       80      |            1024         |       160       |
|      112      |            2048         |       224       |
|      128      |            3072         |       256       |
|      192      |            7680         |       384       |
|      256      |           15360         |       521       |
+---------------+-------------------------+-----------------+
             Table 1: NIST Recommended Key Sizes

In NSA Suite B, we do have AES-256 (for TOP SECRET); however, the ECC is limited to P-384:

  AES with 128-bit keys provides adequate protection for classified information up to the SECRET level. Similarly, ECDH and ECDSA using the 256-bit prime modulus elliptic curve as specified in FIPS PUB 186-3 and SHA-256 provide adequate protection for classified information up to the SECRET level.

  AES with 256-bit keys, Elliptic Curve Public Key Cryptography using the 384-bit prime modulus elliptic curve as specified in FIPS PUB 186-3 and SHA-384 are required to protect classified information at the TOP SECRET level.

Despite P-521 being officially codified in NIST FIPS-186-4, an entropic choke point appears to have been introduced, as if we have a cryptographic "pipeline".

Example: If we're doing ECDH with P-384 keys and then use AES-256 to encrypt, we're effectively passing just 192 bits of keying entropy into the AES-256 engine.

Reading the only known response (that I know) on this IETF thread, the statement reads

  Regarding NSA's omission of P-521, P-256 and P-384 will satisfy all of the U.S. Government's requirements so only these are included in Suite B. We don't have a requirement that warrants the inclusion of P-521.

I'm unable to put these seemingly contradictory pieces of information together, so I thought I'd ask other people here. Why was P-521 excluded? Was it technical or non-technical? Any additional info would be appreciated.

EDIT:

This is not very directly related, but I checked some empirical testing results. Seems computation times roughly double going from P-256 => P-386 => P-521, for almost any EC operation. Take for example signing a short (1200 bytes) message.

P-256:  8ms ( 64 byte signature)
P-384: 15ms ( 96 byte signature)
P-521: 30ms (132 byte signature)

It's not directly representative of the entropic bottleneck above, more aligned towards the "good enough" line of thought. But then again, AES-192 should have also sufficed...

The real question isn't "Why doesn't Suite B use P-521?" It is, "Why doesn't Suite B use AES-192?" NSA were only interested in 192-bit security for Suite B, but they chose to use AES-256 because AES-192 wasn't widely supported.

  "In fact we had wanted to use AES -128 and AES-192, but a quick survey of AES implementations (hardware centric, I believe) showed that there were very few implemented AES-192, whence the decision to go with AES-128 and AES-256 in Suite B, paired with P256 and P384.   All of the crypt purists grumbled endlessly about the mismatch betwixt AES-256 and P384."

  -- Kevin M. Igoe, NSA

(I am choosing to take his explanation at face value, but you never know with intelligence agencies.)


Constructing private matrix for Algebraic Eraser Having look into Algebraic Eraser key exchange (AEDH) seems the private key matrix may not be random to prevent weak-key results from the key exchange.

From the documentation and articles available it is not really clear for me how to construct the private key matrix. This session paper states:

$M_A = \sum_{i=0}^{N-1} \alpha_i . M_i^0$

however I am unable to find what is meant by $\alpha_i$ and $M_i^0$

For my spare-time projects maybe I will be ok with a random private key matrix $M_A$, but when I'm learning something, lets do it properly.

Thank you in advance.

You copied the equation wrong! I just checked your link.

The matrix $M_0$ is chosen from the set of $n\times n$ invertible matrices over $GF(q)$ (a group under multiplicatin) by some "proprietary" method.

A private key polynomial
$$\sum_{i=0}^{N-1} \alpha_i x^i,$$
over $GF(q)$ is specified and $M_A$ is this polynomial evaluated at the matrix $M_0:$

$$M_A = \sum_{i=0}^{N-1} \alpha_i  M_0^i$$


Uncovering file hidden in .BMP I've recently been linked by someone to this particular puzzle which seems to point to a hidden file within the image. The clue given to me was "anagram" although I could not make much sense of it. Steganography comes to my mind but despite several effort at cracking it, nothing works.

http://securitystartshere.org/downloads/cddc/homework/

How can we generically process to try attack this kind of problem, where we are given an image (especially, an uncompressed one), suspect a primitive form of steganography, and do not know the method (contrary to Kerckhoffs principles, but according to practice as faced by  cryptanalyst, especially in the field of practical steganography)?

Fgrieu has given a few tips such as binary comparison after identifying and proceeding with proper conversion of a clean file to the same format as the encoded file. However I am unsure of the follow-up to this methodology, having extracted the byte difference into a separate file, no common file extension seem to yield any executables.

One of the simplest textbook example of steganography in a bitmapped image (as opposed to formats providing lossy compression such as JPEG), is low-order-bit steganography. In such system, the low-order bits of the pixel components (gray-scale or RVB or CYMK levels, typically stored as a binary number of 8 bits) are modified in some way to hold information; this is hardly visible to the eye (especially on natural images with some degree of noise).

In some systems, the hidden information is the low-order bits of the pixel components. In that case, it is often possible to conclude that the image contains a steganographic message (and get at it, unless it is encrypted before insertion). Detection is based on the fact that in natural images, the low-order bits are correlated with nearby bits (that is, the higher-order bits of the same pixel component, bits of any other color components of that pixel, and bits defining adjacent pixels). The stego replacing the low-order bits removes this correlation, and instead it is seen low-order bits exhibiting the statistical characteristics of those in the payload if uncompressed and unencrypted; or seemingly close to uniformly random and independent otherwise.

But there can be other ways, including XOR-ing the low-order bits of the base image with the hidden information, as in a stream cipher. In that case, we (and the intended receiver) need some information about the low-order bits in the base image. Possibilities include

somewhat get hold of the base image (that would typically apply to the receiver);
exploit some known/guessed/assumed characteristic of the low-order bits in the base image (like their aforementioned correlation with nearby bits).

Worth considering: perhaps few low-order bits are changed; this makes conclusively proving the use of stego much more difficult, but worsens the already large bandwidth requirement.

On the particular problem: we are given MOVIE.BMP (2764854 bytes), a BMP (short for bitmap) file on a web page with a message hinting at stego in the image. Webmasters almost never uses BMP files that large, especially for an image promoting a movie, where JPEG easily saves an other of magnitude on bandwidth usage. All this prompts at steganography on low-order bit, or similar.

The 2764854 bytes consists of a 54-byte header (14-byte BMP header and 40-byte BITMAPINFOHEADER) followed by 1280x720 RVB components of 3 bytes each. There is no extra data (a primitive form of steganography is to append the payload at the end of a file, where rendering programs typically ignore it). The header is unremarkable, except perhaps that the 8 bytes for the horizontal and vertical resolution are zero.

Since the image is promoting a movie, it is worth feeding it to a search engine accepting images, in hope to locate the base image used. We want a visually very similar image, such that when some common program saves it (or a crop/resize thereof) as bitmap, we get something extremely close to the bitmap in MOVIE.BMP. I tried a few of the first hits of two search engines, and two programs: a paint program bundled with Windows, and IrfanView. I used primarily the later, because it is the only of the two I found sometime leaving the horizontal and vertical resolution fields at zero; and also because it can save images into a simple text format (PPM-text) which eases comparison and analysis.

I quickly narrowed down on maxresdefault.jpg (118533 bytes) as remarkably close to the original: after conversion to BMP format using IrfanView, a file compare (with fc /b maxresdefault.bmp MOVIE.BMP) yields only 955 different bytes (list by the OP), and the differences all are in low-order bits. By contrast, the other program yields 88119 different bytes, with differences not limited to the low-order bit (lots of ±1 that change more than the low-order bit, and many ±2; that could be due to minor differences in the JPEG decompression, like using the lower precision arithmetic of SIMD instructions versus the FPU). Some other online images I tried, like IMG_0825.jpg (128356 bytes), yield the exact same 955 differences (ignoring the resolution field); others (including conversions of MOVIE.BMP to JPEG) give overwhelmingly more differences.

I so far conclude that

with good certainty, MOVIE.BMP was prepared from a JPEG image yielding the same pixel data as maxresdefault.jpg does;
the tool used for the JPEG decompression of that file uses algorithms yielding very close to the same result as the algorithms used by IrfanView, hopefully exactly the same;
likely, after the JPEG decompression, at most 955 low-order bits (and hopefully exactly that much) have been altered;
accidental variants in JPEG decompression code seem more likely to yield differences of ±1, then only ⊕1 as observed. That tends to comfort that indeed there is stego involved (but is far from proof).

I tried just a few more things, but basically I'm stuck:

In the (conjectured) base image maxresdefault.bmp, 1323359 out of 2764800 low-order bits are set (47.865%). 439 out of 955 bits flipped in MOVIE.BMP were previously set (46.0%), that's not a significant difference (a Pearson chi-squared test gives a two-tailed p-value 0.24).
I found no pattern in the addresses, pixel coordinates, or RGB planes where the flips occur.


Formal modeling and automated verification of a remote attestation protocol I'm involved in the design of a communication protocol that requires mutual
remote attestation of both communicating parties prior to exchanging any other
data. We found several tools for symbolic security analysis of cryptographic
protocols such as ProVerif, Tamarin or Verifpal.
However, we barely have any experience with formally analyzing crypto protocols.
The manuals of the previously mentioned tools already provide some
examples. Are there any other good sources that concretly explain how to
formalize a secure communication protocol in a machine checkable way? Are there
any other tools that are better suited for this task considering the focus on
remote attestation?

Maybe this is a good starting point:
"Formal Analysis and Implementation of a TPM 2.0-based Direct Anonymous Attestation Scheme", which appeared at ASIACCS 2020:
https://people.inf.ethz.ch/rsasse/pub/eccdaaimp-asiaccs20.pdf
It uses the Tamarin prover, and the Tamarin model files are available for download.


What is the MD5 collision with the smallest input values? I am interested in MD5 collisions for small input messages.

The collision examples given at http://www.mscs.dal.ca/~selinger/md5collision/ show two different strings, where only a tiny amount of data has been changed to give the same md5, but it feels more like just changing values that are not factored into the calculation. I've yet to come across an example where two seemingly random things reach the same value. I did try a small script to find out, but obviously it didn't get anywhere near far enough.

One formalisation of my question would be:

What is the minimal $b\in\mathbb N$  such that there exists $a\in[0,b)$ with $\mathbf{MD5}(a)=\mathbf{MD5}(b)$

To answer your question, we must first state that for an integer $x$, we define MD5($x$) to be the MD5 hash of the encoding of $x$ as a sequence of bits. Indeed, MD5 expects a sequence of bits as input, not an integer. We should choose a conventional encoding; I select big-endian. Thus, integer $44$ encodes as a sequence of 6 bits: 101100. One may note that by doing so, I miss on half of possible MD5 inputs: indeed, when converting an integer to its minimal-length big-endian unsigned encoding, the first bit is always a '1'.

Though the encoding is not important for the discussion below, it impacts the value of $b$ that you are looking for. Indeed, each encoding will yield another $b$.

Since MD5 has a $128$-bit output, it can have (at most) $2^{128}$ distinct outputs. If I take the integers $0$ to $2^{128}$ (inclusive), then I have $2^{128}+1$: it is thus mathematically guaranteed that at least two of them hash to the same value. In other words, it is proven that there exist integer values $a$ and $b$ such that $0 \leq a < b \leq 2^{128}$ and MD5($a$) = MD5($b$).

The actual minimal value of $b$ is not known. However, it is expected that the minimal $b$ is around $2^{64}$. This comes from the so-called birthday problem: if I take at random $n$ value within a set of size $N$, then I will pick one that I already picked previously when $n$ reached $\sqrt{N}$ or so.

To obtain $b$, one would have to, indeed, generate MD5($x$) for all values of $x$, beginning with $0$, until we get a value that we already had. The expected cost for the MD5 is high: $2^{64}$ is within reach of technology, but not of a home computer. On a quad-core x86, one may expect about $2^{26}$ MD5 evaluations per second; with a good GPU, you could reach $2^{33}$ per second (this guy claims a bit more than $2^{36}$, but that's with 8 GPU). You'd still need about 60 years to reach $2^{64}$. Another issue, which may become quite a problem in the long run, is how to detect that you did obtain twice the same hash output: $2^{64}$ 16-byte results will not fit in RAM... In fact, this search problem is likely to be a bigger issue than just computing all the MD5.

(There are nifty collision-search algorithms which need very little RAM, but I am not sure they could be applied to the exact problem you stated, in which you do not look for just a collision, but for the minimal $b$ value.)


Security of the server's private key In some papers,
server generates keys for users as follows:
$$sk_i=msk+H(ID_i)v_i\ (mod \ p)$$
where $msk=$ the secret key of server

$v_i$ is randomly selected from $Z_p$ for i-th user , $p$ is a prime number

$ID_i=$ the identity of i-th user

$sk_i=$ the secret key for i-thuser

$H$ is the hash function

If there is a user who knows more than one secret key, does that key generation scheme prevent to reveal the value of $msk$ from users.

How to prove the security?

I have forgotten paper references. Sorry for that.

Not really worked with these kinds of schemes, but here's my viewpoint.

Write $w_i=H(ID_i)v_i$. The value $H(ID_i)$ is some fixed public value, so we can kind of forget about it. That is, if $v_i$ is uniformly random, then so is $w_i$.

Now the key is generated as $sk_i=msk+w_i\pmod{p}$. Since $w_i$ is uniformly random, this is simply a generalisation of the one-time pad. In other words, $sk_i$ reveals no information whatsoever about $msk$. Therefore however many times you repeat this, the user will still learn nothing about $msk$.


Is using RSA with SHA-1 considered as secure as HMAC-SHA-1? I know SHA-1 hashing is regarded insecure. HMAC-SHA-1 is still regarded secure as this is an encryption process with symmetric key of the hash produced by SHA-1.

So signing using RSA with a key size of 2048 with a SHA-1 hash over the content should be regarded secure just like HMAC-SHA-1, correct?

No, unfortunately your well meant comparison with HMAC fails and RSA with SHA-1 - as defined for PKCS#1 v1.5 padding and PSS - is considered insecure.

The construction of HMAC makes it near invulnerable to attacks on the collision resistance of the underlying hash. That is because it uses the secret key as input to the hash function to create the additional resistance. Any adversary does not have access to that secret key.

However, if the hash is used in a signature, they hashing of the data is commonly performed before the keyed operation is applied. No shared secret is available to allow for the same construction as HMAC and no randomization of the hash is performed. That means that the (lack of) original collision resistance is preserved, and that the signature generation function is therefore vulnerable as well.

As noted in the comments and explained in this answer an additional random input to the data could strengthen the hash and thus signature function significantly, even if that randomization doesn't rely on a shared secret. It would however change the signature API as provided by many RSA functions libraries significantly to add randomization to the hash function as they often directly accept hash values as input.


SHA1 no longer considered secure for SSL Certificates -- what about Cipher Suites? Many browsers and Internet companies have recently claimed that SSL Certificates with a signature algorithm of SHA1 will imminently no longer be considered secure.  Most notably, Google and Google Chrome.

Yet I've read that since the SSL/TLS negotiation and Cipher Suite don't make use of plain SHA1 (or even MD5), and instead use SHA1 within an HMAC; that using a Cipher Suite with SHA1 is still an acceptable security practice.

Is this the case?

While we're on it, is it also the case of using MD5 in a cipher suite?

The main thing that makes HMAC secure in typical use even with MD5 is that it is used with a secret key. That means only preimage attacks are really relevant, since finding a collision is always an online attack if you don't know the key. With known attacks the preimage resistance of both MD5 and SHA-1 is > 100 bits. Additionally, HMAC may be secure even with some insecure hash functions.

However, not all cipher suites just use HMAC for message authentication. Older SSL cipher suites (before SSLv3) use plain hash functions for that. Hash functions are also used in many suites as message digests for public key signatures. Is that secure?

Well, yes. Probably. Again, only preimage attacks should apply to the ways they are used in SSL/TLS. A collision attack would require generating a large number of messages to find a pair with equal hash values. That is only a concern whenever the attacker can both predict the data to be signed and influence some of it. E.g. signatures are used for key exchange, where they are used to sign random keys, which the attacker cannot know much less influence.

Still, attacks only get better. Where using more modern algorithms is possible, you should do that.


Matsui's paper on Linear Cryptanalysis of DES I am trying to derive the best linear approximation for one round DES.

I read the question and answer

Regarding matsui's Paper on Linear Cryptanalysis of DES

several times but still could not figure out the part

"
y_3y_2y_1y_0 can be propagated to bits 7, 18, 24 and 29 of the output of the round function, this time taking into account the effect of the bit permutation P(.)
"

The output of S box #5 is Y[13], Y[14], Y[15] and Y[16] (when counting from right). And after permutation these bits would be Y[26], Y[20], Y[10] and Y[1] respectively. I could not find the desired bit number i.e. F(X,K)_7, F(X,K)_18, ...

Confusion is from notation differences between standard DES notation and Matsui's notation. After reading this: Matsui's Linear attack on DES P box
and make some rearrangements I can find the solution.


What happen if a asymmetric crypto-system deals with only one key Assume there is a crypto algorithm that deals with matrices to encrypt and decrypt. Regardless of the specification of such algorithm, what if the algorithm assumes that two parties can securely agree on a matrix and use it along with its inverse to encrypt and decrypt? What I am trying to understand, is that, such thing plays excatly the same role of asymmetric/public key cryptosystem. However, in this algorithm (unknown), there is only one key to encrypt and decrypt messages and is known to two parties who have never met before (agreed on it through a public channel). I would like to know in point of security, and consideration of public key cryptoo

Thanks in advance

Well, each party would know that the other party uses the same key, because they would probably have the same public key.

Now, if some person I have never met before would use the same key as me, I would go into paranoid panic mode. That person could decrypt all messages that were only meant to be decrypted by me (and of course vice versa).

However, if I only use my public-private key pair for communication with this one person, and nobody else, it would be not that bad, because the messages are no secret for either of us anyway. BUT: you never know if some stranger takes care of his passwords the same way as you do. An attacker could capture the pub keys, see that you both use the same key, and in case the other person is a little sloppy, and the attacker would get hands of the other persons keys, he could not only decrypt messages meant for your partner, but also messages meant only for your eyes.

When it comes to security, it is always good to be as paranoid as possible, if it does not take that much extra effort, and avoiding to use the same key as someone else (as unlikely as this is) is definitely something that is easily avoidable, with quite a big impact. (And while there might be even fancier attacks for scenarios like that, these are the most obvious points, which are enough to say 'don't do that')


How to generate the Keystream from IV+Key in RC4 So I understand that a keystream is generating from a key and is the length of the message you want to send, so that you can properly XOR every bit. But I'm having trouble finding and understanding the algorithm for creating the keystream from the IV and key.

One idea I had is if you have a message of length 100 and key of length 10, then your IV is 90 bits to cover the rest of the message, and then the key string is just the concatination of IV + key.

The length of Key and length of IV bear no relationship with the length of the message.

RC4 is deprecated. The way it was supposed to be used is:

Generate a random IV, wide enough that it will remain unique (e.g. 32 bytes), and emit that as header of the ciphertext since the receiver will need it.
Concatenate Key (limited to 256 minus IV size in bytes) and IV
Initialize the cipher with that (there are 256 steps that cycle on the concatenated Key and IV).
Generate as much output a there is plaintext, and use it as keystream to XOR with plaintext, yielding ciphertext.

But various attacks exist. If for some reason one is locked with that cipher from the past (rather than e.g. ChaCha which is safer, faster, and less RAM-intensive), and nevertheless wants to be secure, it's advisable to at least discard some of the initial keystream (e.g. the first 1024 bytes) in an intermediary step before 4.

And of course if one is locked with a particular protocol, it must be done as in that protocol.

Note: if the key is derived from a passphrase memorized by a user, then it is highly advisable to use some form of stretching for the password-to-key conversion:

The best would be a modern and well parametrized password hash function such as Argon2 or Scrypt.
If not, we can use RC4 itself by using the amount of keystream skipped as the workfactor parameter (e.g. 222 bytes). Also, we need to limit the password length to be sure that there remains room for the IV.

Independently, the character set of the password must be well-defined (e.g. UTF-8).


Why are there so many versions of the TEA block cipher? Why are there so many types of TEA, for example TEA, XTEA, and XXTEA? What are the differences?

The original algorithm is TEA, which is a very lightweight Feistel cipher. However, its extremely simple key schedule has two weaknesses. The first weakness allows what's called a related key attack, which is not an issue if the keys are chosen randomly. The second weakness causes equivalent keys. This means that, for TEA, any given key is equivalent to three other keys. This effectively weakens the keyspace from 2128 to 2126, which is bad, but not terrible. This is not normally a major problem unless the cipher is used in ways it shouldn't, such as for a hash.
XTEA was designed to fix the weaknesses in the original algorithm, in particular by adding a more complex key schedule. However, it was found that XTEA introduces some related key vulnerabilities of its own and did not meet the intended security target. This lead to another revision called XXTEA. However XXTEA is also vulnerable, in particular to a chosen-plaintext attack requiring only 259 queries (although the attack is impractical). The wide-block variation which avoids the usual downsides of a 64-bit block cipher is highly vulnerable as well, negating yet another benefit of XXTEA. In the end, it turns out that TEA itself is still quite secure as a cipher. It remains secure as long as it is used correctly, i.e. as a block cipher with uniform random and unrelated keys.


What is the GnuPG process for going from a passphrase to a symmetric key? Suppose I use GnuPG to symmetrically encrypt a file like so:

gpg --no-options -c --cipher-algo AES256 --no-random-seed-file -o my.out my.file

I then provide a passphrase when prompted.

What steps does the software actually take to get from the passphrase I provide as a user, to the actual 256-bit AES key which is used to secure the data?
What data relating to or derived from the passphrase is stored in the output ciphertext file?
What of the above is guaranteed by the standard, and what is implementation-defined?

GPG implements the OpenPGP standard RFC 4880, so it implements the String-to-Key Specifiers.

  3.7.  String-to-Key (S2K) Specifiers

  String-to-key (S2K) specifiers are used to convert passphrase
  strings    into symmetric-key encryption/decryption keys.  They are
  used in two    places, currently: to encrypt the secret part of
  private keys in the    private keyring, and to convert passphrases to
  encryption keys for    symmetrically encrypted messages.

  3.7.1.  String-to-Key (S2K) Specifier Types

  There are three types of S2K specifiers currently supported, and
  some reserved values:

   ID          S2K Type
   --          --------
   0           Simple S2K
   1           Salted S2K
   2           Reserved value
   3           Iterated and Salted S2K
   100 to 110  Private/Experimental S2K

I wrote my own implementation of OpenPGP a while back, if you dont want to search through the GPG source code. If I remember correctly, while decrypting test data I generated with GPG, I found that by default, GPG uses Iterated and Salted S2K (S2K3).

std::string S2K3::run(std::string pass, unsigned int sym_len){
    // get string to hash
    std::string to_hash = "";
    while (to_hash.size() < coded_count(count)){// coded count is count of bytes, not interations
        to_hash += salt + pass;
    }
    to_hash = to_hash.substr(0, coded_count(count));
    // hash string
    std::string out = "";
    unsigned int context = 0;
    while (out.size() < sym_len){
        out += use_hash(hash, std::string(context++, 0) + to_hash);
    }
    return out.substr(0, sym_len);
}

As for your second and third questions, I don't know. I would hope that no information of the password is stored in the file. I have tried to read the GPG source code, but failed doing so. It is very large and complex.


Is AES-GCM with static key and dynamic salt safe to reuse IV/nonce Problem: want to encrypt messages/objects/files using AES-GCM with the same secret key in a safe way, but want to do it in distributed/stateless way, so the IV of previous encryptions with the same key are not known and as I understand AES-GCM is not so secure with many messages if random IV is used.

Would example of this solution be secure?

For each encryption generate 16 bytes random salt (16-BYTES-RANDOM).
TMP-AES-16-BYTES-KEY = HKDF-EXPAND-SHA1(STATIC-AES-KEY-16-BYTES | 16-BYTES-RANDOM, 16)
Write in message first plain 16 bytes generated random.
Use the TMP-AES-16-BYTES-KEY to authenticate first 16 random bytes and encrypt secret data and add tag using 12 bytes IV all zeros.

To decrypt do the opposite - derive temp key from message random and secret key.

In your description, AES/GCM is always used with a new, fresh key, different from all previous keys. Thus, you are not reusing IV with the same key. In that sense, this should be fine from a security point of view.

However, this seems overly complex and begs the question of: why? The simple way would be to use the static key "as is" and to use a random IV for each message.

GCM is actually defined for all IV sizes up to $2^{64}-1$ bits. When using as IV a controlled monotonic counter such as a message sequence number, a 12-byte IV is recommended, as it guarantees non-reuse. However, when using a random IV, the probability of IV reuse is actually lowest if you use a bit larger IV os 16 bytes or more. When the IV is not exactly 12 bytes in length, the GCM specification mandates a first pass of hashing with its internal, keyed, soft-of-hash function (called GHASH). As an added bonus, internal IV reuse, which would be made quite improbable thanks to the whole 128-bit space, would furthermore be "hidden" from onlookers because GHASH is keyed. Not all implementations of GCM support IV sizes of more than 12 bytes, but then, why would you use poor implementations?

To sum up, while what you suggest does not seem obviously flawed, a simpler and more standard solution exist: just use your key as is, and a random IV. Preferably, boost the IV size to 16 bytes.


Generalized Merkle Signatures, SHA-3 and Sakura Sakura specifies a tree hash mode for e.g. Keccak (SHA-3). Are there any reasons to use the Sakura tree hash mode in a Generalized Merkle Signature Scheme? It seems to me Sakura primarily solves a uniqueness problem with using tree hashes for large data when the depth of the tree is variable.

Trivially, if Sakura mode is not used and the depth $d$ tree-hash of data $M = M_0|M_1|...|M_{n-1}$ is $D$, then the depth $d-1$ tree hash of data $M'$ (where $M'_0 = f(M_0)|f(M_1)$ etc) is also $D$. If Sakura is used, such trivial collisions will be impossible.

This problem doesn't seem to exist in GMSS, considering that the leaf-nodes consist of OTS public keys and not plain text fragments.

In general there is no reason to use tree hash modes for Merkle trees. The reason is that a Merkle tree itself is already some kind of tree hash mode. The important thing about this kind of mode is that it allows to compute the root node given the value of one leaf and one node per tree level.

The possible ambiguity of hashes is not relevant for hash-based signatures as for these the tree height and thereby the number of leaves are predefined.


Which bitwise operations are used in SHA-256? From the wikipedia entry on SHA-256 I'm a bit confused about which operations actually go into the algorithm. From the pseudo code it appears the operations are $\texttt{xor}$, $\texttt{and}$, rotate, shift, and addition. But further down it says that $\texttt{or}$ also goes into the algorithm. This description (p 5-6) makes no mention of $\texttt{or}$.

So, which is it?

The functions used by SHA-2, called $Ch$ and $Maj$ are defined like this in the standard:

$$Ch(x, y, z)  = (x \land y) \oplus (\lnot x \land z)$$
$$Maj(x, y, z)  = (x \land y) \oplus (x \land z) \oplus (y \land z)$$

However, an equivalent way to define them replaces the XOR with OR, as the standard (pdf) states:

  Each of the algorithms include $Ch(x, y, z)$ and $Maj(x, y, z)$ functions; the exclusive-OR operation ($\oplus$) in these functions may be replaced by a bitwise OR operation ($\lor$) and produce identical results.

Of course, any functionally complete set of operators is sufficient to implement the functions, but at least some implementations (e.g. PyPy) do elect to use OR here.


What does “simulator” and “interactive” mean in a cryptographic credential system's definition of security? Definition 1 on Page 7 of “An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation” by Camenisch and Lysyanskaya, uses the term “simulator” in defining the security of a cryptographic credential system, which I'm finding a little confusing.

In particular, the sentence says:

  CSS is secure if there exists a simulator S (ideal-world adversary [defined above as a probabilistic polynomial time machine]) such that the following holds: […]

What does “simulator” in a cryptographic credential system's definition of security?
Also, what does it mean for a probabilistic machine to be "interactive"?

"simulator":

That's a definition of security in a model that is related to but weaker than the universal composability framework (thanks to Yehuda Lindell for making that clear and you can look at the paper in his comment). You could also look up the wiki link and I think there are also several question on this site.

As @Yehuda Lindell mentions in a comment, if you are not familiar with the concept of a "simulator" at all so far it is better to look at definitions of secure (multiparty) computation or the zero-knowledge property of interactive proofs.

"interactive":

Think of two probabilistic polynomial time Turing machines (Turing machine with additional random tape) who have local input and output tapes (as usual), but also additional tapes to write input to the other machine and receive input from it. Both machines after interacting halt with local outputs.

For instance, a machine $A$ may run on local input a secret key and machine $B$ on the respective public key and a message. After interaction $B$ halts with a signature for the message and $A$ with no local output (that would be the signing procedure of a blind signature scheme, which you probably know or are familiar with when studying anonymous credentials).


Measuring cypher strength It fairly simple to measure the strength of a key space, largely it's just the number of possible keys.

But how might I measure other properties, namely, a ciphers reliance to attacks such as:

Frequency analysis
Differential Analysis
Linear cryptanalysis

I was hoping for examples with DES or DES contrasted with something simple like Caesar Cipher.

There is no such thing as the "strength" of the key space, just the size of the key space.

For DES and RSA the key size differs from the encoded size of the key.

DES may also contain parity bits.

For RSA the key size is usually regarded the size of the modulus as the key strength depends on the size of the modulus. But you would also have to encode the exponents and in case of the private key, possibly the CRT parameters as well. Then it is still missing padding and overhead.

Generally we still show the strength after attacks in bits. For instance, the strongest attack requires about $2^{49}$ plaintexts. As a plaintext block is $2^3$ bits, the strength of the cipher - if this attack is possible - is about 52 bits instead of the promised 56 bits. As can be seen, DES is just insecure because of the small key size rather than cryptographic weaknesses. This allows it to be used for Triple DES which may still provide adequate security even nowadays.

The original Caesar cipher just has 25 keys (not counting the 0 key of course). So the key size is 4 to 5 bits. I think we can forgo cryptanalysis here; brute force will be fastest. DES is therefore at least 47 bits stronger than the Caesar cipher.

Key size and certainly key strength can be pretty good estimates of how strong a cipher is. But never forget that these values are just extrapolations from the known attacks. We use them to simplify the world; you'd have to look into the actual attacks possible for more detailed information.

And if you use the ciphers incorrectly, you may never ever get even near the security promised.


How is it possible that $g^q \equiv 1 \pmod p$ for a generator g? The context of this question is coming up with the parameters for the ElGamal encryption scheme.

One of the requirements for the parameters for ElGamal is that we have primes $p$ and $q$ such that $p = q \cdot k + 1$ for some $k$. For simplicity, let $k=2$. We also need a generator $g$ for $p$ such that $g^q \equiv 1 \pmod p$. (Feel free to correct me if I got any of this wrong).

However, according to this Crypto SE answer to “How to test if a number is a primitive root?”, a number $g$ is a generator of $p$ iff $g^{\varphi(p)/j} \not \equiv 1 \pmod p$ for all prime factors $j$ of $\varphi(p)$. Since $\varphi(p) = p-1$ (as $p$ is prime) and $p-1$ has just two prime factors, $2$ and $q$, we have $g^q \not\equiv 1 \pmod p$.

Doesn't this directly contradict the above requirement of ElGamal?

For a real world example, take IKE groups 1 and 2 from RFC 2409. With group 2, we have $p = $ some large prime and $(p-1)/2$ also equals some large prime. They give us the generator $g=2$. This checks out for ElGamal because $2^p \equiv 1 \pmod p$. I've also tested it with my implementation of ElGamal encryption and everything works fine. However, doesn't this contradict the definition for a generator? If I try to find a generator for $p$, the first one I get is $g=11$, because $11^q \not\equiv 1 \pmod p$ and $11^2 \not\equiv 1 \pmod p$. But if I use $g=11$, the encryption fails because, as far as I can tell, $11^q \not\equiv 1 \pmod p$.

You are probably getting confused with the meaning of "generator" here. You are correct that a generator for the entire multiplicative group modulo $p$ cannot satisfy $g^q \equiv 1$ by definition.

However - assuming $k = 2$ here - what you probably read is that $g$ is the generator of the quadratic residues modulo $p$, and this group has order $(p - 1)/2$. A generator $g$ for that group is, obviously, a quadratic residue, meaning it is of the form $g = a^2 \pmod{p}$ for some group element $a$, and therefore must satisfy $g^q \equiv 1 \pmod{p}$, since $g^q = (a^2)^q = a^{2q} = a^{p - 1}$.

Does that clear it up?


Straightforward method for hampering frequency analysis on deterministic encryption I'm brainstorming some different ways of making deterministic encryption more secure. I want to use deterministic encryption to preserve searchability over the keywords in a document set. However, I know that frequency analysis is always a concern when preserving searchability in this way.

The strategy I came up with basically still does deterministic encryption (with SIV mode), except instead of just one IV I use ten different ones.* When I encrypt a keyword I choose a random number modulo ten and use that to index into the array of IVs. I then append the index to the ciphertext so it can be decrypted.

To search, you just encrypt the keyword with all ten possible IVs and make a big OR query with all ten ciphertexts.

I don't know a lot about frequency analysis, so I'm not sure how much (if any) additional security this provides compared to regular deterministic encryption. Anyone have any ideas?

My intuition is that for small document sets with relatively few keywords this does provide nontrivial protection against frequency analysis. But I also think the security might not scale to very large data sets.

*In practice the 'IV' here will be additional input to the first step of SIV.

Such a scheme would have two effects against an attacker trying to analyze the frequency of words and word combinations:

They would need more samples to differentiate between two tokens at the same level of confidence.
For two different tokens with similar frequency they would no longer know that the words differ.

The first means you are making the problem like that of breaking a smaller data set. Larger collections of ciphertext are still breakable. You could correct for this by making the number of different IVs depend on the total plaintext size to be encrypted, but then you make searches even slower.

The second may even be more of a problem for an attacker. The less likely options can occur at almost the same frequency – e.g. in letters there is a significant difference between the frequency of 'e' and 't', but 'j' and 'x' are almost equally uncommon. That means even if you can deduce one token from context, you've only solved e.g. one twentieth part of the problem.

Are these insurmountable problems? No. The fix may patch some leaks, but the encryption remains much less secure than non-deterministic, semantically secure encryption.

Trying to extend your tweak, it might be better to use a non-uniform distribution for the different IVs. For example, illustrating only two IVs with letters, if the probability was $\frac{1}{3}$ for one and $\frac{2}{3}$ for the other, the frequency of 'e' with the first IV would become about equal to that of 'n' with the other.

Again, I emphasize that you should only encrypt information like this if you are OK with an attacker learning nontrivial facts about the plaintext.


Is the random oracle commitment scheme secure against PPT active adversaries? The probability that a probabilistic polynomial adversary corrupting the sender can finds two pairs $(m,r)$ such that the output of the random oracle $c$ is the same (break the binding property) is negligible.
At the same time, the probability that a probabilistic polynomial adversary corrupting the sender finds a pair $(m,r)$ starting from the commitment $c$ (break the hiding property) is negligible.
Is there any difference between the case in which the adversary is semi-honest or active in this context? The only threat I see is that an active adversary could change the message of the sender, but this is not relevant since the sender could have chosen that message.

There is no active attack an adversary could do, so the random oracle commitment is secure in (both the passive and) the active adversary model.