To prove $r \cdot f_1 +f_2 \cdot (s+1)$ is secure We define the polynomials $r, f_1,f_2,s \in R[x]$. Where $r$ is a random degree 1 polynomial and $s$ is a random polynomial such that: $degree(s)=degree(f_1)=degree(f_2)$, let $R$ be $\mathbb{Z}_p$ where $p$ is a large prime number.

My question: " How to To prove: Given $\ r\cdot f_1 +f_2 \cdot (s+1)$ one who knows only $f_2$ cannot learn anything about $f_1$."

Or even simpler: Given $\ f_1 +f_2 \cdot s$, one who knows $f_2$ can learn anything about $f_1$?

Thanks

First, a fact.

For some polynomial $f_x$ and some random polynomial of the same degree, say $t$, an adversary given only $f_x+t$, knows no additional information about $f_x$. Basically (due to the finite ring), this operation is the same thing as the one-time-pad.

On to the problem at hand.

Let $f_3=f_2\cdot(s+1)$. Since $f_2$ and $s$ have the same degree, we know that $f_3$ has double that degree. Say the degree of $s$ (and $f_2$ and $f_1$) is $d$, so the degree of $f_3$ is $2d$. Since $2d>d$ (when $d>0$), if you could prove that $f_3$ was a random polynomial, then clearly an attacker given the values you specified above would learn no additional information about $f_1$. Problem is, $f_3$ is not a random polynomial since the coefficients would have interdependencies. For example (using $\mathbb{Z}_{11}$), let $f_2=3x+5$ and $s=7x+2$, then $f_3=(7*3)x^7+(2*3+5*7)x+(5*2)=10x^2+8x+10$. The terms (before I reduced the multiplication) have interdependencies.

Since $f_3$ is not random, Adding $f_3$ to another non-random polynomial ($f_1$ or $r\cdot f_1$ in your case) would not be indistinguishable from a random polynomial. So, I don't think you can make an information theoretic argument.


Characteristic of Public Key? Is Public key used directly to encrypt a message or it is used to derive other keys ?
Can we decrypt a message with same public key using which it was encrypted ?

So far I understand, as PKI is based on mathematical functions which are hard to solve in opposite direction, an encrypted message should not be decrypted using same Public key, but article https://blog.cloudflare.com/encrypted-sni/  mentiones that Public key is used to derive some other keys which are actually used for encryption, thus need clarification.

Is Public key used directly to encrypt a message or it is used to derive other keys?

A public key is used to encrypt a message.

Example:

If Alice wants to send a message to Bob she would take Bob's public key and encrypt the message and send the encrypted message to Bob.

A key to derive other keys is done with a Key derivation function and this key is commonly called a "master key", so it has nothing to do with public-private-key-encryption.

  Can we decrypt a message with same public key using which it was encrypted?

No, you can only decrypt the encrypted message with it's corresponding private key (you always create a private & public key pair together).


Ensuring that an operation takes a relatively specific amount of time, but easily verify the result I want an algorithm of some sort that can ensure that an operation takes a fairly specific amount of time, but proof that this operation was done can be completed relatively inexpensively.

For instance, I can prove that an operation will probably take around 30 seconds by doing a cycle with a hashing algorithm such as SHA256 such that the output of the hash feeds directly back into the input. If I count how many hashes are computed within 30 seconds on a modern computer I can be relatively sure that it can't be significantly faster on better hardware.

So, you can ensure that another user waits for around 30 seconds by giving them the amount of rounds they must do of the hash.

And then, for the receiver to verify that they did the hash, they would calculate the given input X amount of rounds and verify that the result matches what they were given.

However, this is hard, because to verify they took that amount of time, the verifier must also take that amount of time.

Is there a way to do such a thing with the verification taking significantly less time than the actual computation?

For instance, one idea is to use asymmetric RSA encryption. Usually, signing a given input is slower than verifying the signature. So, you could possibly sign the input for X amount of rounds and then verifying X amount of rounds would be significantly faster. However the actual amount of data that would get signed would explode (because each round requires adding another signature) and I think  RSA would not be secure to use in this manner.

Is there some way to do this securely and without exploding amounts of data for each required round?

Timelock puzzles solve this problem.

For instance, consider the function $f(x) = x^{2^t} \bmod n$, where $n$ is a RSA modulus and $t$ is large.  For people who don't know the factorization of $n$, computing $f$ takes $t$ squarings modulo $n$.  If you do know the factorization of $n$ (the private key), then computing $f$ can be done with $O(\lg n)$ squarings, regardless of how large $t$ is, by first reducing $t$ modulo $\varphi(n)$.  This lets you create a puzzle that will take a controllable amount of time for someone else to solve, and where you can very efficiently verify the answer: e.g., choose $n$ to be a 2048-bit prime and $t$ to be a million, or whatever you want $t$ to be to make computing $f$ take exactly as long as you want for the other person.

See, e.g., Time Capsule cryptography? and Parallel-resistant proof-of-work scheme? and What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?

If you want a proof of work puzzle that requires the other person to do 30 seconds of work, I don't see any practical reason to worry much about quantum computers.  Right now there are no quantum computers that could pose a serious threat to this scheme.  If they ever become possible, you can always change the scheme out.  The scheme only needs to be secure for 30 seconds, not for 30 years....


Bulletproofs with ranges not in power of two I am new to bulletproofs. From what I understand, if I was to do a range proof using bulletproofs, both the start and end number have to be a power of 2.

is there any algorithm/approach which can be used to expand this to numbers that are not powers of 2?

Example: find if a number is in the range 18 to 65?

You can use an AND statement to do this.

To prove that x is between a and b , you can prove that (x-a) > 0 AND (b-x) > 0


how to calculate non linearity of AES S-box? S-box has to satisfy different design criteria. How to calculate non-linearity , propagation criteria for an AES S-box?

The non-linearity of an s-box is related to its linear approximation table.

For an $n$-bit input x $m$-bit ouput s-box the LA table is a $2^n$ x $2^m$ table. In the case of AES this is a 256x256 table. The entries of this table represent the difference between how many matches are found and how many are expected for a linear expression of the s-box boolean functions given an input/output mask pair. The expected value is half of all combinations match, which would be a value of 0. A value that differs from 0 means that combination is more likely to be either a 0 or a 1, resulting in a bias.

The linearity of an $n$ x $n$ s-box $S$ such as AES is the maximum distance from 0 in the LA table for input and output masks not equal to 0 (nonzero linear combination), which is 65025 out of 65536 entries for an 8x8 s-box. For AES the maximum value is +128 (256 matches) for a 0 mask, and +/-16 (112 or 144 matches) for a non 0 mask, therefore $lin(S)$ = 16.

For an $n$ x $n$ s-box $S$ such as AES, the non-linearity is $2^{n-1} - lin(S)$, which for AES is 112. All 8x8 s-boxes created using Galois Field inversion plus an Affine Transform have the same non-linearity, as the Affine Transform does not change the linear or differential properties. In practice, the LAT is calculated much faster than testing linear expressions per mask 1 at a time by using something called a Walsh Hadamard Transform.

Propagation is related to avalanche. If a specific bit changes to the s-box input, then of the $m$ output bits, they should change with probability of exactly $1/2$ for all inputs and all changed bits. If an s-box meets this, it meets the 1st order Strict Avalanche Criterion (SAC). In reality, very rarely (never) does this happen, so we want it to happen with probability of $1/2$ or higher, with the probability being as close to $1/2$ as possible, and the combined difference in probabilities being as small as possible (Distance to SAC (DSAC)). Functions that do meet SAC are generally not suited for cryptographic use, as they do not meet other required properties, such as to resist differential analysis.

There are 8 input bits in the AES s-box, there are 8 1-bit masks for 256 inputs, 8 output bits, resulting in 2048 8-bit values being tested, and 64 compared values of s-box output bits to 1-bit masks. AES meets probability $1/2$ or higher for $43/64$ bitmask/outbit combinations, with a min difference of 12 bits for those that do not, and a max difference of 16 bits for those that do. DSAC is 432 bits.

Higher orders of SAC use larger input masks. For 2 or 6-bit masks there are 28 combinations, for 3 or 5-bit masks there are 56 combinations, for 4-bit masks there are 70 combinations, and for 7-bit masks there are 8 combinations. The $k$-th order SAC is met if for a $k$-bit mask, the output bits change with probability of exactly $1/2$. For 2nd order SAC, AES meets probability $1/2$ or higher for $127/224$ bitmask/outbit combinations, with a min difference of 16 bits for those that do not, and a max difference of 16 bits for those that do. 2nd order DSAC is 1664 bits.

Propagation extends to ALL combinations of input bit masks of $1$ to $n-1$ bits. An s-box is said to meet $k$-th order Propagation Criterion if SAC is met for all orders {$1 .. k$}. 3rd order PC would mean 1st 2nd and 3rd order SAC are met. Maximum order PC means all orders of SAC are met. Once again, this is not likely to occur, so we try to target SAC orders with the probabilities closest to half, and with the smallest difference from SAC. Unlike linearity, the affine transform of AES has dramatic changes on SAC test results, although there are groups of AES-like s-boxes with different affine transformations that have the same results. These groups are called Affine Equivalence Classes, with each group having identical results in a variety of other tests as well.


Can you type your own keys? Instead of generating keys, is it possible to type your own? For example, could all the characters be A's for example sake. Or do they have to be generated because they are based off of prime numbers or because it would be to hard to create a matching public key as well?

Since your question has RSA tag, I'm going to speak mostly about RSA, but first...

symmetric cryptosystems

With symmetric key, your key could be anything binary with given length. But, since passwords are weak and aren't binary, you should pass it trough key derivation function (KDF).

RSA and other asymmetric cryptosystems

With asymmetric key, there is some structure to it (at least in some cryptosystems, like RSA. There are asymmetric systems where there isn't any special structure to private key - Thanks Ilmari Karonen). For example in RSA you need two primes p and q of close length, and public key is n=p*q (there are some more things commonly saved, but this smallest amount of information to get key). So you can't simply convert your password to key with KDF.

But there are some techniques that can be used to derive private key solely from password (And for given security and some more things that can be constant). For example, you can use your key as input to CSPRNG (A random function), and then generate 2 random numbers with given length, and then search for closest next prime for those numbers. This (albeit somewhat slowly - same as generating a key) will give you a private key, that will be same for same password. Same can't be done with public-key as far as I know - everything you can do there is use optimal encoding of it and give it to user. But after all it's public key so it's meant to be shared anyway.

This way, every asymmetric cryptosystem can be made where key gives you same key, just by feeding password to KDF and then using it as seed in CSPRNG. This isn't usually done, because this will lead to appearance of same keys (because two people or more used same password). And this is somewhat slow (same as just generating new key). And there are no standardized ways to do that (Thanks user4982).


Why the need to hash before signing small data? I’ve got two questions:

I’m doing the following:

Data :  uuid + int + nonce
Signature:  ECDSA(sha256(Data) )

To verify the signature:

decrypt(Signature) == sha256(data)

So if the data, hash function, and public key are known, why is there a need to hash?
If the same Data with a different nonce is sent over and over, can someone figure out my private key?

First of all I do not know your implementation, but it seems that you have some basic misunderstandings.

  Signature:  ECDSA(sha256(Data) )

ECDSA is typically implemented in a way that you do not explicitly hash the data prior to passing it to the signing algorithm (but as this might be your own implementation and signing may still work correctly).

  decrypt(Signature) == sha256(data)

In ECDSA signature verification you do not decrypt anything nor compare the hash value of the message with some signature value, but the hash value of the message is used implicitly in the verification relation. So I do not see any chance that your verification will work.

I think you actually read a bad source about RSA signatures which uses the wrong and misleading term "decrypt with public key". This is sometimes used because in RSA the  enryption and decryption function is commutative and thus RSA encryption and RSA signature schemes use the same operations in different order. So you sometimes read instead of signing the term "encrypt with private key" and instead of verifying "decrypt with public key", but you should not use this terminology, as this does not apply to other signature schemes such as ECDSA. Furthermore, due to this way of signing in RSA in the verification you compare the value obtained by performing the public key operation on the signature with the hash value, but also this does not hold for other signature schemes such as ECDSA.

To your next question:

  So if the data, hash function, and public key are known, why is there a need to hash?

If you do not hash the data before signing you cannot have one consistent signature algorithm, because you could only sign messages up to a certain size and if the size of the message gets too large you would need to hash. But that is not a good practice for signature schemes. More importantly, there are signature schemes which can easily be forged when the data is not hashed, such as RSA, see my answer here. In order to have security independent of the size of the signed message, we typically use this hash-then-sign paradigm, i.e., hash the plain message before performing signing operations on it, and thus the signature algorithm works for any size of the message and we do not really have to care about the message size.

So to your final question

  If the same Data with a different nonce is sent over and over, can someone figure out my private key?

If you use a secure digital signature scheme (for instance  ECDSA - which internally hashes the message) and a correct implementation thereof, then you are safe.

  Finally, your last question in context of ECDSA, i.e., would your private key be safe in ECDSA when not using a hash function?

All ELGamal type signatures (ECDSA is one of those) are existential forgable if no hash function is used. Although this does not reveal your private key, it allows everyone to compute valid signatures for messages which you have not signed. Although the adversary has no choice over the message for which the forged signature is computed, don't do that and use the standard ECDSA with hashing.


How to collect, process, and transmit data securely? In my question "Authenticating data generated by a particular build of an open source program", Dave Cary requested that I post a question stating my real problem on a high level rather than the partial solution and abstract approach I took. So here goes:

Need to develop a program that collects raw scores at a competition, compute the winning scores for that competition, and save that results so that it can be transmitted to a server for display and validation. The results must be in some human readable form (preferably XML). There must be some way to trace what version of a program generated a set of results. There must be complete transparency in the program in terms of how the winning scores are processed and computed. The server will only accept correctly computed results.. The server should be able to distinguish between results computed by an official build of the program versus a wildcat build. The machines running the program are essentially offline. Not all machines will be updated with new versions at the same time.

This question comes up often enough in the context of cryptography that it probably is relevant in a practical sense. I suspect we'll hear even more about it if homomorphic encryption raises interest in "computation in an adversarial setting".

It's not just theoretically unsolvable. A great many software development organizations have tried to keep data secure on someone else's computer and they have all failed. The only exceptions are when no one cares enough about the data to give it any effort, but this is not reliably predictable in advance.

Consider the great effort online game software companies go to in order to discourage cheaters. Yet still, cheating is sometimes a problem even with closed (and continuously online) systems like the PlayStation 3. Even trusted hardware modules fall to reverse engineers with "hardware-based liquid chemical and gas technologies in a lab setting to probe with specialized needles to build tungsten bridges".

The only reasonable goal is to deploy enough obfuscation and misdirection that it delays the inevitable long enough to be worth its cost. As you say in the comments, perhaps you can make it more worthwhile for someone to pursue the contest legitimately.

Obfuscation may occasionally be worthwhile, but its costs and benefits are notoriously difficult to quantify in advance. For one thing, it's somewhat antithetical to your goal of "complete transparency". How can the participants know that the obfuscated code is something they should trust to run on their own computer? Furthermore, it's likely that some would find the challenge of hacking to be more interesting than the competition itself.

That's why every hard-core security professional will advise you not to attempt this when it really matters. Here are some things not to do:

Don't have the application initialize a PRNG from a wide variety of build-dependent data (e.g., a key supplied at build time) as well as system-dependent data. Don't incrementally mix into the PRNG data from intermediate processing steps. E.g., all program inputs, their timestamps, and the arguments of every function call. In the transmitted results, don't include all the runtime-specific data used to initialize the PRNG, the raw input, the timestamps, and some amount of final PRNG output. Don't use self-modifying code. Don't take hashes of the executable memory pages at various points in time. Don't fork the process periodically and take a crash dump which is then included in the submitted data. Don't make a custom gcc back-end targeting a custom VM runtime that is revealed only at the time of the competition. Don't include a bunch of other misdirecting code that ultimately amounts to meaningless random junk in the output. Don't use hardware exceptions and signals to effect ordinary control transfer. Don't develop another program to verify the results produced by the official build, the source of which is revealed only after the competition has closed.

You don't want to do any of that because it can all be defeated in only a few hours or days, max, against a skilled reverse engineer.

Read the history of Microsoft PatchGuard, a software-only system of preventing unauthorized modifications to a running kernel. Version 3, for example, held out for exactly one weekend.


Why are the factors p and q (for n) secret in Fiat-Shamir Authentication? I am studying about this authentication and I don't understand why the factors of $n$ are kept secret as I can't see how they would give the prover or verifier anymore information.

My professor said that the verifier could learn the secret of the prover with the factors, but I don't understand how he would come about that mathematically. An explanation would be great to learn and understand this: Why are the factors $p$ and $q$ (for $n$) secret in Fiat-Shamir Authentication?

Knowledge of $p$ and $q$ makes computing square roots modulo $n=pq$ easy.

Using the Tonelli-Shanks algorithm, one may determine square roots modulo $p$ and $q$ individually and then combine them to a square root modulo $n$ using the Chinese remainder theorem.

Therefore, anyone who knows $p$ and $q$ can compute the prover's private key (which is a square root of the public key) to impersonate them.


Is the following 4 digits code generator secure and non-deterministic? In a C# WCF service, I need to send a 4 digits code by SMS to validate a user account/password. For security reasons, the code has to be non-deterministic (so that a malicious user/hacker should not be able predict what the next code will be).

I use the following code :

protected string Generate4DigitsCode()
{
    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
    byte[] bytes = new byte[4];
    rng.GetBytes(bytes);
    return string.Format("{0:D4}", BitConverter.ToUInt32(bytes, 0) % 10000);
}

I am especially worried by the modulo operation, which probably focus on the lowest bytes. Would it be better to do a integer division ?

I'm assuming that RNGCryptoServiceProvider is an interface to a properly implemented CSPRNG.  If so, its output should be impossible to predict (for an adversary with any practical amount of computing power, and no access to the internal RNG state) and uniformly distributed (i.e. every $n$-bit output is generated with the same probability of $1/2^n$).

Thus, assuming that your CSPRNG isn't broken, as far as the attacker is concerned you're effectively generating truly random 4 × 8 = 32 bit random numbers and then applying a known function (reduction modulo 10,000) to map them into strings of four decimal digits.

The only possibly exploitable source of bias is therefore the non-uniformity of your reduction function: if the function maps more of the 32-bit random inputs to some 4-digit codes than to others, an attacker will know that those specific 4-digit codes will be more likely on average, and can optimize their attack to try them first.

So, how biased is your modulo reduction, then?  It turns out that, while it's not perfectly unbiased, it's as close to unbiased as any map from 32-bit numbers to 4-digit codes can be.

Since the number of possible outputs (10,000) does not evenly divide the number of possible inputs (232 = 4,294,967,296), there must necessarily be some bias.  A perfectly unbiased reduction would have to map 429,496.7296 inputs to each output, but that's obviously not possible — the number of inputs mapped to each output must be an integer.  So at best, we can arrange for some outputs to be generated by 429,496 inputs and some by 429,497 inputs, making the latter ones about 1.0000023 times as likely to occur as the former kind.

The modulo reduction indeed achieves precisely this.  Specifically, using your generation scheme, the codes 7295 and below are about 1.0000023 times as likely to occur as the codes 7296 and above.

For all practical purposes, this bias is completely negligible.  Certainly, it won't be the weakest point of your authentication system, at least not compared to the obvious weakness that, regardless of how carefully you generate the codes, an attacker has a one-in-10,000 chance of getting the code right just by guessing randomly.

(If you did wish to eliminate even this tiny amount of remaining bias, you could either generate even more input bits for each code (e.g. 64 bits, for a bias of 1,844,674,407,370,956 / 1,844,674,407,370,955 ≈ 1.0000000000000004), or you could use rejection sampling and regenerate a new 32-bit number whenever the original one happens to be equal to or greater than 4,294,960,000 (= the largest multiple of 10,000 not greater than 232).  But, as noted above, this would surely be overkill.)


With the random numbers generated, can I know which RNG seed was used? My teacher challenged us to find out which seed was used to generate some random numbers. I would like to know if it is possible to decipher the seed using the generated numbers (break the linear congruence algorithm). If possible, I ask you to explain how to do it.

If the RNG is cryptographically strong, then you should not be able to do any better than the naive brute force: try each seed until you get matching random numbers.

If this is a homework question, then I would guess that either they used a very small seed (like "3" or "15"), or the RNG is not cryptographic strength and with some time analyzing the linear congruence algorithm, you might see how to invert it.


Pseudorandom permutations on domains of arbitrary (i.e. not a power of 2) size The Feistel cipher algorithm produces a pseudorandom permutation with domain size equal to $2^{2m}$ (for some $m \in \mathbb{Z}^+$).  That is, a one-to-one function $\pi$ of the set $\{0, 1, 2, \dots, 2^{2m} - 1\}$ onto itself.

Furthermore, with so-called unbalanced Feistel ciphers, it may be possible (though I don't know this for certain) to produce pseudorandom permutations of the set $\{0, 1, 2, \dots, 2^m - 1\}$ onto itself.

Is there an algorithm (possibly a modification of one of the ones mentioned above) to produce a pseudorandom permutation $\pi$ of the set $\mathbb{m} = \{0, 1, 2,\dots, m - 1\}$ for an arbitrary $m \in \mathbb{Z}^+$?

(Actually, the domain of the function $\pi$ produced by the algorithm may be a proper superset of $\mathbb{m}$, as long as the restriction $\pi|_{\mathbb{m}}$ is a permutation of $\mathbb{m}$.)

Yes. This is called format-preserving encryption.

The most flexible algorithm is FFX, which uses a Feistel network with AES-based round-functions, but performs addition modulo $m$. For certain values of $m$, the range of the round function is extended in order to limit statistical biases to negligible values.

When $m$ is very small, this approach isn't that great because its provable security gaurantees start to vanish if the adversary can see around $\sqrt{m}$ queries. If this is a concern, you can look at slower but more secure algorithms like Sometimes-Recurse Shuffling.


One-Way property of Random Oracle I'm currently working on a proof in the Random Oracle model, and could not find the formal argument on why the random oracle is one-way (i.e. for an Oracle $O$, it is easy to calculate $x=O(n)$, but not efficiently possible to compute $n = O^{-1}(x)$).

Now, I know that the random oracle has that property, and it is intuitively obvious why (as the output is randomly chosen, it is independent from the input and does not contain any information about it). However, as it is not part of the formal specification of a random oracle as per Bellare and Rogaway (as far as I know), I'd like to know how you would formally prove it, based only on the formal specification of a random oracle.

This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven by Rudich and Impagliazzo in their groundbreaking work on black-box separations. You can find a formal proof in Rudich's thesis, Section 6.2, or in the paper Limits on the provable consequences of one-way permutations by Impagliazzo and Rudich.


Discrepancy in modular encryption I'm trying to work through an encryption assignment and the instructions aren't particularly clear because they don't go hand in hand with the lecture video.

  Using encryption key e = 9 in modulo 23, perform the following
  calculations:

  Take the secret message M = 21, encrypt this message as a number E. Note down the value of E.
  Let d be the decryption key for this encryption system. Compute d. Complete the following sentence: e × d ≡ a(mod b). Note down the value of a, b and d.
  Use the results above (or an alternative approach) to decrypt the secret message M that was encrypted as E = 15. Note down the value of M.

I was sorta able to do the first one but I have my doubts.  So e = 9, p = 23(got this from a classmate) and M = 21.  The encryption algorithm given in the lecture was E ≡ M^e (mod p) and that turned out to be 17.  So the message 21 was encrypted to 17.  I am going off of p = 23 from a classmate but I don't quite get she got that value from.

The 2nd issue that I'm having is E = 15 in #2.  The value is suppose to be 17.

The 3rd issue I'm having is the value of a.  I know the value for e and I can find d by isolating it but I don't know what to make of a.

I'm not asking anyone to do my homework for me.  My problem is that this is super unclear and half-assed.  I was wondering if those well-versed in encryption can break this down for me and highlight my mistakes.

This is a toy system that is used in didactic contexts as an introduction to RSA, in a way.

We have some prime $p$ (we are going to do the power operations modulo this prime).
If $m$ is the message (an integer in $\{1,\ldots,p-1\}$), we have some encryption exponent $e$, and encryption indeed works as $$E(m) = m^e \pmod{p}$$.

So for $p=23$, $e=9$ we indeed have $E(21)=17$, as $21^{9} = 17 \pmod{23}$.

The decryption exponent $d$ can be found by solving $ e \times d = 1 \pmod{p-1}$ (the $p-1$ is $\phi(p)$ and Euler's/Fermat's theorem tells us that $m^{\phi(p)} = m \pmod{p}$ for all non-zero $m$.) So exponentiation with $d$: $$D(m)=m^d \pmod{p}$$ is the inverse of $E$ and vice versa.

In your number example with $p=23, m=21, e=9$ we have $p-1=22$ and $9 \times 5 = 1\pmod{22}$ and indeed $D(17)=17^{5}=21\pmod{p}$ as expected: we get back our starting value $m$.

In #3 you know $E(m)=15$ so $m=D(15)=15^5 \pmod{23}= 7$. You should distinguish $E = E(m)$ from the exponent $e$.

So this system crucially depends on $e$ being kept secret, otherwise $d$ is pretty trivial to compute via Euclid's algorithm (that's how I found $d=5$ too) and anyone can decrypt. RSA depends on the fact that given $n$ of the form $pq$, with large unknown $p$ and $q$, makes it hard to find $\phi(n)$ and hence $d$ from $e$, as we find $d$ by solving $e \times d = 1 \pmod{\phi(n)}$ where $n$ is the modulus we are using, like $p$ in your case.


Berlekamp Massey Algorithm I am trying to solve the BM algorithm to find the shortest LFSR and the feedback polynomial but i keep getting stuck. Is there anybody who could solve any binary code so the steps could be little clear. I had seen the algorithm on Wikepedia but too many letters without any implemented examples are very confusing for me. I would be very grateful if someone could explain the steps with actual numbers. Any numerical example would work.


How did you get the key from message & cipher text seems that step is flawed.
The general approach seems correct.

Also most people would write a tiny bit of code in their programming language of choice rather than do this by hand. If you are not comfortable writing code, I strongly urge you to pick up a tutorial. Even classic cryptography is far easier with some basic programming skills.


RSA - Compare two values for encryption exponent, both are relatively prime and $e < λ(n)$ So we have $q = 311$, $p = 163$, $e = 101$, I found $d = 39281$ using Euclidean Algorithm and checked by encrypting and decrypting a message.

Next it is asking if $e = 101$ was a good choice or would the value $e = 9131$ be better.

What I know:

$101$ = prime
$39281$ = not prime ( $23 x\times 397$)

Both options for $e$ are relatively prime to $(p - 1) \cdot (q - 1)$ and both options for $e$ satisfy $ < λ(n)$.

Are there any other things I need to consider for $e$ to answer the question? I have looked around the forum and web but I'm stuck right now.

Hints preferred not a full answer!

Hint: compute $d$ for the alternate value of $e$ considered. Isn't something rather remarkable? What is the probability that it occurs by chance?

While that is totally immaterial given that $p$ and $q$ are billions-n'-billions times too small to prevent factorization (gross understatement), what if we scaled things?  Why would it matter (caution: there are several levels of answer to that later one)?

Facts relevant to this (and many other sensible RSA questions) can be found by combing Dan Boneh's classic Twenty Years of Attacks on the RSA Cryptosystem (in Notices of the AMS, Vol. 46, No. 2, pp. 203-213, 1999).
I might have properly cited that followup attempt if it had acknowledged what inspired it.


Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable? There's a classical method to efficiently test if a LFSR with $n$ bits is maximal-length (or equivalently, if the feedback polynomial is primitive), when the factorization of $2^n-1$ is available.

Do we have an efficient method working when that factorization is unavailable, e.g. because we do not want to depend on a full factorization algorithm, or on the factorizations of $2^n-1$ (for all $n<2991$, and some much higher $n$) amassed by the Cunningham Project?

For reference, the classical method goes:

Check that starting from a particular non-zero original state (e.g. the low-order bit set), and after stepping $2^n-1$ times, we get back to the original state; if not, the LFSR is not maximal-length (since it did not cycle after the maximum period $2^n-1$).
If $2^n-1$ is not prime, then for each of its prime divisors $p$

check that starting from the original state, and after stepping $(2^n-1)/p$ times, we do not get back to the original state; if we do, conclude that the LFSR is not maximal-length (since it cycled before the maximum period $2^n-1$).

Conclude that the LFSR is demonstrably maximal-length (since its period starting from the initial state is bound to be a divisor of $2^n-1$, and we checked a multiple of any divisor of $2^n-1$ other than itself in the previous step).

The algorithm is fast, because the linearity of the LFSR allows computing the state after $k$ steps in time $O(n^2\cdot\log_2k)$ and memory $O(n^2)$.

This is basically the problem of finding a generator $g$ in a group $G$ of order $2^n-1$, where the factorization of $2^n-1$ is unknown.

Here is a pragmatic solution that should work fine in practice.  Use ECM factoring to find all small factors of $2^n-1$; in this way, find as many prime factors of $2^n-1$ as you can.

Now, pick $g$ uniformly at random.  For each known prime divisor $p$ of $2^n-1$, test that $g^{(2^n-1)/p} \ne 1$.  If this test holds for all known prime divisors $p$, then output $g$.  Otherwise, go back to the beginning and pick a new $g$.

Of course, you can only do this test for the prime divisors that you know of, so in principle, there is some risk that that you were unlucky and accepted a $g$ that isn't actually a generator (because $g^{(2^n-1)/q}=1$ for some prime divisor $q$ that you didn't know of).  The good news, though, is that the probability of this happening is exponentially small.

For instance, suppose we have found all prime divisors of 80 bits or less---something that ECM should easily be able to do.  Then there can be at most 37 additional prime divisors of $2^{2991}-1$.  The probability that $g$ happens to satisfy $g^{(2^n-1)/q}=1$ for a single one of them is $1/q$, i.e., $\le 1/2^{80}$.  Therefore, by a union bound, the probability that $g$ happens to satisfy $g^{(2^n-1)/q}=1$ for any of those 37 prime divisors is $\le 37/2^{80} \le 1/2^{74}$, which is so small it can be safely ignored for all cryptographic purposes.

This assumes there is a good practical reason to want to find a maximal-length LFSR of length exactly 2991, something that sounds pretty dubious to me.

In particular, the algorithm I have in mind for choosing a maximal-length LFSR on $n$ bits is as follows:

Choose a random feedback polynomial, uniformly at random from the set of all monic polynomials of degree $n$.  (As an optimization, make sure the constant term is $1$ and that the number of terms is odd; this will reduce the number of rejections in step 3.)
Choose a random non-zero starting state $S$.
Starting from $S$, step the LFSR forward $2^n-1$ times and check that you get back to $S$.  If not, it is not maximal-length; go back to step 1.
For each known prime divisor $p$ of $2^n-1$: Starting from $S$, step the LFSR forward $(2^n-1)/p$ steps and check that you do not get back to the starting state.  If you do get back to $S$, it is not maximal-length; go back to step 1.
Output the feedback polynomial; it is probably maximal-length.

This algorithm is making use of the following fact:

Theorem. If we randomly choose a feedback polynomial whose period divides $2^n-1$, then the probability that the period of the LFSR divides $(2^n-1)/q$ is $\le 1/q$.

Proof: Suppose $f(x)$ is a feedback polynomial for which the corresponding LFSR has period dividing $2^n-1$.  Then $f(x)$ is irreducible and $GF(2)[x]/(f(x))$ is a finite field of size $2^n$.  But there is only one, unique finite field of size $2^n$, so there is a field isomorphism between $GF(2)[x]/(f(x))$ and $GF(2^n)$, say $\varphi : GF(2)[x]/(f(x)) \to GF(2^n)$.

Now let's look at the next-state function for the LFSR with feedback polynomial $f(x)$.  It corresponds to multiplying by $x$ in $GF(2)[x]/(f(x))$.  Let $g=\varphi(x)$; applying $\varphi$, we see that the next-state function can also be thought of as multiplying by $g$ in the group $G=GF(2^n)^*$.  Note that the order of $g$ is equal to the period of the LFSR with feedback polynomial $f(x)$, since $x^k \equiv 1 \pmod{f(x)}$ iff $g^k=1$.  And, of course, $G$ has order $2^n-1$.

In this way, we obtain a bijection between feedback polynomials $f(x)$ and elements $g \in G$, where the period of the feedback polynomial is equal to the order of $g$.  The probability that a randomly chosen element $g \in G$ has period dividing $(2^n-1)/q$ is $\le 1/q$, from which the theorem follows (by applying $\varphi^{-1}$).


AES-CCM replay attack and nonce My wireless sensor nodes and gateway application use timestamps as nonces and guarantee that different messages use different nonces so that security is not compromised.
If the gateway does not include logic to discard packets with old timestamps relative to its own clock for some reason, a replay attack can be sent to it. Beneficially, the sensor would then also be able to re-transmit the same packet later if the gateway was down. Let's say the sensor was not able to deliver the packet to the gateway, but an eavesdropper picked it up.
If the eavesdropper would like to replay this message for some reason, it would actually do the system a favor, as I can see it.
If the sensor only transmits sensor data samples with timestamps, can one say that it's invulnerable to replay attacks?
And if the "sensor" includes a button to switch something on and off (real-time function), one could discard packets with old timestamps.
Let's say a counter was used as the nonce rather than timestamps, and there are hundreds of sensors connected to the gateway. The gateway would then need to keep track of each counter that belongs to each sensor (complications like power cycling retention, flash endurance, etc.) to prevent replay attacks. However, by using timestamps (and sharing the current time to the sensors initially), no such counters need to be monitored -- wouldn't this be right?
Let's go back to the button example and say that a counter nonce was used. The man in the middle could then listen in to a button event packet and simultaneously do jamming at the end of the data packet (during CRC). This way, the gateway did not receive the packet, and it has not incremented its counter value (for this sensor). The jammer, however, did receive the packet (hoping that there were no bit errors). The jammer will continuously jam the sensor for future packets -- to prevent the gateway from updating its counter. Later, it would transmit the packet it copied earlier -- and the packet would be accepted(!) Using timestamps, this would not happen, as I can see it. Or am I missing something here?

It seems you're worried about two distinct attacks: replay attack (attacker reads a packet and re-sends it later), and a "delay attack" (attacker intercepts a packet, blocks it, and sends it later).

The replay attack can be avoided with counters or timestamps; as you mentioned, timestamps can be easier. The hard part is keeping clocks synchronized.

The delay attack can be detected with a timestamp (you need to authenticate the timestamp, e.g. in CCM mode you can include it in the additional data field).

Of course, you need to think about your application to see if you really need to protect against these attacks.


Bitmasks or seed along with public key in WOTS+ post-quantum signatures The state of the art hash-based post-quantum signature schemes, like Sphincs and XMSS, are using variations of WOTS (Winternitz OTS), like WOTS+, that require extra random bitmasks along with the public key.

Some history: These bitmasks were initially introduced from Dahmen et al. in order to build hash-based signatures out of 2nd-preimage resistant functions. The main benefit is that collision-resistance is not required and the signature schemes are NOT affected by the birthday paradox. The aforementioned allows WOTS+ to use hash functions with shorter output than original WOTS for the same security level.

However, a drawback of W-OTS+ compared to previous W-OTS variants is the increased public key size due to the inclusion of these bitmasks; even if we reuse the bitmasks, we still need a list of them. For instance this affects the Sphincs key size.
On the other hand, if I understand correctly, the XMSS rfc makes reference on a single SEED required, that will be used in a PRF to generate all required bitmasks.

That said, is it correct to say that we don't need to send a list of bitmasks, but a single n-sized SEED is enough?

Note that WOTS+ key compression using L-trees is out of scope. I know bitmasks are used there as well. This question focuses on the original WOTS+ scheme without public key compression.

The XMSS Internet Draft actually does not implement the original XMSS scheme but XMSS-T as described in Mitigating Multi-Target Attacks in Hash-based Signatures, by Hülsing, Rijneveld, and Song (PKC 2016). There also a security reduction is given that shows that exactly this is ok (using a SEED instead of a list). It also introduces keying all hash function calls (which is also implemented in the Internet Draft) to prevent multi-target (second-)preimage attacks. The drawback of using a SEED is that this step requires a (Q)ROM proof. The reason is that the standard model PRF / PRG security properties all require the seed / PRF key to be kept secret (while it gets published in the given scenario).


Difference between hash functions and algorithms? Wikipedia lists "Hash function algorithms" within the "Hash function" page. I'm wondering what are the differences and if I can use the terms "hash(ing?) algorithm" and "hash function" interchangeably.

Strictly speaking, an algorithm is a method of computing a function. The function is the thing you stick an input into and get an output from. The algorithm is how it does it. In the context of cryptography, however, hash function and hash algorithm are often used interchangeably. People will know what you mean by it.

I believe hash function is the more common term though. Plain old hash is  totally fine as well.


How fast can a SHA-256 implementation go? I'm looking for high-speed SHA-256 implementations, and specifically, ones with low latency; that is, the time between when you submit the message block, and when the output (or internal state) is produced.

I've googled it, and the fastest I've found appears to take circa 70nsec; does anyone know of something faster?

Now:

I'm not interested in parallel implementations (which can obviously do far more than 1 hash every 70nsec); I am specifically looking for a single high-speed hash.
An ASIC implementation (or even a proposal that gives a plausible outline of how fast it would be) would be quite acceptable.
We can assume that the preimage fits within a single SHA-256 block (or that we're just doing the compression function itself).
An alternative way of answering this would be 'how fast can we compute SHA-256 on a single large message'; can we do something faster than about 1GByte/second?
I specifically asked about SHA-256, however if someone has something similar about, SHA-3 or AES, I'd be interested in hearing that as well.

Thanks!

Ryzen supports special instructions for SHA-256, achieving 1.9 cpb on long messages according to eBACS (graph). Assuming a 4 GHz clock, this corresponds 2.1 GB/s, 17 Gbit/s or 30 ns per block.

From the 22.5 cpb value for an 8-byte message (a single block), we get 180 cycles per block, 2.8 cpb or 45 ns for a single unpadded 64-byte block.


Does encrypting a result of AES block cipher provide more security? I would like to know if encrypting a result of AES256 block cipher provides more security.

Concretely, I am developing a system in which a client sends to a server a ciphertext encrypted with AES256. The server needs to store it in the database and later send it back to the client. Incidentally, the ciphertext is an encryption of some key important to the client, and is sensitive.

On the server side, there are two options:

Save the ciphertext without further processing
Encrypt the ciphertext again with a different key, and save the result (let's call it c). When the server needs to send the original ciphertext back to the client, it will decrypt c to the get original ciphertext, and send to it the client.

Option 2 sounds more secure, but I am unsure if it really provides more security. Any ideas?

Long Story Short

If you only want to store the data as a backup service, do your double encryption yourself, have a backup somewhere. If you want to process the data, you may need FHE, but you need integrity, authentication, and freshness.

Let assume that the client wants to store some data on the cloud and the cloud service provider (SP) offers the client two ways as in your question.

Let's define the models for the service provider;

Honest: obeys the protocol
Semi-honest; obeys the protocol but tires to extract information. Can copy but cannot modify.
Malicious: Doesn't need to obey the protocol. Can diverge from the protocol whenever appropriate.

Assuming that SP doesn't add encryption.

In this case, if the data has no semantic security, The semi-honest SP can extract information by frequency analysis.
A malicious SP has much more power on your data than semi-honest SP. When the client requests data $d$, SP can return $d'$ where the $d'$ can be some other data or the previous version of $d$ and we call it the freshness (rollback) problem. There is no easy way for the client to believe that the data is authentic without storing some information about the data he uploads to the server as Merkle-Tree.

If the SP offers additional encryption as in your case 2, then;

The semi-honest SP can still extract information as in no encryption case since the encryption is performed by the OP.
The malicious SP same as no encryption with more power, he doesn't need to store with double encryption, he can store as you sent him.

What about the attackers. In short, we can talk about the attackers as malicious SP. Some may claim that the frame of the attacks is short, but not necessary.

The biggest problem here, the attacker may steal the data and the encryption key of SP. So, SP encrypted or not the data can be accessed by the attackers as the client uploaded. Some cay says that Hardware Secure Modules can store the encryption keys, but the attackers can use them as an encryption/decryption oracles as the SP does.

So, the second encryption may not give much benefit as one consider.


Is RSA encryption with a private key the same as signature generation? It is often said that RSA encryption of a cryptographic hash with a private key is the same as signing (signature generation). And that verification consists of decryption using a public key.

Is RSA encryption with a private key over a cryptographic hash equivalent to  signature generation?

Short answer

No, RSA encryption with a private key is not the same as RSA signature generation. RSA encryption can only be performed with an RSA public key according to the RSA standard.

The terms Raw RSA or textbook RSA are often used to indicate RSA without a padding scheme. Raw RSA simply consists of modular exponentiation. Raw RSA is vulnerable to many cryptographic attacks and is not safe for general use.

Sources of confusion

It is often mentioned that signing is equivalent to RSA encrypting (the hash over) the message using the private key. This is only true if you disregard the required padding mechanism. The RSA padding mechanisms are different for encryption and signing.

Another reason why the two can be confused is that the public key is often identified with the ASN.1 OID for RSA encryption: 1.2.840.113549.1.1.1 or {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)}. This is for instance often the case within X.509 certificates. This OID is however generally used as a generic pointer to the PKCS#1 specifications; the unfortunate name is tied to the history of the X.509 and RSA specifications.

A deeper look into padding schemes

The PKCS#1 RSA Cryptography Specifications clearly define different schemes for RSA encryption and RSA signature generation.

The older PKCS#1 v1.5 standard contains two padding schemes that are often simply referred to as PKCS#1 v1.5. The padding for these encryption and signature schemes are however quite different, which is reflected by their official names RSAES-PKCS1-v1_5 and RSASSA-PKCS1-v1_5 - the first one is an Encryption Scheme (ES) and the other one is for Signature Scheme with Appendix (SSA).

Fortunately the confusion that arises from two padding schemes with the same name is not present for the newer OAEP encryption - which uses RSAES-OAEP padding - and PSS signature generation schemes - which uses RSASSA-PSS padding. So the name of the padding for encryption and signature generation is different even though they rely on the same mechanism (called a mask generation function or MGF with one implementation: MGF1).

The actual modular exponentiation is mathematically the same for RSA encryption with a public key and RSA signature generation using the private key. This is easily verified by looking at the last part of paragraph 5.2 [emphasis mine]:

  The main mathematical operation in each primitive is
     exponentiation, as in the encryption and decryption primitives of
     Section 5.1.  RSASP1 and RSAVP1 are the same as RSADP and RSAEP
     except for the names of their input and output arguments; they are
     distinguished as they are intended for different purposes.

In general, a signature created by performing RSA encryption will fail if the other party correctly implemented the verification method.

However, some software libraries actually perform RSA padding for signature generation if the private key is used for encryption. One possible reason for this is SSL/TLS; versions of TLS up to v1.2 used a "signature" created from an MD5 hash concatenated with a SHA-1 hash. Such a scheme is often not compatible with the signature generation methods provided by RSA implementations, hence they rely on the RSA encryption routine to magically do the right thing.

RSA implementation notes

A lot of implementations do not allow encryption with a private key. Trying to simulate signature generation using private keys is often not possible. Implementations of public key operations often assume a small public exponent. Furthermore, they will generally not apply the Chinese Remainder Theorem that is used to speed up private key operations.

Note that public keys do not require protection against information leakage, while private keys should be kept secure at all times. Hence RSA encryption implementations - when programmed to be used with a public key - may not contain protection against side channel attacks, possibly exposing the private key to an attacker that is able to apply a side channel attack.


What are the cryptographic assumptions in the Dolev Yao model? In the Dolev Yao model for interactive protocols, the cryptographic primitive (encryption, for example) is considered as a blackbox.

Does blackbox here mean that the primitive is to be considered CPA secure, or does it even require CCA security?

My guess is that CPA is sufficient (and it is the minimum requirement), since the adversary model is rather passive. But could someone confirm this?

In Dolev-Yao and other formal models, the assumptions about adversary behavior are encoded via the grammar and entailment relation, and there's no mention of a specific computational definition of encryption security.

But your question is still meaningful, and can be interpreted as follows:

  If my encryption scheme is CPA secure, and my protocol is secure in the sense of Dolev-Yao, then is my protocol necessarily computationally secure?

This question has been studied, starting in a very nice paper by Abadi and Rogaway.  For your question, their answer is "No, but CPA is almost enough."  Caveats in the security definition involve whether the adversary can detect if two ciphertexts were generated with the same key, or if you encrypt "key cycles", whether message length is leaked, etc.  The linked paper resolves all of these details.


Understanding a method of vector multiplication Recently, I attempted to implement the HQC Post-Quantum KEM in (almost) pure python. In the scheme specification whitepaper, it states the following:

Here is a simplified version of the function I used to calculate the vector product (the actual function is implemented using bit-twiddling but this makes it more readable):
def _convolute(b, a, l):
        aa = [int(c) for c in ('{0:0' + str(l) + 'b}').format(a)]
        bb = [int(c) for c in ('{0:0' + str(l) + 'b}').format(b)]
        out = [0] * l
        for i in range(l):
            if (aa[i] == 0):
                continue
            for j in range(l):
                out[(i + j) % l] ^= bb[j]
        return int(''.join([str(c) for c in out]), 2)

Here, l, is always going to be the cryptosystem parameter $n$. This is an attempt at implementation of the vector product method described above. The vector a is always going to be incredibly sparse (~100 1s), so the naive method works fine. I believe the actual implementation uses a constant-time method to avoid SC timing attacks, but I'm not too concerned with that now.
I implemented this, and the cryptosystem worked as expected, encryption and decryption were correct, and the essential arithmetic given in the correctness proof section of the whitepaper was also correct, so I didn't give it much thought.
However, revisiting the project I decided to actually test all the functions against the KAT data given in the submission package. From the 04/10/2019 submission, I checked against the hqc-256-3 data for the reference implementation.
For the values of x, y, and h given in the data, the value of $s = x + y \cdot h$ does not match against my implementation, so I decided to take a look at the function again. Using Sage to perform arithmetic in the quotient ring $\mathcal{R}$ defined in the whitepaper, my _convolute function does not agree with it (using the interpretation that vector bits correspond to coefficients of the polynomials). I can't check against the reference data as Sage appears to do the calculations too slowly and cannot take advantage of sparse polynomials, so I was using elements of smaller degree for testing.
In conclusion, where am I going wrong? Am I correctly interpreting/implementing the vector product method in the whitepaper with the convolute function? Is a direct comparison to multiplication in $\mathcal{R}$ misguided? Lastly, would anyone be able to provide an algorithm which definitely works for computing products in $\mathcal{R}$, preferably without using FFT or similar, and just done in a schoolbook method.
In addition, if my method is completely incorrect, to what extent is the cryptosystem actually weakened by this wrong product computation?

I can't completely answer your question, but I don't see how sage can't compute the polynomial multiplication - are you computing in the residue ring modulo $x^n + 1$?
The following executes within a few hundreds of milliseconds on my computer:
R.<x> = PolynomialRing(GF(2), "x")
RR.<z> = R.quo(x^57367 + 1)
RR.random_element() * RR.random_element()

Maybe you can use this to debug your implementation.
Hope I could help!


Is it possible to find the key of an HMAC-SHA-512 given the input and the hash output? Is it possible to find the key of an HMAC-SHA-512 given the input and the hash output?

If so, what algorithm if any prevents this?

I'm working on a simple E2E communication system between two self-managed servers, and my idea is to store a static key on both servers, and it is critical that the stored key cannot be reverse-engineered from the sent requests. The requests would contain both an unencrypted and encrypted version of a string, the encrypted one being hashed with the stored key. This does sound unorthodox, but the maths checks out if the mentioned reverse-engineering operation is impossible.

EDIT: Clients will not be able to use an old authentication string to authenticate a new message.

HMAC

$\operatorname{HMAC}$, in extended form keyed-hash message authentication code or hash-based message authentication code, is a MAC that includes a cryptographic hash function and a secret key.

With these properties, it can be used for data integrity and authentication.

With the used hash function $H$, $\operatorname{HMAC}$ defined as;

\begin{align}
  \operatorname{HMAC}(K, m) &= \operatorname{H}\Bigl(\bigl(K' \oplus opad\bigr) \parallel
\operatorname{H} \bigl(\left(K' \oplus ipad\right) \parallel m\bigr)\Bigr) \\
                         K' &= \begin{cases}
                                 \operatorname{H}\left(K\right) & K\text{ is larger than block size} \\
                                 K                              & \text{otherwise}
                                \end{cases}
\end{align}

HMAC is usually written as HM$\operatorname{HMAC-X}$ where the $\operatorname{X}$ represents the used hash function and in your case it is $\operatorname{HMAC-SHA512}$

Security;

Security of $\operatorname{HMAC}$ depends on the deployed key size and hash output. The most common attack is a brute force attack. In your case, the attacker will try all possible keys to match the input and the output. If your key size is above 128 you will be fine for single target attacks. If possible prefer larger key sizes like the 256-bit key size. With SHA-512 one can use key sizes up to 1024 since the limit is determined by the block size of the used hash function.

As proven by Bellare 2006 that if the compression is PRF than HMAC-SHA512 is a PRF. As a result, HMAC doesn't suffer the weakness found in MD5 - the MD5 collision attack.

php hash_hmac supports various hash algorithms, the current list contains 43.

Note 1: HMAC-SHA512 uses the underlying hash function two times to countermeasure against length extension attacks. For the SHA-3 series, there is KMAC that uses SHA-3 directly and SHA-3 has resistance to length extension attacks by design.

Note 2: As of today (21/05/2020), I didn't see a PHP implementation of KMAC.


Change a secret key in an embedded device There is a device that uses a secret key Sk to encrypt data.
Assume this Sk is compromised.

Could the following scheme be considered safe, in case we want to change the compromised Sk:

We store some secret random number in the device- SRN.
The new secret key would be equal to Sk = SRN xor RN, where SRN is the stored in the device secret random number (we know this number), RN is some random number that we send to the device when we want to change the Sk.

What's proposed is unsafe if used more than once: assume $\text{Sk}_1$ is (re-)established this way by sending $\text{RN}_1$; then, after compromise of $\text{Sk}_1$, $\text{Sk}_2$ is re-established this way by sending $\text{RN}_2$. The adversary can find $\text{Sk}_2$ as $\text{Sk}_1\oplus\text{RN}_1\oplus\text{RN}_2$.

Also, $\text{RN}$ does not seem integrity protected, allowing the adversary to play nasty tricks.

A better practice is to send a fresh $\text{Sk}$ protected by authenticated encryption with a dedicated Key Enciphering Key (having the role of $\text{SRN}$ here).


Decision to Search LWE when modulus $q=p^e$ I am reading Applebaum et al..

In Lemma 1. (page 7), Applebaum et al. proved the decision to search reduction when the modulus $q=p^e$ for prime $p$.

In the proof, they define the hybrid distribution $A^i_{\mathbf{s},\chi}$ and say "By a hybrid argument and standard amplification techniques, we can use an algorithm $D$ that distinguishes between $A_{\mathbf{s},\chi}$ and $U$ to solve for $\mathbf{s^\prime}=\mathbf{s} \mod p$".

I don't understand this step clearly.

Also, I cannot find the full version that includes the "entire proof".

Could anyone please tell me the details about this step?

In particular, how to use the "standard amplification techniques"?

First of all, it is a search to decision reduction: we are using an algorithm that distinguishes  $A_{\mathbf{s},\chi}$ (the LWE distribution with secret $\mathsf{s}\in \mathbb{Z}_q^n$ and error distribution $\chi$) from $U$ (the uniform distribution on $\mathbb{Z}_q^n\times\mathbb{Z}_q$) in order to find the secret vector $\mathbf{s}=(s_1,\cdots,s_n)$. A decision to search reduction for LWE (like for most other problems) is trivial.

Let's see first how the reduction works when $q$ is prime [R, Lemma 4.2].

Prime $q$. Suppose we have a distinguisher $\mathsf{D}$ for LWE that works with overwhelming probability (i.e., $1-\mathsf{negl}(n)$) -- any distinguisher $\mathsf{D}'$ that works with probability that is bounded away from half by a non-negligible value can be turned into one that works with overwhelming probability using standard amplification techniques: i.e., carry out independent trials, take the majority and apply the Chernoff bound (see e.g., [AB, Lemma 7.9] to see how this is used for $\mathbf{BPP}$). We will use $\mathsf{D}$ to construct an algorithm $\mathsf{F}$ that finds $\mathbf{s}$ as follows. For $k\in\mathbb{Z}_q$ and $l\leftarrow\mathbb{Z}_q$ (where $\leftarrow$ denotes sampling uniformly at random), consider the transformation
 $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l,0,\cdots,0),b+lk).$$
If $s_1$ denotes the first entry of the secret vector $\mathbf{s}$ in the LWE distribution $A_{\mathbf{s},\chi}$, there are two cases:

$k=s_1$: here, the transformation maps $A_{\mathbf{s},\chi}$ to itself, as shown below
$$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(l,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+ls_1\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e\right)=(\mathbf{a}',b'),$$
where $\mathbf{a}'$ denotes the vector $\mathbf{a}+(l,0,\cdots,0)$.
$k\neq s_1$: the transformation maps $A_{\mathbf{s},\chi}$ to the uniform distribution (as $l$ masks everything).

Now it is easy to recover $s_1$: $\mathsf{F}$ simply runs $\mathsf{D}$ over all $k\in\mathbb{Z}_q$ and outputs the $k$ for which $\mathsf{D}$ outputs $0$ (indicating "LWE"). Since the size of the modulus $q\leq\mathsf{poly}(n)$, this is still efficient. The remaining entries of $\mathbf{s}$ can be recovered by iterating the above procedure, shifting the $(l,0,\cdots,0)$ vector to the right in each iteration. $\square$

Note that the step in the proof which requires $q$ to be prime is the second case ($k\neq s_1$): if $q$ is composite then the map $b\mapsto b+lk\bmod{q}$ is not necessarily bijective and the distribution gets skewed away from uniform when $l$ is one of the factors of $q$. Extending this to the case when $q=p^e$ was sketched in [ACPS, Lemma 1]. The complete proof can be found in [MP, Theorem 3.1] (albeit phrased differently from below).

Prime power $q=p^e$. For simplicity, let's focus on $e=2$ as the argument can be easily extended for $e>2$. For $i=0,1,2$, consider the distributions
  $$A_{\mathbf{s},\chi}^i:=\left\{(\mathbf{a},b+r\cdot p^{2-i}\bmod{q}):(\mathbf{a},b)\leftarrow A_{\mathbf{s},\chi},r\leftarrow\mathbb{Z}_q\right\}.$$
Note that $A_{\mathbf{s},\chi}^0$ is identical to $A_{\mathbf{s},\chi}$ as $r\cdot p^2=0 \bmod{p^2}$. On the other hand, $A_{\mathbf{s},\chi}^2$ is identical to $U$, the uniform distribution on $\mathbb{Z}_q^n\times\mathbb{Z}_q$ as $r$ masks everything.

Step $1$. The first step is to use the distinguisher $\mathsf{D}$, which distinguishes $A_{\mathbf{s},\chi}^0$ from $A_{\mathbf{s},\chi}^2$ to extract $\mathbf{s}'=\mathbf{s}\bmod{p}$. By the hybrid argument, it is guaranteed that $\mathsf{D}$ distinguishes $A_{\mathbf{s},\chi}^0$ from $A_{\mathbf{s},\chi}^1$ or $A_{\mathbf{s},\chi}^1$ from $A_{\mathbf{s},\chi}^2$ with overwhelming probability. We show that in either of the cases it is possible to extract $\mathbf{s}'=\mathbf{s}\bmod{p}$ using the ideas we saw for the case when $q$ is prime. Let's focus on the first case as the second case is analogous, and the only difference is in the transformation.

Case $1$. We are given a distinguisher $\mathsf{D}$ that distinguishes $A_{\mathbf{s},\chi}^0$ from $A_{\mathbf{s},\chi}^1$ with overwhelming probability. The idea is to use a slightly different transform from the previous case. To be precise, we use
  $$(\mathbf{a},b)\mapsto(\mathbf{a}+(lp,0,\cdots,0),b+lkp),$$
where $l\leftarrow\mathbb{Z}_q$ (as before) and $k\in\mathbb{Z}_p$. If $s_1=s_1'+s_1''p$, there are two cases:

$k=s_1'$: the transformation maps $A_{\mathbf{s},\chi}=A_{\mathbf{s},\chi}^2$ to itself, as shown below
$$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(lp,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+lps_1'\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e\right)=(\mathbf{a}',b').$$
Here, we use the fact that $(a_1+lp)s_1=a_1s_1+lp(s_1'+s_1''p)=(a_1s_1+s_1'lp)\bmod{p^2}$, where $a_1$ is the first component of $\mathbf{a}$.
$k\neq s_1'$: the transformation maps $A_{\mathbf{s},\chi}$ to $A_{\mathbf{s},\chi}^1$ as
$$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(lp,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+lpk\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e+rp\right),$$
where $r=lk\bmod{q}$. Here, multiplying by $k$ preserves the distribution $l\leftarrow\mathbb{Z}_q$ since $k$ is coprime to $p$.

Now we recover $s_1'=s_1\bmod{p}$ as before: $\mathsf{F}$ simply runs $\mathsf{D}$ over all $k\in\mathbb{Z}_p$ and outputs the $k$ for which $\mathsf{D}$ outputs $0$ (indicating "LWE"). $\mathbf{s}'=\mathbf{s}\bmod{p}$ is obtained by the shifting trick.

Case $2$. Now, given a distinguisher $\mathsf{D}$ that distinguishes $A_{\mathbf{s},\chi}^1$ from $A_{\mathbf{s},\chi}^2$ with overwhelming probability, the only difference is in the transform, which is now
  $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l,0,\cdots,0),b+pr+lk),$$
for $l$, $k$ as above and $r\leftarrow\mathbb{Z}_q$. Note that when $k=s_1'$ the transformation maps $A_{\mathbf{s},\chi}$ to $A_{\mathbf{s},\chi}^1$ and when $k\neq s_1'$ it maps $A_{\mathbf{s},\chi}$ to $A_{\mathbf{s},\chi}^2=U.$

For general $e>2$, the hybrid distributions are defined as
  $$A_{\mathbf{s},\chi}^i:=\left\{(\mathbf{a},b+r\cdot p^{e-i}\bmod{q}):(\mathbf{a},b)\leftarrow A_{\mathbf{s},\chi},r\leftarrow\mathbb{Z}_q\right\}$$
and the $i$-th transformation is
  $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l\cdot p^{e-j},0,\cdots,0),b+(pr+lk)\cdot p^{e-j}).$$

Step $2$. Given $\mathbf{s}'=\mathbf{s}\bmod{p}$, $\mathbf{s}$ can be recoved as described in [ACPS]. $\square$

[AB]: Arora and Barak, Computational Complexity: A Modern Approach

[ACPS]: Applebaum et al., Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems, Crypto 2009

[MP]: Micciancio and Peikert, Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Eurocrypt 2012

[R]: Regev, On lattices, learning with errors, random linear codes, and cryptography, JACM 2009


Showing that $2^{N-1}\equiv1\pmod N$ when $N=2^p-1$ for prime $p$ I got this question on a previous exam and I got it wrong. I've gone back through it several times since then, but I can't seem to get it. I would really like to know how to do it, so if someone could give me a step by step walk through (answers included), I would really appreciate it! Thanks! The question is the following:

Let $p$ be an odd prime number and $N=2^{p}-1$. The goal of this problem is to show
   that $2^{N-1}$ is equivalent to $1 \mod N$, namely that $N$ passes the Fermat primality
   test for $a=2$. [Note: This doesn't mean that N is necessarily prime. For example,
    if $p=11$, $N=2047=23*89$ and if $p=23$, then $N=8388607=47*178481$.] Then, do the following:

a) Explain why $2^p$ is equivalent to $1 \mod N$ is true

b) Show that $N-1$ is equivalent to $0 \mod p$

c) Use parts a and b to show that $2^{N-1}$ is equivalent to $1 \mod N$

a) $2^p \equiv 1 \mod N$ because $2^p = N + 1$. When you reduce $\mod N$ (take the remainder when dividing by $N$),  you are left with 1.

b) $N - 1 = 2^p - 2$

By Fermat's little theorem, $2^p \equiv 2 \mod p$:

$2^p - 2 \equiv 2 - 2 \equiv 0 \mod p$

c)

From a) we know that $2^p \equiv 1 \mod N$

From b) we know that $N - 1 \equiv 0\mod p$, therefore $N-1$ is a multiple of $p$.

Let $N-1 = kp$ for some integer $k$

$2^{N-1} = 2^{kp}$

$(2^p)^{k} \equiv 1^k \equiv 1 \mod N$


SHA256: Padding a 512 bits length message I am currently implementing the SHA256 hash-algorithm for a "custom-built" embeded-device. Obviously I have a problem with message padding. The routine I wrote does not work with message whose size equals exactly 512 bits.

In that case, how should the message be padded ? i.e.

M = "AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPAABBCCDDEEFFGGHHIIJJKKLLMMNNOOPP"

I mean, what should be the hexa-decimal representation of the last padded block?

Any message that is 448 bits or larger is padded beyond the block size, and runs a second iteration of the compression function. If messages beyond this limit excluding intervals of 512 bits seem to work correctly, it is probably a simple math error. If it was an endianness issue, all lengths greater than 1 would fail.

I assume you are using a byte oriented approach to the design, therefore the padding byte [80] starts the first block, followed by [00] valued bytes, followed by the 64-bit length [0000000000000200], making the block look like this:

80 000000000000000000000000000000000000000000000 0000000000000200


Why is this MAC flawed? Consider a function to create a tamperproof cookie as follows:

$$\text{cookie}(m, k) = m \| \text{hash}(m \oplus k)$$

where $m$ is a message provided by Alice, and k is a secret key known only to Bob. Bob receives m from Alice and returns the cookie to her. $\text{hash}(m \oplus k)$ functions as a MAC.

Why doesn't this properly authenticate the cookie? What's wrong with the MAC?

To supplement the other answer, I will show that the proposed scheme cannot be shown secure assuming only collision resistance of the hash function. (I.e., the  standard assumption on hash functions.)

Let $H' : \{0,1\}^* \to \{0,1\}^{\ell-1}$ be a collision resistant hash function. We construct another hash function $H : \{0,1\}^* \to \{0,1\}^{\ell}$ as follows:
$$ H(x\|b) := H'(x)\|b,$$
where $b$ denotes the last bit of the input.

It is easy to see that $H$ must be collision resistant whenever $H'$ is collision resistant. This is because any collision in $H$ trivially (and by construction) must also yield a collision in $H'$.

If you, however, instantiate your proposed MAC construction with $H$, we end up with a scheme that is existentially forgeable under a known message attack. Suppose an adversary receives a message $m$ and a tag $t=H(k\oplus m)$.

Let $k = k'\|b_k$, $m=m'\|b_m$ $t=t'\|b_t$ where $b_k,b_m$ and $b_t$ are bits. Then by construction of $H$ we have

\begin{align*}
t=&\ H\bigl((k'\|b_k) \oplus (m'\|b_m)\bigr)\\
=&\ H\bigl((k'\oplus m') \| (b_k\oplus b_m)\bigr)\\
=&\ H'(k'\oplus m')\|(b_k\oplus b_m).
\end{align*}

This means, that the adversary can simply output $m^*=m'\|(b_m\oplus 1)$ and $t^*=t'\|(b_t\oplus 1)$ as a forgery. This will verify, since

\begin{align*}
H(k\oplus m^*)=&\ H\bigl((k'\|b_k) \oplus (m'\|(b_m\oplus 1))\bigr)\\
=&\ H\bigl((k'\oplus m') \| (b_k\oplus b_m\oplus 1)\bigr)\\
=&\ t'\|(b_t\oplus 1).
\end{align*}


Motivation of Adversarial Indistinguishability Experiment I had a question about the motivation behind this definition provided in Katz and Lindell's cryptography book. I copied the paragraph in question along with the definition of the experiment.

  Perfect (adversarial) indistinguishability. We conclude this section
  by
      presenting another equivalent definition of perfect secrecy. This
      definition is based on an experiment involving an adversary passively observing a
      ciphertext and then trying to guess which of two possible messages was encrypted.

In the text, this is supposed to be an experiment where the adversary is passively observing a ciphertext and then trying to guess. My question is that in this game, it seems as if the adversary is choosing the two messages. Isn't this not simply an eavesdropping adversary, but rather one that can choose the messages being encrypted? I tried reading more about this, but I couldn't find anything regarding motivation behind this particular definition.

Rather than letting the adversary choose two messages, why not consider for any two arbitrary messages from the message space, sending an encryption of one of them to the adversary along with the two messages? More formally stated:

$$\forall (m_0, m_1) \in M^2,\; [m_0, m_1, E(m_0)] \approx_c [m_0, m_1, E(m_1)]$$

In this way, the adversary does not have a choice in what was encrypted, which seems more in line with the original definition.

Thank you in advance for the help.

My question is that in this game, it seems as if the adversary is choosing the two messages. Isn't this not simply an eavesdropping adversary, but rather one that can choose the messages being encrypted?

Yes, the adversary gets to choose the two plaintexts. There are a few ways to think about why this is appropriate.

It is very realistic to assume that the adversary has a-priori partial information (imagine an encrypted protocol session where we know that all protocols start with a "hello" message, like SMTP) or even partial control (imagine a website where you type a username and the website responds with a message "Hello, <username>") over what plaintext is getting encrypted.
In order to cover these realistic cases, it is necessary for the definition to allow the adversary to influence the choice of plaintexts. Once you include that into your definition, you end up converging on the standard chosen-plaintext-attack-style definition, since it is the most pessimistic and conceptually simplest way.

If the security definition didn't allow the adversary to influence the choice of plaintext, then every time you used an encryption scheme, you would have to think to yourself: am I absolutely sure that no external entity had any influence over what I'm encrypting? The standard definition gives you a guarantee that you can more-or-less encrypt whatever you want (there are weird edge cases like encrypting the key itself, etc).

Note that quantifying over all possible $m_0, m_1$ is equivalent to giving the adversary choice of $m_0, m_1$. This is because for every $m_0, m_1$, you can consider the adversary whose only strategy is to choose those $m_0, m_1$.

Having the game itself choose the two message $m_0,m_1$ is not equivalent. Such a definition would not rule out the existence of "bad" plaintexts. Consider a scheme that says: "to encrypt $m$, if $m$ is all zeroes then reveal the secret key, otherwise do a reasonable thing." This scheme would be secure under this weaker definition (since all-zeroes $m$ is rare, assuming the message space is large enough), but not the standard definition.

One reason to favor the "adversary chooses" style of definition is that we are already quantifying over all adversaries. We don't need another quantifier.

Actually in other settings (e.g., public-key encryption, poly-time adversaries), the "forall $m_0, m_1$" style is actually stronger! I think this is contrary to your suggestion. Imagine the public key contains $f(x)$ where $f$ is a one-way function. The encryption scheme says "if $m=x$ then give out the secret key, otherwise behave as normal." Quantifying over all $m_0, m_1$ would include quantifying over $m_0 = x$, and the scheme would be deemed insecure. But no poly-time adversary could actually choose $m_0 = x$ (that implies inverting the one-way function), so the modified scheme is equivalent to the original scheme under the "adversary chooses" style, so it would be considered secure.


GHASH with a finite field multiplication algorithm in reverse order NIST SP 800-38D § 6.4 GHASH Function describes the GHASH algorithm thusly:

  Prerequisites: block $H$, the hash subkey.

  Input: bit string $X$ such that len($X$) = $128m$ for some positive integer m.

  Output: block $GHASH_H$ ($X$).

  Steps:

  Let $X_1$, $X_2$, ... , $X_{m-1}$, $X_m$ denote the unique sequence of blocks such that $X$ = $X_1$ || $X_2$ || ... || $X_{m-1}$
  || $X_m$.
  Let $Y_0$ be the "zero block," $0^{128}$.
  For $i$ = $1$, ..., $m$, let $Y_i$ = ($Y_{i-1}$ ⊕ $X_i$) • $H$.
  Return $Y_m$.

The multiplication algorithm works in "little endian" order. Quoting NIST SP 800-38D § 6.3 Multiplication Operation on Blocks, "The convention for interpreting strings as polynomials is "little endian": i.e., if $u$ is the variable of the polynomial, then the block $x_0x_1...x_{127}$ corresponds to the polynomial $x_0 + x_1u + x_2u^2 + ... + x_{127}u^{127}$" (emphasis mine).

So let's say I have an existant multiplication method that operates in big endian order instead of little endian order and that this existant method is significantly faster than the method proposed in NIST SP 800-38D. My question is...  what's the most effective way to utilize this existant method?

The best that I've been able to come up with thus far is this:

  $Y_i$ = reverseEndianness(reverseEndianness($Y_{i-1}$ ⊕ $X_i$) • reverseEndianness($H$))

reverseEndianness($H$) can be precomputed but idk it just seems like there has to be a better way that doesn't require so many endianness reversals idk. I mean, even with the endian reversal (which can be done surprisingly quickly) it's still a lot faster than the method proposed in NIST SP 800-38D but I'd still like to minimize how many are performed.

The reason I have an existant multiplication method operating in big endian order is because that's the order you're supposed to do it in for elliptic curves in $F_{2^m}$. Per SEC 1 § 2.3.5 Field-Element-to-Octet-String Conversion, where elliptic curves are concerned, one should "view the coefficients of the polynomial as a bit string with the highest degree term on the left and convert the bit string to an octet string".

My question is... what's the most effective way to utilize this existant method?

Well, you could rearrange things to take 1 reverseEndianness operation per block, plus 1 reverseEndianness operation per GCM operation (plus 1 per key setup).

  Let $X_1$, $X_2$, ... , $X_{m-1}$, $X_m$ denote the unique sequence of blocks such that $X$ = $X_1$ || $X_2$ || ... || $X_{m-1}$
  || $X_m$.
  Let $Y_0$ be the "zero block" $0^{128}$.
  For $i$ = $1, ..., m$, let $Y_i = (Y_{i-1} \oplus \text{ReverseEndianness}(X_i)) \cdot H_{\text{reverse}}$.
  Return $\text{ReverseEndianness}(Y_m)$.

where $H_{\text{reverse}}$ is the precomputed $\text{ReverseEndianness}(H)$ value.

This is essentially the same as what you had, except we keep the intermediate $Y_i$ values in bigendian format


The security of data traffic over both SSTP & SSL Suppose you're connected to a VPN server via an SSTP VPN, and then you're trying to sign in to your webmail account that is already secured with an SSL certificate, e.g. hushmail.com.

However, it seems your original data traffic is double-encrypted by both SSTP & SSL. Now suppose that for any reason your SSTP connection is hijacked and decrypted by a third party, e.g. the attacker stole your SSTP password or your SSTP-signed certificate is a fake one.

My question is: does the ability to decrypt the SSTP traffic pose any threat to the security of your email communication? I mean, does this hijacking of SSTP lead to decrypting the SSL traffic of your email?

Assuming that the keys used for the SSL and SSTP layers are independent (which they should be, since both layers have their own separate key setup processes), compromising the outer layer (SSTP) cannot make the inner layer (SSL) any less secure than it would be if used alone.

To see why this is, imagine that there was an attack that did allow breaking SSL + SSTP significantly more easily than plain SSL alone.  Then an attacker could break plain SSL just as easily as SSL + SSTP, simply by taking a plain SSL datastream, tunneling it over his own SSTP connection (a trivial operation) and then breaking the combination.  But this contradicts the original assumption that breaking SSL alone would be harder than breaking SSL + SSTP.

For a more detailed analysis, see Maurer and Massey, "Cascade Ciphers: The Importance of Being First", Journal of Cryptology 6(1), pp. 55–61, 1993.


using random encrypted RSA challenge as key material Assume a simple protocol for authentication - one side sends a randomly generated challenge string and encrypts it with RSA.

The receiver decrypts it and replies with a hash of the challenge, proving that he owns the private key (and nothing more).

My question: is it safe to also use parts of the same random challenge to derive encryption keys, e.g. for a symmetric cipher or a HMAC?

If not, is it safe to hash only part of the challenge as proof, and use another part of the challenge as key material?

As concrete example: send e.g. a 2600 bit random challenge, encrypted via 3072 bit RSA-OAEP. Is it safe to hash the 2600 bits (and return the hash to the sender in cleartext) as proof, and use hkdf on the first 128 bits to derive a shared AES key?

If you want to be really sure, you could generate both the reply and the encryption keys from the challenge using a suitable key derivation function, such as HKDF (RFC 5869), e.g. as in:

salt = sender-ID | recipient-ID
PRK = HKDF-Extract(salt, challenge)

reply = HKDF-Expand(PRK, "reply", reply_len)
encrypt_key = HKDF-Expand(PRK, "encrypt", keylen)

Provided that HKDF is instantiated appropriately and that the underlying hash function is secure, it should not be possible for an attacker observing the reply to learn anything useful about the challenge or the encryption key, at least provided that the same challenge is never sent twice between the same parties.  (If you want to eliminate even that minor loophole, include something unique, such as a timestamp, in the salt.)

Edit: Your originally proposed scheme could also be safe, but there are some potential pitfalls.  For example, if you're using the same hash function to generate the reply as for HMAC, and if your challenge is longer than one hash input block, and you're not using any kind of salting to differentiate the two uses, then you could have a problem.

That's because, if the keystring is too long, HMAC will first hash it down to less than one input block using the underlying hash function, and then use the hash output as the actual key.  Thus, anyone knowing the hash of the key would be able to compute the HMAC output just as easily as if they had the key itself.

That's one reason why I'd recommend using a KDF to generate both the reply and the encryption / HMAC keys, with different role strings as I suggest above.  That's exactly what a KDF is designed for.


What characters does AES output? From what I understand after testing the Crypto-JS file here:

http://crypto-js.googlecode.com/svn/tags/3.1.2/build/rollups/aes.js

AES creates encrypted strings that contained letters, both capitalized and lowercase, as well as numbers, division characters, addition characters and equal sign characters.

Do AES encryption strings only contain the characters mentioned above, or can they contain any character from UTF-8?

Thanks in advance. I know this question might seem a bit dumb, but I haven't been able to find the answer after online research.

AES does not operate on or produce characters — it has no knowledge or care of any particular character encoding. AES and other modern block ciphers accept and output arrays of bytes. The same concept applies to the key, and (in block modes that require one), the initialization vector.

How (and if) you choose to encode the output is up to you. For storing in a file or database, there is typically no need to encode the output – byte buffers work just fine. For showing the result to a user, things like hex-encoding are frequently used. For transport mediums that require only 7-bit clean ASCII, you can encode with Base64.

That said, CryptoJS appears to automatically encode outputs with Base64. I question the wisdom of this as a default (along with several others made by the CryptoJS authors), but that's the situation as it stands.


differential and linear cryptanalysis I have been reading about differential and linear cryptanalysis. They were mainly introduced by Adi Shamir and Biham to show weakness of DES. However, many of articles state that they have been considered as a technique to evaluate all other block ciphers. My question is, are they beneficial for public key cryptography? or are they limited to private key schemes ?

They are generally relevant only to symmetric-key cryptography (e.g., block ciphers, hash functions, message authentication codes).  There's no deep reason why -- it's just that differential and linear cryptanalysis tend to be effective against the sort of structure that are commonly used in block ciphers, but not very effective against the sort of designs that are commonly used for public-key  crypto.


PKCS #11 – Deriving a Key where MSB perform encryption and LSB perform CMAC operation? I am using Thales HSM, a PKCS #11 Compliant device. I have an 32 byte AES key and derivation input.

I want to use AES-ECB encryption Mode to derive a 32 byte key where 16 MSB should be considered as one key, and 16 LSB should be considered as an another key. How do I achieve this?

I know that CKM_AES_ECB_ENCRYPT_DATA mechanism and C_DeriveKey PKCS #11 functions allow for derivation of keys using the result of an encryption operation as the key value. But my problem is how do I get 2 separated Keys (16 MSB and 16 LSB)?

This is very much needed for me to implement a System where 16 MSB perform Encryption operation, and 16 LSB perform CMAC operation.

EDIT

I am adding some more inputs to my query here.

Derived_Key = encrypt_Aes_Ecb(Master_Aes_Key, Derivation_Input)

where Master_Aes_Key is a 32byte Key and

Derivation_input = Concatenate(Input1 , Input2)

Both Input1 and Input2 are 16bytes.

My understanding is, if

Derivation_input = Concatenate(Input1, 16B of Zeros)

gives 16MSB of derived Key, and if

Derivation_input = Concatenate(16B of Zeros, Input2)

gives 16LSB of derived_key. Am I correct?

EDIT 2

Sample Input1:

00 00 00 F0 00 00 00 00 00 00 00 00 WW XX YY ZZ

Sample Input2:

00 00 00 0F 00 00 00 00 00 00 00 00 ww xx yy zz

where WW, XX, YY, ZZ , ww, xx, yy, zz would be keep changing always.

Derivation Input: Concatenate(Input1, Input2)
Derived_Key = encrypt_Aes_Ecb(Master_Aes_Key, Derivation_Input)

Now How do I get 16MSB of derived_key as one key used for encryption/decryption, and 16LSB of derived_key as another key used for CMAC operation?

OK so your problem is the following: You have a secure key and want to / can use it only for AES-ECB. You want to extend the security of this key to derived keying material which deterministically depends on some context material. Finally you need to derive a 32-byte key.

Now, one could use NIST SP800-108 (PDF) as guidance and use the counter-based construction. Here you would take the variable parts of your input, put them into the "fixed part" and run a counter for two blocks. So you would take the 8 variable bytes as the 8 most significant bytes to the ECB input and use the lower 8 bytes as a counter. So your input would be WW XX YY ZZ ww xx yy zz 00 00 00 00 00 00 00 00 and WW XX YY ZZ ww xx yy zz 00 00 00 00 00 00 00 01 and the first output block could be used for the encryption and the second for the MAC of the scheme.


Non-commutitive and nonassociative algebraic structures in cryptography Are there any cryptographic algorithms or primitives that have been developed and studied that make use of non-commutative or non-associative algebraic structures such as quaternion integers or octonion integers? It seems to me that many of these structures can preserve the things that make them useful to cryptography (the trapdoor nature of multiplication for example) while removing some of the tools used to attack it (symmetries exploited in commutativity and associativity).
There are several structures that are non-commutative and non-associative that have many features of unique factorization domains, such as Hurwitz quaternions and the 'Cayley' integers studied by Conway and Smith; It wouldn't surprise me to learn there are other structures that have similar properties that are close enough to the integers we're familiar with yet with broken symmetries that make them more resistant to cryptanalytic attacks.
The most obvious utility I can think of is using quaternion or octonion based unique factorization domains in RSA, but many cryptographic systems that use objects like integers I can see being extended to alternative structures. The downside I can see is that some hidden congruence relations that could be exploited don't exist in the integers. Are there cryptosystems that use such alternatives to the integers?

A self-distributive algebra is an algebra $(X,*)$ that satisfies the identity
$x*(y*z)=(x*y)*(x*z)$. There are several cryptosystems that use self-distributive algebras as platforms and these cryptosystems should be thought of as non-associative versions of the more well-known non-abelian group based cryptosystems (such as the Anshel-Anshel-Goldfeld and Ko-Lee key exchanges). Since the current quantum algorithms have nothing to do with self-distributivity, I would suspect that cryptosystems based on self-distributive algebras would be no less secure against quantum attacks than they are against classical attacks.

Cryptosystem 1: This paper by Kalka and Teicher presents a self-distributive algebra based key exchange which is a modifification the Anshel-Anshel-Goldfeld key exchange for groups.

Cryptosystem 2: In this paper, Patrick Dehornoy proposed an authentication protocol which (with some modification) could use any self-distributive algebra as a platform.

Cryptosystem 3: The Ko-Lee key exchange for non-abelian groups extends to a self-distributive algebra based key exchange. Define terms $t_{n}$ for $n\geq 1$ by letting
$$t_{1}(x,y)=y,t_{2}(x,y)=x,t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y).$$
Then $x*(y*z)=t_{n+1}(x,y)*(t_{n}(x,y)*z)$ for all $x,y,z$ and $n\geq 1$. Consider the following key exchange.

  A self-distributive structure $(X,*)$ and an element $x\in X$ are
  public.

  Alice selects some $a\in X$ and $n\geq 1$ and sends $r_{1}=t_{n+1}(a,x),r_{2}=t_{n}(a,x)$ to Bob.
  Bob selects some $b\in X$ and sends $s=x*b$ to Alice.

  Let $K=a*(x*b)$.

  Alice computes $K$ using the fact that $K=a*s$.
  Bob computes $K$ using the fact that $K=r_{1}*(r_{2}*b)$.

Now these cryptosystems just need a suitable self-distributive algebra as a platform.

Platform type 1: racks and quandles. Racks and quandles are among the most well-known self-distributive algebras. Racks and quandles arise from groups, so I would consider these cryptosystems a part of non-abelian group based cryptography instead of non-associative cryptography.

Platform type 2: Shifted conjugacy on braids. Braid based cryptography does not appear to be secure and Dehornoy's authentication scheme for shifted conjugacy has been attacked in this paper.

Platform type 3: Algebras of elementary embeddings. These are the algebras which I have been working on, and there is currently no one else studying these structures. The algebras of elementary embeddings are self-distributive structures that arise from the rank-into-rank cardinals at the top of the large cardinal hierarchy. It is too early to comment whether these algebras of elementary embeddings could be made into secure cryptosystems.

Note: The action of braid groups on quandles could be used to greatly improve the security and efficiency of braid group based cryptosystems.


Relative merits of AES ECB and CBC modes for securing data at rest I need to store several million Payment Card Numbers (PCNs) securely in a mainframe database (that is, 'at rest'). I assume that any attacker will have access to all of the stored data.

I assume the availability of a secure device that can:

Store a unique, constant ('master') key that is to be used for all
PCNs
If necessary, store a unique, constant IV to be used for all
encryption with the master key
Encrypt (AES-256) data in ECB or CBC mode
Decrypt (AES-256) data in ECB or CBC mode

What are the relative merits and demerits of the following possible options for encryption and decryption?:

Use the master key in ECB mode. I have heard/read that this is
cryptographically weak (Why?).
Use the master key and IV in CBC mode.
Prepend a 16-byte, microsecond-or-finer, timestamp to the PCN, then use the master key and IV in CBC mode. This would mean storing an additional 16-byte block of ciphertext, but this isn't a problem. On decryption, just discard the first 16 bytes of the resulting plaintext.
(If available) As (3), but have the device provide a 16-byte pseudo-IV.
Something better (please specify)

Extra kudos for explaining possible attacks on a large quantity of sixteen-digit numbers encrypted under any of these schemes.

I'm new at this, and I know it's very easy for noobs to produce stuff that an average cryptologist would find laughable, so please be gentle -- I'm just trying to learn.

I've placed this here, rather than on security.SE, because it looks like a better fit; if y'all disagree, I shall be most grateful if you will migrate it, rather than closing as off-topic.

For additional clarification, following the answer from @curious :

The reason I include ECB mode here is that it could allow me to save half the storage space. Since the messages are only one block long, I suspect this may affect the 'traditional' arguments against ECB.

But I am interested in understanding whether there are any specific vulnerabilities arising from:

The relatively low entropy of the messages (message space of 1E16 possibilities, reduced by PCN checksums)
The use of a fixed, universal key or key+IV

While I'll try to answer your question at a theoretical level below, I'd like to first stress the following:  It's a bad sign if, in the course of writing software, one is making such low-level decisions about encryption methods.  Encryption security is extremely brittle, with seemingly insignificant details causing complete failure.

With that said, the question brings up some interesting issues with encryption security versus efficiency.

As the other answer notes, ECB reveals when the same block has been enciphered twice and CBC does not (as long as the IV is unique or random).  If you are, for some reason, absolutely sure the same block will never be enciphered, then ECB is in theory fine.  (One technique might be to encipher the blocks in "batches" using a wide-input blockcipher, so that now a ciphertext will repeat only if an entire "batch" repeats.)  But in my opinion this is an unnecessary risk.

Will you ever change blocks of the data once it is written?  This need is one of the distinguishing requirements when dealing with "data at rest" (as opposed to e.g. data being sent over an SSL connection).  ECB, while insecure, will allow you to efficiently change the data in place while CBC will not.  But be aware that the security your are achieving in either case is not ideal.

In general, and especially if local updates are needed, a better technique is to employ a "tweakable block cipher" with the disk location as the tweak.  This will hide repeats amongst different blocks if one uses the block's index (disk location, etc) as the "tweak."  Moreover, it will allow for efficient updates.  This can be combined with the "batching" technique above to provide a level of security that seems pretty strong:  A repeat will only be noticed by an adversary who can watch you change the data, and only when you write the same batch of numbers to the same location twice.  Otherwise the data will be kept private in a strong sense.

It might be help to look at the IEEE 1619 standards documents and associated references for information about tweakable blockciphers and the wide-input batching technique.  The theory outlined there is a long way from a "secure" implementation, and again it seems you probably want to use an existing implementation of this stuff rather than roll own.