Given enough RSA signature values, is it possible to determine the public key value? Given enough RSA signature values, is it possible to determine which public key is required to verify the values?

Could there be enough information to establish which key is required? Is there anything in the RSA scheme to retrieve the modulus, assuming the public exponent can be guessed?

Only padded RSA for signature generation with PKCS#1 v1.5 padding or PSS padding may be considered, not raw/textbook RSA.

This question is related to this one asking about the same question for RSA encryption.

First, assuming any padding, the answer given by fgrieu to your related question still holds. You can associate public keys with signatures by looking at which signatures are consistenly (minimally) smaller than the modulus.

The second method, as suggested by poncho in the comments of your related question and the comments of this post cleverly uses small prime factoring to find $N$. I put this here, so it doesn't look "tagged-on" at the end of the post. The idea is the same as in the third method below, but with a clever twist. Where I collect enough samples to get a decent probability that there's on coprime pair of $t_i$ values, he suggested to take much less pairs and calculate the GCD of all $t_i$. This is $\gcd(t_1,...,t_k)=\gcd(r_1N,...,r_kN)=N*\gcd(r_1,...,r_k)$, where $\gcd(r_1,...,r_k)$ is likely to be a factor which is small enough ($<2^{128}$) to be factored out by methods which can find small primes efficiently, like ECM, yielding the desired $N$, as the largest factor.

The third method is a bit more specialized. It's basically a re-statement of my previous answer to a similar question and goes into a little more detail than poncho's answer to your related question, while standing on similar feet.

Assumptions

It needs to be assumed that you have a set of message-signature pairs, it needs to be assumed that the padding is deterministic (i.e. something like PKCS#1 v1.5) and that the public exponent is known or can be brute-forced easily.

Method

Assume you're given the public RSA exponent $e$, the set of message-signature pairs $\mathcal S = \{(m_1,\sigma_1),...,(m_k,\sigma_k)\}$ with $|\mathcal S|=k$ and the padding function $\operatorname{Pad}(m)$. Note that knowledge of the padding function implies knowledge or a good estimate of the size of the modulus.

The first step is to reduce this problem from one with a complex padding scheme to one of simple raw RSA signatures. For this, we apply $\operatorname{Pad}(m)$ to each message $m_i$ in $\mathcal S$ and and replace the unpadded $m_i$ with the padded $m_i'$ for the set $\mathcal S'$.

Now observe, that as per the normal verification process, $(m_i')^e \equiv \sigma_i \pmod N \forall 0<i\leq k$. This can be rewritten as $(m_i')^e = \sigma_i + r_i * N$. As we know $m_i', e, \sigma_i$, we can calculate $t_i=(m_i')^e-\sigma_i=r_i * N$. Now we observe that all $t_i$ share one common factor: $N$, which we can recover (with a given probability) by calculating the pair-wise greatest common divisor of all $t_i$. The smallest result is likely our $N$. The fancy writing for this would be: $N=\gcd(t_1,...,t_k)$. Once we have a guess for $N$, we can confirm it by checking if all signatures are valid, i.e. if all equations $(m_i')^e\equiv \sigma_i\pmod N$ hold.

Success Probability

The first thing to observe or assume is that the values of $r_i$ are random non-zero integers. Due to their large size (beyond $2^{100,000,000}$), we will model them as randomly distributed numbers. Next, we observe that we found the modulus, if $\gcd(r_1,...,r_k)=1$ holds, i.e. if the set is co-prime. As we modeled the integers randomly, we can use the standard approximation for the probability that $k$ random integers are co-prime which is $1/\zeta(k)$ where $\zeta(x)$ is the riemann zeta function. So the probability that our guess $N'$ for $N$ is correct, is equal to the probability that all $r_i$ are co-prime and thereby:

$$\Pr[N'=N]=1/\zeta(k)$$

This formula can be used to retrieve the number of pairs neccessary to get a good probability for finding the correct $N$. The probability is at $99.99%$ with $k\geq 14$.


Possible to use an accumulator to "license" or restrict the qty of certificates being used? Suppose in a future version of x509 PKI, it is possible to limit the quantity of certificates being used, what would that look like?

Here is a concept that won't work in the real world, but illustrates what I'm trying to do:

The child CA sends a list of primes to the parent CA (the prime is the public key of an issued certificate and therefore unique)
The parent CA checks the quantity of primes, and if it's less than the license threshold, it creates the product of those primes. (quasi-commutative hash)
The parent CA signs the result of #2
Each validator (web client) gets the signed result of #2, and ensures membership of the public key in the accumulator

The reason I ask is because I'm working with a different crypto system developed by a 3rd party, and  was told I need to constrain its usage somehow.  The design of the 3rd party system is similar to PKI, and therefore many of the thoughts are transferrable.

In short:  The parent CA would sign the public key of an n-time signature scheme, as opposed to the public key of a signature scheme which is valid for an unbounded number of signatures (the current design).

n-time signature schemes are usually just constructed by generating n instances of a one-time signature scheme and then accumulating their public keys together into one public key.

The child CA would present their n-time public key (along with a proof that the public key accumulates only n OTS instantiations) to the parent CA to be signed, just like usual.


Where could I submit my algorithm? I have come up with an encryption algorithm and I am looking for a place to possibly publish it.  Any ideas?

First, and I know this isn't exactly the answer you're seeking, but I'd mull over it for a while. Hopefully you have read Schneier's Memo to the Amateur Cipher Designer; it speaks the truth.

In short, before you try to go the route of publishing your algorithm, here are some things you should consider:

What makes your scheme compelling to study? Is it more secure or more efficient than already-existing schemes like AES, Salsa20, Sosemanuk, ...? Is it interesting from a theoretical point of view? Does it solve some heretofore difficult problem? If none of these things, you might have difficulty generating interest in it.
What analyses have you done already? Does your scheme exhibit proper diffusion, e.g. does it possess a good avalanche effect? Do you have some proof of security contingent on the difficulty of another cipher/problem? (This is often not the case for encryption schemes, but it could have such a thing.) Have you verified that your scheme resists common cryptanalytic techniques like differential and linear cryptanalysis?
Are you prepared to justify everything in your design? And I do mean everything: cryptographers want to know details. Why did you do this, why did you do that, how did you generate those constants, could the constants be better? Why not improve on your design in such-and-such maybe-or-maybe-not-obvious way? How's your scheme's efficiency? Good, bad? Does the security level it provides justify its efficiency?
Who else has looked at your scheme? What are their credentials? Like Schneier says, anyone can make a cipher they themselves cannot break; the real test is having others try.

That said, you might already have considered all of these things and more, in which case I apologize profusely. Supposing you have, where can you publish it?

If you're more amateurish and looking for general community input, I'd pick somewhere like the /r/crypto subreddit and maybe try to hang around some other crypto-related spots on the web. If you're related with a university in some way, you might be able to track down cryptology researchers at yours, depending on your position and so forth.

If you're talking about more prestigious academia-related spots, I'd go with one of the IACR publications, where a great deal of cryptography papers are published. For general preprint hosting, almost all papers are submitted (at some point or another) to the Cryptology ePrint Archive, also ran by IACR. If you're familiar with academia, this is an arXiv-esque site for cryptology specifically.


Mitigating timing attacks with a random sleep Could you mitigate all timing attacks by putting a sleep(random()) with a naive crypto implementation? Eg if your implementation looks solid, but you're not sure what the next CPU cache vulnerability is around the corner, would this be a legitimate mitigation strategy?

To clarify, this would be a random delay measured from before the algorithm starts, so that you're not simply adding fuzz to the runtime.

Adding random sleep may make it slightly harder, but not more than that. The problem with adding random noise is that the average time will still be different between the two measurements you are trying to make. So, you will need more measurements, but eventually will get the right thing, since the averages will stand out. This is how timing attacks can be done over the Internet (see Remote Timing Attacks are Practical), even though there is timing noise in networks.


Is RC4 secure with a single-use 32-byte random key prefix and 3072 prefix bytes discarded? Are there any known attacks against RC4 if used with a single-use, random-generated 32-byte key, and 3072 random bytes prepended to the plaintext?

Are there any reasons why we should consider such a use of RC4 less secure than an other state-of-the-art stream cipher with a single-use, random-generated 32-byte key?

Yes, there are reasons to avoid RC4 and to consider it hopelessly insecure.

The single-byte biases—the biases that were so obvious that Bob Jenkins found them empirically on his 1994-era laptop within days of RC4's publication—may decay as you go down the keystream.  But these are the tip of the iceberg.  Many other detectable multi-byte biases have been identified that continue long into the keystream, notably in Fluhrer–McGrew 2000 and Fluhrer–Mantin–Shamir 2001, and applied in practice on TLS and WPA year after year after year.

The only reason academics chose to spend precious grant money on designing and implementing public attacks on RC4 is that people kept using it in important protocols against the advice of cryptographers for twenty years after it was broken.

That nobody has broken your protocol with RC4 probably just means your protocol isn't as important as TLS and WPA.

Just Say No to RC4, kids!


TLS/SSL's usage of Non-Ephemeral DH vs DHE These questions revolve around DH and ECDH vs DHE and ECDHE.  Specifically within the context of TLS/SSL.  There are three questions in total (and a fourth bonus question).

The goal of using Diffie-hellman at all in TLS/SSL is to avoid the case where the contents of the certificate are the sole source for seed value for generating symmetric keys.  In a non Diffie-Hellman TLS/SSL session (aka, an RSA key exchange), if an attacker where to capture all the traffic, then at some time in the future acquire the private key, they can decrypt the entire content of the previously captured data.

Using Diffie-Hellman, however, a compromised private key won't instantly allow the attacker to decrypt all the prior captured cipher text.  Which is why you'd want to use Diffie-Hellman for key exchange, instead of RSA.

But from my reading, DH and ECDH perform the diffie-hellman key exchange using values stored in the certificates.  My first question: is specifically which of the DH values are stored in the Public Certificate and Private Key?

Having said that, my second question is does using DH/ECDH provide forward secrecy?

Lastly, it would seem that there is a bigger security increase going from DH/ECDH to their ephemeral counterparts (DHE/ECDHE), than there would be from going from RSA to DH/ECDH.  Given that, my third question is what would the benefit be (if any) of using DH/ECDH instead of the ephemeral counter-parts?

bonus question:  Does DH/ECDH have much usage in present day SSL/TLS implementations?  Or is it mostly just RSA and DHE/ECDHE that are typically used for key exchanges?

A Diffie-Hellman key agreement has the following general form, presuming it is done in a group $G$ of order $q$ with generator $g$:

$A$: Generate $x \in \mathbb{Z}_q$ at random. Calculate $X = g^x$
$B$: Generate $y \in \mathbb{Z}_q$ at random. Calculate $Y = g^y$
$A \to B$: $X$
$B \to A$: $Y$
$A$: Calculate $S = Y^x$
$B$: Calculate $S = X^y$

First question: The certificate of $A$ contains the public key $X$ and a reference to the group $G$. The group might either be explicitly specified (as is common in the case of DH) or referenced by an identifier (as is common in the case of ECDH). The corresponding private key is the secret exponent $x$. Note that such certificates are rare; most commercial certificates contain RSA public key and might not be used for DH or ECDH (obviously).

Second question: No. If static-DH/ECDH or ephemeral-static-DH/ECDH is used, at least one party will always use the same private key. If that private key is apprehended by an adversary, all prior shared secrets that involve the key pair that private key belongs to, might be calculated from the protocol messages.

Third question: The security of RSA key transport trivially requires that the client (who generates and sends the RSA encrypted pre master secret) has access to a good (pseudo) random number generator. This is true for all attack scenarios; if the client random generator is compromised, RSA key transport will provide no secrecy. For DH/ECDH on the other hand, there are attack scenarios where the client doesn't even need a random generator.

Fourth question: AFAIK DH/ECDH are rare for SSL/TLS, because they require that the server has a DH/EC certificate, and those are rare.


What is the name of this public key encryption cryptosystem? I have been trying to find the name of a public key encryption cryptosystem that I learnt as an introduction to cryptography some years ago but the only scheme I could find was something similar but not the same called "Learning with errors". The scheme I am trying to find the name of works as follows:
Let $q$ be the private key where $q$ is a large prime.
Make a large list of $n$ items with each item being $q * z_n$ where $z_n$ is a different large and random prime number for each position in the list.
So $z_1$ may be $q*a$ and $z_2$ may be $q*b$ where $a,b$ are different primes.
Make this list the public key.
The sender will be sent the public key by the recipient and the sender will encrypt his message $m$ by first taking a $ ^nC_r $ set from the public key list where $r$ is a random number and $1 < r < n$.
Then they sum all the values in this $ ^nC_r $ set and add $m$ to this sum to get the encrypted message $t$.
Note: $m$ must be $ < q $ (we assume it is known that $q$ has some minimum value).
The encrypted value is sent to the recipient and to decrypt it they do $\frac{t}{q}$ to get $m$.

Maybe I miss something, but after some quick thoughts about that algorithm, I think it is not secure. Therefore it may not be used and be more like an example for teaching (with no name).
The problem with the algorithm is that you can derive the secret key q from the public key. When you have two integers a and b, where both are a multiple of q (like all q*z_i in your case), then a - b is also a multiple of q, that is much smaller.
So the private key q can be reconstructed within a fraction of a second for primes with few thousand bits. All you have to do it to take two q*z_i from the public key and compute the greatest (only) common divisor.


How is Diffie Helman secure when the exchanged number is a power of the generator less than the modulo I'm trying to understand how Diffie Helman is still secure when $A$ ends up being a power of $g$ less than $p$.

I chose $p$, where p is prime, and $g$ is a primitive root modulo $p$.

$g=2$ and $p=29$

Now considering Alice creating her $A$ where  $A=2^a\mod{29}$. If she chooses $a=30$ this results in $2^{30}=4\mod{29}$, which means I can trivially recover an $a$ with the same result $a=log_2{4}=2$ and use that to recover the shared secret.

In general any returned $A$ that is a power of $2$ less than $29$ (ie. $2,4, 8,16$) can be trivially recovered by taking $log_2{A}$ and getting a valid $a$.

How does Diffie Helman resist against this? I'm I missing something else? I know I chose a small $a$ and $p$ but it seems this problem would exist with large $a$ and $p$ too.

If $g^a<p$, then the discrete logarithm mod $p$ becomes plain logarithm, even for a 2048-bit $p$. So, you are right that in this case $a$ can be easily computed from $g^a$. However, this is not bad because there are only at most $\log_2 p$ such $a$s (that satisfy $g^a<p$). Compared to $p$, $\log_2 p$ is a negligible number. In other words, since $a$ is chosen uniformly at random from $p-1$ values, the probability that it falls into the first $\log_2 p$ values is negligible (in $\log_2 p$, the bit length of $p$).


AES: Given two deterministic plaintexts, compute two keys let the ciphertext is the same, is it possible? Given two plaintexts $p_1$ and $p_2$, is it possible to find two keys for AES(-CBC) so that $$E_{k_1}(p_1) = E_{k_2}(p_2) $$

I want to make sure that will never happen, or is there any way to prevent that from happening? Because that will make my system unreliable.

What is the mathematical property stating that it is hard to find a collision in the AES algorithm?

The answer of Lindell is important.

For an adversary with infinite computation power it is always possible to find $p_1$ and $p_2$ s.t. $E_{k_1}(p_1) = E_{k_2}(p_2)$. Choose any values $k_1, k_2$ with $k_1 \neq k_2$ and calculate $p_3 = E^{-1}_{k_2}(E_{k_1}(p_1))$ and stop if $p_3 = p_2$, otherwise repeat with different $k_2$.

However if the question is how easy it is to find such $k_1, k_2$ it is a different story.


What was the first hash and what problem was it supposed to solve? Today's hashes have many uses. File integrity, verification of a secret without revealing the secret (i.e. passwords), hash maps, bloom filters, and probably a few more cases not immediately coming to mind. The Caeser Cipher and Vigenere Cipher were both originally done with pencil and paper long before computers as we know them today existed.

I'm curious, what was the first hash we know about and what problem it was trying to solve?

Knuth, TAOCP, Vol. 3, 6.4 states (on non cryptographic hashing):

"The idea of hashing appears to have been originated by H. P. Luhn, who wrote an internal IBM memorandum in January 1953 that suggested the use of chaining; in fact, his suggestion was one of the  rst applications of linked linear lists."

Konheim has a recent book, "Hashing in Computer Science" which focuses on the mathematics and history of non cryptographic hash functions but considers post 1973 cryptographic hash functions only.

Gustavus Simmons worked on authentication codes at Sandia Labs for many years, I looked up for some history in his book but there isn't anything pre 1970 for cryptographic checksums.

CRC type of linear checksums [not strong cryptographically] conceptually date back to error correcting codes. A CRC was specifically proposed by Peterson in 1961.

Edit: (my thanks to @SamuelNeves) In the Georgia Tech School of Computer Science OSP Research Report from 1978 entitled "Foundations of Secure Computation", which can be found here, Rabin explicitly discusses, from p. 157 onwards, cryptographic hash functions and their use in digital signatures. One year later, Merkle invented Merkle trees for hashing.

IFFs are a kind of authentication mechanism, used in military signaling since the 40s, but more resemble challenge response protocols.

Claude Shannon in his "Theory of Secrecy Systems" from the war years, published in 1949 after declassification, focuses exclusively on secrecy as a goal.

Sol Golomb points out that Jevons (1874) had anticipated the difficulty of factoring and discussed how a type of authentication might work, by means of ruling out messages that don't conform to a set of numbers which were output. See here and the screenshot below.

The second fragment refers to the successive striking out of non-compliant statements, and is almost an algorithmic description of authentication.


Are My Answers to This Hash Question Correct? Question

When determining the security of a hash system, the cryptanalyst tries the following attacks.

(a) If the attacker is NOT allowed to modify the original message, determine the number of hash calculations that would be required to have a 50% chance of generating a new message with the same hash as the original message. In your calculations, assume the hash length is 8 bits.

(b) Derive the expression of number of hash calculations, $n$, required to have a 30% chance of generating two different messages with the same hash. Determine the approximate value of $n$.

My Answer

These are what I think is correct, please let me know if I am wrong, Thank you!

a)

$\text{Hashed} = \big(\frac{2^8}{2}\big)$
        = $\big(2\big)^7$

$p = 1 - \big(\frac{(2^7-1)}{2^7}\big)^n$

$n = 88.38 \rightarrow n = 89$.

b)

$\text{Hashed} = \big(2^\frac{8}{2}\big)$
        = $\big(2\big)^4$
        = $16$

$p(n) = 1 - (\frac{\text{Hashed}!}{\text{hashed}^n(\text{hashed}-n)!})$
      = $1 - (\frac{16!}{16^n(16-n)!})$

$p(n) = 1 - e^{(-n^2+n/2 \times 16)}$

$n = 4.57 \rightarrow n = 5$

Birthday Attack

$q(n) = 1 - \big(\frac{365-1}{365}\big)^n$

What needs to be memorized in applied science (physics, crypto) is not a set of formulas. It's, for a few of the simplest formulas studied: what the formula yields, for what inputs, the units for inputs and output, and how to derive the formula when it does not boil down to multiplying or dividing the inputs in a way that can be found from the units. When one can't derive a formula or don't know its units, it's risky to apply it in real life¹.

We have an illustration: the question originally came with all the right formulas, but what the inputs should be was lost, or in the wrong unit (number of hashes versus hash length in bits), as quickly hinted by the terser answer. And for the now added formula-as-a-picture $q(n)=1-\left(\frac{365-1}{365}\right)^n$ it is lost what the formula yields, which has next to no relation with a birthday attack, contrary to the formula's heading.

That formula gives the probability that among $n$ persons, at least one was born on the 4th of July² of some unspecified year, assuming even repartition of birth days of humans on each of 365 days in a year³, and random selection of the $n$ humans⁴.

How do we derive a formula for that probability $q(n)$ ? Picture a room. Let $n$ be the number of persons in the room, $k=365$ the number of days in a year. If the room is empty, no one in the room was born on the 4th of July. Thus $q(0)=0$. Now, picture persons entering the room one by one (nobody leaves) until there are $n>0$. Someone in the room was born on the 4th of July if and only if at least one of two events hold:

Before the last person who entered the room did so, there was already one person born on the 4th of July. The probability of that event is $q(n-1)$, by the definition we give to $q$.
The last person who entered the room was born on the 4th of July. The probability of that event is $1/k$ and independent of $n$ and of the previous event (under hypothesis above following "assuming").

There's a formula for the probability that one of multiple independent events hold. Do yourself a favor and forget about it. Instead: if the probability of an event does not come evident, try the complementary event. Here that complementary event is: nobody in the room was born on the 4th of July. It should be clear that in our (non-empty) room there's nobody born on the 4th of July if and only if that held before the last person entered the room, and that person was not born on the 4th of July, which is the complementary event of (2.) above.

Now it's time to apply three indispensable rules in probability:

The probability that independent events all hold is the product of their probabilities.
The probability of the complementary event is 1 minus the probability of the event.
Independence of events is maintained when going to the complementary event.

And we get: $\forall n>0$, it holds $1-q(n)=(1-q(n-1))\times(1-1/k)$.

By induction, or directly by applying the first rule to all persons in the room, it comes $1-q(n)=(1-1/k)^n$, which we can rewrite as
$$q(n)=1-\left(\frac{k-1}k\right)^n$$
and obtain the question's formula for $k=365$.

How does that apply to the question then? Well, in (a) we want the probability that $n$ hashes of $b=8$ bit length have the same value as a the hash of a particular message. Picture a hash as an 8-bit value like $\tt 01100101$. Under the standard assumption that the hash function (the thing producing hashes from messages) behaves as a random function, the hashes behave as random values among $2^b=2^8=256$. That parallels the birth days of people in the room, which behaves as random values among $k=365$. We can thus adapt our existing formula, replacing $k$ with $2^b=2^8=256$, and get $q(n)=1-\left(\frac{2^b-1}{2^b}\right)^n$ or the equivalent $q(n)=1-\left(1-2^{-b}\right)^n$.

Here, we can directly apply that formula since $b=8$ is small. But take note that in cryptography, our hashes often use much larger values of $b$, e.g. $b=224$ would be considered a bare minimum nowadays in some applications. That formula still holds, but we can get into issues with its numerical stability. Using an ounce of math around that is not hard.

I really suggest that a student derives the formula for question (b), and only uses the ones in my Birthday problem for cryptographic hashing, 101 to verify the outcome, or after trying hard.

¹ Wrongly applying formulas can kill or cause huge losses, in engineering, chemistry, medicine, and business. In higher ed, well-thought notation at such exams should IMHO penalize incorrect answers, much more than no answer vs correct answer.

² That also works for my birthday, or any particular day in the year except February 29th.

³ An approximate model, mostly because reproductive activity is seasonal in most species, including humans to some degree.

⁴ That hypothesis could be seriously wrong at an exam for the driver's license.


Can universal hashing functions be (ab)used as stream ciphers? These days, universal hashing functions like GHASH and Poly1305 are very trendy because of their simplicity and speed.

Now during a discussion related to export restrictions, it came up that mainly encryption techniques are regulated and these hashing functions wouldn't be hit by this.

Now to the question:
Can you run a universal hashing function in CTR mode to get a secure stream cipher?

No. Consider the simple universal hash function $H(k, x) = k \cdot x \in \mathbb{F}_{2^n}$. It is universal as $\text{Pr}[H(k, x) = H(k, y)] \le 1/(2^n - 1)$ for a randomly-selected $k$; polynomial evaluation degenerates to this function when run on a single block. If you run this in counter mode you get as ciphertext $k \cdot 0$, $k \cdot 1$, $\ldots$, which is clearly insecure and leads to immediate key recovery.

Universal hash functions (or the weaker almost-xor-universal variants) work with authentication because their sole job is to uniformly map a potentially long message to a shorter one; the secrecy job is handled by some PRF or PRP.


Wrong key length for EC public key I have a problem with EC public key reading from smartcard using pkcs11 library.
With the secp256r1 EC algorithm, I always get 65 or 67-byte length public key with different smartcards. But with the ePass2003 token, the length of the public key is 61 bytes. Using the pkcs11 library all sign and verify methods work fine with these pair keys(so it seems key pairs are OK), but when I read public key I get 61 bytes.
I tried opensc for double testing. There is also EC_POINT is 232 bits with ePass2003, whether 256 bits with Safenet 5110.
You can see opensc keygeneration command and result below:
"C:\Program Files\OpenSC Project\OpenSC\tools\pkcs11-tool.exe" --modul C:\Windows\System32\eps2003csp11.dll --login --login-type user --keypairgen --id 1 --key-type EC:secp256r1
Using slot 0 with a present token (0x1)
Logging in to "ePass2003".
WARNING: user PIN to be changed
Please enter User PIN: Key pair generated:
Private Key Object; EC
  label:
  ID:         01
  Usage:      sign, derive
  Access:     sensitive, always sensitive, never extractable, local
Public Key Object; EC  EC_POINT 232 bits
  EC_POINT:   a6ea6b9ce6bd0e086f029b082e1a4096062b79293b782bb0d255363994fd846e93ef0950a1338fa2106769a46f692da9a1607cd98a68b42b85a1ab47c9
  EC_PARAMS:  06082a8648ce3d030107
  label:
  ID:         01
  Usage:      encrypt, verify, wrap, derive
  Access:     local

And it is the same code for Safenet 5110 token below:
"C:\Program Files\OpenSC Project\OpenSC\tools\pkcs11-tool.exe" --modul C:\Windows\System32\etpkcs11.dll --login --login-type user --keypairgen --id 1 --key-type EC:secp256r1
Using slot 2 with a present token (0x2)
Logging in to "GlobalSign SafeNet Token".
Please enter User PIN: Key pair generated:
Private Key Object; EC
  label:
  ID:         01
  Usage:      decrypt, sign, unwrap, derive
  Access:     sensitive, always sensitive, never extractable, local
Public Key Object; EC  EC_POINT 256 bits
  EC_POINT:   0441044de0b0df2e13f532240a9c3dd8123c86963ee7e456e62c4be767ff76a74ee935ba431a4d6159db031377d0a1e9cf2fc0b4e818912e9cfc124bc90c13f5b055c7
  EC_PARAMS:  06082a8648ce3d030107
  label:
  ID:         01
  Usage:      encrypt, verify, wrap, derive
  Access:     local

The EC_POINT must be a ASN.1-encoded octet string, and the ePass2003 result does not seem to be valid ASN.1 (compare the Safenet 5110 value and the ePass2003 value)
(Due to a fun coincidence, the octet string ASN.1 prefix is also 04, so the byte that identifies that it's an uncompressed point is actually the second 04 in the third byte, in the Safenet 5110 output)
I don't know exactly what it's returning, but it's certainly wrong. It doesn't matter for the signing/verification process because they happen inside the token and don't rely on the EC_POINT value returned by the token.
My guess is that internally it has the correct value, but the ePass2003 code that returns the EC_POINT value has a bug.


Why does applying 56-bit DES twice only give 57 bits of security? Given two 56-bit keys, $k_1$ and $k_2$, why does $E_{k_1}(E_{k_2}(M))$ only give 57 bits of security?

So basically I'm unsure why it only gives 57 bits of security; I understand that one key will provide 56 bits. Only thing I can think of is that when adding another 56 bit it will cycle through all the bits and realize they are the same so it just adds 1 extra bit, for the second keyblock instead of another 56 bits?

If I'm wrong, could someone please explain it simply and step-by-step?

Decrypt the ciphertext with every possible key and store the result: $2^{56}$ decryptions. Now encrypt the (known) plaintext of the ciphertext with every possible key: $2^{56}$ encryptions. Now you have to check every entry, which is in both lists and try it with another plaintext-ciphertext pair. If you can successfully decrypt that, you are very likely to have found the correct key. All in all $2^{56} + 2^{56} = 2^{57}$ DES operations (encryptions and decryptions), much less than $2^{112}$. You need some work to search inside the list and check every possible key, but for DES this is not really much work.

All this is called Meet-in-the-middle attack.


Can the original message be retrieved from a public/private key signature? When I sign a message (which has potentialy low entropy) using a private key and I send it without the original message, can the original message be retrieved from the signature(s)?

I want to prove – over an unsecure channel – that I know a secret password without revealing it.

Could a man-in-the-middle (who does not know the original message) create a signature using a different private key which would look like he knew the original message? That would give him the oppertunity to claim to also know the message without really knowing it.

When I sign a message (which has potentialy low entropy) using a
  private key and i send it without the original message, can the
  original message be retrieved from the Signaturen?

It depends.
If you use a signature scheme with appendix it will be impossible to recover the message using other ways than brute-force (so the answer would be "yes" for low-entropy). This is the usual case for most signature schemes (like RSASSA-PSS and ECDSA). If you use a signature scheme with message recovery (quite rare, like ISO/IEC 9796-2) you can indeed recover the message.

  I want to prove over an unsecure channel that i know a secret password
  without revealing it

I suggest you give SRP a try for this.
It's specifically designed to combine password authentication with key-agreement (and thereby prove of knowledge of password).

  Could a man in the middle who does not know the original message
  create a signature using a different private key which would look like
  he knew the original message?

A signer needs to know the message in order to be able to sign it. If you can create a signature that is valid without letting the signer ever see the message, you have successfully broken the standard definition of security for this scheme.


Is an HMAC based on a second-preimage resistant hash function always unforgeable? If hash function is collision-resistant, then its associated HMAC is always unforgeable.  But suppose that a hash function is only second-preimage resistant, not necessarily collision-resistant.  Then my question is, its associated HMAC always unforgeable?

Even collision resistance is not sufficient to make HMAC unforgeable, so neither is second-preimage resistance.
Let $H : \{0,1\}^* \to \{0,1\}^n$ be a collision resistant hash function. We define the hash function $H' : \{0,1\}^* \to \{0,1\}^{n+1}$ as
$$H'(m\Vert b) = H(m)\Vert b,$$
where $|b|=1$.
Since for any $m_0\Vert b_0$ and $m_1\Vert b_1$, it holds that $H'(m_0\Vert b_0) = H'(m_1\Vert b_1)$ if and only if $b_0=b_1$ and $H(m_0)=H(m_1)$, it is easy to see that any collision in $H'$ implies a collision in $H$. Thus $H'$ must remain collision resistant.
However, HMAC instantiated with $H'$ is easily forgeable.
\begin{align}
\mathsf{HMAC}(K,m\Vert b) =& H'\Bigl((K\oplus \mathsf{opad})\Vert H'\bigl((K\oplus \mathsf{ipad})\Vert m\Vert b\bigr)\Bigr)\\
=&H'\Bigl((K\oplus \mathsf{opad})\Vert H\bigl((K\oplus \mathsf{ipad})\Vert m\bigr)\Vert b\Bigr)\\
=&H\Bigl((K\oplus \mathsf{opad})\Vert H\bigl((K\oplus \mathsf{ipad})\Vert m\bigr)\Bigr)\Vert b\\
\end{align}
I.e., an adversary can take the tag $t$ for some arbitrary message $m$, and present $(m\oplus 0\dots01,t\oplus 0\dots01)$ as a valid forgery with probability $1$.


Line by line encrypted logging stored with iv/salt/iterations. How safe is it? I'm building an encrypted logging application. Log entries are encrypted with AES-256-GCM, using password-derived keys with PBKDF2.
The application must support log rotation, and I would like to make each log entry "self sufficient". This would allow me to discard previous logs that have already been processed/are too old.

By self-sufficient, I mean that having the log entry and the password is sufficient to decrypt the payload. I do not wish to maintain a separate file/record with information about the key or its derivation.

That means I have to store a whole bunch of information with my each log entry:

pbkdf2 salt
pbkdf2 iterations
iv
gcm tag
encrypted payload

The PBKDF2 salt and iterations are not likely to change often, if ever.
The IV will be randomly generated for each log entry.
The payload is user-provided content
The tag is the verification tag for the GCM encryption.

Here's an example of such a log file:

timestamp  pbkdf2 salt              iter   iv               tag                      encrypted payload
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,IxsZwVEjYvO0vgjl,w4EdRjRJQNCK/sOYKYyXYA==,DCqFFCGQbpYhWEy3u3OlKMN2iMn9JF2vFZFY
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,n1PscNktuug1Os7b,e1oZAg31XCZOZUC4ZrKjzg==,cLhr1baGonaTt/k/PJZ2s5hboTBjNCmqFu281w==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,RqKtky2ICMORWqGZ,G5VHGDkhWuUch7ZN0AiRBg==,mjexQ9aUHCZGomrlrnQrk6K9ULBEYHPSsjeAxw==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,JY3h/TQSlk+yP/5W,bXL8xK5QVC9uPi2vJ+IDQw==,xu5e/UKPyeEnghFVJL+JLmV2yXYlN2cKBmGGZw==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,W/3uKytKkGmPezdP,HuGNKT6L+Bh/bEvwnlkI5A==,rwVB3ssIKNaz0ZldNRR608JKOIjlimnuu5ZAyQ==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,l7RSko8EvTydWWgt,Ahwjm63IR/8MK03gn//uQQ==,cVS+O0nP7BrhuFCheXn1EDSdGSXumzu8PL1cUQ==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,H+5ywMwpalZVPwLj,nzVSRSz08gJ+OxcktniAOQ==,4WbpNcfcIEcx0wDyzH7s40u+Utx+xzlIFfosuA==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,hF5i+nCT3lFFxHJh,w9MYSR4j3tlebur+ZkUyVg==,9ZIlK8ooUhV0AVAJso6DIstAZ3IdxXCbNhpG4A==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,RAqAaY4cXsAMXZ3m,JzS4uU4QuMeenWqOMnCoRA==,phjLHaBeETJ+H5mRq0i1EUIe/MIbNmxEnNhLcA==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,iGXfpm7FZ7Rmj0F1,TRi0/ElsdCbdUUGBrhxqhQ==,P2yMW+1pn9F7kTTU7bWOm19xrjWQU+0UuhJGKw==
1584815488,IqdD09R5kbtA4recw5LQeg==,100000,IXNxT6RwDu3BnoFB,7khAMRKSLcE6nAcxdUsQbQ==,FMv3gUuO5Q2HVwetr/uo73ph4UOuA+Z3IOiXEg==

Is it safe to store all of that information at the same place?
A log file will typically contain hundreds/thousands of such entries. Does the encryption get significantly weaker as entry count increases?
The timestamp has to be stored in cleartext, for practical reasons. However, I would like to validate that it hasn't been tampered with. What's the best approach for this?

Is it safe to store all of that information at the same place?

All the information (salt, pbkdf2, iterations, iv, GCM tag, encrypted payload) is listed can be considered as public information. We already consider that an attacker has the knowledge of all of these but the encryption key by the Kerckhoffs's principle.

  A log file will typically contain hundreds/thousands of such entries. Does the encryption get significantly weaker as entry count increases?

The IV is generated randomly. If the random generator is weak then it might cause an IV reuse and this is a big security issue under the same key for AES-GCM due to the underlying CTR mode and that can reveal the plaintext by crib-dragging and even more it can cause forgeries.

The IV can be generated with a counter or LFSR as recommended by NIST 800-38d  8.2 IV Constructions so that it will never repeat. A better idea is half counter/LFSR half random.

$$\text{nonce} = \text{random} \mathbin\| \text{LFSR}$$
This can prevent a system failure issue that the last stage of the counter/LFSR is not stored then it can cause a nonce repetition. Although one may repeat the counter/LFSR stage, the new random will prevent the IV reuse issue.

AES-GCM has IND-CCA2, it is not getting weaker especially with a 256-bit key size. However, it might be a good idea to change the key over a period of time. This can be done using a master key and derive keys form using HKDF or using different salts for PBKDF2.

  The timestamp has to be stored in cleartext, for practical reasons. However, I would like to validate that it hasn't been tampered with. What's the best approach for this?

The Authenticated Encryption (AE) is also known as Authenticated Encryption with Associated Data (AEAD). You can provide the timestamp as associated data and the AES-GCM will use it in the integrity part. That is designed for such purposes. This can be formalized as

$$(C,T) \leftarrow \operatorname{AES-GCM-}\mathcal{E}^{N,A}_K (M)$$ where

$\mathcal{E}$ stands for encryption, $K$ stands for key, $N$ stands for the nonce, $A$ stands for the associated data. C is the ciphertext and T is the authentication tag. Similarly the decryption;

$$(M | \perp) \leftarrow \operatorname{AES-GCM-}\mathcal{D}^{N,A}_K (C)$$ where $\mathcal{D}$ is the decryption and $\perp$ is the tag mismatch halt.

update per comment

  What if the attacker had one line of that log file, and the corresponding cleartext payload. For example, knowing that line #1 of the example above says "Initial log entry". Does that compromise the key?

AES is primitive and it is supposed to be a pseudorandom permutation. It can achieve IND-CPA or IND-CCA or authenticated encryption using by using the appropriate mode of operation together with AES.

We assumed that one has solved the IV reuse, then in CTR encryption of AES-GCM, we have;

$$C_i = P_i \oplus \operatorname{AES}(k, \text{nonce}\mathbin\|\text{counter}_i) $$ and that means the attacker will know the plaintext and ciphertext blocks. This is actually the Known Plaintext Attack (KPA) and AES has believed to be secure about this. You can also read here the possible attacks on AES-128 and AES-256 far from it.


Multiplicative inverse in $\operatorname{GF}(2^8)$? I know how to do multiplication over ${\rm GF}(2^8)$:

uint8_t  gmul(uint8_t  a, uint8_t  b)
{
    uint8_t p=0;
    uint8_t carry;
    int i;
    for(i=0;i<8;i++)
    {
        if(b & 1)
            p ^=a;
        carry = a & 0x80;
        a = a<<1;
        if(carry)
            a^=0x1b;
        b = b>>1;
    }
    return p;
}

So, I tried to create a ${\rm GF}(2^8)$ multiplication table using this code.
I've given below the values in the 3rd row of the table, but I don't think they're correct:

    0  1  2  3  4  5  6  7   8  9  A  B  C  D  E  F
0
1
2   0  2  4  6  8  A  C  E  10 12 14 16 18 1A 1C 1E
3
.
.
E
F

I don't know what went wrong. I built the table by multiplying the values in the first row with those in the first column.
E.g. in the third row, I multiplied 2 × 0, 2 × 1, …, 2 × E, 2 × F.

How can I create a multiplication table for arithmetic in ${\rm GF}(2^8)$?

Also, how can I find the multiplicative inverse of a number in ${\rm GF}(2^8)$?

For example, how can I determine that the inverse of 95 is 8A?  I tried to do this using the multiplication table above, but when I took 9th row and the 5th column in the multiplication table I got 2D, not 8A.

The standard method for doing multiplication (and multiplicative inverses) in $\operatorname{GF}(2^8)$ is using a log and antilog table.  Each table takes up only 255 bytes; hence it is much smaller than a full $256 \times 256$ multiplication table, and it is much faster than the multiplication procedure you give above.

To create such tables, we need to pick a generator $g$; that is a field element such that $g^i$ is all 255 nonzero elements for $0 \le i < 255$ (where $g^i$ is what you would expect; $g$ multiplied by itself $i$ time).  Such an element always exists, and (IIRC) $g=3$ happens to be a generator in the field representation you are using.

Now, the antilog table is defined as:

$${\rm antilog}(i) = g^i$$

This table has 255 elements, and can be easily built using your multiplication procedure.  You may want to extend it farther (as discussed below); it just continues in the obvious way (and it just repeats itself).

The log table is defined as its inverse, that is:

$$\log(\operatorname{antilog}(i)) = i$$

This table also has 255 elements (but is indexed from 1 to 255), and can be built using the antilog table we already have, or just initialized at the same time:

uint8_t log_table[256], antilog[255];
const uint8_t g = 3;

void init_log_table(void)
{
    log_table[0] = 0;  /* dummy value */
    for (int i = 0, x = 1; i < 255; x = gmul(x, g), i++) {
        log_table[x] = i;
        antilog[i] = x;
    }
}

Once we have those two, we can do multiplication by:

uint8_t gmul_table(uint8_t a, uint8_t b)
{
    if (a == 0 || b == 0) return 0;

    uint8_t x = log_table[a];
    uint8_t y = log_table[b];
    uint8_t log_mult = (x + y) % 255;

    return antilog[log_mult];
}

This works because, if $a = g^x$ and $b = g^y$, then $a \times b = g^x \times g^y = g^{x+y} = g^{(x+y) \bmod 255}$

As you can see, that should be considerably more efficient than your original algorithm; you can omit the % 255 operation by extending the antilog table for 255 more elements.

We can also use those tables to compute multiplicative inverses:

uint8_t ginv_table(uint8_t a)
{
    if (a == 0) return 0;       /* as needed in the context of AES */

    uint8_t x = log_table[a];   /* x       is in range [0..255] */
    uint8_t log_inv = 255 - x;  /* log_inv is in range [0..255] */

    return antilog[log_inv];
}

You can also compute inverses using the Extended Euclidean Algorithm (which can be adapted to work in $\operatorname{GF}(2^8)$; however it's considerably more work than two table lookups.

Here is how that algorithm would look like:

uint8_t ginv(uint8_t x)
{
    uint16_t u1 = 0, u3 = 0x11b, v1 = 1, v3 = x;

    while (v3 != 0) {
        uint16_t t1 = u1, t3 = u3;
        int8_t q = bitlength(u3) - bitlength(v3);

        if (q >= 0) {
            t1 ^= v1 << q;
            t3 ^= v3 << q;
        }
        u1 = v1; u3 = v3;
        v1 = t1; v3 = t3;
    }

    if (u1 >= 0x100) u1 ^= 0x11b;

    return u1;
}

where bitlength(x) returns the position of the most significant 1 bit of x (i.e. the smallest number y such that (1 << y) - 1 >= x).


How to find a triple of keys that maps plaintext to given cipherext using EDE What is a practical method for for finding a triple of keys that maps a given plaintext to a given ciphertext using EDE?

I think this requires something similar to a man-in-the-middle attack...

Indeed, that's a case for Meet-in-the-Middle.

Notice that $E_{K_3}(D_{K_2}(E_{K_1}(P)))=C$ if and only if $D_{K_2}(E_{K_1}(P))=D_{K_3}(C)$. Therefore, finding $(K_1,K_2)$ and $K_3$ making the two sides equal solves the problem. Both sides take random-like values when $(K_1,K_2)$ and $K_3$ vary. Therefore trying $2^{b/2}$ values (e.g. incremental) of $(K_1,K_2)$ and $K_3$ leads to collision with fair probability (where $b$ is the block size in bits).

For an actual implementation with $b=64$ (as in DES), I would

fix an arbitrary $K_1$ and compute $Q=E_{K_1}(P)$
tabulate values of $D_{K_2}(Q)$ for incremental values of $K_2$ in a data structure allowing fast access given the result and recovery of $K_2$. Well over $2^{31}$ values of $D_{K_2}(Q)$ fit in my computer's available memory of 30 GB.
compute $D_{K_3}(C)$ for incremental $K_3$ until getting a match.

Success is expected with about $3\cdot 2^{32}$ DES operations, which is very feasible.

Note: in the above, incremental must deal with the fact that the low-order bits of DES key bytes is ignored, so as to lower DES's resistance against brute force attack.

That has cost $\mathcal O(2^{b/2})$ effort and memory. The memory, but not the effort, can be reduced a lot, and the attack made parallel (reducing time), using techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999. That would be a must for $b=128$ of AES.


RSA primes vs. largest known primes In the context of a new largest (mersenne) prime number being found this week -

The largest known prime number is now 2^57,885,161 − 1, and it took 5 years to find it since the last largest prime was found.

But we know that various asymmetric encryption algorithms require ridiculously large primes which are used as the infamous p and q factors. For example, 1024-bit RSA would require two 512-bit primes.

But this article, if correct, claims we are able to enumerate no more than ~1.7M prime numbers.

How does this settle with cryptographic prime number generation?

A Mersenne prime is a prime number that can be written in the form $M_p = 2^n-1$, and they’re extremely rare finds. Of all the numbers between 0 and $2^{25,964,951}-1$ there are 1,622,441 that are prime, but only 42 are Mersenne primes.

The second sentence is wrong.

What they meant to say is that there are 1,622,441 numbers of the form they mentioned in the first sentence below $2^{25,964,951}-1$.

There are 1,622,441 primes below 25,964,951 and thus 1,622,441 numbers of the form $2^p-1$ (with prime $p$) below $2^{25,964,951}-1$. See Wolfram Alpha.

There are over $2^{500}$ primes with exactly $2^{512}$ bits, so there are plenty to choose from for our RSA keys.

Take a look at the Prime number theorem which tells you that there are approximately $\frac{n}{\ln(n)}$ primes below $n$.


Hide message length in symmetric key cryptography Is there any way to hide message length from adversary in symmetric key cryptography?

Suppose we want to hide message length from active and efficient adversaries.

Yes, you can pad the message. As long as you can retrieve the location of the message inside the padded plaintext then you can hide the exact message length.

Note that statistical methods can still be applied; you will have to always create a message size of $N$ if you want to full hide the length of messages of $0$ to $N$ in length - excluding normal padding that may be required for block modes of encryption. Obviously, you still leak the information that the message is lower than $N$. But that cannot be avoided; an encrypted message of size $N$ cannot be created for all messages larger than $N$.

Just adding a padding of random length may not be good enough as you will still leak some data about the message size if you average things out. This paper by Cihangir Tezcan and Serge Vaudenay makes it clear that providing random padding cannot practically hide enough information when a minimum amount of security is required. It still depends on the use case if random (sized) padding is sufficient for a use case, but it should be avoided.

There are several ways of padding that are independent of the message contents, that allow for deterministic unpadding:

include (prefix) the message length with the size, then use any kind of padding behind the message up to the size N of the input plaintext, note that you must be able to parse the length encoding (having a single ASN.1 / DER encoded structure is a special case of this);
perform bit padding, putting a single bit valued 1 and then add zero's untile you reach size N (or, for byte oriented protocols, use a byte valued 0x80 or 0x01 depending on the bit order within the bytes - usually big endian / 0x80 is used);
end the padding with a padding length indicator, retrieve it and remove the bytes (possibly validating the intermediate bytes, depending on the scheme).

The advantage of using the length of the message is that you can skip decryption of the last part of the ciphertext. But note that this doesn't work for authenticated encryption with one authentication tag, and that not decrypting the last part may leak the size of the plaintext through side channel attacks.

The disadvantage of bit padding is that you may need to go all of the decrypted bytes until you find the set bit (or the byte with the single bit set), starting at the end of the decrypted bytes.

Note that you'd need at least one bit or byte for the bit padding method or space enough to store the length encoding. It is impossible to create a deterministic unpadding method where the size of the message M is identical to N and the message itself cannot be used to determine the size.


Degree vs index of regularity I'm studying the multivariate cryptography and specifically attacks using Groebner basis. On the complexity of such direct attacks, it is well-known that the most important parameter is the degree of regularity.

It is very confusing that there are index of regularity and degree of regularity in literature. Often, the definitions of them are different. For example, The degree of regularity of HFE systems by Dubois and Gama defined the degree of regularity using nontrivial degree falls.

However, in the Asymptotic behaviour of the index of regularity of quadratic semi-regular polynomial systems by Bardet et al., they defined the index of regularity by using Hilbert polynomial. And some article (I cannot remember, sorry) defined the index of regularity as a maximum degree of Groebner basis.

Referring the algorithm complexity formula everywhere, it seems like all are the same. Are those definitions all equivalent? How about this example?

What is the degree or index of regularity of the set $\{x_1,\cdots,x_n\}\subset\mathbb F_q[x_1,\cdots,x_n]$? I think the degree of regularity by the first definition (nontrivial degree fall) is $(q-1)n$ since there never be a nontrivial degree fall. However, the index of regularity by the second and third definition is 1, obviously.

It will be also thankful if you recommend some material to read about them.

There are a couple of definitions in the literature that each aim to capture an aspect of the degree $d$ to which a system of polynomial equations must be expanded before linear algebra on its Macaulay matrix will yield a solution. Some of them are confusingly referred to as the degree of regularity, despite being different things. I will do my best to avoid this term and call them by something else.

Index of Regularity. The index of regularity is defined using the Hilbert polynomial and sequence of an ideal $\mathcal{I}$ [1]. Denote the set of polynomials in $\mathcal{I}$ of degree $s$ or lower as $\mathcal{I}_{\leq s}$ and the same for $\mathbb{F}_q[\mathbf{x}]_{\leq s}$. The Hilbert function $HF_\mathcal{I} : \mathbb{N} \rightarrow \mathbb{N}$ of an ideal $\mathcal{I}$ is defined as $HF_\mathcal{I}(s) = \mathsf{dim} \, \mathbb{F}_q[\mathbf{x}]_{\leq s} / \mathcal{I}_{\leq s}$ and it follows immediately that $HF_\mathcal{I}(s) = \mathsf{dim} \, \mathbb{F}_q[\mathbf{x}]_{\leq s} - \mathsf{dim} \, \mathcal{I}_{\leq s}$. For sufficiently large $s$, the Hilbert function of $\mathcal{I}$ is identical to a polynomial $HP_\mathcal{I}(s) = \sum_{i=0}^d b_i \binom{s}{d-i}$ for some $b_i \in \mathbb{Z}$ and $b_0 \in \mathbb{N} \backslash \{0\}$. This polynomial is called the Hilbert polynomial. The index of regularity is the smallest $s_0$ such that for all $s \geq s_0$, $HF_\mathcal{I}(s) = HP_\mathcal{I}(s)$; this value is also called the Hilbert regularity [2].

Degree of Semi-Regularity.
A sequence of polynomials $(p_1(\mathbf{x}), \ldots, p_m(\mathbf{x}))$ is regular if $g \cdot p_i \in \langle p_1, \ldots, p_{i-1}\rangle \implies g \in \langle p_1, \ldots, p_{i-1}\rangle$. Regular systems capture the worst case of polynomial systems.
The Hilbert series of an ideal $\mathcal{I}$ is defined as the formal power series $HS_\mathcal{I}(t) = \sum_{s=0}^\infty HF_\mathcal{I}(s) t^s$.The Hilbert series of the ideal $\mathcal{I} = \langle p_1, \ldots, p_m\rangle$ spanned by a regular sequence of homogeneous polynomials $(p_1, \ldots, p_m)$ is given by $HS_\mathcal{I}(t) = \frac{\prod_{j=1}^m (1-t^{\mathsf{deg} \, p_j})}{(1-t)^n}$. It is known [3] that the degree of the highest-degree elements in a degree reverse lexicographical Gröbner basis is bounded (up to a linear change of variables) by the Macaulay bound: $\sum_{i=1}^m (\mathsf{deg}(p_i) - 1) + 1$. This bound can be used to estimate the complexity of Gröbner basis algorithms for regular (i.e., worst-case) systems. If $m = n$, the sequence is regular if and only if $HS_\mathcal{I}$ is a polynomial [4]. This means that for some bound $s_0$ and all $s \geq s_0$, $HF_\mathcal{I}(s) = 0$ and so $HP_\mathcal{I}(s) = 0$. In this case, $s_0 = \mathsf{deg}(HS_\mathcal{I}) + 1$ is exactly the index of regularity.

Unfortunately, regular systems do not exist when $m$ is larger than $n$. In this case, one must assume the ideal has a zero-dimensional variety, and given that this is the case one can adapt the definition of regular sequences as follows. A sequence of polynomials $(p_1, \ldots, p_m)$ is $d$-regular if for all $g \in \mathbb{F}_q[\mathbf{x}]$ with $\mathsf{deg}(g) < d - \mathsf{deg}(p_i)$, $g \cdot p_i \in \langle p_1, \ldots, p_{i-1} \rangle \implies g \in \langle p_1, \ldots, p_{i-1} \rangle$. The sequence $(p_1, \ldots, p_m)$ is semi-regular if and only if it is $s_0$-regular, where $s_0$ is the index of regularity [3]. For a semi-regular system the Hilbert series $HS_\mathcal{I}(t)$ will not be a polynomial but it can be written as a formal power series (i.e. a polynomial with an unlimited number of terms). In this case $s_0$ is the degree of the first term in this formal power series whose coefficient is zero or negative. I like to call this the degree of semi-regularity but it is in fact identical to the degree of regularity assuming the system is semi-regular. Treating random systems of quadratic polynomial equations as semi-regular seems to be empirically justified, but there is no proof that random systems are indeed semi-regular.

First Fall Degree. The first fall degree was first introduced by Dubois and Gama [5] in an attempt to explain why HFE systems seem easier to solve than random systems of the same dimensions. It recycles the intuition that the ``degree of regularity'' should be the lowest degree at which the system starts behaving irregularly, which in interpreted in this case as exhibiting a non-trivial combination of polynomials resulting in a degree fall.

Specifically, let $R = \mathbb{F}[x_1, \ldots, x_n] / \langle x_1^q-x_1, \ldots, x_n^q - x_n\rangle$, i.e., the ring of functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$. (In fact, we might as well use $R = \mathbb{F}_q[x_1, \ldots, x_n] / \langle x_1^q, \ldots, x_n^q\rangle$ because we only care about the functions' polynomials' homogeneous highest-degree part.) Consider the algebraic combination map $\psi : R \rightarrow \mathbb{F}_q[x_1, \ldots, x_n]$ defined by $(c_1, \ldots, c_m) \mapsto \sum_{i=1}^m c_i \cdot p_i$. We are interested in non-trivial elements of $R$ that are sent to $0$ under $\psi$; these represent combinations (with polynomials as coefficients) of the polynomials $p_1, \ldots, p_m$ that disappear --- a special word for this type of cancellation is syzygy, although that term applies more generally to algebraic combinations that result in any kind of cancellation and not necessarily mapping to zero. In fact, the syzygies we are interested in do not have to map to zero per se; it is enough for the image of $\psi$ to have a lower degree than $\mathsf{max}_i \, \mathsf{deg}(p_i) + \mathsf{max}_i \, \mathsf{deg}(c_i)$. Moreover, we are interested in syzygies of as low degree as possible. For simplicity, let $\mathsf{deg}(p_1) = \cdots = \mathsf{deg}(p_m) = 2$. Let $R_k$ be the subset of $R$ of homogeneous polynomials of degree $k$ and define $\psi_k : R_k \rightarrow \mathbb{F}_q[x_1, \ldots, x_n]$ accordingly as sending $(c_1, \ldots, c_m) \mapsto \sum_{i=1}^m c_i \cdot p_i$ and in this case the kernel of $\psi_k$ consists of exactly the syzygies we are interested in. Define the space of trivial syzygies $T_k(p_1, \ldots, p_m) \subset R$ as spanned by all basis elements of the form

$c \cdot (0, \ldots, 0, p_j, 0, \ldots, 0, p_i, 0, \ldots, 0)$ where the $p_j$ is in the $i$th position and the $p_i$ is in the $j$th position, and where $c \in R_{k-2}$;
$c \cdot (0, \ldots, 0, p_i^{q-1} - 1, 0, \ldots, 0)$ where the $p_i$ is in the $i$th position and where $c \in R_{k-2(q-1)}$.

The reason why $T_k$ is identifiable with trivial syzygies is that its basis elements can be derived without looking at the contents of the $p_i$; they can be described as functions of $p_i$ without replacing the symbol $p_i$ by the polynomial it represents. This leaves the space of non-trivial syzygies which can be characterized as the quotient space $\mathsf{ker} \, \psi_k / T_k$. Phrased crudely, this is the space of syzygies that do not boil down to clever combinations of trivial syzygies.

The first fall degree of the list of polynomials $p_1, \ldots, p_m$ is defined as $\mathsf{min}_k \{ \mathsf{ker} \, \psi_{k-2}(p_1, \ldots, p_m) / T_{k-2}(p_1, \ldots, p_m) \neq \{0\} \}$. Phrased crudely, this is the lowest degree at which algebraic combinations of the polynomials results in non-trivial degree falls. The first fall degree is useful because it is more easily bounded. See Ding et al. [7][8][9] for a series of upper bounds on the first fall degree of multivariate quadratic systems derived from the HFE construction. However, these bounds are not tight, especially for large field order $q$. While the index of regularity is always at least as high as the first fall degree, it can be higher. So a low first fall degree does not necessarily imply an easy-to-solve system although it definitely indicates that something fishy is going on.

Solving Degree. The solving degree was introduced by Ding and Schmidt [6] as a contrasting notion to the first fall degree. It is defined as the degree of the polynomials in the largest extended Macaulay matrix involved in the algebraic system solver. Linear algebra on this matrix dominates the solver's complexity, and so this degree is a good characterizer of this complexity. However, it is much more difficult to bound. Ding and Schmidt show experimentally that the solving degree lies close to the first fall degree. Nevertheless, it is possible to construct artificial systems where the difference is large.

[1]: David Cox and John Little and Donald O'Shea. Ideals, Varieties, and Algorithms. 2nd edition. Ch.9 Sect.3.

[2]: Wikipedia. https://en.wikipedia.org/wiki/Hilbert_series_and_Hilbert_polynomial

[3]: Magali Bardet and Jean-Charles Faugère and Bruno Salvy. On the complexity of Gröbner basis computation of semi-r egular overdetermined algebraic equations. https://www-polsys.lip6.fr/~jcf/Papers/43BF.pdf

[4]: Magali Bardet and Jean-Charles Faugère and Bruno Salvy. On the Complexity of the F5 Gröbner basis Algorithm. https://arxiv.org/pdf/1312.1655.pdf

[5]. Vivien Dubois and Nicolas Gama. The Degree of Regularity of HFE Systems. https://link.springer.com/chapter/10.1007/978-3-642-17373-8_32

[6]: Jintai Ding and Dieter Schmidt. Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields. https://link.springer.com/chapter/10.1007/978-3-642-42001-6_4

[7]: Jintai Ding and Timothy Hodges. Inverting HFE Systems Is Quasi-Polynomial for All Fields. https://link.springer.com/chapter/10.1007/978-3-642-22792-9_41

[8]: Jintai Ding and Thorsten Kleinjung. Degree of regularity for HFE-. https://eprint.iacr.org/2011/570

[9]: Jintai Ding and Bo-Yin Yang. Degree of Regularity for HFEv and HFEv-. https://link.springer.com/chapter/10.1007/978-3-642-38616-9_4


RSA - Does knowledge of part of the ciphertext decrease encryption security for the rest of the ciphertext? There is a language called SystemVerilog that can be protected via encryption to allow sharing/licensing code for others to use, but prevents them from seeing the code contents. This is done based on the recommendations of IEEE 1735 (paywall) and through support through the Compiler/Simulation software. If the correct keys are used, the compiler/simulator is able to read the 'shared' IP, compile, and run the protected IP.

Within IEEE 1735, it recommends RSA >=2048 for Asymmetric encryption.

I can have some code, protected by this encryption scheme, that prints text out to a log file. If the text it prints out is static text, will I need to worry about the encryption security of my file?

module my_encrypted_module;
 initial begin
    $display ("This text will be printed to log file");
 end
endmodule

The encrypted file is 1000 characters long
500 characters is a text message that will be printed to the log when running
Does knowledge from seeing the resulting print message decrease the security of the other portions of this same file, allowing someone to more easily decrypt the file?

Thanks.

No known, modern cipher should be vulnerable against known plaintext attacks. Now just RSA 2048 is not likely to be used on all the text, and RSA encryption can be implemented in different ways, but it is unlikely to the extreme that the protocol is vulnerable against known plaintext attacks. It may of course well be vulnerable against other attacks, such as padding oracle attacks on PKCS#1 v1.5 padding, if that is used.

So you can create a string as large as you want and still be secure against known plaintext attacks, no matter how much of it is guessed or gets known otherwise.

Hah, and I looked up the standard after I wrote this answer and got this in return. It doesn't contain known plaintext attacks of course, that would be too easy. But it does use PKCS#1 v1.5 - which may be vulnerable and AES-CBC without authentication which is even more likely to be vulnerable (ugh).

The paper by the way has been "withdrawn for non scientific reasons" - probably to hide it under the carpet, but you can still download it if you know how to retrieve old internet content (deliberately not linked). Here is the security advisory that links to the missing paper.


How is a public/private key pair generated from a Diffe-Hellman key exchange? I very well understand the DH key exchange. But what is the public key and private key at the end of the exchange.

For example:
Alice and Bob agree to use a modulus $p = 23$ and base $g = 5$ (which is a primitive root modulo $23$).

Alice chooses a secret integer $a = 6$, then sends Bob $A = g^a \bmod p
= 5^6 \bmod 23 = 8$

Bob chooses a secret integer $b = 15$, then sends Alice $B = g^b \bmod p
= 5^{15} \bmod 23 = 19$

Alice computes $s = B^a \bmod p
= 19^6 \bmod 23 = 2$

Bob computes $s = A^b \bmod p
= 8^{15} \bmod 23 = 2$

Alice and Bob now share a secret (the number $2$).

So is $2$ the private key here ? If it's a private key then both Alice and Bob know it even though the eavesdroppers don't know. Please explain how public key/private key pair is generated from this shared secret $2$.

So is 2 the private key here ?

No, it's referred to as a "shared secret" (because it is shared between Alice and Bob, and is secret to everyone else).

If there were 'private' and 'public' keys (which is not the standard terminology with DH), then Alice's private key would be $a=6$, and the public key would be $g^a = 8$.  In this case, the 'private key' is private, in the sense that it allows her to perform the operation of deriving the shared secret; something that we hope is difficult if someone has only the public keys.


How does AES/CTR/PKCS5Padding works when the bits to encrypt is more than 8 bits I am a bit new to java crypto, lately, I was going through some articles regarding the use of AES/CTR/PKCS5Padding for encryption. I read that

  The block size is a property of the used cipher algorithm. For AES it is always 16 bytes.
  So strictly speaking, PKCS5Padding cannot be used with AES since it is defined only for a block size of 8 bytes. I assume, AES/CBC/PKCS5Padding is interpreted as AES/CBC/PKCS7Padding internally.

So, Even if the data is more than 8 bytes (say 10 bytes), will this be padded upto the next block size of 32 bytes (AES Block size) or 16 bytes (PKCS5 block size) or will this not be padded at all?

PKCS#5 was initially written for block ciphers using 64-bit blocks, and up to and including PKCS#5v2.0 had no provision for larger ones. PKCS#5v2.1 remains littered with references to eight octets, including in padding.

The principle that PKCS#5 uses for 64-bit blocks padding is easily generalized to block ciphers with larger blocks (up to 255 octets per block), and that's what PKCS#7 padding is: for a message of $m$ octets ($8m$ bits) and a block cipher of $k$ octets ($8k$ bits), pad the message with $p=k-(m\bmod k)$ octets with value $p$. When $k=8$, that's precisely PKCS#5 padding.

AES is a 128-bit (16 octets) block cipher, thus (at least in CBC mode) is not amenable to PKCS#5 padding with 64-bit blocks. For this reason, PKCS#5 was revised and for AES-CBC-Pad PKCS#5v2.1 footnote 2 of section B.2.5 prescribes 128-bit padding, effectively that of PKCS#7.

The question's quote sticks to the 64-bit definition of padding of PKCS#5 before revision 2.1, and makes the simplest possible conjecture when it assumes that AES/CBC/PKCS5Padding really is internally AES/CBC/PKCS7Padding. Otherwise, it would be impossible to process some messages. For example, with 64-bit padding, the 2-octet message 0x41 0x42 would be padded to 8 octets as 0x41 0x42 0x06 0x06 0x06 0x06 0x06 0x06, and that can't be CBC-enciphered with a 16-octet block cipher; the padding used by AES/CBC/PKCS5Padding thus is 0x41 0x42 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E. And that's what PKCS#5v2.1 prescribes.

Another plausible conjecture is that AES/CTR/PKCS5Padding uses the same padding as AES/CBC/PKCS5Padding, and is internally AES/CTR/PKCS7Padding; but to be sure, we would need to look at the code or some test data, because CTR mode (contrary to CBC mode) does not require padding to block boundaries, and AES-CTR would also be compatible with no padding at all, or with strict PKCS#5 padding. According to this source, this varies across implementations, and it looks like the Sun Oracle Java official stance is that AES/CTR/PKCS5Padding is not supported, should raise an exception if used, and does so with few exceptions that are designated as bugs. Such important boring details are arguably off-topic.


How does MD5 process text which is shorter than 512 bits MD5 processes a 512-bit block and produces a 128-bit (16 byte) message digest often expressed as 32-digit hexadecimal value

For example if I hash the word "how" using MD5 , I get the following hash value

db88a0257c220dbfdd2e40f6152d6a8d

The word "how" is represented in 3 bytes which is 24 bits. How does MD5 process a 24 bit into a 512 bit block???

It's called padding.

MD5 fills the "not finished block" with exactly one "1" bit and a number of "0" bits until the length of the number is 64 bits away from being divisible be 512. It could happen that you don't need to add any "0" bits, that's okay, but never omit the "1" bit! After that, the length of the original message in bits is added, formatted with the fixed length of 64 bits in little-endian in words of 32 bit. Now the block is divisible by 512 and ready to be used in the "core" MD5 algorithm.
The biggest message which can be processed in a single block is 417 bits long: 417 bits for the message, 1 bit for the mandatory "1" bit and 64 bits for the length: $417 + 1 + 64 = 512$. (We don't need any extra "0" bits for this message.)

The plaintext of "how" in ASCII is:
$$ \text{01101000 01101111 01110111} $$
Now we concatenate a "1" bit:
$$ \text{01101000 01101111 01110111 1} $$
That are 25 bits. Now we need the lowest number which is divisible by 512 and at least 64 higher than our current message length. 512 is this number for our example. 64 bits lower than 512 is $512 - 64 = 448$. We need to add $448 - 25 = 423$ "0" bits.
$$ \text{01101000 01101111 01110111 10000000 [416 "0" bits]} $$
The length of the original string is 24. The binary representation of 24 as 64 bit number is this. (Little-endian, so the least-significant byte comes first!)
$$ \text{00011000 [56 "0" bits]} $$
Now we concatenate this number to the block:
$$ \text{01101000 01101111 01110111 10000000 [416 "0" bits] 00011000 [56 "0" bits]} $$
Now follows the full block, converted from little-endian and written (big-endian) as 32-bit integers, like MD5 will process them.

0x80776F68 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000018 0x00000000

If you want to hash more data, divide it into blocks. You still have to add the "1" bit and the length of the hashed message. If the last block is already under 64 bits away from being divisible by 512, than you have to add a new block, just for padding! Omitting the padding is very bad because the hash is even more susceptible for length extension attacks than it's normally the case for MD5.


Does the MixColumns step come before or after AddRoundKey in AES decryption? I found these images depicting the AES decryption process:

In the first image, the MixColumns step comes before the AddRoundKey step, while in the second image, the AddRoundKey will come before the MixColumns.

Which order is the correct one?

InvMixColumns is a linear operation. And because of that it follows:

InvMixColumn(x+RoundKey) = InvMixColumn(x) + InvMixColumn(RoundKey)
                                             ^^^^^^^^^^^^^^^^^^^^^^
                                         "new" round key for decryption

So, the structure on the right is compatible with the structure on the left as long as you use different round keys. The idea behind this is to make the decryption structure look like encryption structure with just a couple of "Inv"s in there. But I'm actually not sure what the benefit of this is. For a block cipher like Anubis (which is similar to AES) it makes much more sense because each operation is an involution. The only difference between encryption and decryption for Anubis are the round keys. So, you can reuse the encryption code for decryption which is a nice property.


HMACSHA1 vs HMACSHA2 (for PBKDF2) I need to choose an HMAC function for PBKDF2.

I'm using .net so I don't have the option to use SHA3. At first glance, and according to this answer by Thomas Pornin  it seems like SHA512 would be best.

However, I've heard that there are some possible downsides to SHA2 compared to SHA1. One of them possibly having something to do with quantum computers. (Yes, I know they're not practical yet, but why not choose better over worse?)

So the bottom line is - should I use HMACSHA1 or HMACSHA2 (512)? Or in other words, is the abovementioned answer a recommendation to always use SHA2 or is it dependant on some factors?

[Also, I would like to verify that I understand correctly that in any case, I should only ask it for the native output (160 bits for HMACSHA1 and 512 for HMACSHA2-512 - right?). Right?]

More (possibly relevant) info

I have a requirement to use only Microsoft libraries. And I need to implement a password stretching function with feedback - how far is the function done. So I can't use Rfc2898DeriveBytes (which doesn't provide feedback), nor SHA3 (unless I write it myself. But I've already written the PBKDF2 myself, and would rather use a built in HMAC rather than write that too.).

The only downside to SHA-2 over SHA-1 is that SHA-2 is a little slower.

In this case, that is of no practical consequence whatsoever because you're trying to make something slow to compute, and it is only a matter of raising the number of iterations to make it cost a certain number of bit operations in serial.

However, please consider using the modern memory-hard password hashes scrypt or argon2 instead of PBKDF2, to limit the advantage that attackers with highly parallel low-memory GPUs, FPGAs, or ASICs can attain over the defenders using ordinary CPUs.

Of the SHA-2 family, SHA-512 is a little faster than SHA-256 on CPUs with native 64-bit integer arithmetic, which are the vast majority of personal computing devices today.  So it provides a tiny advantage to the defender to use SHA-512 instead of SHA-256.


Does XChaCha20 exist with similar properties to XSalsa20? Does XChaCha20 (built from ChaCha20 just like XSalsa20 is built from Salsa20) exist and have XSalsa20's desirable properties?

Unfortunately, there is no specification for XChaCha20. But several implementations provide a HChaCha20 function, built the same way as HSalsa20.

XChaCha20 can be built with HChaCha20 + ChaCha20, and the security proof is similar to the one for XSalsa20.

The Libsodium documentation has a section on HChaCha20, which includes a code snippet to build XChaCha20 out of it.


Paillier Homomoprhic addition overflows after a certain value I'm new to encryption and am trying to implement Paillier encryption from the wikipedia page here: https://en.wikipedia.org/wiki/Paillier_cryptosystem

I managed to implement the encryption and am successfully able to decrypt as well to get the same message - so thats working which is good.

Then I wanted to check homomorphism and followed this formula for homomorphic addition:

$D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod  n}^{2})=m_{1}+m_{2}{\bmod  n}$

And it works as it should until the number goes larger than a certain value.

For example if msg1 = 50 and msg2 = 100, then using the above formula I can multiply their ciphertexts and it will decrypt to added = 150.

But if the addition of the two numbers go higher than 390 the decryption overflows (?). For example:

msg1 = 100 and msg2 = 100, would give added = 200 once decrypted.

msg1 = 290 and msg2 = 100, would give added = 390 once decrypted.

msg1 = 291 and msg2 = 100, would give added = 0 once decrypted.

msg1 = 292 and msg2 = 100, would give added = 1 once decrypted.

msg1 = 293 and msg2 = 100, would give added = 2 once decrypted.

and so on.

Is this expected behaviour? I must be doing something wrong, but going over the implementation I seem to have every step implemented correctly.

Some guidance here would be appreciated.

I am using Matlab as my tool and I am using the variable precision toolbox for my inputs so overflows should not happen from Matlab, the problem must be at my understanding of the system

The plaintext space for Paillier is integers modulo $n$. You are seeing "overflow" at the modulus, which makes sense. You should choose larger primes for both security reasons and to make it so that you can support larger numbers without the "overflow".


What is the opposite of embed? We often embed items from one space into another space, e.g. embedding plaintext items from $\{0, 1\}^m$ into some ring $R_q/\langle x^N + 1 \rangle$ for RingLWE.

What is the inverse of this action called?

(Feel free to move this question to Math.SE or other related. Though I am specifically interested in the opposite of embed in the context of math and crypto, rather than the general English language.)

Embed usually implies the target algebraic structure is of larger cardinality (assuming finite). So, I would say project.


How to mutually share values without influencing senders Goal

I want Alice and Bob to communicate a message without their answers influencing each other. More formally:

Alice wants to send Bob a message, a.
Bob wants to send Alice a message, b.
But Alice must not know b before sending a
And Bob must not know a before sending b.

Attempt

I was thinking I could have:

Alice sends an encrypted message, f(a, p1) = a', and a hash with the original message and the private key, h(a, p1).
Bob also sends an encrypted message, f(b, p2) = b' and hash, h(b, p2).
Alice and Bob exchange private keys once they have received their messages
They decrypt the received messages and verify the hash matches

Is there any problems with this method? Would it be feasible for Alice to construct a p' that causes the message to be decrypted as something other than a yet still satisfy the hashing function? (assuming cryptographically secure f and h)

Are there more commonly accepted ways to do this?

previously posted in security stack exchange but was told it'd be more appropriate here

What you want is a commitment scheme.
Typically these are a pair of functions $c(m), v(c,m')$ where the first creates a commitment (while not leaking information on $m$) and the latter verifies a commitment against a message.

Let $c(\cdot)$ be such a committing algorithm, then you can use the following protocol:

\begin{align}
A\to B:\quad &c(a)\\
B\to A:\quad &b\\
A\to B:\quad &a
\end{align}

In this case, A doesn't know $b$ when sending $a$, and B doesn't know $a$ when sending $b$. When A then sends $a$, B can verify that this $a$ is indeed the $a$, A commited to earlier and thus that it wasn't chosen in dependence of $b$.


Algorithm for anonymous but associated communications from a set of verified communicants? Let's say that I'm selling a product, and I want to get authentic feedback from my customers. However, I have the following two constraints:

My customers must be able to give [at least some of] their feedback anonymously (and, due to practical constraints and legal reasons, it is impossible for I and many customers to agree on any auditor or provide any reasonable assurance that I "simply don't know", say, which "return envelope" I include into each box; otherwise, I'd simply pack each device with a smartcard and a video of my initializing such without observing it before sealing it in tamper-evident packaging.)

I must be able to associate multiple feedback entries from the same customer with each other; i.e. a customer must not be able to trick me into thinking that multiple customers share their required use-case. However, I want to be able to receive e.g. follow-ups or corrections, clarifications, etc. on feedback items with assurance that the original communicant is the one making the correction. (I additionally want to be able to track, say, particularly needy—or insightful—customers across multiple pieces of feedback.)

(It goes without saying that I must also have assurance that each piece of feedback is coming from a customer, not least of the reasons behind which is: this not being the case would break (2) indirectly by enabling customers to launch sybil attacks.)
Additionally, it can be assumed that customers will generally either know each other, or know of each other and be able to get into contact with one another; a solution may assume that every customer is able to get in contact with at least a few other customers (to verify that they have the same public key on file for me, etc.)
Is this a solved cryptographic problem?

If so: what is the solution; or what algorithm, system, or class of algorithms or systems allows this?
If not: what is the state of the art / discussion on it; or what terminology do cryptographers refer to this class of problems by?

You are describing linkable ring signatures. Here's a paper from ICCSA that goes into the model and proposes some schemes.


Security of non-standard use for AES-256-CTR? I have a string secret that I would like to encrypt for storage in a Yubikey's second slot. These slots can be configured to store up to 38 characters that are later "typed" by the USB device acting as a keyboard. This means it can't store raw bytes, but fortunately it's sufficient for my use case for my secret to consist of 38 base64 characters.

Using a strong password, I'd like to use OpenSSL v1.0.1+'s implementation of aes-256-ctr to encrypt the secret for storage on the Yubikey. I am asking about using a counter cipher rather than an alternative because I need for the output to have the same number of bytes as the input. I also need to decode the input from base64 first so that it's using the bytes efficiently, and then encode it as base64 again after the encryption so that the result can be "typed".

echo -n "secret+that+is+exactly+38+base64+chars" | \
openssl enc -base64 -A -d | \
openssl enc -base64 -aes-256-ctr -nosalt -k "this will be a strong password"

Is this a secure way to store my secret? Would it be safe to, say, post the encrypted secret on the public Internet? I'm not planning to, but I also don't want to have to be constantly vigilant about the physical security of the Yubikey itself.

Edit: Thanks for the answers and comments! I apologize for having left some things ambiguous initially, but my lack of domain knowledge made it difficult to know what's relevant. Here are some clarifications:

The Yubikey functionality I'm using is called Static Password mode. While the Advanced configuration for this mode can contain 64 modhex characters, the user cannot choose the password so this does not match my use case. The alternative is the Scan Code configuration which can store up to 38 ASCII 256 characters. I can select either US or DE keyboards in the Yubikey Personalization Tool that I'm using to configure the device; as I understand it, this determines the scan codes that are emitted to correspond to my saved password, and a US keyboard will work for me. I realize this is 4x the different characters I get from base64, but since I was able to get something that seemed to work as-is, I didn't try to convert the encrypted bytes to ASCII 256 for more efficient storage. Links: Yubico knowledge base, PDF documentation (see page 25), scan code explanation.
The secret I'm planning to encrypt and store is a 1Password Secret Key, so it will have 128 bits of entropy. (I removed some dashes to make it fit the 38 characters, and converted the remaining dashes to pluses.) I'm trying to set up a recovery plan that is more accessible than a piece of paper in a safety deposit box, and more secure and durable than a piece of paper in my wallet. I omitted this detail from my original question because it seemed like a distraction, but I see now it's relevant to certain types of attacks.
I was planning to use a proper diceware password with at least seven words. If I use ten for 128 bits, is my original proposal sufficient?
I'd love to find a way to make this work securely with the standard tools in OpenSSL. Part of the reason for this is that other tools (such as argon2) seem a bit over my head / beyond what I can trust myself to use properly. Most of the reason, however, is that I want to use tools that are at least somewhat universally accessible so that I'm able to decrypt my 1Password Account Key and recover from hardware loss in the widest variety of possible circumstances (i.e. if I'm abroad without my laptop). One appealing thing about OpenSSL ciphers is that there are Javascript implementations that I could use on a trusted iPhone to do the decryption, obviating the need to install and use OpenSSL on some unknown machine. I was able to get the above encryption/decryption to work using Forge, for example.

This is insecure if more than a single secret is processed with the same password. Plus, OpenSSL has abysmally insufficient key stretching in its processing of the password, making brute force password search a concern.

The first (and worse) problem is because AES-CTR is a stream cipher, and thus malleable; and with no IV (-nosalt) it reduces to bitwise exclusive-OR with a key-dependent value. Knowing any secret $S_i$, the encrypted secret $E_i$, and another encrypted secret $E_j$, allows to find the other secret using $S_j=E_i\oplus S_i\oplus E_j$ (where $\oplus$ is bitwise exclusive-OR with arguments converted from Base64, and the result converted back to Base64).

Insecurity extends to changing a secret: knowing the old secret, its encrypted form before and after change, the new secret is revealed.

I have checked for key stretching built into OpenSSL enc in openssl-1.1.0f, that is the process by which the argument to -k is turned into an AES-256 key. What I found is not pretty. The man page rightly says "There should be an option to allow an iteration count to be included". If I did not got lost in the maze of C code with terse variable names and few helpful comments, there's an iteration count permanently set to 1 and in the case at hand, the AES key ends up as the SHA-256 of the argument to -k. That other answer is right to point that a better password hashing scheme is missing.

In addition, usual warnings apply: the argument to -k must be kept secret, and of course the hardest: it must be entered only on machines trusted from a hardware and software perspective.

Ah, a boring detail: openssl enc -base64 -A -d processes its input by multiple of 4 characters, and will ignore the last 2 characters of its 38-character input; correspondingly, the output of the script shown is only 36 characters. I see no fix to get the full 38-character capacity asked.

What's really needed is a 228-bit block cipher with a tweak (the slot index in the Yubikey), and a conversion of password to key with modern key stretching. Perverting openssl enc do that would be extremely hairy.


Differences between Work Factor and Time Complexity I am interested to know if work factor means the same thing as time complexity.

Quoting Work Factor : Uncovering keys in cryptosystems

  The Work Factor of a cryptosystem is related to its key-length and the
  working mechanism used (encryption and decryption algorithms). For
  example, if the brute force attack method is used to break the system
  (trying all possible combinations of the key), then the work factor is
  directly proportional to the length of the key.

This sounds awfully similar to what time complexity means to me. I hope to find out if the terminologies are similar.

Work factor is a more appropriate description because time factor is relative to processing power. Time factor, time complexity, computational complexity, and work factor, are used to describe the same thing. When someone says time complexity, they are probably not talking about actual time, but rather computation.

Work factor would be something like "200 trillion iterations of the block cipher", which is constant.

Time factor would be something like "20 years", but if you double the compute power, that is now 10 years. Therefore, time factor is only a good comparison with a fixed level of compute or when you can accurately estimate the amount of computation over a given length of time. Time is easier to explain to someone, and compute power raises at a fairly consistent rate, so using time is acceptable, and thus you can give an expiration date to things like public keys.

That being said, "time complexity" is probably the more common term used to describe computational complexity.


Should I assume that all exponent syntax in the description of a Diffie-Hellman-based protocol implies modding? I am examining the SPAKE2+ protocol introduced in Chapter 9 of a paper called The Twin Diffie-Hellman Problem and Applications. I noticing the use of a lot of syntax that looks like exponents. I am just becoming familiar with the mathematics behind the Diffie-Hellman protocol so forgive my ignorance, but does this imply the use of a modulus or are the exponents literally meant to be exponents alone?

A diagram of the protocol itself is pasted below for convenience:

but does the use of a modulus or are the exponents literally meant to be exponents alone?

Well, in SPAKE2+, all operations are done within some finite group, typically either a prime multiplicative group, or an elliptic curve group.

If we decide to use a prime multiplicative group, then yes, addition, subtraction and multiplication are all done implicitly modulo the prime (division needs to be computed differently, doing a school book division and then taking the modulus does not work).

Because this is so universal in cryptography, we generally don't insert all the 'mod p' operations (and if you're using an elliptic curve group, that wouldn't apply anyways)


RSA: Fermat-Euler Theorem - coprimality of message and modulus I understand the implication of the Fermat-Euler theorem and how it applies to RSA and the detailed explanation by user Ninefingers at What is the relation between RSA & Fermat's little theorem? is very useful.

However, the Fermat-Euler Theorem states that $a$ and $n$ should be relatively prime to satisfy the following equation.
$$
a^{\phi\left(n\right)}\equiv1\mod n
$$
But I do not recall RSA stating any exceptions of $a$ which cannot be properly encrypted

Edit: Note that I have seen Does RSA work for any message M? which is very similar BUT the question is different and thus the given answer satisfies it however the answer does not show or prove why the fermat's theorem could still be used.

Edit 2: The reason it is a different question is because I am looking for the number theory function which enables the cryptographic system to work the way it does.

It's a consequence of the Chinese Remainder Theorem (look it up, if you don't know it) if you want to be more precise and understand it algebraically. If $n=pq$ and $de \equiv 1\;(\textrm{mod }\phi(n))$, then we also have that

$$de \equiv 1\;(\textrm{mod }p-1),\;\;de \equiv 1\;(\textrm{mod }q-1),$$

since $\phi(n)=(p-1)(q-1)$. It follows that for any integer $a$,

$$a^{ed} \equiv a\;(\textrm{mod }p),\;\;a^{ed} \equiv a\;(\textrm{mod }q),$$

which follows from Fermat's Little Theorem. Note that this also holds if $a\equiv 0$ modulo $p$ or $q$, since both sides of the equation becomes zero. Now the Chinese Remainder Theorem in the case when $p\mid a$, will translate the equation

$$a^{ed} \equiv a\;(\textrm{mod }n)$$

into the two equations

$$0^{ed} \equiv 0\;(\textrm{mod }p),\;\;\; a^{ed} \equiv a\;(\textrm{mod }q)$$

Since we know that these equations are true by Fermat's Little Theorem as well as the trivial case when the element is zero, the Chinese Remainder Theorem will say that since the equation holds in these two cases, it also holds in the original (since more technically it's an isomorphism between the original ring and the product ring). Therefore, RSA's encryption/decryption algorithm also works in these degenerate cases.

In other words, it's not purely a consequence of Fermat's Little Theorem, but you can use it in the subcases that the CRT translation will give you.


Test the randomness of a random permutations, that was generated without Fisher-Yates? Overview of the problem
Before this gets immediately flagged as duplicate, I'm not interested in testing the Fisher-Yates shuffle for randomness, since this can simply be done by testing the underlying RNG. I'm interested in testing the quality of any function that generates random permutations.
How can one test the quality of a random shuffle function, of which I don't know the underlying implementation?
My specific problem
To be a bit more specific to my conundrum, I'm currently trying to implement a 64 bit version of a permutation algorithm from this blog post.
TLDR: You can use a hash function, that is invertible for a given power-of-two sized domain, to generate random permutations, by rounding up the range to the next power-of-two and excluding and indexes generated that are smaller than the range.
A hacky solution
I came up with a hacky solution, but I'm not sure if there are better ones and how to calculate the bias introduced by this solution:
One thing that comes to mind when evaluating random permutations is what happens if we shuffle an array that contains consecutive integers and just use the first index as a randomly generated number, which can now be tested for randomness using test suites like PractRand.
This approach has an obvious problem though, since we are interested in the correlation of a single permutation and not between different permutations, since e.g. in the algorithms from above the initial index is always properly random.
Now the next idea would be to use the first k indexes as random numbers, but this also has a problem since once a number is generated it can't occur again.
This can be elevated to an extent, by storing the consecutive integers multiple times each in the array. So every integer in [0,n] is stored m times in the array and k shuffled integers are used for testing.
With an increased m the bias in getting repeated integers would go down, and thus this is a theoretically useable solution.
This would require a huge amount of memory though, but fortunately the algorithm I'm interested in testing generates one random index at a time and thus this can be done quite efficiently, by using the mod n of the indexes generated.
Edit: To clarify what I'm talking about on a smaller scale: Say I had an array that contains m zeros and m ones (so n=1). I now shuffle the array and write the first k zeros and ones as bits to a testsuite like PractRand and then repeat this process. With a very large m (e.g. 2^50) and a smaller k (e.g. 2^8) the bias of repetitions should be so small that it's negligible.
I don't know though what values for k, n and m to choose and what the corresponding bias is.
Questions

Are there other methods of testing a function than shuffles an array for randomness, without knowing the underlying implementation of the function?
Is there anything wrong with my proposed method?
How do I calculate the bias my method introduces for given values of k, n and m?

One thing that comes to mind when evaluating random permutations is what happens if we shuffle an array that contains consecutive integers and just use the first index as a randomly generated number, which can now be tested for randomness using test suites like PractRand.

No, you can't do that, but almost.  A pseudo/truly random sequence has multiple same values, repetitions and +/- runs of digits. Your solely incremental sequence will easily fail the test even when perfectly permuted, probably even fail something as simple as ent.
You test the shuffle algorithm by inference.

Generate a large file from something like /dev/urandom or the windows equivalent.

Sort it into order, either rising or falling.

Then permute that.

Then test for randomness.

The test hypothesis is that since the original sequence was cryptographically random with the correct $\chi^2$ distribution, a proper shuffle will not make it worse. And it will space out the values into random positions. So the standard randomness tests should then pass it.


Are there any issues to doing 2 rounds of AES-128? How is the security compared to AES-256? I have a SoC with hardware AES-128 encryption, which is obviously quite efficient in terms of power usage and memory used. However, we would like to have AES-256 encryption (half for commercial reasons, half for post-quantum security).
To achieve this, we consider:

Using software encryption (which will be slower, use more power, and at the least require more code and hence flash space).

Using 2 rounds of AES-128 one on the other, with different keys, effectively giving us a key length of 256 bits.

I am aware that 2 round of 128 bits is not the same as 1 round of 256 bits, but as I'm not an expert, I was wondering if anyone knows about drawbacks or vulnerability introduced by such practice, and ultimately if this would be equivalent to the security brought by AES-256 (ie, take a similar amount of time to break the encryption).
Also, I use AES CTR. The planned implementation would be create 1st cypher block, XOR it with 2nd, and XOR this with the plain text.

Double encryption with 128-bit AES and two different keys does not give 256-bit security. In particular, a classic Meet-in-the-Middle attack applies, with expected cost $2^{128}$ encryptions and $2^{127}$ decryptions. As is, the attack requires ridiculously large amounts of memory, but improvements (using cycle finding with distinguished points) exist that greatly reduce memory requirement. See section 5.3 on MitM in Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1).
I find it likely that a system has weaker points than AES-128's key size; systems may be vulnerable against key compromise or side-channel attacks for example.