Is it worth applying a MAC on data in a HSM? I'm building a basic HSM out of an Arduino, and am using the following scheme to store data:

Master symmetric key $k_m$ stored in firmware (secure bit set to prevent trivial extraction).
Secondary symmetric keys $k_s$ stored as plaintext in web application database, one per user.
HSM record key $k_r$ generated by xor'ing the two keys together computing $AES(k_s, k_m)$, using AES-128-ECB. This means that both the HSM and application server would have to be compromised in order to reveal the key.
AES-128-CBC used to encrypt the data, using a unique pseudo-random IV and the record key.
Each record on the HSM consists of a plaintext record ID, the IV, and a data block.

Is it worth applying a HMAC-SHA1 hash over this data to provide integrity and authenticity checking? If so, what should I use as key material?

Designing an HSM or other secure device is relatively easy; making it reliable even in the absence of adversary requires careful engineering; making it safe against adversaries with some level of physical access is hard; demonstrating that it is safe (for some definition of that) is even harder.

One thing to worry about is integrity of stored data (including keys) w.r.t. to both accidental events and deliberate attacks. One should consider problems often neglected in other embedded developments:

memory writes during power loss, which can leave a data block partially erased or written, in manners depending heavily on technology:

for RAM, it is easy to observe a data block left partially written, with e.g. low addresses holding new data, high address still holding old data;
sometime it can be observed that in between, a word is garbled apparently randomly;
for EEPROM and Flash, the physical erasure before write (typically, with alignment to some page boundary) is often apparent;
with EEPROM or Flash, it might be observable that some memory cells are left in an unstable state where the content read (until another erase or write) will vary randomly, or/and as a function of operating temperature (if you do not trust me on this one, ask the IC vendor to put in writing what it guarantees about what's read in memory that was being written or erased at time of power loss, with rationale at the physical level to support that);

non-deterministic CPU operation, which itself can occurs when operating conditions (e.g. power supply) are non-nominal, and there is no adequate (e.g. voltage) sensors to block operation in these conditions;
cosmic rays; incidence vary enormously with memory technology, capacity, altitude, solar activity, location on surface of earth, and (metaphorically) phase of the moon; search Single Event Upset RAM for references;
deliberate fault attacks trying to cause or simulate some of the above.

Carefully designed and tested measures (software and/or hardware) to deal with at least power loss is a must. Some kind of integrity protection on top of that is a good idea. One option is to substitute AES-128-CBC with AES-GCM; another is to use a separate MAC, e.g. HMAC-SHA1 (if we neglect side-channel leakage issues, it is fine to do this on the plaintext, and probably fine to use $k_r$ as the HMAC-SHA1 key, though $\operatorname{AES}(\operatorname{key}=k'_m,\operatorname{data}=k_s)$ would be more academic and work with any MAC). If that's tolerable from a functional standpoint, moving the HSM to a zeroized state in case of error is the safest from a security standpoint (but zeroization itself requires care; something like "on error detected erase $k_s$", where that erasure is performed in two halves, potentially leaves open to an attack halving the effective key size).


Why did Argon2 win the PHC? I've been reading up on Argon2 (and, to a lesser extent, other recent password hashers). I'm trying to understand why it won the competition versus the other finalists, like Catena, Lyra2, Makwa or Yescrypt.

Unfortunately, I don't see much technical discussion on the competition's website. It does link to the mailing list archives, but I can't find the actual mailing list there (although I haven't tried the NNTP option, since I don't have an NNTP client) due to some broken links. I'm unclear if that's a temporary problem, or a permanent one.

I have two closely-related questions, either of which I would be grateful for insight on:

I've been proceeding under the belief that PHC is a well-regarded and competently run competition that is considered to have advanced the state of the art in password hashing. Was there any notable controversy surrounding it, e.g. serious concerns with the panel, submission or winner selection processes?
What were the key factors that led to Argon2 being declared the winner by the PHC panel, compared to the other finalists?

I have been part of several cryptographic competitions (AES, eSTREAM, SHA-3, PHC). In every single one of them, some people worded bitter reproaches and wailed and whined about the unfairness of the selection process. It's just that people are like that, and being very good at cryptography does not prevent smart cryptographers from being basically people.

The mailing-list was hosted on Gmane, which was a free resource maintained by somebody on his spare time. In July 2016 he decided he had had enough of it (he was fed up with recurrent DoS attacks). The PHC mailing-list archives, though, were recovered and put back online by Alexander Peslyak (aka "Solar Designer", who was behind the yescrypt PHC candidate). You can see for instance the winner announcement there.


How to prove in zero-knowledge that the attributes of Pointcheval Sanders signature is the opening of a commitment? In anonymous credentials schemes, it is possible to anonymously prove knowledge of a signature. Proposals for anonymous credentials with attributes also include a method for proving statements about the signed attributes in zero-knowledge, i.e. proving to a third party verifier that the signed values are the opening of a commitment. For example if I have a credential which is a signature on my current income, it is valuable to be able to prove to a third party that a committed value opens to the same income, without disclosing my actual income.
Reading the Pointcheval-Sanders proposal for anonymous credentials, I cannot find any description for how to prove relations of the signed attributes to a commitment. Is there any publication describing such a procedure?

Quoting the proposal page 10, just before Theorem 8:

..and carries out a zero-knowledge proof of knowledge $\pi$
(such as the Schnorr’s interactive protocol [Sch90]) of $(m_1, . . . , m_r)$ and $t$ such that..

That means introducing protocol responses $(M_1, \cdots, M_r, T)$
for secrets $(m_1, . . . , m_r)$ and challenge $c$
like $M_i = m_i \cdot c + \xi_i$.
Combine responses above and commitment components for Schnorr verification equations.


Can a zero knowledge proof (or MAC) be generated from human-typable input? Edit: My goal is to create a voting scheme that doesn't require a lot of crypto infrastructure to be deployed on the client side.  Smartcards, and tokens are impractical for these purposes.  I envision a user typing a "code" into a web browser (which is imperfect) and submitting the inputs.  The code is either static, or with minimal circuitry that can be covered in epoxy and embedded in a card.
Ideally this code could manifest itself in a way that is non-linkable to the original voter.  I would like these anonymised ballots to be publicly acessible for verification.
If I can somehow "convert" a human typeable code into Microsoft's UProve, then all my requirements would be solved.

Is it possible to create a ZKP (or comparable MAC scheme) that can be typed by a human with relative ease?  What would that crypto system look like?
If I were to design a crypto system around what can be typed easily by a human, say  26 uppercase ASCII letters, or 16 mixed case letters I believe that leaves me with security of 2^92 bits of security.

How should I take this design detail and turn it into something that can be used into a ZKP?

For example, take an ECC key with n bits and simply sign data with my key.  Or use that crypto material in a comparable standard such as UProve or PGP.

The usual way to encode long random bitstrings, so that they can be easily memorized and/or entered by humans, is to break them into blocks of (typically) 10 to 12 bits and map each block to an entry in a fixed dictionary of common words.  This approach is commonly used for secure passphrase generation, e.g. by Diceware, S/KEY and PGP.

Assuming an 11-bit (i.e. 2048 word) dictionary, which seems to be close to the "sweet spot" for English (in terms of difficulty of memorization per bit), you could compute a MAC of the current time using the shared secret key, truncate it to 88 bits and map these to a sequence of eight words for the user to enter.

Ps. The optimal choice of words to include in your list depends somewhat on the use case and especially the entry method you're envisioning.  For typed entry, shortness is important, whereas for spoken entry you want longer words with easily recognizable sounds.
For typed passphrase generation, I've personally found a good starting point to be the set of exactly 4-letter words in any basic English dictionary (which should give you around 2000 to 3000 words, depending on the size of the dictionary), optionally filtered to remove any inappropriate, obscure or confusingly similar words.

Edit: I didn't see your clarification before posting this answer.  Honestly, I'm not sure if the method I describe will help you in your task "to create a voting scheme that doesn't require a lot of crypto infrastructure", but then, I'm not really sure what would, either.  In the answer above, I implicitly assumed that storing the secret key and calculating the MAC would be done by a computer, with only the MAC entry stage being done by hand.  If you want the MAC calculation to be done by a human too, this becomes a very different (and much more difficult) challenge.


How costly is to find millions of large prime numbers for RSA? Consider I need to assign a large distinct prime number to each element in a large set. This must be deterministic so the function always gives me the same prime to the same value.

What is the most efficient way to do this (if there is any).
Would this function work if I need to find millions of prime number to assign them to the set elements.

Btw.: With “large prime number”, I mean the one is usually considered for RSA.

Yes, this is doable.  Here is a construction, built out of several basic primitives:

Let $R$ be a randomized  primality generation algorithm; there are many of them.

It uses randomness, so let's make the bits of randomness it uses explicit as input: $R(c)$ is the output it produces, when given a random number generator that outputs the random bits $c$.
Let $G$ be a cryptographically secure pseudorandom generator: something that stretches a short seed (key) to a long pseudorandom output.  You could use AES in CTR mode, or any stream cipher, for this.
Let $H$ be a cryptographic hash function, e.g., SHA256.

Now, to element $x$, you can assign the prime number $R(G(H(x)))$ to $x$.  It's as simple as that.

This is a deterministic algorithm that will assign a prime to each element, and always assign the same prime to each possible element.  Also, if you generate primes from a large enough range, then the primes will almost surely be distinct.  For instance, if you generate 256-bit primes, then by the birthday paradox, it is essentially guaranteed that all the primes will be distinct (the chances that two different elements $x,x'$ is exponentially small, and negligible in practice).


Correctness in Multi-party Computation: Real/Ideal Paradigm in Malicious case I need to know:

1- What does exactly correctness mean in this context?

2- How is correctness implied in malicious model?

3- If the correctness means " the adversary cannot cause the output to be incorrectly distributed"[1] then it can change the computation result with the correct distribution.

[1].Carmit Hazay · Yehuda Lindell,Efficient Secure Two-Party
Protocols,Techniques and Constructions.

1- $\:$ I believe correctness does not have an exact meaning in this context.

It would certainly involve not letting the distinguisher see the transcript,

and might involve not letting the distinguisher see the adversary's randomness,

and possibly involved not even letting the distinguisher see the auxiliary input.

2- $\:$ [Computational/Statistical/Perfect] correctness is implied by

[computational/statistical/perfect] indistinguishability of the Real and Ideal cases,

since the distinguisher gets to see the honest parties' outputs.


Will using large keys with Classic cryptographic algorithms beat quantum computers? This is a purely theoretical question. Everyone is talking about quantum cryptography being the next big thing as quantum computers will be much faster than the computers we have today.

So, from my understanding, quantum computers will have a much larger computation speed.

My question is, instead of looking for new algorithms to beat the computation speed of quantum computer, why can't we just use huge sized keys to encrypt data?

For symmetric cryptography, it is highly plausible that doubling the key size compared to current practice (say from 128 to 256-bit) provides more than adequate protection against hypothetical quantum computers capable of running Grover's algorithm (or similar) on large inputs. It requires $O(2^{n/2})$ effort for $n$-bit key, compared to $O(2^n)$ for brute force key search on classical computers.

Many asymmetric cryptographic algorithms, including all those commonly used (RSA encryption and signature, Diffie–Hellman key exchange, ElGamal encryption, Schnorr signature, DSA, ECDH, ECDSA, ECIES, EdDSA..) are in principle vulnerable to an hypothetical quantum computer capable of running Shor's algorithm on large inputs, which uses resources and work only polynomial in the number of key bits $n$. That does not work on symmetric cryptography because Shor's algorithm derives the private key from the public key under assumption of arithmetic relations between them, which do not exist between symmetric key and the rest of what an adversary is expected to know in symmetric cryptography. Due to the polynomial growth, demonstrably high security would require impractically large RSA or even ECC keys; this is made quantitative in the two RSA entries of the NIST Post-Quantum Cryptography round 1.

Still, increasing the key size of common asymmetric cryptosystems does increase their resistance to hypothetical quantum computers usable for cryptanalysis. At least, that makes it necessary to use proportionally more coherent qubits, which is a hurdle. We are so far from having quantum computers useful for anything crypto-related that predictions are hard.


Crypto puzzle as proof of randomness? I need an untrusted client to generate a random public/private keypair (in particular, an Ed25519 keypair, which can be generated really fast), but I'm only allowed to see the public key. The randomness is important because the public key is used in attack-sensitive ways such that being able to influence it more than a few bits is a security risk.

I had the following idea:

Create a nonce and send it to the client.
Let the client create a public/private keypair such that hash(public_key + nonce) starts with at least n zero bits and send it back.
If the client returns a public/private keypair after t seconds, reject it.

Is this a correct scheme to ensure randomness of the keypair, given an appropriately chosen n and t?

An alternative:

Client generates preliminary keypair $(t, T)$ with $T=tB$
Clients sends $T$ to server
Server sends a random scalar $n$ back(alternatively choose $n = \mathrm{HMAC}(k, T)$ with secret key $k$), and assigns the public key $A = T + nB$ to the client
Client uses $a = t+n$ as private and $A$ as public key.

That way the server decides the public key, without knowing the associated private key. If the server shouldn't be able to influence the public key either, you can use a commitment scheme that allows mutually distrusting parties to generate a random number.

Your proof-of-work approach doesn't really work since there isn't a good value for the timeout. For typical hash proofs, an attacker can easily have several thousand times the computational power of a defender. GPUs, FPGAs, using cloud computing to rent lots of power for a short time, etc.


Proofs of security methodologies I'm looking for course material on the subject of proofs, reductions, and games, as used to prove cryptographic schemes secure. What are the methodologies? What are the preferred ones? In what cases is it best to use a method rather than another?

The two primary techniques I'm familiar with is structuring a cryptographic primitive as a sequence of games and the universally composable security framework.

Sequence of Games
The idea here is to represent a protocol/primitive as a game played between an attacker and a challenger. You define a bad event and show through the game that the event happens with (close to) some target probability (say 1/2 or 0). For example, if we are modeling an RNG and want to show that the attacker can only guess the next output bit with probability very close to (formally, negligibly close to) 1/2. If they are able to do better than that, then the RNG isn't very good. 1/2 is chosen since there are only 2 choices for the next bit (0 or 1) and they should occur each with probability approximately 1/2 so an attacker who simply always guesses 0, for example, should be right 50% of the time.

The paper I linked to above has some good examples.

UC Framework
This is a framework proposed by Canetti that sees a lot of use in protocols, especially multiparty computation, but is useful in many situations. The UC framework defines a scenario where we have a real world with an environment $\mathcal{Z}$, an adversary $\mathcal{A}$ and an ideal world with the same environment, a simulator $\mathcal{S}$ and an ideal functionality $\mathcal{F}$. In each world, we also have the participant parties $p_1,\dots,p_n$. The setup is pictured below (taken from Martin Geisler's dissertation):

In the real world, the parties execute some protocol $\pi$, in the ideal world the ideal functionality $\mathcal{F}$ provides the same functionality as $\pi$ but is secure by definition (think a trusted, uncorruptable third party). The UC Security theorem says that $\pi$ securely realizes $\mathcal{F}$ in the real world if there exists a simulator $\mathcal{S}$ in the ideal world such that $\mathcal{Z}$ cannot distingush the two worlds. In other words, if $\mathcal{Z}$ cannot tell which world they are operating in, then $\pi$ must be at least as secure as $\mathcal{F}$. But $\mathcal{F}$ is as secure as possible by definition, so in this case $\pi$ is also secure.

Another cool thing about the UC framework is the composability theorem which says that UC-secure protocols can be composed with other UC-secure protocols (including itself) in arbitrary (even adversary controlled) ways and the resulting composition is also UC-secure. Canetti's paper above has examples.

Reduction
A third technique that is often used is a reduction proof. This is very similar to reduction proofs in theoretical computer science. Basically it says we have some problem $X$ which is hard to break (how exactly that is determined is beyond the scope of the answer, but usually it is that a bunch of really smart people have been trying to break it and haven't). Say I have a new cryptosystem and have shown that breaking my cryptosystem is equivalent to breaking $Y$, i.e., if you break $Y$ you can break my problem. Then, if I can show that breaking $Y$ is at least as hard as breaking $X$, then there is reason to believe my cryptosystem is also secure. For example, see this answer.


One-way Functions for Floating Points Are there any commutative one-way functions for floating points?

I tried to explain why I need these functions.
First, I describe the problem on a high level and then I further formalize it;

There are three parties. Alice, Bob, and Charlie.
Charlie wants to check if Alice and Bob have the same value without knowing the exact value except if it is the same. This problem is called the socialist millionaire problem. However, there are four extra additional constraints/requirements in this situation:

There are three parties instead of two. Alice and Bob don't want the other parties to know their values.
The values to be compared are not integers, they are floating numbers.
We would like to know if the values are roughly the same.
There is no back and forth communication possible between Alice and Bob and Charlie. Only two one-way messages. One from Alice to Charlie and one from Bob to Charlie.

More formally,

$x_a$ and $x_b$ are the values of Alice and Bob respectively.
They are represented by floating numbers, $x_a, x_b\in\mathbb{R}$.

Charlie wants to check if the values are roughly the same:  $x_a \approx x_b$.
This can be written as $|x_a - x_b| < \epsilon$, with $\epsilon$, a small positive floating number.

If we would have commutative one-way functions for floating numbers, it could help here to keep the exact values secret.

Alice and Bob would transform their values with the one-way function:
$y_a = f(x_a, k_a)$, with $k_a$, a public key produced by Alice
$y_b = f(x_b, k_b)$, with $k_b$, a public key produced by Bob
Then Alice would share ($y_a$, $k_a$) and Bob would share ($y_b$, $k_b$) by sending a single message to Charlie .

Charlie can then check if $|x_a - x_b| < \epsilon$ by checking
$|f(y_a, k_b) - f(y_b, k_a)|<\delta$, which is equivalent to
$|f(f(x_a, k_a), k_b) - f(f(x_b, k_b), k_a)|<\delta$

Is my assumption correct that I need commutative one-way functions for floating points?

Does anyone know of any commutative one-way functions for floating points?

This would appear to be impossible.

You require that $|x_1 - x_2| < \epsilon$ implies that $|f(f(x_a, k_a), k_b) - f(f(x_b, k_b), k_a)|<\delta$ ; this implies that $f(f(x_a, k_a), k_b)$ is continuous over $x_a$.

Now Charlie knows $k_a, k_b$ and can compute the target value $f(f(x_a, k_a), k_b)$; a simple bisection search over the function $f(f(x, k_a), k_b)$ would allow him to recover $x_a$ (or at least, a good approximation).


Key generation for DH key exchange - benefits of using KMI Context
We need to generate a key pair in order to perform DH key exchange with the other party.
Some suggest to use a KMI solution (think: AWS KMS or like) in order to generate the key pair.
Questions

What would be the benefits of using a separate KMI solution to generate key pair for DH key exchange?
Are there any benefits over on-the-fly generation using a proper library (in this context)?
Would there be any generic reason to keep key pair used solely for key exchange, after the key exchange has been completed?

Using a Diffie-Hellman key exchange is best using keys generated on-the-fly. The reason comes down to a historical issue...
Let's say we contact a web server. The server uses the key pair $S_{pub},S_{pri}$, and out client uses key pair $C_{pub},C_{pri}$. If the web server never changes its key pair, and we don't either, the handshake will always yield the same result. Let's hypothesize, the server could possibly have a hard-coded key pair (web servers and browsers used to have a vulnerability where the DH key pair was literally hard-coded. This has since changed but we don't wanna revert to old mistakes). Now, if I contact 2 web servers with the same keys I will always get the same private key. Thus, now each server can read my communications with the other, assuming they get the ciphertext.
Even if only one side has an unchanging DH key, a compromise of that key would result in the compromise of every message between the parties. However, if the key is generated randomly each time, by both sides, you get a system with perfect forward-secrecy.
However if we want to use an IPS with DPI on our communication, it would allow the IPS to make sure the data isn't loaded with exploits and malware and all sorts of nasties. That's the only reason I can think of to use an unchanging key pair.


Can Grover's algorithm be parallelized? Grover's algorithm can search an unordered list of length $N$ in time $\sqrt{N}$  on a quantum computer. Applied to cryptography, this means that it can recover n-bit keys and find preimages for n-bit hashes with a cost of $2^{n/2}$.
But the basic version of Grover's algorithm is sequential. Each iteration uses the output of the previous iteration as input. I don't see an obvious way to parallelize the algorithm. Reducing the number of iterations significantly reduces the success probability more than linearly.
If the algorithm is inherently sequential, building a bigger computer won't speed up the attack, limiting its impact. $2^{80}$ sequential cipher invocations looks pretty hard to achieve to me. On the other hand, $2^{80}$ parallel cipher invocations is already on the edge of feasibility today using classical computers.
Assume an attacker using a quantum computer is limited to $T$
timesteps with $T<\sqrt{N}$, so they can't run Grover's algorithm with the optimum number of sequential steps. What's the cost for finding a preimage/recovering a key? What is the average cost per-break if they have multiple targets?

We recently discussed this question with some colleagues, and this is what we came up with (no guarantees):
Grover's algorithm only outputs a correct answer if it is fed with an input set such that the target function evaluates as 1 for a single input and as 0 otherwise. The algorithm then iterates a subroutine $\sqrt{N}$ times (where $N$ is the size of the input set) to push the amplitude of the input that evaluates as 1 up. That way, the correct input is measured with a high enough probability (sorry for being vague at this point).
To use Grover's algorithm to attack a hash function's preimage resistance, you select a random subset of inputs and hope that there is one input that is actually a preimage of the target value (I guess a small number of preimages should also be OK, as all their amplitudes should be pushed up and eventually one of these is measured). Now, the runtime of Grover's algorithm depends on the size of the input set $N$. So, we want to keep this $N$ small. On the other hand, we have to select $N$ such that with significant probability there is a preimage in this set. In general, it is assumed that we need to take $N$ in the order of the output size of the hash function to get this probability high enough.
If we want to parallelize this, it should work as follows. Assume we get a quantum computer with twice the number of qubits needed to run Grover with an input set of size $N$. In that case, we can run it on two input sets of size $N$ while still taking only time $\sqrt{N}$. However, the benefits are also only linear, the probability of finding a preimage (or rather the probability of finding an input set containing a preimage) is only doubled.
Of course, we could also run it with an input set of size $N^2$, increasing our success probability exponentially, but this also increases the runtime exponentially.


Does limiting the sales market to U.S. only, releive my application of Export Admin Regs? I have a steganography application that uses one-time-pad encryption. Obviously, key lengths can be very long.

If I were to limit the sales market on the Microsoft Store to U.S. only, would that be sufficient action to relieve the application of any Export Admin Regulation? Or, would it still be subject to other forms of regulation?

Any direction or feedback is appreciated as I find the BIS regulations rather confusing. I'm bureaucratically challenged :)

First, Crypto.SE is not a forum of attorneys, and is definitely not your attorney, and cannot provide legal advice.  So don't make your business decisions on the basis of queer pseudonymous feathery strangers on the internet!

That said, the Bureau of Industry and Security's current web site (archived 2017-11-03 because it changes all the time) claims that ‘open source encryption source code available for free online’ is not subject to the Export Administration Regulations once you send email to crypt@bis.doc.gov and enc@nsa.gov notifying them that you have published it per 15 C.F.R. §742.15(b)(2).

You should always publish your source code, and provide ways for users to verify that it is being used (e.g., let users build it from source, and if you provide a binary distribution, also provide the tools for reproducible builds), because sensible users will reject secret proprietary crypto algorithms and implementations that they cannot study and audit or ask their friends to study and audit.

(Say what you will about the insanity of US crypto export controls, the BIS rules provide additional incentive to do the right thing about publishing crypto source code by giving you mountains of bureaucratic paperwork if you don't.)


How many bits should a token have to be unguessable (given some computational resources)? If an attacker may try 10 billion (1E10) random numbers per second.
And its attack can last 500 years (500*365*24*3600 = 1.5768E10 seconds).

Then the attacker will try 1E10*1.5768E10 = 1.5768E20 combinations.

Now suppose I have 100 billion (1E11) tokens, which are random numbers of n bits.

I want to calculate n so that the probability the attacker finds any token is around 1 in a billion (1E9).

I believe the answer is n = log2(1E11*1.5768E20/1E9) = 73.74 bits.

Questions:

Is this calculation correct?
If instead of independent random numbers the attacker can avoid repeating numbers, how much is n? I guess I should use factorials, and I guess this relates to the birthday paradox, but my mathematics seems to escape me know.
If simply knowing one of the tokens serves as authentication, what is the recommended n for an attacker with a few million dollars available, as of 2017?

Update:

By using the formula in https://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions, with my specific numbers, in WolphramAlpha, I get: sqrt(2*(2^n)*ln(1/(1-(1/1E9))))=1.5768E20.

Wolphram solves for n: n=163.088. I guess this is the answer to my question 2. I think my calculation for question 1 is correct, but since question 2 is the more realistic scenario I am satisfied with that and will close this question.

Well whilst AES can take 256 bit keys, it still only accepts a 128 bit IV. And the width of the AES block is considered secure in 2017. So that would be a good guide.

Also, there are type 4 UUIDs that use 122 bits of uncertainty and are currently in widespread use.  There's not a lot more to say other than to extract this from my reference:-

  Thus, for there to be a one in a billion chance of duplication, 103 trillion version 4 UUIDs must be generated.

Increasing the size to 128 bits would require 8e14 tokens for the same 1 in a billion risk of collision. Should be okay.


Bouncy Castle and Salsa 20 I want to use Salsa 20 in Java, so I downloaded Bouncy Castle, and... it makes no sense to me. I've got it working, but most of my choices were essentially random. But I can't see there anything leading me to the right path. The interface CipherParameters accepts nearly any nonsense and a key size of 257 bits works perfectly.

private static StreamCipher newCipher(byte[] password, byte[] salt) {
    int iterations = 50000; // really?
    PBEParametersGenerator generator =
        new PKCS5S2ParametersGenerator(); // really this one?
    generator.init(password, salt, iterations);
    Arrays.fill(password, (byte) 0);
    final CipherParameters cipherParameters =
        generator.generateDerivedParameters(256, 64); // would 257 be better? :D
    final StreamCipher result = new Salsa20Engine();
    result.init(true, cipherParameters);
}

As I wrote, it works, but is this the right way? Especially,

Is PKCS5S2 with 50000 iterations a good choice?
The password gets stored nowhere, so I'm assuming, the only thread would be an attacker having access to both the plaintext and the ciphertext, xoring them together, and using it for verification of their password guesses. Am I right?
Concerning the practical POV, is there a way how to verify I did nothing seriously wrong (like switching password and salt or using a inappropriate method)?

My code above is a fascinating huge damping pile of... you know.

generator.init(password, salt, iterations);
Arrays.fill(password, (byte) 0);

BC fails to copy the content of the password array, so my security "improvement" of clearing the password after use, clears it before use and leads to a password of all zeros.

Btw., the mailing list was no better than this site. No answer.


Confused about Merkle Damgard Transform - short messages? With the Merkle Damgard Transform, how does it handle messages that are shorter than the input message length - hash digest length? Or in other words, how is the last block handled? So for example, if I have a 40 bit long message and I want to use SHA 256 to get a hash digest, how would I do that? Doesn’t SHA 256 require a 512 bit message and the IV plus my message is only 296 bits? Thanks guys

In SHA-256, the message is padded to a multiple of the block length by appending a single 1 bit and then as many 0 bits are needed to fill a message block to 448 bits; finally the 64-bit length is appended to make the input length an exact multiple of 512 bits.


Differential Privacy: What is the 'game' between data holder and adversary? I have been reading the Differential Privacy (DP) literature for some time to get familiar with it. I feel comfortable with the Math and Stats foundations of it, but I am suffering a bit from the 'setting' of response release.

What I don't get is, the traditional definition of Differential Privacy says that any two neighbors should be indistinguishable from each other under an event. Since this holds for any neighbors and any possible event, all the individuals in the database are 'hidden'. But, what is the setting behind this definition? For example, some potential settings may be (with counter-examples):

We let the user (adversary) send the same query about the true
database at hand (say $D$), and since we have DP, then the true
query will not be able to found by the adversary.
Counter-example: The adversary can ask the same query many times, average responses, and obtain the true query.
We give the user a single response. We also let the user know the true distribution of the additive noise. Then, he can try any possible 'candidate' database, and try to find the true database, but he will fail since the DP definition holds. Counter-example: After we send the response to the user, we should disappear and the user should try figuring out $D$ himself. This does not make any sense. Although, the most convenient mathematical definition to me is "even if the adversary knows the true noise distribution, and just one sample of our response, he won't figure out $D$"
We let the user ask a query only one time, so we never release multiple responses. Counter-example: If this is a one-time thing, then DP definition wouldn't make much sense. We can just sample a standard normal noise, and since we give  a single sample of our response, the adversary won't be able to figure out anything. So DP should be of use in a repeated setting.

I lack knowledge in database systems. I just want to learn, in what setting does the DP definition makes sense? What kind of a game is going on between the data holder and the adversary?

What differential privacy guarantees is that the query output communicates at most $\varepsilon$ bits of information about any individual (row). I now comment on each setting outlined in your question:

Independently repeated queries constitute several distinct releases. There is a straight-forward composition theorem (See e.g. Sect 3.5) that follows directly from the definition of differential privacy. It states that aggregate privacy-loss is at most the sum of the individual privacy-losses of the constituent releases. So, in this case, the results of $k$ repeated queries of an $\varepsilon$-differentially private mechanism taken together constitute a $(k\cdot\varepsilon)$-differentially private release. If the adversary is supplying the queries, a typical mitigation strategy is to enforce query limits. You may also need to worry about collusion.
This is a non-issue. Again, from the definition of $\varepsilon$-differential privacy, one can argue that after observing the contents of the release, an adversary's posterior remains point-wise close to their prior. Specifically, for any candidate "true" database, the ratio of the posterior to the prior lives in the range of $[e^{-\varepsilon}, e^\varepsilon]$. Thus, when $\varepsilon$ is small, this remains close to 1 and the adversary can only negligibly improve upon their initial guess.
This is valid and does not contradict the definition of differential-privacy which, even in this case, ensures that even if the adversary possesses a lot of knowledge of the database, say even all up to a single row, they remain unable to conclude about its presence or absence with certainty.

Just to make sure I answer the question as asked, one formulation as a game is the following: Fix a privacy mechanism, $\mathcal{A}$. An attacker chooses a pair of databases $D_1$, and $D_2$ that differ only by insertion (or deletion) of a single record, gives these to a 3rd party which randomly evaluates either $\mathcal{A}(D_1)$ or $\mathcal{A}(D_2)$ and returns the result to the attacker, without indicating which database was used as input. The attacker knows the exact contents of $D_1$, $D_2$, and is given a full specification of the privacy mechanism $\mathcal{A}$, so that the attacker can independently evaluate $\mathcal{A}$ over $D_1$, $D_2$, or any input of their choosing. The goal of the attacker is to guess whether the provided evaluation is $\mathcal{A}(D_1)$ or $\mathcal{A}(D_2)$.

A good mechanism is one where the attackers success over random guessing is remains small. Intuitively, if the attacker is unable determine the input database from the result even with knowing the complete contents of $D_1$, $D_2$, and being permitted full knowledge of and experimentation with $\mathcal{A}$, it must be that the result carries little information about the row in which the databases differ.


Why would this algorithm be vulnerable to a preimage attack? If I created this algorithm:

Break the message $M$ up into $n$ blocks $m_1,\ldots,m_n$ of 512 bits each.

Compute the hash by alternating AND and OR operations on the blocks. More specifically:

The first block and the second block are combined using AND
The result is combined with the third block using OR
The result is combined with the fourth block using AND
The result is combined with the fifth block using OR
• and so on…

In other words, $h(M) = (\ldots(((m_1 \wedge m_2) \vee  m_3) \wedge m_4) \vee m_5) \ldots )$

Why would this be vulnerable to a preimage attack?

Firstly, remember what is the pre-image attack*;

The pre-image attack is that given a hash value $h$ one need to find an $x$ such that $h = \operatorname{Hash}(x)$. The founded value doesn't need to be the pre-image that is used for the given hash value rather it can be any input value that its hash matches the given hash value, i.e. $x' \neq x$ and $h = \operatorname{Hash}(x')$.

Let call $\operatorname{H}_\ell (M) = (\ldots(((m_1 \wedge m_2) \vee  m_3) \wedge m_4) \vee m_5) \ldots [\vee|\wedge]\, m_{n-2})$ i.e words just before the last two operation. And

$$\operatorname{H}(M) = \big(\operatorname{H}_\ell (M)  [\vee|\wedge]\, m_{n-1}\big) [\vee|\wedge]\, m_n$$

The number of the blocks determines the order of the last two operations, the $\vee$ is the last or $\wedge$.

Now the trick is that

by using  $\wedge$ you can make any bit zero  $x \wedge 0 =0$ and
by using $\vee$ you can make any bit one $x \vee 1 =1$.

Therefore only using the last two blocks - actually using only two blocks - the attacker can create any hash value.

There are much more simple attacks as a note by Fgriue:

$h = \operatorname{H}(h)$
$h = \operatorname{H}(h\mathbin\|h)$ since $h = h \wedge h $
$h = \operatorname{H}(1^n\mathbin\|h)$ since $h = 1^n \wedge h $
$h = \operatorname{H}(h\mathbin\|h\mathbin\|h)$ since $h = (h \wedge h) \vee h $
$h = \operatorname{H}(\bar h\mathbin\|h\mathbin\|h)$ since $h = (\bar h \wedge h) \vee h $

* The formal definition can be found in this seminal work Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton.


Can Secure Multi-party Computation be used to reconstruct secret shares? When using Shamir's Secret Sharing is it possible to use Secure Multi-Party Computation to reconstruct the original secret without revealing one's secret share?

When searching I have found results talking about using secret sharing as part of a Multi-Party Computation scheme. But that is not my question.

Sure you can.

Suppose there are $t$ shares $(x_1,y_1),\ldots,(x_t,y_t)$ hold by $t$ different parties. Recall that in Shamir secret sharing, the secret is the free coefficient in the polynomial. Then to reconstruct the secret, the parties need to compute jointly:

$$L(0) = {\sum_{j=1}^{t}} y_j \cdot l_j(0)$$

where

$$l_j(0) =\prod_{\begin{smallmatrix}1\le m\le t\\ m\neq j\end{smallmatrix}} \frac{x_m}{x_m-x_j}$$

Usually $x_1,\ldots,x_t$ are public, so all parties can compute all $l_j(0)$ locally. Then what they need to do is to share $y_j$ among them and compute $L(0)$ securely using generic secret sharing based MPC.


How to correctly pad by PKCS#7 for AES? I want to implement AES-CBC mode with PKCS#7 padding, along with a way to validate a correct padding given the ciphertext. My initial understanding was that for an input of size n (where n is less than 16) PKCS#7 pads 16-n until the input becomes divisible by 16 (or equal to 16 in this case). But later I realized that this would make it impossible to validate a correct padding.
Then I found out that you always pad at least 1 byte when doing PKCS#7 padding (with byte 01 if length of input is divisible by the desired amount). Is this understanding correct? If so, should I divide my input into blocks with size of 15 bytes (with 16th byte being the pad byte)?

Then I found out that you always pad at least 1 byte when doing PKCS#7 padding (with byte 01 if length of input is divisible by the desired amount). Is this understanding correct?

Actually, if the input was already a multiple of 16 bytes, the padding would consist of 16 10 (hex) bytes, which you would append to the end of the input.  Then, the padded input will then be a multiple of 16 bytes (which, with this padding method, is always the case, even if the original input was an odd length).

If so, should I divide my input into blocks with size of 15 bytes (with 16th byte being the pad byte)?

No; you need to add padding only to the end of the message - there is no reason (or permission, as far as PKCS#7 is concerned) to add padding to the intermediate blocks.


Is SHA-256 OK to use for key derivation for a key that is never persisted? The scenario: On the one side a user enters a pass phrase to encrypt a stream of data (AES-GCM) and a symmetric encryption key is derived from the pass phrase using plain SHA-256 (so not a slow function). Data is sent using TLS. On the other side another user has to enter the same pass phrase to derive the same key for decryption. If the key is never persisted, does it matter that a fast key derivation function is used?

In Key derivation functions, you enter a secret that is your password, salt, and the number of iterations.

$$key = \operatorname{KDF}(\text{passowrd}, \text{salt}, \text{iterations})$$

The salt is a countermeasure against the rainbow table attacks. The salt also increases the entropy of the produced key. Since the attackers cannot use a rainbow table, they have to use execute password search, the most popular is hashcat where it can utilize GPU's cores. This where the number if iterations become important. If a fast key derivation is used then the password search will be very fast. Think about the usual 10000 iterations vs 1.

In your case, you even didn't mention the salt. Without the salt, a SHA-256 rainbow table can easily find the password if it exists in the table.

As mentioned in the comments, by F.Grieu; The modern Key derivation functions has more parameters. For example; Argon2 has also memorySizeKB and parallelism parameters as a countermeasure against GPU and ASIC based passwords search attacks. Without these parameters, the GPUs and ASICs can search the passwords massively in parallel process.

An 8x Nvidia GTX 1080 can calcaulte 2865.2 MH/s SHA-256 hashes.

You should use the Scrypt or Argon2, the winner of Password Hashing Competition.


What is the reason for length differences in RSA? In NIST FIPS 186-4, "digital signature algorithm", the minimal length allowed is 1024 bit (page 22). On the  contrary, in NIST SP800-56B, page 63, RSA-OAEP encryption, the minimal length is 2048. Why 1024 is secure enough for digital signature but not for encryption?

Three reasons:

Technical: often the integrity and origin of a piece of data becomes immaterial after the data is acted upon; and for long-term use (e.g. document signing), if the security of the signature becomes questionable, there is often the option to stop considering the key valid, and make a new signature with a larger key size, restoring security. When for encryption (one of the common goal of key establishment), we can't make the ciphertext disappear from the adversary's archive. Therefore, at any given time, we arguably need less security margin (smaller RSA modulus) for signature than for key establishment targeting long-term confidentiality.
Scope: my reading of NIST's FIPS 186 standard is that it specifies modulus sizes mostly for interoperability purposes, with security level not in the core scope; when NIST SP 800-56B is a recommendation with security level in scope. At least, only the later includes comparison with symmetric cryptography key sizes.
Historical: FIPS 186-4 (July 2013) is a standard with a long history, with RSA included in FIPS 186-1 (December 1998) which as RSA is concerned essentially approved a subset of ANS X9.31, with minimal key size set to 1024-bit for both; that size then made a lot of sense. When NIST SP 800-56Br1 is more recent (September 2014), revising earlier NIST SP 800-56B (August 2009) which still allowed 1024-bit RSA.


What is a “witness” in zero knowledge proof? I've seen the term "witness" tossed around when talking about knowledge extractors, but I have no idea what it means. I can't find a definition.

What is a “witness” in zero knowledge proof?

A witness for an NP statement is a piece of information that allows you to efficiently verify that the statement is true. For example, if the statement is that there exists a Hamiltonian cycle in some graph, a witness would be such cycle. Given a cycle, one can efficiently check whether it is a valid Hamiltonian cycle, but finding such cycle is difficult.

Knowledge extractors are used in the definition of proofs of knowledge. There, you don't just prove that some statement is true, but that you know a witness for this statement. A machine knowing something is defined via the existence of a knowledge extractor that, roughly speaking, interacts with the machine and then output the (extracted) witness.


Two party protocol using only hash function I have been told by my professor to compare two passwords as we do it in Yao's two-party protocol but without using any crypto functions. We are only allowed to use a hash function. The passwords are taken from the dictionary so we can't even send the hash of that word as we can't risk a dictionary attack.
I am thinking of changing the alphabets to ASCII code and then pass it down the garbled circuit using Yao's protocol but don't know whether it will work.
Any suggestions? Thanks

That is impossible (at least as I understand your question) because:

The ability to privately test whether two strings are equal (even if just 2 bits, even with security only against semi-honest parties) implies oblivious transfer. (Kilian: A general completeness theorem for two party games)
It's impossible to realize oblivious transfer from hash functions alone. More formally, the "Minicrypt" model is that all parties have access to a random oracle and are computationally unbounded -- this model captures all the things you can get from one-way functions, hash functions, "without any other stronger kinds of crypto." Oblivious transfer is impossible in Minicrypt. (OT implies all secure function evaluation which implies key agreement which is impossible in Minicrypt: Impagliazzo-Rudich Limits on the provable consequences of one-way permutations)


What is the official, generally accepted definition of "lightweight crypto"? I frequently stumble upon the term "lightweight crypto". It tends to be used is a for special algorithms that use less resources, for constrained systems. Yet, it's somewhat unclear to me where to draw the line between "regular algorithms" and "special algorithms".
Since even some well-known cryptographers use the term "lightweight cryptography", I assume there must be an official, generally accepted definition for it. Yet, I fail to find it... since every source I trace down seems to define the term a bit different. For example: some even put AES into the basket when they were able to make it run on some limited-abilities piece of hardware, while others explicitly exclude AES from the lightweight crypto group. Same for ChaCha20, etc.
To avoid confusion, knowing the official definition (and maybe even having a reference to point to) would definitely help.
TL;DR
What is the official, generally accepted definition of "lightweight crypto"? And where (reference) is it defined?

There is no official definition, of course. However, at least in my experience, the word is used consistently.

The word lightweight typically refers to something that is significantly less expensive to use than other stuff, while at the same time achieving the same desired effect, but this lightweight-ness has some cost. (If there was no cost to lightweight-ness, it would not be lightweight, but just "better".) This means that the lightweight stuff may be desirable in some situations, but not in others.

Typically, a lightweight block cipher will be amenable to implementations that are small or use little power or ..., compared to the usual block ciphers. This happy state is achieved at some cost, perhaps by reducing the security margin or having more rounds, etc.

Note that people may talk about lightweight public key cryptography, but it is lightweight only when compared to ordinary public key cryptography, not compared to other kinds of cryptography such as block ciphers.

People also talk about lightweight implementations of cryptographic primitives. Again, lightweight refers to some reduced cost, typically achieved by increasing some other cost. People may be interested in an AES implementation with extremely small gate count, for instance, even if it would be slower or use more power than other implementations.

The word lightweight is of course not limited to cryptography, but is used everywhere, with somewhat differing meanings. Consult your dictionary. In technical contexts, it usually has positive connotations in my experience.


IND-CPA security of mode of operation using triple AES with plaintext || IV+counter I have found this figure of a mode of operation using a triple AES with m||IV+ctr input:

I suppose it's a custom mode of operation since I haven't seen it anywhere else. My question is if it is IND-CPA, and how to prove it in an adversarial model?

Seems to me that if you just look at the first layer that uses K1 that you can already show that it is CPA secure. After all, if the IV is always unique then $M_n \| IV + n - 1$ is always unique in this scheme. So then the input to the $\text{AES}_{K_1}$ block cipher is also unique. This makes the scheme have the same properties as the key stream of Counter Mode, with $IV + n - 1$ is the counter.

So unless $K_1$ is reused within the scheme, the scheme must be secure - regardless of any other encryption operations.

Now one thing to notice with the above reasoning is that I've proved it to be secure given key $K_1$. If you expect it to have a security of the 3 keys together (e.g. 128 x 3 = 384 bits for AES-128) then you may need to read up on meet in the middle attacks. At most the security will be 256 bits - that is if we don't put any constraints on memory usage. That's a separate security issue than IND-CPA though.

Of course, when it comes to practicality, this is one of the worst schemes you can think of. The number of key bits and operations is tripled to achieve additional security of about two times specified. More importantly, you'd also need more encryption operations as the IV takes away message space from each message block. The ciphertext also expands with the same factor.


Alert protocol in TLS Assuming the alert protocol is encrypted AFTER a session has been established and the structure below, how does the client know whether to expect encrypted data or not?

http://en.wikipedia.org/wiki/Transport_Layer_Security#Alert_protocol

Switch from plain to encrypted is marked by a special record type called change_cipher_spec (which is neither handshake, alert or application_data); it is unambiguous. Plus, the moment the switch occurs is quite clear from the client point of view, given the previous handshake messages.

If unsure, have a look at the actual standard, which is quite clear (for a standard). This answer can serve as an introduction.


SHA1 collisions and the impact for ECDSA signatures What will it mean for ECDSA using SHA1 when we have practical attacks breaking the collision resistance property of SHA1?

[UPDATE] Added a bit more details to be clear.

If $(r,s)$ is the ECDSA signature for $m$, is it possible to give a different message $m'$ that will have the same signature.

The problem is that, imagine you sign a message $m$ using ECDSA and SHA-1 as hash algorithm. If an attacker manages to find a message $m'$ such as SHA-1$(m)$ = SHA-1$(m')$ then the computed signature for $m$ will be valid for $m'$.

So the attacker can substitute $m$ for $m'$ while keeping the same signature value. The receiver who will try to validate the signature won't be able to tell the difference.

[UPDATE]
Let's explain it in details:

So when signing a message $m$ using ECDSA algorithm with SHA-1 hash function, according to wikipedia, it goes this way:

We compute $e =$ SHA-1$(m)$
Calculate $r = x_1\,\bmod\,n$ (where $(x_1, y_1) = k \times G$, $k$ is a random integer from $[1, n-1]$ and $n$ is the order of the elliptic curve)
Calculate $s = k^{-1}(z + r d_A)\,\bmod\,n$ (where $d_A$ is the private key signature and $z$ the $L_n$ leftmost bits of $e$)
The signature is the pair $(r,s)$

So if an attacker finds a message $m'$ as SHA-1$(m')$ = SHA-1$(m)$ then $e' =$ SHA-1$(m') = e$ and then $z' = z$.
So the signature $(r,s)$ will be valid for the message $m'$ even if the attacker doesn't know the private key $d_A$ because all computations have been done for him.

Note that in this case the attacker needs a valid signature and to find a second pre-image to forge a signature.

An interesting comment from Ilmari Karonen:

  There are practical scenarios where both $m$ and $m'$ may be
  controlled by the attacker, in which case a collision attack suffices.
  For example, the MD5 collision attack was used to forge SSL
  certificates by getting an established CA to sign an innocent-looking
  certificate, and then replacing it with another certificate with the
  same MD5 hash, but far higher privileges.


Computational Cost of bilinear maps What is the exact computational complexity in absolute operation numbers (multiplications, exponentiations, etc) of a bilinear map evaluation both for symmetric and asymetric groups. And how this is comparable with exponentiation?

This question can't be answered exactly, because it depends on a lot of the actual details of the realization. But as a rule of thumb: They cost a lot. In fact they cost so much, that in any protocol they are the sole determinator of the computation time and you can neglect the other operations.

First, keep in mind that usually bilinear maps are realized with elliptic curves. There is no straight forward bilinear maps in $\mathbb{F}_p$, which can be used for cryptographic tasks. Currently the only known constructions for (cryptographically useful) pairings are:

Weil pairing
Tate pairing

So first we need to consider the elliptic group operation, where the number of operations (addition, multiplication, etc.) can vary. Looking at the definition of the Weil pairings, we soon get to the following conclusion:

There is an integer $n$, which is chosen at the setup, but its role isn't that clear to begin with.
There is a function $F$ (on values $P,Q$), which just has to fulfill some property, but isn't specified any further. But the definition of the divisor has a sum, where the number of addends are linear in $n$, so the compuational complexity of $F$ will depend somehow on the choice of $n$.
The function definition $w(P,Q):= F/G$ has the $n$-th roots of unity as its image. Thinking of the bilinear map, this is the target group. And for cryptographic purposes we need a group where the discrete logarithm is hard in the target group, so we can conclude that $n$ has to be large.

This already shows, that unless you specify exactly what kind of elliptic curve and which kind of Weil pairing (or Tate pairing) you have, you can't state an explicit number of operations.

For further information I would suggest reading Pairings for beginners from Craig Costello, which also has plenty of examples with numbers.


How can a derived key be verified to be the right key? Assuming I am using some derivation function to generate encryption key from the string to encrypt a file. How that string is later verified during decryption?

If user enters wrong password/string, why system / app doesn't decrypt entire file resulting in incorrect clear text? What mechanism is behind the scene?

It depends on the protocol, there is not one way of handling this.

If a symmetric cipher does not provide integrity protection or message authenticity (through a MAC calculation) then it may well be that the decrypted plaintext is not correct.

Usually we try and use an authenticated cipher like GCM to avoid such problems. In that case the verification of the authentication tag fails and the file is not decrypted.

If the ciphertext is large it may be a good idea to create a separate MAC over some known information and include it with the ciphertext. That way the validity of the key can be determined without having to decrypt the entire message. It may also help detecting that e.g. the decrypted file isn't fully present in it's original form. It seems wasteful to perform the full verification of the ciphertext in case a wrong password is provided, and it makes no sense to have more security for large files as for small files in case an adversary tries to find the password.

Note that above trick is basically an enhanced version of a Key Check Value, and the usefulness of KCV is debatable. There is no good way of distinguishing between a bad password and an altered ciphertext. Even if you include an additional MAC with the ciphertext, then that MAC value may be altered as well.

Obviously providing a signature over the ciphertext may also work. You must make sure that the public key of the sender is trusted by the receiver, otherwise signature verification is useless. Do note however that other trusted parties - if any - could remove the signature and sign the file themselves.


POODLE attack on TLS 1.2 The POODLE attack uses the way block ciphers in CBC mode are decrypted in combination with the packet's padding to determine some byte's value.

From what I understand, even TLS 1.1 can be vulnerable (when using a suite such as DES with CBC). Why aren't other cipher suites that use CBC vulnerable?

From the following table it looks like CBC mode is still used in some cipher suites in TLS 1.2.
https://en.wikipedia.org/wiki/Transport_Layer_Security#Cipher

The table states that TLS with AES in CBC mode is secure. Is this true? And why isn't TLS 1.2 vulnerable to POODLE?

POODLE is primarily a padding oracle attack against SSLv3.0, which is inherently vulnerable to the attack due to the protocol design. The "on downgraded legacy encryption" part of POODLE's name comes from the fact that most SSL/TLS client implementations will allow a TLS connection to downgrade to SSLv3.0 if the handshake fails - see this answer for more detailed information around TLS downgrade attacks. Since an attacker in a man-in-the-middle position can simply drop or mangle packets, it is relatively trivial to cause a TLS connection to downgrade to SSLv3.0, which then becomes vulnerable to the padding oracle attack against CBC.

SSLv3.0 only validates that the padding byte length is ok, and doesn't require the actual padding bytes to be checked for validity; they can be anything, as far as the protocol specification is concerned. Furthermore, the padding is not authenticated; it uses a MAC-then-CBC method. The padding oracle attack works by causing the padding data to move across a block boundary (this can be done by increasing the plaintext length until the ciphertext length increases by one block) and then swapping out the padding block for any previous ciphertext block. If the decrypted result has a final byte of value equal to the expected padding length, it will be accepted, which leaks the value of a single plaintext byte. As the process is non-deterministic due to the random IV per connection, it should take at most 256 connections to leak each byte. The attacker can then shift the position of the target plaintext within the connection by one byte and attack it again, repeatedly testing via the oracle and shifting across until all target bytes have been revealed.

The normal recommendation for POODLE where SSLv3.0 cannot be disabled entirely is to implement TLS_FALLBACK_SCSV support. As this answer describes, this flag forces the negotiated connection to use the highest possible supported protocol version, which is mutually authenticated by the use of exchanged Finished messages, thus preventing downgrades outright.

There is a secondary variant of POODLE which works against certain implementations of TLS, instead of just the SSLv3.0 protocol. The key point here is that the vulnerability is not inherent to the TLS protocol at all, but rather is exploitable only in cases of poor implementation. The reason that sensible implementations of TLS (see note below) are protected against POODLE is that the CBC padding is fully validated at the server side (i.e. all padding bytes must be equal in value to the integral size of the padding, and the server must check this fact). This makes attacking the padding significantly more difficult. However, it was found that some implementations of TLS did not check the padding correctly, and were still vulnerable to POODLE.

(note: the TLSv1.0 specification does not state that padding must be checked; this requirement was introduced in TLSv1.1 and continued in TLSv1.2. As such, TLSv1.0-compliant implementations may still be vulnerable to POODLE, hence why I used the term "sensible implementations" rather than "compliant implementations" above.)


Which precautions to protect against side-channel attacks on ARX ciphers? In recent crypto there has been a trend to design ciphers using only the ARX set of instructions - i.e. additions (modulo $2^{32}$ or $2^{64}$), rotations (by a fixed constant) and XORs, examples include Threefish, Salsa20 and ChaCha20.

One of the nicer, claimed properties of such ciphers is that they are supposedly easier to implement in a side-channel resistant fashion.

Assuming one would want to implement Threefish (on a multitude of architectures such as ARM, x86 and x64), which precautions does one need to take to avoid side-channel attacks for such implementations? And are there any precautions which would be applicable to ARX designs specifically? If, which precautions against side-channel attacks can/should be taken?

What I don't count here: attacks that would work by exploiting unproperly erased/freed memory. I'm looking for the standard cryptographical side channels: cache-timing, "normal" timing and maybe (differential) power (/EM) analysis.

What I would consider "pre-cautions": any code solely intended to defeat side channel attacks while not being documented in the original specification (which usually gives only a mathematical approach).

Side channels

Essentially, side channels tell something about the secret data by using properties (e.g. timing, power consumption) of the algorithm itself. If an algorithm executes in a different way for different messages/keys, the attacker can deduce information about the message/key from the properties of the execution.

Even if the attacker only gains a little information about the key in one execution, they can do statistical analysis on arbitrary many measurements and thus still get a lot of information.

Where I come from I have learnt that you must assume that the attacker:

Can query the device an arbitrary amount of times with their own chosen messages/ciphertexts.
Knows every instruction (and branch) as they are executed  (by using timing attacks/power traces).
Knows the execution time of every instruction (by using timing attacks/power traces).
Knows every address that is looked up during the execution of the algorithm (by using cache timing attacks).

Solution: All crypto algorithms must run deterministically. In other words:

Do not branch on secret data.
Do not do any memory lookups dependent on secret data. I.e. you can do memory lookups, but only if the algorithm does exactly the same lookups each time it executes.
Only use instructions that execute in constant time. (For example, div-instructions often do not execute in a constant amount of cycles.)

ARX ciphers

ARX ciphers limit themselves to only three basic operations which all run in constant time on pretty much all platforms. Because of their design, there are not really that many precautions to be taken, as long as you adhere to the rules above.

But know that, while you will be ok most of the time, it just really depends on the implementation and on the platform. As Squeamish notes: hardware implementations of ARX ciphers can just as easily be vulnerable against DPA/EM attacks, even if you follow all the rules above.


Representations of secret keys on Curve25519 https://tools.ietf.org/html/draft-josefsson-tls-curve25519-06#appendix-A.2 gives the following as a secret key / public key combo:

         S_a = 0x6A2CB91DA5FB77B12A99C0EB872F4CDF
                 4566B25172C1163C7DA518730A6D0770

         P_a = 85 20 F0 09 89 30 A7 54 74 8B 7D DC B4 3E F7 5A
               0D BF 3A 0D 26 38 1A F4 EB A4 A9 8E AA 9B 4E 6A

https://tools.ietf.org/html/rfc7748#section-6.1 gives another secret key / public key combo:

Alice's private key, a:
  77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a
Alice's public key, X25519(a, 9):
  8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a

Note how the public key is the same for both but the secret key is not.

sodium_crypto_box
_publickey_from_secretkey seems to concur with the RFC but not the IETF Draft:

https://3v4l.org/i61aE

My question is...  what is the RFC doing that the draft is not?

I ask because I have an implementation that is giving me the correct public key from the secret key in the IETF Draft and I'm wanting to make it so that I can use that same implementation to get the public key from the secret key in the IETF RFC. But, more than that, I'm just curious.

Thanks!

I'm pretty sure this is an endianness issue.  Specifically, taking the S_a value from the Josefsson draft and reversing the order of the bytes (i.e. pairs of hex digits) in it gives:

70076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c6a

which is almost the same as the value of a given in RFC 7748 § 6.1.  In fact, XORing the values shows that they differ at only four bits:

  70076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c6a
⊕ 77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a
------------------------------------------------------------------
= 0700000000000000000000000000000000000000000000000000000000000040

The remaining difference seems to come down to canonicalization; in particular, RFC 7748 § 5 says (emphasis mine):

  For X25519, in order to decode 32 random bytes as an integer scalar, set the three least significant bits of the first byte and the most significant bit of the last to zero, set the second most significant bit of the last byte to 1 and, finally, decode as little-endian.

The S_a value given in the Josefsson draft appears to have this canonicalization correctly pre-applied (after accounting for the byte reversal, that is), whereas the a value in RFC 7748 § 6.1 has the three least significant bits of the first byte set to one, and second most significant bit of the last byte set to zero.

Alternatively, one could simply interpret this as a from RFC 7748 § 6.1 being the raw input sequence of 32 random bytes (written as 32 pairs of hex digits concatenated together), whereas S_a from the Josefsson draft is the corresponding 256-bit number (written as a hexadecimal integer literal) obtained after those random bytes have been canonicalized as described above and decoded in little-endian order.


KDF-based password manager I want to make a password manager that from a single master password generates passwords for my services. For that I thought that HKDF suits my needs, as it is able to generate multiple keys from a single strong key.
Here I read that HKDF is secure if the key is "good" which password aren't. So I thought about using PBKDF2 to generate the key to be used with HKDF.

Is this design good?

master_key <- PBKDF2(master_password, ...)
service_key <- HKDF-Extract(master_key, ...)

How would I then handle salt? It should be random, so it should be stored somewhere. Can I store it anywhere? Can I use the same salt for the two phases?

EDIT: I think I should add a clarification.

The reason why I would do this is to have a way to have my password wherever I am without the need to have on every single device I am using the database file (I've used keepassx for a while and that was frustrating, because you then need to handle syncing and such). This way the user is required to remember only the master password (and the salt?) and perform the calculations with a specific tool.

What you describe will work once, and it will be fine to use one salt, which need not even be secret as long as it's different from everyone else's salt.  Just derive each service password from the same master key with a different HKDF info parameter.

But what happens when a site's password database is breached, and turns out not to have been hashed, and you need to generate a new password for the site?  What happens if a site imposes restrictions on the character set, length, or structure of the password?

See Tony Arcieri, ‘4 fatal flaws in deterministic password managers’, blog post, 2016-11-22 for further discussion.  (The title should perhaps have been about stateless password managers rather than deterministic ones.)


Enc-Mac (AES CTR+CBC) mixing AES-256 and AES-128 and splitting keys I'm looking to accomplish a Enc-then-Mac approach using
AES-CTR
and
ECBC-MAC

Now ECBC-MAC requires 2 distinct keys, one for the MAC, and one to encrypt the Tag.

If I do this:
Use AES256-CTR for the encryption.
Then split the AES256 key into 2, and use each 128 bit key to do
AES-128-CBC-MAC
and
Encrypt the Tag using AES-128.

Is this semantically secure? Or do I definitely need 3 distinct keys?

Don't share keys (or derive new keys with a simple method like splitting the original key) for different purposes. If you can't generate truly seperate keys, get a "master key" and derive two keys for encryption and MAC with a strong hash function.

Sharing a key for encryption and authentication with ECBC-MAC is really bad. Splitting the key to generate new ones sounds insecure, but it could also be secure - do you know it? In any case your scheme will break totally if an attacker learn either your encryption or MAC key. That itself is already bad, but with your scheme it's really simple to get the respective other key, compromising both.


How do you communicate the hash function used with RSA signing? When it comes to RSA signing, I understand why you need to hash the data before signing it, but don't you need to communicate what hash algorithm you use to whoever will need to verify the signature? How does that normally work? How do you communicate the hash function used with RSA signing?

Normally, yes, the hash algorithm in use is communicated beforehand.  For example, sending an algorithm identifier during the TLS/SSL handshake process.  However, depending upon the "padding scheme" in use with RSA, it may be possible to determine which hash algorithm was used from the signatures themselves.

Some padding schemes encode information specifying the hash algorithm that was used to generate the hash into the padding data.  "PKCS #1" is possibly the most well-known padding schemes that does this.

When data is signed in this manner, you can determine the hash algorithm used to generate the hash by decrypting the signature--taking it to the power e--then examining the data.  This check must be done carefully, because otherwise you might cause security breaks (Nintendo Wii comes to mind).

In PKCS #1, you take a hexadecimal representation of the hash, shown here in big-endian form, and prepend padding to the front.  The format of PKCS #1's padding is like this:

00 01 FF FF FF ... FF FF 00 <der> <hash>

(FF's are added until the entire byte string is the length of the RSA modulus.)

The <der> is an ASN.1-encoded identifier of the hash algorithm unique to that algorithm.  For example, the following identifier represents SHA-256:

30 31 30 0D 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20

Thus, the following would be a 768-bit big-endian signature block of an empty string, using SHA-256:

00 01 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF 00 30 31 30
0D 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20
E3 B0 C4 42 98 FC 1C 14 9A FB F4 C8 99 6F B9 24
27 AE 41 E4 64 9B 93 4C A4 95 99 1B 78 52 B8 55

If you saw this string, you could determine the hash algorithm by checking for the 00 01, followed by a string of FF bytes, then a 00 byte.  Following it should be a known hash algorithm's DER, then the number of bytes present in that algorithm's digest, then the end of the block.  If all of these exactly match, it is a possible signature, so you could then use that hash algorithm to verify that the data matches.

Just make sure that you only allow hash algorithms that you approve of.


Small values with non-uniform distribution encoded as large values with uniform distribution Given a non-uniformly distributed set of 32-bit values (for example), is there a way to reversibly encode each one as a 128-bit value (for example) where they'd be approximately uniformly distributed in that larger 128-bit space?
Block ciphers do this as I understand it but they require a key and are computationally expensive due to security concerns. If I didn't want security, just the property of approximate uniform distribution and increased size, is there a more efficient way?

LFSR based
Since you want some simple not necessary secure than here one solution based on the LFSRs.
Let assume that each of your inputs has a length of 32-bit. Now, choose a maximal binary LFSR of length 128 ( yes not 32). Fill the LFSR's first 96-bit with 0s and the last 32 with your data. Now, run the LFSR $x$ times where $x>128$. Now take the next 128-bit as the mapping of 32-bit to 128-bit.
Maximal LFSR's with length $L$ generates all binary sequences of length $L$, except the all-zero case, in their periods. Your data will be the starting point on the sequence of length $2^{128}-1$ and the values will be not the same.
You can get your value back by running the LFSR in reverse. This is easy since you know the tap points. Otherwise, you will need 256-bits to construct the LFSR with the Berlakamp-Massey algorithm.
OTP based
A more simple solution based on OTP;
Generate a random 128-bit, and x-or you inputs by repeating 4 times. You did not want security, and this can map your input into 128-bit random. You can get your value back by x-oring the 128-bit key and taking the first 32-bit.
Block cipher based
Block ciphers are a family of permutations and with a fixed key, you select only one permutation from the family. Otherwise, selecting a random permutation and storing is infeasible, you need $2\cdot 2^{128}$ space to store. With the key, you can transfer back and forth. Also with the expected PRP of the block cipher, you can achieve good randomness, too.
AES is quite fast, especially with AES-NI can reach GB/s. Fix a key and use AES. This is quite easy since you can use OpenSSL tools to achieve this.


Where do key generation algorithms take the randomness from? I was just wondering, because in many encryption tools like Veracrypt or GnuPG you have to generate pseudo randomness with your mouse movement. So, where do automatically generated keys take that randomness from? For example, when you generate a RSA certificate with OpenSSL.

Applications that generate key get the randomness (entropy) from the operating system. The operating system, in turn, gets the randomness where it can find it. Ideally the OS gets randomness from a proper hardware generator, which is present in modern PC and smartphone processors. These hardware generators are based on physical phenomena that are not reproducible; a variety of techniques exist. Additionally, the OS accumulates randomness through the timing of user actions (such as moving the mouse), of network packets, of disk reads, etc. White noise from a microphone or camera can also provide randomness. The difficulty with such ad hoc sources is that it's difficult to estimate how random they are: a hard disk's timing is predictable in theory (and an SSD much more), a given user tends to act in broadly similar manners, a sensor may be saturated, etc. This is why a dedicated hardware generator is preferable, assuming that it's programmed and used properly.

Hardware randomness sources are never used directly, because they tend to have strong biases: they don't come in neat bits that have an even chance of being 0 or 1. The randomness is fed through a cryptographic algorithm called a pseudorandom number generator (PRNG) which produces a practically endless stream of uniformly random bits from a small amount (hundreds of bits) of entropy.

Operating systems have a useful tool to reduce the expense of collecting entropy: entropy doesn't wear out, so it can be saved and reuse. An operating system can save the state of the random generator and, at boot time, load it, generate a new state and save that. This way, as soon as there has been sufficient entropy once, there is sufficient entropy forever on that machine.

Applications such as Veracrypt, GnuPG, etc. ask the OS for randomness. On Linux, they can read /dev/random or /dev/urandom, or call the getrandom system call (the differences between those are beyond the scope of this answer). On Windows, the system call is CryptGenRandom. Other operating systems designed to support cryptographic applications have similar interfaces.

Applications almost always use the OS's random generator as a seed for their own PRNG. This is cryptographically safe and improves performance.

Why do some applications ask you to move the mouse? There are several reasons:

In case the OS doesn't have as much entropy in its random generator, this improves the situation a bit.
Some applications were written for 20th century operating systems that lacked a random generator interface (e.g. Windows 9x) and needed to collect their own entropy.
As you can witness, it gives the user a warm fuzzy feeling that they're getting something really random. It's actually mostly for show.


Do PGP keys with expiration date set expiration date in Encrypted messages too? So I am little confused about a type of encryption I read about. You can encrypt your E-mails and pretty much all kind of information using PGP key pairs.

However, I am confused if an encrypted message has an expiry date if a key used to encrypt the message has an expiry date too?

Let's say I am using a Key1 to Encrypt a Message and Key1 has an expiry date of 1 week from now, Can a person who received a message decrypt an encrypted message after a 1 week?

It is the keypair that is doing the encrypting, not the one doing the decrypting, that the expiration date applies to. And yes, they will be able to decrypt it after one week. In fact, they will always be able to decrypt it. The expiration date only applies to the key and is nothing more than a gentle reminder that the key is supposed to be replaced and should no longer be used for encryption (for public keys) or signing (for private keys). There is nothing stopping anyone from decrypting data that was encrypted with an expired public key. Unless a revocation certificate is generated and imported, an expired public key can have its expiration date retroactively modified by the holder of the private key. This is common practice.

If a public key has passed its expiration date, most PGP programs will warn you if you try to encrypt a message with it. There is nothing fundamentally that prevents you from forcing encryption, although some programs may refuse to encrypt with it and do not provide any override option. In those cases, forcing encryption with an expired public key is as simple as changing your computer's clock.


Multiple (RSA) public key encryption how to verify others received the same information? Non-deterministic encryption I have an RSA system between multiple parties. Alice takes the targets (Bob and Oliver) public keys and encrypts a message using them and sends it to them. All parties know each other's public keys and the ciphertexts received.

I wanted to verify that all the targets are receiving the same message, so I thought Bob could take Oliver's public key and encrypt the received message(after decrypting with his own private key) and compare it but I'm using non-deterministic encryption, therefore, the ciphers produced are different for the same message and public key.

I know using deterministic encryption prone to attacks so I was wondering if there are any other solutions out there or do I have to risk using deterministic. For reference, I'm using JavaScript and AES for encryption.

How do I verify that Oliver and Bob receive the same message without them having to send it to each other?

As long as you are not wedded to RSA, here's a way that completely solves the problem (and scales to more than two targets).

The general idea is that we do EC-ElGamal in a pairing friendly curve (that is, an elliptic curve that has a computable function $e(X, Y)$ that satisfies the identity $e(aG, bG) = e(G, G)^{ab}$, for any integers $a, b$ (and $G$ is the generator point), and for which $e(G, G) \ne 1$.  The power on the right is typically a multiplicative group of a finite field (which would depend on the curve you're using), that's not important at this point.

In any case, Bob and Oliver would select private keys $b$ and $c$ (I'll use c rather than o for Oliver, because o is too easily confused with 0), and their public keys are $B = bG$ and $C = cG$.

The encrypt, Alice takes the message $m$, and maps it in a way that is both invertable and nondeterministic to a point $M$ (it has to be nondeterministic, otherwise a third party with a guess of $m$ can verify his guess using the $e$ function).  Then, she selects a random value $r$, and generates the two ciphertexts:

$$rG, rB + M$$

$$rG, rC + M$$

(note: each ciphertext can use the same $rG$ value, or use different ones; both varieties work).

Bob and Oliver first check whether all the points in the ciphertexts are actually points in the curve (I'm not sure what can go wrong if they're not, but it's an easy check to do).

Then, Bob can decrypt his received ciphertext $X, Y$ by computing $M = Y - bX$ and then mapping $M$ back to the original $m$.

Bob can then verify that Oliver got the same message by reconstructing $rC$ (using the value $M$ he got during decryption), and then verifying that $e( G, rC ) = e( rG, C )$ (where $rG$ is the value from Oliver's ciphertext); if they received the same message, then both values are $e( G, G )^{rc}$


What kind of ECDSA signature encoding is this? I am trying to generate an ECDSA signature using ARM's CryptoCell 310 (hardware cryptography module) and verify the signature using mbedTLS software library.

The harware module documentation says that the ECDSA is performed according to
ANS X9.62 standard.

The cryptocell generated signature for SECP256R1 is 64 bytes long and looks like this:

95D9AFCC53A8618FF99AA7AB86013F59148B112BDFB15A7775BDE04B1001A84AB77A0F1C82327BA3B420AA172DB288CA030028CAF7C43637EF3B9990B21D082C

I need to convert it into DER encoded signature so that mbedTLS can verify it, but I don't know how the R and S parameters are encoded in it.
I have tried to take first half of that string as the R parameter, second half as S and encode it to DER like this:

304602210095D9AFCC53A8618FF99AA7AB86013F59148B112BDFB15A7775BDE04B1001A84A022100B77A0F1C82327BA3B420AA172DB288CA030028CAF7C43637EF3B9990B21D082C

Unfortunately it didn't work. I have also tried to do big/little endian swaps, trying the second half as R and first as S, but it still didn't work.

I have tried to obtain the X9.62 standard, but couldn't find anything about the encoding.

Does anyone know what encoding is that?

Thanks in advance.

ANS X9.62–2005 states in appendix E.8:

  When a digital signature is represented with ASN.1, the digital signature shall be ASN.1 encoded using the following syntax:

ECDSA-Sig-Value ::= SEQUENCE {
    r INTEGER,
    s INTEGER
}

I found no issue with the DER encoding in the question.

Implementing this is a pain in the neck if there's no library for it (from a painful experience: a common language runtime once accepted invalid encoding with more zero bits in the high order bits of $r$ and $s$ than allowed by ASN.1, then became more strict, breaking invalid but working code calling it).

Update: the standard also states:

  X.509 certificates and CRLs and CMS SignedData represent signatures as a bit string. Where a certificate, CRL or SignedData is signed with ECDSA, the entire encoding of a value of ASN.1 type ECDSA-Sig-Value shall be the value of the bit string.

But AFAIK this is only for certificates.

Now this looks like a purely programming issue, largely off-topic. Best option seems to be: dig documentation or test case for mbedTLS.


Is my pin algorithm secure? I'm a hobby programmer and very new to this field.
I opened a bank account recently and got two pins. One for the girocard and the other for a creditcard. And I needed two more pins for the online banking account, that I could choose by myself. Just for fun I tried to come up with an algorithm, that generates each pin for me, so that I don't need to remember all.

Let's say the two predefined pins are:

2812
7791

The other two pins will be generated shortly.

The algorithm I came up with is the following and it operates on each digit seperately.

(x + n(k + n)) mod 10 = d

where d is one digit of the n-th pin.

Using simple arithmetic I got the following lists:

x = [9, 1, 5, 5]

k = [2, 6, 5, 6]

k is the secret key I memorize.

If I want to get the second pin for example I set n = 2 and use the first k with the first x to get the first digit of my second pin.

the other two pins my algorithm generates with n = 3 and n = 4 are

4893
3115

With this method I can generate up to 10 pins and need to remember only one key.
I don't have any knowledge of cryptography and this is just my amateurish attempt. I'm not even sure if this has something to do with cryptography but I hope this is the write place to ask.

Is there some mysterious way someone could decrypt those pins just knowing of the algorithm and the list x?

Assuming that someone discovers your encrypted PINs, knows about your algorithm, but does not know $n$ or $k$, then it is more secure than if they discovered the plain PINs. As you normally only get a few attempts at guessing a PIN

However, there are some features of your algorithm that make it less than perfectly secure.

If you replaced the expression $n(k+n)$ with just $k$, and memorised a different four digits for $k$ for each PIN to encode, then what you would have is a one time pad. This is perfectly secure, but you have gained very little - you may as well remember the PINs. It might be relevant though if you needed to send a new PIN to someone else in future, but could only communicate privately and securely beforehand. So you could agree a value of $k$ in private then send the encrypted PIN safe in the knowledge that to an observer not knowing $k$, the real value of the PIN could be anything.

The security of re-using your value of $k$ depends on the behaviour of $n(k+n)$ mod $10$ with different $n$. Immediately we can see a problem - when $n$ is $0$, the output is the original PIN. Therefore using $n=0$ is out. Other values of $n$ have a more subtle problem - several of them do not cover all possible variations, $n=5$ for instance only gives 16 variations of $n(k+n)$ mod $10$ for a 4-digit PIN, so if an attacker knew or guessed $n=5$ they would have a good chance of guessing the original PIN without needing to know $k$. The "bad" values of $n$ for you are anything which shares a common factor with $10$. The "good" values are therefore $[1,3,7,9]$

So your algorithm can in theory protect four PINs reasonably well? Sort of, there is one more problem. The algorithm is easily reversible, therefore if somehow an attacker learned one of your PINs, they would be able to figure out 4 potential values of $k$ and only need 12 guesses (different values of $n$ and $k$ that still work) to figure out the next PIN. Then only 2 for the third one, and immediately get the fourth.


Is the inverse of a point on an elliptic curve over $\mathbb{Z}_p$ always in the group? I'm working on a zero knowledge proof system that uses ECC over $\mathbb{Z}_p$ (currently using NIST P-256 since mbed TLS doesn't support group operations on Curve25519, but the problem should be general). Part of this involves calculating the inverse of a group element. For some point $a=(x,y)$ I calculate

$$a^{-1}=\left(x, \text{mod-inv}(y)\right)$$

where $\text{mod-inv}$ is the modular inverse with respect to $p$, the prime of the group. This seems to be correct; I've verified that $a + a^{-1} = 0$, i.e. that performing the group operation on the two points results in the point-at-infinity. The problem is that $a^{-1}$ doesn't seem to actually be a point on the curve! For example, on NIST P-256 I have the points

$$ a = (59480773761400674036851792405749936131635847707891677548254384759310415166102, 54215024246639578077221526092518955906039351892854133302257636019166433313823),\quad a^{-1} = (59480773761400674036851792405749936131635847707891677548254384759310415166102, 112829638001096970751397729889429500563993392391887472719416027848261694765589)$$.

$a + a^{-1} = 0$ (http://imgur.com/NkK39iL), but letting $a^{-1} = (x,y)$ and $A,B$ be the appropriate constants for the curve,

$$y^2 = 4361752682281060789769969552305091818972826646482745173947303219865743305577,
x^3-Ax+B = 108077544024096556861625085656772704192358526678289221948404493713765226661298$$

which means that $a^{-1}$ is not on the curve. Is this to be expected? Am I somehow calculating the inverse incorrectly? Thanks for any help!

Edit: Changed to additive notation for the group operation

poncho has it right, I was calculating the inverse incorrectly. The inverse of a point $(x,y)$ is $(x, -y)$. It just so happens that $(x,y) + (x, y^{-1}) = 0$, but this was a red herring. Thanks!


Is it safe to say that a XOR with an unknown input provides a random output? I am wondering if you have an input $x_{1}$ and you XOR it with an unknown random second input $x_{2}$, is it safe to say that the resulting $x_{1}\oplus x_{2}$ will be random ?
The final idea would be to first fix all the $x_{i}$ for $i>0$ so that one cannot change its $x_{i}$ afterwards, then set $x_{0}$ to a random value.
Then, person 1 $p_{1}$ gets a value $a_{1}=x_{0}\oplus x_{1}$, $p_{2}$ gets $a_{2}=x_{2}\oplus a_{1}$...
In the end person $p_{i}$ gets the value $a_{i}=x_{i}\oplus a_{i-1}$ $\forall i$
The point of this is to choose someone at random among them so we could pick $p_{min}$ where $a_{min} = min_{i}(a_{i})$.
Do you think it would be safe to choose someone at random in this way ? We probably need to make sure that two different people won't have the same $x_{i}$ otherwise there could be two people with the same $a_{i}$ value but apart from that I don't see any weakness where one could improve its chances at being the chosen one, do you see one?
Edit: I have to add that all of the $x_{i}$ will also be picked at random otherwise there would be a clear link between one $x_{i}$ and the previous $a_{i-1}$.

I am wondering if you have an input $x_{1}$ and you XOR it with an unknown random second input $x_{2}$, is it safe to say that the resulting $x_{1}\oplus x_{2}$ will be random ?

Yes, this is literally what proofs of the security of one-time pads come down to.  Informally it comes down to the following observations:

If $x_2$ is random, then it means that each of its bits is 0 or 1 with equal probability and independent of all other bits in $x_2$;
If $x_2$ has those properties, then $x_1 \oplus x_2$ also must.

And this really comes down that after the XOR, for each bit in $x_1$ you get with equal probability, either the original bit from $x_1$ or the flipped bit, and that you XOR all of the bits independently of all other ones.


The multiplicative group $\mathbf{Z}_p^*$ of non-zero integers modulo $p$ is cyclic of order $p-1$, so it has exactly one subgroup of order $k$ for each divisor $k$ of $p-1$. In particular, it has exactly one subgroup of order $q$, which consists of those integers $a$ such that $a^q \bmod p = 1$. Let $G$ be this subgroup.

To obtain an element $g$ of $G$, take any element $a$ of $\mathbf{Z}_p^*$ and let $g = a^{(p-1)/q} \bmod p$. Then $g$ is an element of $G$ because
$$g^q = \left(a^{(p-1)/q}\right)^q = a^{p-1} = 1 \pmod p.$$

The order of $g$ is a divisor of the order of $G$, so it is a divisor of $q$, and since $q$ is prime, it equals either $1$ or $q$. The only element of order $1$ is the identity $1$, so if $g \not\equiv 1 \pmod p$ you are done. Otherwise, try another $a$.


What are options to compute DES retail MAC (aka ISO 9797-1 mode 3) under PKCS#11? The DES retail MAC, also known as ISO 9797-1 mode 3 with DES, computes the MAC of a block of data using a 16-byte (112 bit) key. It can be seen as CBC-MAC using simple DES with the first half of the key for all the blocks, except the last where 3DES with the full key is used. I've left padding and truncation out of the picture.

I need to compute that MAC

using a standard PKCS#11 token,
with all DES operations in the token (for fear of side-channel attacks),
using PKCS#11 semantic compatible with most tokens,
if at all possible, with built-in derivation of the key using CKM_SHA256_KEY_DERIVATION (the key is the first 16 bytes of the hash) and no exposition of that key material in the host's RAM.

Is that DES retail MAC sometime available in PKCS#11, under some name that I missed? If not (or that's not supported in my token), what are my options to implement that MAC given that the token I use is documented as supporting encryption using CKM_DES3_CBC, but not CKM_DES_CBC (deprecated), nor MAC using CKM_DES_MAC, CKM_DES3_MAC (not available)?

So far the best I see is two separate encryptions using CKM_DES3_CBC, the first with a DES2 key emulating a DES one; but that's hairy, and I fail to derive the first key inside the HSM.

An answer surfaced from careful reading of appropriate documentation.

The MAC in the question is also defined in ANSI X9.19, and is supported by some PKCS#11 tokens as the mechanism CKM_DES3_X919_MAC_GENERAL.

Other than that, this MAC can be simulated using CKM_DES_MAC_GENERAL (or CKM_DES_CBC or CKM_DES3_CBC) for all but the last block, then CKM_DES3_CBC; but derivation of the key for the first part is hairy, and an adversary observing the intermediary result for a single plaintext can mount a key recovery attack requiring about $2^{56}$ work.

Independent of implementation and intermediary result, as pointed by poncho in comment, there is a key recovery attack on that MAC when so much plaintext is processed that an internal collision occurs, which is in the order of $2^{32}$ MACs, then allowing an attack with about $2^{57}$ work.