When/why is RSA (hybrid) encryption used rather than alternatives? I've read that RSA is not meant for encrypting large plaintext because:
(Are these also true for other public-key encryptions like ElGamal?)

It is slow.
Padding makes the ciphertext blocks much longer.
No one uses RSA that way; so its security is not scrutinized.

Instead, a hybrid scheme is used, e.g., samoz's answer at How can I use asymmetric encryption, such as RSA, to encrypt an arbitrary length of plaintext?

And apparently, that is also encryption in PGP works:

Select a random symmetric key.
Encrypt plaintext with this symmetric key.
Encrypt the symmetric key using the receiver's public key.
(optionally) Sign (the hash of) the ciphertext plaintext.
Send symmetric ciphertext, the encrypted symmetric key, and (optionally) the signature.

This scheme has the same problem that I asked about here Why use Diffie-Hellman key exchange over RSA (or any public-key encryption)?, i.e., encrypting a ''unilateral'' symmetric key with the receiver's public key.

So why not use Integrated Encryption Scheme? This scheme uses the receiver's public key to create a Diffie-Hellman symmetric key. With this, I don't see how public-key encryption would ever need to be used at all. For example, TLS only uses RSA signature (or DSA) to sign key exchange, not RSA encryption. This makes me wonder when and/or why one would use public-key encryption at all.

The Integrated Encryption Scheme offers no qualitative advantage (in term of cryptographic service offered) compared to hybrid encryption using RSA. In particular, neither provides Forward Secrecy: if the private key of the recipient leaks, past cyphertexts can be deciphered. All there is to do is apply the decryption algorithm.

This contrasts with Diffie-Hellman key exchange followed by symmetric encryption with the session key, which can provide Forward Secrecy because the seeds used to generate the session key are never available to an adversary.

Asymmetric encryption protocols allowing forward secrecy (like authenticated DH combined with symmetric encryption) tend to require two-way communication (I know no exception), and thus are not universally usable. Public key encryption schemes (like IES/ECIES, and RSA combined with symmetric encryption for large messages) are the only common option for one-way communication, including email and enciphered backup (communication from past to future, thus one-way, from a cryptographer's perspective).

The rest of this answer compares advantages of the two encryption schemes discussed in the question.

The main advantages of RSA (with hybrid encryption, for all except very small messages) are that

it was first there;
it allows for very significantly more efficient asymmetric encryption (not decryption); this is an important feature in some applications where messages are of moderate size, and the enciphering party has limited computing power, or decryption seldom occurs.

The main advantage of IES is that it allows to perform asymmetric encryption based on the difficulty of solving a problem related to the Discrete Logarithm in a finite group (when RSA relies on solving a problem related to factoring). In turn, this allows:

more efficient decryption, because smaller exponents are involved;
and when using a finite group based on an Elliptic Curve, that is ECIES:

yet more efficient decryption because elementary operations can involve smaller values for conjectured equivalent security;
slightly smaller cryptograms when compared to straight hybrid encryption (this advantage all but disappears, except for very small messages, when we take the mildly unusual step of embedding part of the message into the RSA cryptogram).

Per request: such embedding could be as follows. Assume a 3072-bit (384-byte) public RSA modulus, and some 256-bit (32-byte) hash function $H()$. RSAES-OAEP of PKCS#1v2 allows to encipher any message $M$ from 0 to 318 bytes into a 384-byte cryptogram, by

padding $M$ into $\widetilde M$

where

seed is a fresh random value as wide as a hash;
lHash is the hash of some public constant;
PS is filler bytes with value zero;
the Mask Generating Function is some PRF, usually built from the hash.

then applying the raw RSA public-key transformation $\widetilde M\to C=\widetilde M^e\bmod N$.

This is reversible by applying the raw RSA private-key transformation $C\to \widetilde M=C^d\bmod N$, followed by un-padding.

For $M$ above 318 bytes, we can encipher the message portion past that limit using AES-256 in CTR mode, using the 32-byte seed as key (the IV can be all-zero, or the low 128-bit of $C$). The overhead for encryption is 66 bytes (2 hashes plus 2 bytes), comparable to that of ECIES with affine coordinates on a 256-bit curve (64-byte).

Note: this simplified scheme does NOT provide message integrity; breaks the security argument of RSAES-OAEP by reusing seed; and for that reason is not easily implementable on top of usual RSAES-OAEP APIs, which tend to give no access to seed.


What is base of $\log$ in Subexponential Algo for DLP? I am currently going through this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem" by Leonard Adleman.

On page 56, author mentions that Dixon's algorithm - Asymptotically Fast Factorization of Integers, works in $RTIME (O(2^{O{(\log(q)\log\log(q))}^{1/2}}))$ and on page57, mentions that $r_i, s_i$ are smooth with respect to bound $2^{c ({\log(q)\log\log(q)})^{1/2}}$ .

My question is are these logs mentioned in equation, base $e$ or $2$? Because in his paper (on page 255), Dixon has mentioned the complexity equation in $\ln$ which means natural log, i.e. base $e$.

In this case, the base does not matter as the $\log$ terms are wrapped in an $O$ expression. The $O$ expression lets you throw away constant factors and to convert something base $X$ to base $Y$ is simply $\log_X Z = \frac{\log_Y Z}{\log_Y X}$, well, $\log_Y X$ is a constant, so it can be thrown out in the $O$ expression.

The reason the second reference explicitly use $\ln$ is that the $O$ expression includes an exponent that does not also contain an $O$ expression. In this case, the base does matter.


two public keys with same passphrase insecure? | can two hashes be compared? Suppose someone had generated a 2.048-Bit RSA GPG/PGP key pair and published the public key on the usual key servers. Then he withdraws this key and generates a new one in 4.096-Bit RSA using the same passphrase again.

Theoretically, can the passphrase be cracked by mathematically comparing the two public keys or does that give away any security whatsoever, e.g. by the fact that both of them are out there?

I'm not a mathematician, so I'd be especially interested if 'comparing two keys' would make any theoretical sense at all and if so, what impact this would have on the integrity of the passphrase.

Edit: please note that this question is not about reversing a hash to its passphrase (or in this case reversing two hashes to eventually learn they were made from the same pass) but if there are mathematical methods to compare two hashes to

see if they might have originated from a single passphrase or even
obtain information about this common pass through this comparison

No.

The passphrase you use creates a symmetric key that is used to encrypt the private key. You're not uploading the private key to the server, at least let's hope you aren't.

But even if you are doing that, the password is salted and iterated in hashing, and that means that the visible encrypted private key is radically different even if the password is the same, because the same password produces two different symmetric keys.


ECDSA signature with Brainpool curves in TLS possible? Even the up to date RFC 8446 lists at the page 41 as the options for the ECDSA in e.g. TLS_ECDHE_ECDSA_WITH_... only NIST curves:
      /* ECDSA algorithms */
      ecdsa_secp256r1_sha256(0x0403),
      ecdsa_secp384r1_sha384(0x0503),
      ecdsa_secp521r1_sha512(0x0603),

Does it mean that the certificates containing the public key based on Brainpool curves cannot be used for
signing the (EC)DHE parameters in SERVER KEY EXCHANGE?

RFC 8734 defines how to use Brainpool curves within TLS 1.3, including how they can be used in ECDSA signatures (section 4)
.  Hence, yes, there is an official way to negotiate Brainpool curves for use in the SERVER KEY EXCHANGE.


Does the Shappening mean HTTPS can be broken? For years we've been warned that SHA-1 is weaker than originally thought and should not be used.  This reached its peak with the Shappening and experts from Schneier on down have been warning that we should get off SHA-1, or something bad will happen.

What are the practical 'something bad's?  Once an attacker has the capability to create a SHA-1 collision, what then can they do?  I'm interested in confidentiality and integrity of HTTPS, but am open to broader answers.

Specifically would it be feasible to do a MITM attack by creating a fake certificate for an existing website?  It seems plausible: the attacker creates a fake certificate with the same name, but varies the other data in order to produce a SHA-1 hash that matches the SHA-1 hash of the original certificate.

SHA1 certificate is getting weaker because computing power grows to Moore's Law. According to Jesse Walker, who made a back of the envelope calculation of the cost of SHA1 collision attack:

  the cost of the attack will be approximately:

  \$2.77M in 2012
  \$700K by 2015
  \$173K by 2018
  \$43K by 2021

  A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021.

To your question:

  What are the practical 'something bad's?

The practical "something bad" is that sometime this year, all major browser vendors (Google, Firefox, Microsoft) would distrust sha1 certificate. This means that your site/servers will be blocked with a big security warning, it might actually be more sensible to not use HTTPS at all than to use SHA1 certificate at that point. Some browsers now already no longer shows the secure lock icon on sites with SHA1 certificate.

  Once an attacker has the capability to create a SHA-1 collision, what then can they do?

Certificate signature is made by taking a hash of the public key and attached data (owner identity and Common Name/SAN) and then the CA signing that hash with the CA's private key.

If you generate two keypairs with the same SHA1 signature, you can convince a CA to sign one of the public key and that signature will also be valid for the other key. From there on, it's a simple matter to implant the CA's signature on the second certificate. That second certificate could be for a different domain that you don't actually control.


Is it easy to crack a hashed phone number? I want to SHA256 hash phone numbers in order to hide them. Is this a good idea? Are there any other ways I could make this safe?

No, it is not a good idea to hash phone numbers. There are only a limited number of phone numbers, so it is pretty easy for an adversary to try and hash all of them. Then you can simply compare the hash of each with the stored hash. Generally you don't have to deal with all telephone numbers, only a subsection of phone numbers anyway (for a specific country or other group that is logically distinct).
You could use a slow password hash with salt and work factor, but that's only going to mean that time time required is multiplied by a large, constant value. It won't change the order of operations. If the subset is small enough it may not deter an adversary to perform all necessary calculations.
In this case you will probably need to encrypt the phone numbers instead. Or use a keyed hash such as HMAC. For both options you need to perform key management on the secret key though; it's not as easy as just hashing the number.


Reuse nonce with Salsa20 stream cipher with counter It is often said to never use a nonce for more than one message when using a stream cipher. It seems this is to prevent something like this:
Taking advantage of one-time pad key reuse?
Yet what if I keep the same nonce, but increment the block counter depending on the amout of blocks exchanged so far? This should be the same thing as turning the whole exchange into one long message, thus not needing more than one IV.
By exchange I mean two people sending each other stuff.

[What] if I keep the same nonce, but increment the block counter
  depending on the amout of blocks exchanged so far?

This is a "bad" idea.
What Salsa20 is doing can be considered to be "CTR-Mode like" $E_k(IV\parallel CTR)$ where you have to supply $k$ and $IV$.

If you were allowed to supply $IV'=IV\parallel CTR$ this would also mean you'd to absolutely make sure that no two blocks ever happen to share the same $IV'$ under the same key. Even worse to make sure this doesn't happen, you'd have to pick $IV'$ at random (or actually keep track of all the blocks encrypted under the key) as opposed to being able to just increment $IV$ (= uniqueness).

Note that this change was made to the usual API of authenticated encryption schemes to avoid the above mentioned problems and this approach is now standard with modern authenticated encryption schemes (like ChaCha20-Poly1305 and AES-GCM)


Problems when using PBKDF2 to create an ECDSA private key from a password? System based on, e.g.:
PBKDF2, ECDSA and authenticator's random challenges.

Key derived from a password would be ECDSA's private key used to sign random challenges.

Is password brute force the only thing I should worry about or is there another threat involved with using such key as a ECDSA seed?

How are you going to trust the resulting public key that is required to verify anything signed by the private key?

How are you going to maintain security after you've authenticated?

ECDSA may be vulnerable against analysis using quantum computing.

You've only partly described one part of a cryptographic system. This means you've got plenty to worry about.


Go: Should I use secretbox or RSA? I want to encrypt a file with a RSA public key.

I generate a random 16 bytes key
I encrypt the file with AES + the random key (aes.NewCipher() + cipher.NewGCM() + aesgcm.Seal())
I encrypt the random key with RSA (rsa.EncryptOAEP())

Now I can send the encrypted file + encrypted random key to the person who has the private RSA key.

I read that secretbox should be favored over the RSA package: should I keep using RSA? What is the difference with the secretbox package?

Do you need to grant someone the ability to encrypt messages whom you do not want to grant the ability to decrypt messages?  If so, you need public-key encryption—and you probably want public-key authenticated encryption.

For example, if you want to separate the ability to create archives from the ability to read archives at a later time, then you probably need public-key (authenticated) encryption, like Tarsnap.

Although you might be the only human in the system handling the archives, the machine that creates the archives—a virtual server hosted at Amazon constantly listening to the internet, say—might be meaningfully distinct from the machine that reads them—e.g., a laptop deployed only once, in an emergency, with a USB key stored under your mattress—and as such you might impose a meaningful privilege boundary between them.
Consider using NaCl box instead of building something yourself out of difficult parts like RSA with OAEP.

As a bonus, NaCl box is smaller than anything you build out of RSA, and decryption is much faster, and the code will be simpler, and you naturally get public-key authenticated encryption where it would take much more work to design a bespoke system with RSA.

Is the party that encrypts messages the same as the party that decrypts messages, with no meaningful privilege boundaries?  If so, then NaCl secretbox is fine.


Why does RFC8032#8.7 state that the IUF hash API should not be used for Ed25519? RFC8032 (section 8.7) states that IUF (Init, Update, Finish) should not be used in Ed25519 API:

  Avoid signing large amounts of data at once (where "large" depends on the expected verifier). In particular, unless the underlying protocol does not require it, the receiver MUST buffer the entire message (or enough information to reconstruct it, e.g., compressed or encrypted version) to be verified.

  This is needed because most of the time, it is unsafe to process unverified data, and verifying the signature makes a pass through the whole message, causing ultimately at least two passes through.

  As an API consideration, this means that any Initialize Update Finalize (IFU) verification interface is prone to misuse.

  It is a bad idea to modify Ed25519 or Ed448 signing to be able to create valid Ed25519/Ed448 signatures using an IUF interface with only constant buffering.  Pretty much any error in such would cause catastrophic security failure.

Why? What implications does it have?

What implications does it have?

That's because, as designed, Ed25519 does two passes over the message that is being signed:

It first hashes the message (and secret data) to construct the internal value $r$ (which is used to compute the public value $R$)
It then hashes the message (and the public value $R$) to construct the public value $S$.

Because of the ordering of the hashes in the second pass, the first pass must be completed before starting the second pass [1]

Now, the verifier cannot check that $r$ was constructed correctly, and so you could (say) select a random value in its place, which would allow you to create a signature with a single pass.  However, if you did that, and got it wrong (say, using the same $r$ to sign two different messages), you just leaked the private key; Ed25519 was designed to avoid such possibilities.

[1]: Random musing: if you modify Ed25519 by changing the ordering of the hashes $H(R, A, M)$ to, say, $H(A, M, R)$, you could perform it in a single pass (performing both hashes in parallel).  Of course, the verifier would need to know about the modified hash ordering.  I speculate Dan did it the way he did because that change would require a stronger security assumption on the hash function; as it is, Ed25519 assumes second preimage resistance, rather than collision resistance.


Data Security and Encryption I have a research paper on data security using proxy re-encryption, and I need to provide an answer to a reviewer's comment. However, I have no idea on what to do or how to answer it.
The security analysis of the proposed method is based on indistinguishability against chosen plaintext attack. This is the comment:

The security analysis is based on or is limited to known attacks, but no security model/framework is provided that could guarantee security in front of unknown attacks.

What is the "unknown attack" the reviewer is referring to? What is the best answer I can give for this?

What is the "unknown attack" the reviewer is referring to?

The reviewer did not say "the unknown attack", but "in front of unknown attacks". That refers to no attack in particular. Much like a reviewer of a math paper could tell, without thinking of a particular $y$: "the argument that $p$ is prime is unconvincing, for it fails to show $\gcd(p,y)=1$ for hypothetical $y\in\left[2,\left\lfloor\sqrt n\right\rfloor\right]$ with $y\not\in\mathbb S$" (where $\mathbb S$ is a set defined in the paper).
I read the reviewer's argument as equivalent to: the existing analysis gives no proof that the claimed IND-CPA security follows from the difficulty of some assumed-hard problem.
That's what so-called security proofs are when it comes to encryption. Since about the last decade of the 20th century, such proof is considered necessary for proposing a new cryptosystem or protocol in a serious peer-reviewed crypto journal or conference, with few exceptions. These exceptions include block ciphers, hashes, or similar low-level primitives: for these, we still examine known attacks, and prove they do not apply, preferably with some quantitative assessment.
For all other cryptosystems, modern arguments against unknown attacks are on the tune of: Assume a PPT algorithm $\mathcal A$ that breaks IND-CPA security of the proposed system. (..) Hence PPT algorithm $\mathcal B$, using $\mathcal A$ as a subroutine, is able to solve the well-studied smurf problem with non-vanishing probability. Perhaps that smurf problem is: attack of AES with random key under IND-CPA.
If such security reduction is missing entirely from a paper, adding it will be a major rework; or sometime, impossible.
Up to the early 1990s, practice allowed to claim security without proof, or even without a clear definition. It was common the claim was disproved. For example, El Gmamal encryption in $\mathbb Z_p^*$ turned out to leak one bit about the plaintext. Countless attacks where found on RSA encryption and signature schemes. Crypto was then proverbial for it's break and fix cycles, much like bridge design used to be. Fortunately, these times are over when it come to crypto designs in IACR publications. That's still the norm for implementation, some standards, and less than recommendable publications.

My favorite example of why we should not trust security claims based on repelling existing attacks is the ISO/IEC 9796:1991 signature scheme, withdrawn 2000. It was AFAIK the first official standard for RSA signature, and carefully justified by Louis Claude Guillou, Jean-Jacques Quisquater¹, Mike Walker, Peter Landrock, Caroline Shaer Precautions taken against various potential attacks in ISO/IEC DIS 9796 “Digital signature scheme giving message recovery”, in proceedings of Eurocrypt 1990. And then, in 1999, that scheme was broken by Don Coppersmith, Shai Halevi, and Charanjit S. Jutla extending an almost working attack by Jean-Sébastien Coron, David Naccache, and Julien Stern; and independently by me using a technique a child could apply: all there is to do is find two different paths across this maze and collect the node values.

¹ I thank JJQ for having taught me multiprime RSA (then uncommon and perhaps unpublished) and using the Chineese Remainder Theorem for that.


One round of AES-128 Maybe it’s a silly question, I’m interested in the best known/chosen plaintext attack on only one round of AES-128. More specifically, what is the smallest number of known/chosen plaintext/ciphertext pairs which allow us to recover the key with high probability? What’s the relationship between how time scales with the number of pairs?

Let $(m,c)$ be a couple of a plaintext and its ciphertext, and $k_0=\{k_{0,1},\ldots, k_{0,16}\}$ and $k_1=\{k_{1,1}, \ldots, k_{1,16} \}$ are the two unknowns subkeys ($k_0$ is in fact the master key).

Including the MixColumns step, then the encryption is
$$
c = \mathrm{MC}(\mathrm{SR}(\mathrm{SB}(m \oplus k_0))) \oplus k_1
$$

If we apply the inverse of MC and SR, then it becomes
$$
\mathrm{SR}^{-1}(\mathrm{MC}^{-1}(c)) = \mathrm{SB}(m \oplus k_0) \oplus \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(k_1))
$$
For ease of notation, let $c' = \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(c))$ and $k'_1 = \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(k_1))$, then we have
$$
c' = \mathrm{SB}(m \oplus k_0) \oplus k'_1
$$

Suppose you know two plaintexts $m_1$ and $m_2$ and their respective ciphertexts $c_1$ and $c_2$. To get the byte $k_{0,i}$, you make a guess $\tilde{k}_{0,i}$ and compute
$$
\tilde{k}'_{1,i} = c'_{1,i} \oplus \mathrm{SB}(m_{1,i} \oplus \tilde{k}_{0,i})
$$
You do the same by replacing with $m_2$ and $c'_2$ ($m_1$ and $m_2$ should differ on every bytes) and if the obtained values $\tilde{k}'_{1,i}$ coincide, then the guess might be correct and $\tilde{k}_{0,i}$ is a candidate for $k_{0,i}$.

Other plaintexts/ciphertexts can be used to filter the candidates until one remains for each byte, or concluding with an exhaustive search.


Bilinear map + commitment Let $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T$ be yclic group of the same order and $ e: \mathbb{G}_1 \times \mathbb{G}_2\rightarrow \mathbb{G}_T$, such that $u\in \mathbb{G}_1, g \in \mathbb{G}_2, a,b,r \in \mathbb{Z}$.

Question 1: is the following equation correct? Is there any situation under which it might be correct? If not why?

$e(u^a,\frac {u^b}{u^a} g)=e(u^b,g)$

Scenario: assume we have two parties: $A$ and $B$, where $A$ has two messages $m, m'$ and $B$ has a message $m$. $A$ commitments to a message $m$ as: $(r.u^m)^a$, and B commitments the same message as $(r.u^m)^b$. They send their commitments to a server. It's clear that if $A$ gives $g^{\frac{1}{a}}$ to $B$, $B$ can compute $w=g^{\frac {b}{a}}$, and send it to the server to let the server check whether two messages $m$ for different parties are equal: $e((r.u^m)^a,g^{\frac {b}{a}})=e((r.u^m)^b,g)$

Question 2: Given $g^{\frac{1}{a}}$ can B generate $w'$  to convince the server that it has commited to $m'$ rather than $m$?

All operation are $\bmod p$ where $p$ is a large prime number.

If you define $u$ as element of $G_1$, then you can't just use it in $G_2$ (in the first equation), like you did in your equation. Besides, you missed to state, if $u$ and $g$ are generators of those groups. The following holds:

$$e(u^a,g^{\frac{b}{a}}) = e(u,g)^b = e(u^b,g)$$

Anyway, you didn't do that in the actual question, where I don't really see the connection to your construction. Btw, how do A and B know that they are using the same value $r$? And then: How can the server relate anything $B$ sends to $m'$, if the server has no knowledge of $m'$ or a commitment to $m'$? So no, he can't. Because $m'$ is not used in your construction at all.

The question now is: What is your actual goal? Should the server just be able to make sure, A and B committed to the same value? And A and B have to interact to generate the witness for that? You don't need pairings for that.

edit: Maybe even Alice could cheat in the system, by not sending $g^a$ to Bob, but something else. What happens then? Well, if the server check returns true, the "commited" messages are not equal. Too many things that can go wrong, especially with that $r$, which doesn't make sense.


Factorization of the public value $N$ from the RSA cryptosystem It is mentioned here that the public value $N=p*q$ of the RSA cryptosystem can be factorized if one of the factors is reused. Thus, if $N_1=p*q_1$ and $N_2=p*q_2$ and only $N_1$ and $N_2$ are known, then one can factor $N_1$ and $N_2$.

I wasn't able to come up how this can be achieved. Is that statement really true?

Since $p$ is a factor in both $N_1$ and $N_2$ you can simply calculate $p$ by using Euclid's algorithm.

Once you have $p$ you can then calculate $q_1$ and $q_2$ (simply divide $N_1$ by $p$ to get $q_1$ and divide $N_2$ by $p$ to get $q_2$).


Diffie-Hellman: Should the subgroup have prime order? Hi I previously asked a question about Diffie-Hellman parameters but wanted to make sure I got it right.

I need to generate parameters for the SRP protocol. My base strategy is to generate a safe prime q = 2*p + 1 where p is also a prime.
I want to use as low generator as possible, preferably "2". Now, all elements of (Z/qZ) is going to have one of the following orders: 1, 2, p or 2*p due to the group having order 2*p, so 2 must generate a subgroup of one of those orders. Since q is large, we can exclude 1 and 2 as possibilities, leaving p and 2*p as the only possible orders of the subgroup. It can be easily determined which it is by simply checking if 2^p = 1 mod q.

Now my question is, which is cryptographically preferred for security against the discrete-log attack? I.e. is it preferred to select p and q such that 2 has order p, or is 2*p preferable? 2*p clearly implies a subgroup twice as big. On the other hand, p is prime. I don't know if there's any special benefit to the subgroup itself having prime order.

For DH, whether the subgroup is of order $p$ and $2p$ isn't that big of a deal; if it's $2p$, that means that the attacker can deduce one bit of the exponent; that's minimal.  As for computing the discrete log, it's effectively equivalent; given an Oracle that can compute the DLog of an element of one order, you can (with one query) compute the DLog of an element of the other.

On the other hand, you're using SRP, and that changes things.  For SRP, you MUST use a primitive element, that is, one with order $2p$.  If you pick a proper subgroup; that is, a group for which random values in $Z_q$ have a nontrivial probability of not being in the group, the attacker can effectively eliminate many of the possiblities for the secret value from a single exchange; this is a violation of the SRP security policies.

If you want to generate SRP parameters, read the SRP specs; it tells you how to do it - it's important that you follow those (and actually, you're close; it mandates a safe prime;).


Is a KDF needed when using X25519 for ECDH and XChaCha20-Poly1305 for AEAD? Is a KDF needed when using X25519 for ECDH and XChaCha20-Poly1305 or XSalsa20-Poly1305 for authenticated encryption?

My hypothesis is "no" because the key from X25519 is less than 256 bits long; therefore, it can be used in XChaCha20-Poly1305 directly, as ChaCha20 is considered immune to related-key attacks.

Generally speaking, there are (at least) three reasons to put a KDF in between an DH shared secret and the bulk encryption.

Improved re-usability. If you don't post-process the shared secret with a KDF there's no way to give the sender and the recipient different keys for each direction or to split up authentication and encryption keys. An additional bonus would be, that if you keep the shared secret, you could easily implement a session resumption feature by increasing some helper counter which is fed into the KDF.
Weaker security reduction assumptions. If you feed the shared secret into a KDF, then you only rely on the CDH problem holding (and model the KDF as a random oracle). If you feed the key directly into a cipher, you rely on the DDH assumption which is known to be broken for some groups where the CDH holds.
Better match with expected key properties. Symmetric ciphers are constructed, modeled and analyzed with only fully random keys in mind (or some computationally indistinguishable variant). However DH and ECDH shared secrets are integers and curve points which exhibit structure which violates the randomness assumption. A quick pass through a KDF doesn't cost much and fixes this.

 Glossary: KDF: key derivation function; CDH: computational diffie-hellman problem; DDH: decisional diffie-hellman problem; DH: diffie-hellman; shared secret: result of a DH key agreement protocol execution; ECDH: elliptic curve variant of diffie-hellman


Variants of universal composability in security proofs Universal composability (UC) framework seems to be a powerful framework for proving security of protocols, which guarantees security even in the presence of concurrent composition. Though, I see there are multiple variants of the original UC framework, such as simplified UC (SUC), joint state UC (JUC), global setup UC (GUC). I was wondering how all these different variants fit together. For example, assume there is an ideal functionality $\mathcal{F}$, which is defined in $(\mathcal{F}_1,\mathcal{F}_2, \mathcal{F}_3)$-hybrid model, where $\mathcal{F}_1$ is in the original UC framework, $\mathcal{F}_2$ is an ideal functionality such as a global setup or blockchain that should be available to all the other protocols, so we assume that it is in GUC, and $\mathcal{F}_3$ is something like a key generation functionality that is defined in such a way that should have multi instances, so let's assume it is in JUC. So, now when proving the security of $\mathcal{F}$, how should one prove it? Can one just prove it in normal UC? Or do one needs to do the proof in GUC or JUC, since $\mathcal{F}_2$ and $\mathcal{F}_3$ are assumed to be defined in those frameworks, respectively?

Do not take my word for it, but as far as I remember: a GUC-secure protocol is secure in the UC framework; the converse is not true since a protocol secure in the UC framework might not allow for a global setup. The JUC framework is mainly aimed toward having, in the end, a proof in the standard UC framework: a protocol secure in the JUC framework can be composed in a certain, restricted way with UC-secure protocols, and lead to a UC-secure protocol. The advantage is that JUC-secure protocols can be built more efficiently, so when this restricted composition suffices, we are fine.


Would it be possible to create a game where one would need to decrypt a simple encryption? This might sound pretty weird, but I was thinking of a game a person could play alone with a pen and paper.

I got this idea where the person would write a random four letter string on a paper, and would have to decode it. There would be a mean to verify if the person is getting closer to the goal or not. So, I decided to ask here.

Do you think it would be possible to create a simple game where one would have to decrypt a simple string (a bit like the BitCoin miners do, I guess?), where there would be a logical next step from every point during the decryption and where it would be possible to verify if the contemplated logical next step brings the player closer to the solution or not.

Similar Question: Toy encryption system that provides "hints"

Interesting, but not-quite-it option: Vigenère cipher (Wikipedia article)

Caesar cipher? Its a simple substitution cipher where you can solve with just a pen and paper.

Encryption is done by shifting each plaintext letter, x by n places the alphabet or mathematically, ENCRYPT(x) = (x + n) mod 26. Similarly, the decryption will be the reverse, DECRYPT(x) = (x - n) mod 26. (see wiki http://en.wikipedia.org/wiki/Caesar_cipher#Example)

So, you get a friend to pick a random n and compute the encryption for a randomly chosen four letter string (using free online calculators like http://online-calculators.appspot.com/caesar_ext/). You should not know both n and the plaintext. But the plaintext should be some english word or equivalent in order for it to make sense when you decrypt.

Then, you start the decryption process by trying out all possible values of n until the decrypted plaintext is make sense. If your first two/three decrypted alphabets is not an valid word, that means your chosen n value is wrong and you should try another n.


How can XTS be used to detect the presence of TrueCrypt hidden volumes? According to a thread on the VeraCrypt discussion forum, and a single-post followup, it is possible to detect the presence of a hidden volume in certain conditions due to a flaw in the cryptography or the way it is used, rather than a flaw in the software implementation. The fix was to use random data rather than zeros for the plaintext of the hidden volume header. When a hidden volume is in use, the area where the header for the hidden volume is populated and encrypted. When there is no hidden volume, it is initialized with zeros and encrypted. All encryption uses XTS mode. A post in that thread explains my concern:

  I'm somewhat worried about the possibility to distinguish encrypted data from uniformly distributed random data in general, because this could possibly hint some issue with the ciphers or their usage. If even a rather short block of encrypted zeros can be distinguished from random data, what about larger chunks of plaintext which show distinctive patterns (e.g. a 1 GB file of zeros), or plaintext chosen by or known to the attacker? Could they possibly also be detected in the ciphertext?

  I think it could be at least worth investigating why a block of XTS encrypted zeros could be distinguished from an XTS encrypted header, or random data.

And another post with speculation on an issue with XTS:

  My personal opinion is that the presence of 255 consecutive blocks of zeros encrypted by XTS next to a single block different from zero is the key point behind this issue, and that this enables somehow to have a statistical distinguisher for this special case.

I cannot imagine how the design of XTS could lead to that behavior.

Typically, disclosures done in this manner tend to be disclosures of software vulnerabilities which can be found without a large amount of skill. A fundamental flaw in XTS would require far more expertise and would be the sort of thing reported in a groundbreaking research paper, not in an email thread to the author of a single encryption product which uses XTS.

Obviously, the issue isn't a distinguishability attack against the cipher itself, but with how XTS is being used. I do not know enough about XTS to tell what the issue is, but the reported problem seems to violate XTS' cryptographic guarantees. My questions:

How could the presence of 255 consecutive zero blocks and a single non-zero block encrypted with XTS be distinguished, without the key, from the presence of any other 256 arbitrary blocks?
Is this a known issue? At the time of the last post on that thread, no more information about the attack was revealed, and the thread died in 2016 with little extra coverage.
Could this be a hoax or otherwise entirely false? It would seem that XTS, while not extremely simple, is simple enough that the described attack could be trivially independently discovered.
Could the issue be completely unrelated to XTS, for example caused by an implementation issue? This seems unlikely as dm-crypt, which uses proper XTS, works with TrueCrypt.

This issue, if true, seems very severe. I'd love to hear from some actual cryptographers.

They don't issue cryptographer's licenses to pseudonymous carrion fowl, so I can't rightly claim to be a cryptographer, but I can confidently say that if there is any problem here it is far more likely to arise from unrelated mistakes in VeraCrypt's protocol or implementation than in cryptanalysis of AES-XTS.  Any distinguisher on AES-XTS implies a nearly-as-good distinguisher on AES itself, and the difference is so small for a number of queries so far below the birthday bound as this that effectively it would mean someone has broken AES.


Zencash uses your passphrase to identify AND unlock a wallet - how is this secure? When looking into Zencash I stumbled into myzenwallet.io (by the Zencash creators), which gives you the option to enter a passphrase to generate a wallet (seems normal), but then after creating your wallet you can come back later and open your wallet by simply re-entering your passphrase again... this was unexpected and had me not only wondering about how it worked, but also wondering whether whatever means were used to achieve this would remain secure in the future.

Given that I don't need to identify the resource I'm unlocking, but rather just hand over the passphrase, I'm left to assume that their system generates a token by hashing my passphrase a number of times to generate my "master address" or "account ID" (I just made those terms up, because Zencash gives you many addresses, so I also assume you have some sort of master address / account ID), and then also using that same passphrase to lock / authenticate (not to encrypt though, right?) the wallet.

I don't know how Zencash works. For all I know they store all the data in cleartext. But I'm going to explain how this can be done securely to some extent, but with fundamental flaws nonetheless.

The fundamental tool here is a key derivation function. A key derivation $F(P,L)$ calculates a value from a secret key $P$ and a public label $L$ such that:

It is unfeasible to calculate any part of $P$ even if you happen to know the value of $F(P,L)$ for many values $L$.
It is unfeasible to calculate any part of $F(P,L)$ without knowing $P$, even if you happen to know the value of $F(P,L')$ for many $L' \ne L$.

The following protocol allows a site to store some data without being able to decrypt it, using your passphrase as the sole input.

You enter your passphrase $P$ on the web page. The browser does not send the passphrase to the server.
The browser calculates both $A = F(P, \mathtt{"address"})$ and $K = F(P, \mathtt{"encryption"})$.
The browser sends $A$ to the server. The server uses $A$ to retrieve an encrypted blob of data and sends this encrypted blob to the browser.
The browser uses $K$ to decrypt the data.

The server is not able to decrypt the data in this scenario. Note that you need to trust that the Javascript code sent by the server is doing the right thing. If the server is compromised, it could start sending new Javsscript code that does send the passphrase to the server.

The fundamental flaw with this approach is that someone can easily steal money by guessing someone's passphrase. This is inherent in using a passphrase as the sole identification method: it permits a mass untargeted attack. If you can guess anybody's passphrase, you can retrieve their data. You don't need to know who they are: just keep guessing potential passphrases until you find one with a non-empty wallet.

Reasonable systems that use a passphrase to secure something always include a salt in the label for the key derivation. The salt is unique per passphrase. It does not need to be secret, but when you come back to the site, you'd need to re-use the same salt. With a salt, it is not possible to carry out mass untargeted attacks. If the attacker guesses that squeamish ossifrage is a likely passphrase, they still need to try it out with every possible salt value.

For completeness, note that when deriving a key from a passphrase, in addition to using a salt, it is necessary to apply a stretching mechanism to make the computation slower. This is the same problem as password hashing. In fact, password hashing and password-based key derivation are very close cryptographic problems.

If, instead of a human-chosen passphrase, the derivation was based on a sufficiently long randomly generated string, then the protocol above would be secure. The problem with human-chosen passphrases is that they have very little entropy: it's relatively easy to enumerate all likely passphrases. This is compounded by the fact that in this scenario, the attacker only cares about the weakest passphrases, they're generally not trying to attack a particular user who may have been extra careful to pick a strong passphrase. But even a user who chooses, say, a passphrase made of 4 random words from a dictionary of 100,000 (which includes some pretty obscure words) has only reached 66 bits of entropy, whereas the standard minimum size for a random string used as a secret is 128 bits and for a financial application 256 bits would be preferred. And if the passphrase which is a grammatical sentence, the amount of entropy is vastly reduced.


post-quantum threshold secret sharing I am looking for a references for post-quantum threshold secret sharing schemes.

I am especially interested in knowing whether any one based on one-way compressor functions or cryptographic hashes exist.

The trivial secret sharing systems with $t=1$ and $t=n$ give information-theoretic security.

Here are some other alternatives that I don't know the security of:

Shamir's secret sharing - I don't know [Update: gives information-theoretic security]
Blakley's scheme - I don't know
The Chinese Remainder Theorem - It seems like it is a problem a quantum computer would easily solve.

I am not quite sure why you are looking for the kind you have mentioned in your question.

But good old Shamir's polynomial secret sharing over finite fields, look here, provides information theoretic secrecy, i.e., even a quantum computer will not help you to break the secrecy.


Future-Proof Versioning and Validation I am working on a library (using standard primitives: AES256 CTR; HMAC with SHA256; PBKDF2 with SHA256, 128 bit salt, and 10000 rounds) to encrypt and decrypt data, given a password.

The encrypted data includes a header with version information and an HMAC (the header is included in the HMAC).

I am worried about exactly how I should check/use HMAC and version:

In a future release (with a new version number), the HMAC algorithm or parammeters may have changed.  So I need to check version first and abort if the version is newer than the current code.  But that means that if someone maliciously alters the version then they can "trick" the code into aborting (and likely issuing a warning to the user saying that they should update their software).

Alternatively, in the future, if the version is within acceptable range, then I need to use that to select the HMAC.  That will then validate the version.  But it seems like it could lead to an attack that allows an older, broken HMAC to be abused in some way.

Is there some standard way around these issues?  Or are they not considered important?  Or do I simply need to wait until I have more specifics (for the second case).  Is there anything else I should know?  Should I extend the API now to include a flag that controls backwards compatibility?  Since the API is meant to be very simple that needs a default - what should it be?

I realise that I am not the best person in the world to be doing this work, but no similar library appears to exist for Python 3 and so far I have been lucky enough to find useful support from others (eg on HN; also note that I am not writing any algorithmic code - everything is delegated to pycrypto).  Thanks.

You could have "protocol ID's" which describe the set of primitives and parameters each library version is capable of using. You may deprecate older ID's once they become obsolete by just removing them from some future version, this way you can reject files which are deemed too old (or too recent) and thus unsupported, as long as you don't change how you read the ID's.

To illustrate, suppose you have your initial v1 library, with this sole valid hash/cipher/kdf combination:

<MD4, DES-CBC, MyHomemadeKDF> = 0x01

Thus, because this is the only combination available, all files encrypted with v1 will bear the protocol ID 0x01 (somewhere before the header, in plaintext, next to the file version) and this is recognized by v1.

You then realize this is a pretty poor choice of algorithms, and decide to deprecate it. You create your v2 library, remove 0x01 from the protocol list, and add 0x02 and 0x03:

<SHA256, AES-128-CTR, PBKDF2/128/10000> = 0x02
<SHA512, AES-256-CTR, PBKDF2/128/50000> = 0x03

At this point, any attempt to feed it a file encrypted with your v1 will fail, because its ID is 0x01, which is not recognized by v2 as a valid protocol. Similarly, trying to give a v2-encrypted file to your v1 library will also fail, since the file is using a more recent protocol which v1 does not recognize.

Now, an attacker can obviously change the version number, and cause the software to fail. This cannot be avoided, and in this respect is not important, but can be detected easily: if the attacker changes the protocol ID to an invalid one, the software will complain the file is incompatible, and on the other hand, if he does change the protocol ID to a valid one (say 0x02 to 0x03, for v2) then decryption will clearly fail since you're using the wrong algorithms. You can implement a sanity check in the form of an extra HMAC if you really want to make sure, something like an extra header field:

$$\mathrm{HMAC}(K, \mathrm{ProtocolID} ~ || ~ \mathrm{FileVersion})$$

Which the library can use to verify the ID or file version were not tampered with ($K$ is the encryption, or a derived, key). Either the attacker changes those, or he tries to mess with the encrypted header and HMAC's, he gets busted either way. This way he should not be able to manipulate anything.

This is similar, in essence, to the "cipher suite" concept used by SSL/TLS, which uses them to negociate which algorithms should be used for key exchange and secure communication. You could use a plugin system to transparently let the user decide which set of primitives he would like to accept or reject.

The ID's don't have to be monotonically increasing, as long as you don't reuse them, and so you might prefer deterministically deriving them from the names of the primitives involved just for robustness.

If you end up doing something like this, make sure to provide facilities to upgrade files from one version to the next so you don't confuse users who still have files encrypted with old algorithms.

However, as you want simplicity, this may be overkill as a full-blown version management scheme. How simple does your API need to be? Since your library seems to be very high-level, I imagine you'll have a small toolchain of encryption and decryption programs to go with it eventually? Like OpenSSL's enc?


Commitment in two party protocols I have been reading Fast Secure Two-Party ECDSA Signing by Lindell, and I see that in key generating and signing (pages 9-10, especially visible from Figure 1), only the first party performs a commitment, whereas both parties perform a proof-of-knowledge. I have seen this paradigm also in different two party protocols. Though, I do not quite understand why both parties need to provide zero-knowledge proofs, but only the first party needs to provide a commitment? What's the reason for this?

There is no simple answer in general to this question. In this specific setting, the zero-knowledge proof is needed to extract the discrete log of the value sent by the party and this is needed in the proof. In some other two-party protocols, this isn't needed. So, there's no general answer.


Are there recommended modes of operation for lightweight ciphers? There are many recommended modes of operation for block ciphers as described by NIST here, e.g. for DES and AES.

However, I am struggling to find any for lightweight ciphers. I am particularly interested in modes of operation for PRESENT, Clefia and other standardised lightweight ciphers, and why they are suggested.

When using lightweight ciphers, the block size can make a huge difference to security. Fortunately, there has been a lot of work in recent years on tight bounds for modes of operations, and methods for going beyond the birthday bound. These modes are not stated as being especially for lightweight ciphers, so don't search for that. However, there is no doubt that when using lightweight ciphers with block sizes smaller than 128, then different modes of operation are needed (of course, depending on how much you want to encrypt). Here are three examples of work to look at (and the references therein):

CENC is Optimally Secure
New Blockcipher Modes of Operation with Beyond the Birthday Bound Security
Better Bounds for Block Cipher Modes of Operation via Nonce-Based Key Derivation


What does the number 256 in pairing curve BN256 indicate? There are many pairing based elliptic curves like MNT curves, BN curves, SS curves etc., When we say BN256 curve, what does the number 256 indicate? Is it some group order or number of bits required to represent some group?
How to figure out number of bits needed for representing each group G1, G2, and GT for curves like MNT224, BN256, SS512 etc.?

It's the size of the prime number of the underlying field in G1, G2 and GT.

In BN256, G1 is $E(\mathrm{GF}(p))$, G2 is a subgroup of $E(\mathrm{GF}(p^{12}))$ (or $E'(\mathrm{GF}(p^{2}))$ when using a twist) and GT is a subgroup of $\mathrm{GF}(p^{12})$.

Elements of G1 requires the same number of bits as $p$ for each elliptic curve point coordinate. Note that not all prime-friendly curves support cofactor 1, which means that in some cases we need a larger prime for a particular group order. (This is not the case in BN curves).

Elements of G2 require the same as $p^{k}$ for each elliptic curve point coordinate, where $k$ is the embedding degree of the curve. When using twists, we can reduce this by 2, 3, 4 ou 6 depending on the curve. BN curves have embedding degree 12 and support sextic twists, so we can use elements with the same size as $p^{12/6} = p^2$.

Elements of GT require the same size as $p^{k}$.


Explaining RSA to non-scientists I am to give a small lecture on quantum computing in a months' time and I want to shortly give intuition to the fact that Shor's algorithm shows that quantum computers will break RSA. Ideally, I would just state that we have this "evil algorithm" shown by Shor which does prime factorization "much faster" than we know to be possible on normal computers. My problem is that these people don't know what RSA is, they don't know that all numbers consist of prime numbers... they barely know what prime numbers are.
So how I illustrate the concepts of RSA and its relationship to prime numbers without the use of "complicated math"? (I don't want to start throwing around too many terms like modulus and stuff like that).
I was thinking of finding some drawings of keys to illustrate how asymmetric cryptography works, but I feel like there's a decent leap from that to just stating that "hardness of prime factorization is necessary for RSA to be secure".
Any input is greatly appreciated

This should be the flow of the description of RSA

RSA is a public key crypto system that everyone in the room who doesn't live in a cave uses pretty much every day. If you are using a computer to get on the internet, chances are you use RSA a lot.
Being a public key crypto system that means there is a public key that everyone knows and can use to encrypt messages and send them to you. Decrypting those messages is done using a private key that only you have. Pictures of Alice  and Bob  are always helpful here.
RSA works by using numbers of the form $N=p\cdot q$ where $p$ and $q$ are prime. If I have $p$ and $q$, then computing $N$ is really easy. But if I give you $N$, it turns out that breaking $N$ apart into the primes $p$ and $q$ is really hard.

Everyone can understand the math in that description. If someone has a hard time believing that breaking $N$ into $p$ and $q$ is really hard, then show them this

cb 12 fd 3b 32 8c 65 17 ff 39 2f 25 27 e3 80 ba bf d7 e4 5f 9a 65 a9 96 70 96 ef f9 49 36 79 97 e4 22 23 4c 9d af 5b 27 56 ef 6a 36 3f 4a 5d d1 44 fb 5d ca 21 7a f3 7c 39 cb ab 07 1c 6a ec 2c 21 64 37 1d 16 11 73 3f 7e 1f 68 a9 ea b5 bd 7a 05 6d 38 05 8d ef ee 23 1c e2 cf ec aa 22 d9 4e 84 47 38 c2 cd bc 1b 72 51 a3 64 46 f0 55 95 57 ee de 87 db 39 96 57 c0 42 58 1b 48 bc 5c 79 20 d9 96 4e e9 49 86 67 78 4f fe 4b 66 b0 f6 7d b9 e7 07 de c6 da d8 20 96 65 a0 de 4e a0 c4 76 f3 41 e7 e4 de c0 32 47 8d 5f a9 96 09 b8 46 5e e8 c0 3e d1 d0 69 e8 4c 26 3c 8e 69 1c 01 eb 61 ec ec 77 f0 e9 c2 fe 2a bf 8d 68 c2 1a 55 7d 61 ac 85 c8 f7 16 e2 a0 73 97 ff 26 5c 05 38 e6 e1 a7 89 13 d6 ac 13 aa 7e 44 87 83 07 ab f2 da a6 cf 38 a7 6b cb 17 07 62 08 a9 10 8e 58 8d 73 c6 e9

That is the $N$ that Bank of America uses and tell them that if they really think you are wrong, then the two of you should get together after the presentation so that you can go make a lot of money.

Personally I also like to show off pictures like this

Those are the inventors of RSA (Rivest, Shamir, and Adleman). By their picture they are obviously very smart, so the audience should just trust you that they know what they are doing.

In other words, if the audience doesn't need to understand all of the details of RSA, don't even try. Give them just enough that they can understand what they need to know. If they want more, deflect and take it offline as much as possible. Otherwise you will loose everyone else and probably the person asking the question.

Use lots of pictures and try to add some humor.


How many 12 bit integers output are required to reverse the Mersenne Twister? I am creating a web app that applies Python's random algorithm (Mersenne Twister) to generate random 12-bit integers. I am concerned as to how a user can predict future results by recording the needed number of sequence using API calls

import random
def rand12bits():
    return random.randint(0, 4095)

How many of these outputs do i need to predict the future sequence?

I am aware that with enough (624) observed outputs of 32 bit integers, it can be reversed. But in this case, the RNG is only giving off 12 bit integers. Am I missing something? Pardon me for my naivity I am new at this.

How many of these outputs do i need to predict the future sequence?

Well, to recover the RNG state, you need to observe 19968 bits of output (which translates into state); by seeing 12 bits at a time, you'll see enough after 1665 outputs.

One question you might have is: the 12 bits might not come from consecutive Mersenne Twister outputs, so we won't be able to trivial reconstruct the 624 word state.  This is true; however Mersenne Twister is completely linear in GF(2); hence we can describe the 19968 bit initial state as a linear function of the observed output states, and (with enough linear equations), solve for the initial state.  This is obviously more work than the trivial 'here's one intermediate 624-word state'; however it is practical.

The other thing to note is this estimate assumed that the initial state was completely unknown.  If it is partially known (e.g. the initial state was 256 bits of unknown values, followed by a known pattern), this reduces the number of outputs that are needed (because those known initial state bits give us free equations)


Hash or encryption function for challenge-response protocol? Say I have an authentication protocol where the shared secret is never transmitted. The server passes a challenge to the client and the client calculates a response using an algorithm where the challenge and the secret is used.

When choosing the algorithm, what are the benefits and drawbacks of using either a hash (such as MD5) or a symmetric encryption algorithm (such as AES)?

You need to first understand the security properties you are trying to achieve. Possible security goals:

It shouldn't be possible to answer convincingly if you don't know the secret
If you do know the secret and provide a response, an eavesdropper shouldn't be able to extract the secret from seeing the challenge and response
The challenger shouldn't be able to craft a challenge in such a way that it would leak information about the secret
An eavesdropper shouldn't be able to replay responses later and have them accepted

There may be other properties too.

Once you have a list of properties, you have to figure out why these properties hold. The reason should be things like "if the adversary could do that, they could also break the encryption" or "find collisions in a hash function."

How you choose to use a hash or an encryption function is based on the security properties you need and which primitive provides the correct notion of security. Hashing and encryption is not interchangeable. They provide very different properties.

There isn't anything we can say about the relative merits of hashing vs. encryption that applies universally to all challenge-response protocols. It is specific to the exact protocol and what properties you want from it. If you need more help, you could provide the two competing protocols and ask for help with (in a new question) evaluating their relative merits.


Extended Euclidean Algorithm in RSA I am trying to solve an RSA problem. In order to calculate $d$, I have to calculate $d$ with $e=3$ and
$$d\cdot e\equiv1 \pmod{40}$$
Obviously the answer is $d=27$, but I want to solve this with the extended Euclidean algorithm.
Though I know how this works, I am stuck because in the first step of the algorithm I get
$$40=3\cdot13+1$$

The remainder is 1 and the algorithm stops there.
How do I get $d=27$ by using the extended Euclidean algorithm?

I dont have a problem solving other similar examples that dont stop in the first step. But here, because it stops in the first step of the algorithm, I get confused.

First, 40 = 3*13 + 1

So, we have found 1 in the first step.
Then I can write 1 as following:

1 = 40 - 3*13 and this is equivalent to

1 = 40 - 13*3. 40 is equivalent to 0 mod40.

1 = -13*3. Here we get the inverse of 3 as -13 which is equivalent to 27.


How are private keys handed to users in Identity-based Encryption? I'm using IBE in my applied-crypto project in primitive form. I saw many articles about IBE, but didn't find how user can get private key is generated by PKG after EXTRACT method.
So, my question: What is the best practice to hand private key to user after EXTRACT method?

Crypto is nice and clean until you think about how to manage the keys. Common Identity-based Encryption (IBE) schemes have a tremendous disadvantage, that a trusted key authority generates private keys for some user and the user has to be given that key. The most common scenario for IBE is a corporate environment, so I will only ways to solve that in that environment. Note that all communication should be TLS encrypted.

If the user registers, they get an e-mail account and a private key that has that e-mail account as an identity. The security games in IBE schemes usually consider that an attacker can register many e-mail accounts and therefore request many the private keys with those. The schemes are proven secure when the attacker cannot derive the private key of an identity of another user.
This works fine, but the user would have to handle the key themselves and might even inadvertently misplace or leak it.
In a corporate environment, we usually have an IT department which either sets up the corporate workstation or adds a secure container on a BYOD-device. This administrator surely can write the private key for that user to a USB key and copy it to the configuration of the software that uses it. This makes it slightly harder for the user to do something dumb. Keep in mind that the private key can always be regenerated based on the e-mail account.
Other hardware is also possible. An administrator could generate the private key and push it to a smartcard which is then given to the user in person.
This has the added bonus that the user cannot really copy their privileges, because smartcards usually have a hardware-enforced copy-protection. They could still give their card to somebody else.

If the user abuses their privilege to access some data, be sure to have the necessary logs and a system in place to detect those events.


Illustrate NTRU using lattices I studied some papers related to NTRU. All these papers describe NTRU as a lattice based cryptosystem but I could not find any paper which illustrates NTRU algorithm from lattice point of view. It would be of great help if anyone describes NTRU algorithm using lattices and how the algorithm is based on Shortest Vector Problem(SVP).

Currently, there is no formal proof of NTRU being based on a lattice problem, but you can find a description of NTRU in terms of lattices in Section 5.2 of [Ber09]. For lattice-based attacks for NTRU you can review [HPS98]. There is, however, a provably-secure variant of NTRU that is ultimately based on the hardness of the SVP problem [SS11].

References:

[Ber09] Post-quantum cryptography (2009). Springer Berlin Heidelberg.

[HPS98] Hoffstein, J., Pipher, J., & Silverman, J. H. (1998). NTRU: A ring-based public key cryptosystem. In Algorithmic number theory (pp. 267-288)

[SS11] Stehlé, D., & Steinfeld, R. (2011). Making NTRU as secure as worst-case problems over ideal lattices. In Advances in Cryptology–EUROCRYPT 2011 (pp. 27-47).


Given a secure PRF $f(k, x)$, is $f(x, k)$ also a secure PRF? Let $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a secure PRF.
Define $F(k, x) = f(x, k)$.
Is $F(k, x)$ also a secure PRF?

No. A PRF assumes that the key is chosen randomly.

Example based on @LuisCasillas's comment: With a secret random key, you cannot determine the key from input output pairs. If you reverse the role of key and input, then you have the question: Can you learn "input" ($k$) from output ($f(x,k)$) and "key" ($x$)?

Yes. If $F(k, x) = f(x, k) = E_x(k)$, where $E$ is a PRP, then you can recover $k$ from one input/output pair of $F$. If your output is $c = E_x(k)$ then anyone can compute $k$ if they know $c$ and $x$.
$$k = E^{-1}_x(c) = E^{-1}_x(E_x(k))$$

(Where $E$ is block encryption and $E^{-1}$ is the inverse, decryption.

This answers your question because a PRP is a PRF because a permutation is a function. (Or maybe I'm wrong on that. There should be a caveat for small blocksizes. The presence or absence of collisions could distinguish a PRP from a non-PRP PRF.)

However PRPs are an example, not the exception. It's still not safe in general. There can be chosen key attacks, related key attacks, weak key sets, etc. A specific algorithm with no weakness when used correctly is not guaranteed to also be free of weakness when used incorrectly.


What is the reasoning behind the PRESENT key schedule? It seems there are few books on PRESENT and even fewer that give any reasoning behind the mechanics of the key schedule.

I understand how it works to the extent that I made a simple Excel program of it. I can clearly see all the steps and I assume it works as it matches test vectors.

However, I do not understand why certain bits were XORed rather than others, or why the round counters have to be in order $1-31$. My questions are:

In simple terms, how does the key schedule protect it from key related attacks?
What if (for instance) we changed the step $S[b_{78}b_{77}b_{76}b_{75}]$ to something else, such as $S[b_{74}b_{73}b_{72}b_{71}]$ or anything else. Would that make it weaker? Stronger? No different?
What if the round counters were not in the order $1,2,\ldots,31$? What if the round counters were any order of $1-31$? Again, would this make it weaker, stronger or no different?

Thx.

Question 1

  In simple terms, how does the key schedule protect it from key related attacks?

According to the paper "Lightweight Block Ciphers Revisited: Cryptanalysis of Reduced Round PRESENT and HIGHT", the non-linearity of the key schedule contributes to resistance to related key attacks:

  Related-key differential attacks, on the other hand,
  are also believed to be inapplicable because of the sufficient non-linearity due to [sic] key scheduling algorithm.

The above quote then points to a reference to New Types of Cryptanalytic Attacks Using Related Keys, which mentions the following:

  These attacks are based on the observation that in many blockciphers we can view the key scheduling algorithm as a set of algorithms, each of which extracts one particular subkey from the subkeys of the previous few rounds. If all the algorithms of extracting the subkeys of the various rounds are the same, then given a key we can shift all the subkeys one round backwards and get a new set of valid subkeys which can be derived from some other key. We call these keys related keys.

Then, the description of the key schedule they give is:

  The subkeys for each round are derived from the user-provided secret key by
  the key scheduling algorithm. We provide only the details of the key scheduling
  algorithm of Present-128 as it is the main target of this paper: 128-bit secret
  key is stored in a key register $K$ and represented as $k_{127}k_{126}\dots k_0$. The subkeys $K_i (0 ≤ i ≤ 31)$ consist of 64 leftmost bits of the actual content of register $K$. After round key $K_i$ is extracted, the key register $K$ is rotated by 61 bit positions to the left, then S-box is applied to the left-most eight bits of the key register and finally the round counter value, which is a different constant for each round, is XORed with bits $k_{66}k_{65}k_{64}k_{63}k_{62}$...

So the S-Box in the key schedule provides some non-linearity. And the addition of the counter may also serve to make the key schedule function for each round different and provide some resistance to the attack in [2] - If this is in fact the case, it is not explicitly stated anywhere that I can find.

Question 2

  What if (for instance) we changed the step $S[b_{78}b_{77}b_{76}b_{75}]$ to something else, such as $S[b_{74}b_{73}b_{72}b_{71}]$ or anything else. Would that make it weaker? Stronger? No different?

I presume this is about the main round function and not about the key schedule, since these indices don't appear to be a part of the key schedule.

The S-Box is applied on each group of 4 contiguous bits in parallel, so the answer is that both $S[b_{78}b_{77}b_{76}b_{75}]$ and $S[b_{74}b_{73}b_{72}b_{71}]$ are both performed. Swapping one for the other would have no effect.

As for why the 4-bit wide S-Box would be applied on contiguous sections of 4 bits in parallel, the answer is because it is really the only way to do it. The bit permutation that follows the S-Box scrambles the indices so that successive applications of the S-Box are applied to different groupings of bits. But these are separate steps, and doing something like $S[b_{73}b_{71}b_{72}b_{74}]$ simply re-arranges the permutation step to come before the application of the S-Box, rather than after it, and the S-Box would still be applied on 4 contiguous bits in parallel.

Question 3

  What if the round counters were not in the order 1,2,…,311,2,…,31? What if the round counters were any order of 1−311−31? Again, would this make it weaker, stronger or no different?

The reason they are in this order is for performance. If you examine the assembly instructions, using the round counter this way is the cheapest way to implement the operation. Using a permuted order of values 1-31 would require additional MOV/ADD operations. You want to minimize MOVs when designing a fast permutation.

The job of the counter is to ensure each round is different. So long as it is unique for each round, it does not matter so much what the actual literal value is, and so you may as well simply use the most efficient sequence available.


In EC with key chaining, is it possible to verify signature made by root private key using public key of derived keypair? I am not sure whether crypto.SE is the right place for this question, but I assume this is closest to on-topic here.

I am doing personal research on cryptography using elliptic curves. I can see that many projects starting to utilize deterministic key derivation (my terminology may be off here, see below what I mean by it).

What I am wondering is whether knowing how derivation process is done, is it possible to verify signature made my root private key using child public key?

Assuming:

random -> root keypair (rootPriv, rootPub) -> KDF(rootPriv) = childPriv, KDF(rootPub) = childPub

Then assuming two parties Alice and Bob:

Alice holds rootPriv/rootPub and childPriv/childPub.
Bob holds only childPub.
Alice wants to send message to Bob and ensure Bob receives it untampered. Alice then signs message using rootPriv and sends to Bob message and signature.

How can Bob (if it all possible) verify the signature knowing KDF and childPub without knowing rootPriv/rootPub/childPriv?

If that is possible for EC, does such requirement pose any restrictions on which curve can be used or on KDF? E.g. can any curve be used (Ed25519 or any other?) and would KDF need to be reversible in nature or any other restriction?

PS: This is about EC strictly though

I think you're asking about what are called hierarchical signature schemes or blinded signature schemes.  There's a root private key $a$ and public key $A$, and for any tweak $t$, there is a derived private key $a_t = f(a, t)$, and a derived public key $A_t = F(A, t)$, such that signatures made with $a_t$ can be verified by $A_t$, but the set $\{A_t\}_t$ is supposed to be indistinguishable from $\{A'_t\}_t$ for any other $A'$ to anyone who doesn't know $A$.  See an earlier answer for some references.

I think you're further asking about whether there is an easy way to compute $A$ given $A_t$ and $t$, although you didn't mention $t$ so maybe there is only one possible derived key pair.  Whether you can do this depends on the specific signature scheme, so let's pick one for illustration:

Signatures.
$\newcommand{\Z}{\mathbb Z}\newcommand{\concat}{\mathop{\Vert}}$Let $k$ be the field $\Z/(2^{255} - 19)\Z$, and let $E/k$ be the twisted Edwards curve $$E/k\colon -x^2 + y^2 = 1 - (121665/121666) x^2 y^2,$$ whose group $E(k)$ of $k$-rational points has order $h\ell$ for large prime $\ell$ and cofactor $h = 8$.  A public key is a point $A \in E(k)$, and a signature on a message $m$ is an encoded pair $(R, s)$ of $R \in E(k)$ and a 253-bit integer $s$ satisfying the verification equation $$[h s] B = [h] R + [h H(R\concat A\concat m)]\,A,$$ where $B$ is the standard base point and $H$ is the standard hash function mapping long messages to 512-bit integers.

A signer chooses a secret 256-bit scalar $a$ (usually with $a \equiv 0 \pmod h$ and $2^{254} < a < 2^{255}$ so that it is compatible with X25519 secrets, but this is irrelevant to signature security) and a secret 256-bit string $\kappa$ as their private key, and publishes $A = [a]B$ as their public key.  To sign message $m$, they compute $r = H(\kappa\concat m)$, $R = [r]B$, and $$s \equiv r + H(R\concat A\concat m)\,a \pmod \ell.$$

Hierarchical signatures.
So far this is just standard Ed25519.  For a tweak $t$, we can let
\begin{align*}
  a_t &\equiv a H(A\concat t) \pmod \ell, \\
  A_t &= [H(A\concat t)] A.
\end{align*}
Note that $$A_t = [H(A\concat t)]([a]B) = [a H(A\concat t)]B = [a_t]B,$$ so that $A_t$ is the ordinary Ed25519 public key for the private key $a_t$.

Question.
In this hierarchical signature scheme, given $A_t$ and $t$ but not $A$, and given a signature $(R, s)$ on a message $m$ under key $A$, can we verify the signature?

Suppose $H(A\concat t)$ is coprime with $\ell$; then it has a multiplicative inverse, say $\xi$, modulo $\ell$, so that $$\xi H(A\concat t) \equiv 1 \pmod \ell.$$  If $A_t$ is a scalar multiple of the order-$\ell$ point $B$, then $$[\xi]A_t = [\xi]([H(A\concat t)]A) = [\xi H(A\concat t)]A = A.$$
Thus we can recover $A$ from $A_t$ and $t$, and use that to verify the signature $(R, s)$ on $m$.

Under uniform random choice of $H$, then probability that $\ell$ divides $H(A\concat t)$ is negligible; under the standard $H$ based on SHA-512, the overwhelming majority of outputs are not multiples of $\ell$.  If this bothers you on aesthetic grounds (the probability is so small it is inconsequential for security), you could use $H(A\concat t) \bmod 2^{252}$ instead of $H(A\concat t)$ in the above protocol.

Adapting this to other hierarchical signature schemes and other curves is left as an exercise for the reader.


Given the key, the plain text and the cipher text can I calculate the IV used in CBC mode? If I have the plain text, the ciphertext and the key for an AES-128 CBC operation, can I determine the IV, even if I don't know the padding (assuming the padding follows one of the more common formats)?

I believe it should be possible since my understanding is that the IV is only used as an initial XOR of the plain text in encryption, and should, therefore, be able to be available like this:

AESDecrypt(key, ciphertext) => (PlainText XOR IV);
IV = ((Plaintext XOR IV) XOR (Plaintext))

Is this correct?

It is simple.

Just decrypt first 8 bytes encrypted buffer(1 block) in ECB mode (You only need encrypted buffer and key to do so) and then xor the result with the input buffer. Result will be IV.

In decryption of CBC, IV just affect first block. That's why only first block is incorrect in your case.


Does a stream cipher require a KDF when it's key is variable length? RC4 has a variable length key. Is it still necessary to use a key derivation function, such as PBKDF2, to initialize it?

Would using a single character password weaken it's output when compared to a block cipher using, for example, the SHA-256 hash of that same single character password as the key?

One problem with RC4 is that, while it does take a variable length input (up to 256 bytes), it's known not to be great at mixing those bytes together.  Specifically, we see correlations between the RC4 key and the RC4 output stream.

My first recommendation to you would be to use something other than RC4.  About the only advantage RC4 has over most other ciphers is that it is simple enough to be memorizable; for example, if you are going someplace where you don't want to carry any programs with you, if you can get access to anything programmable, you can type in an RC4 program, and have a good chance at having it work properly.  If you don't care about that (and you probably don't), then there are better options available.

My second recommendation (assuming that you ignore the first) is that you ought to obscure the relationship between your password and the RC4 key (as RC4 doesn't do a great job of obscuring the relationship between the RC4 key and the keystream).  Using a KDF to process the password would work; at the very least, you should use a hash function.  Now, I don't know whether the weaknesses in the RC4 key setup logic would be a concern to you; I also don't know that it's not; covering that potential weakness would appear to be a prudent step.

As for a single character password, well, that's going to be weak, whether you use a block cipher or RC4....


Which block cipher mode to use? I am working on securing a chat application, and I am not sure about which block cipher mode I should use. I am aware that I should avoid ECB as it's insecure, but what about CBC? I have watched several videos about block cipher modes, and I have read about it too, but I can't figure out what to use and why.

ECB sucks big time. CBC sucks slightly less, but still a lot.

Generally speaking, when you begin to use an encryption system, it is to achieve a number of security-related properties, e.g. confidentiality and integrity of data. An "encryption mode" is a way to turn some elementary cryptographic function (e.g. AES) into something that can process messages of variable but potentially large size, in a way which achieves these properties. AES itself is called a "block cipher", which means that it really is a key-indexed family of permutations in a space of blocks of bits of a given size. In other words, AES does not encrypt message, no more than a brick provides housing. The encryption mode makes a system that encrypts messages in the same way as a mason assembles bricks to make a house.

Classical modes of operation extend a block cipher into a system that can encrypt a message and hopefully provide confidentiality. ECB does a bad job of it (see the penguin pictures in that Wikipedia page). CBC is better but still flawed (e.g. if the IV is predictable, chosen plaintext attacks can be used to leak information; also, it requires padding, whose processing can lead to padding oracles). Historically, CBC was much used because it seemed to be the best we had, but that was only when compared to ECB, which is atrocious in that respect.

Most importantly, classical modes provide encryption but not integrity. In almost every conceivable scenario that warrants use of encryption, integrity is also needed. There are algorithms called Message Authentication Codes that can provide integrity (but not encryption). Some MAC can even be built out of block ciphers, with yet again some "modes". It turned out that getting encryption and integrity at the same time is not easy to get right. A lot of protocols got it wrong (e.g. SSL/TLS, ant it created a lot of trouble). Thus cryptographers took up to the challenge, and decided to make new modes of operations that provide encryption and integrity, and do it properly. The general term for that is authenticated encryption (specifically, "AEAD" for authenticated encryption with additional data). The most well-known of these modes will be GCM, CCM and EAX. These modes are built over a block cipher that processes blocks of 16 bytes (128 bits), usually AES.

It is also possible to make AEAD systems out of other things than block ciphers. E.g. one can assemble (again, with great care) the stream cipher ChaCha20 with the MAC algorithm Poly1305, to get a very decent AEAD system (see RFC 7539).

A very frustrating feature of cryptography is that you cannot test for security. You can read documents and watch videos and make some code that runs, and add lots of unit tests that show you that your creation works and data flows in and out properly. None of these tests will tell you whether the result is secure. The best way to test security (and it's not a good way, it's just that all others are worse) is the combination of the following:

You absorb all the known published science on the subject. For instance, for encryption, everything I wrote above should be known to you, and much more.
You write your stuff while being extra careful, and documented precisely why all the attacks you know of (and there should be many, thanks to point #1) cannot work.
You show your work to the world at large, and challenge all cryptographers to come test their skills against the might of your intellectual creation.
While the said cryptographers close for the kill and feast on the corpse of your erstwhile proud system, and explain in graphic details all the amusing ways they found to metaphorically disembowel your security, you slump in a corner and sob pitifully.
Then you get up, and start again at step #1, to do it properly this time.
After a few iterations, if you work hard, you may finally achieve the creation of a system that actually survives the onslaught of your vindictive colleagues. Congratulations! The security of your encryption system is not proven yet (in fact, theoretically speaking, it is not clear that a secure encryption system can really exist at all), but at least you will have some reasonably good reasons to assert that if there still are weaknesses in your last creation, they are not obvious.


Determining if a ciphertext can be decrypted I want to know what the state of the art in the following
cryptographic problem is.

Assume a public channel on which encrypted messages are exchanged,
using symmetric key encryption.  I hold a couple of secret keys.
For each ciphertext message on the shared channel, I need to determine if
I can decrypt the ciphertext. If not, I ignore the message, otherwise
I produce   the plaintext as usual. (In my use-case, authentication and message integrity are not relevant.)

What is the industry standard way of doing this, what are the pitfalls? I'd be interested in both, Dolev-Yao formal crypto modes, as well as concrete algorithms. I have no concrete adversary model in mind, what are good adversary models for this question?

In the first part of this answer, I consider the problem of decryption using leaked keys of a protocol not intended for that, which was my original reading of the question. I'll ignore that dominant industry practice is to use random symmetric session keys, leaving little opportunity to "hold a couple of secret keys" without knowing to what session they belong to.

The mode used with symmetric secret keys sometime provides message integrity (e.g. AES-GCM). This gives you a robust mean to determine if a secret key is correct or not, by checking if the integrity test passes. Odds of the wrong key accidentally letting the integrity check pass are demonstrably at least as low as the odds of forgery, thus won't occur for secure modes.

When only encryption is used, any known redundancy of the plaintext can be used to test if the correct secret key was used (deciphering with the wrong key will lead to incorrect plaintext which will be indistinguishable from random). An example of redundancy is the magic number found at the beginning of many practical payloads. Also, for encryption modes with message padding, often the padding is enough for reliable recognition of correct decryption.

For something more general, performing a chi-squared test of the distribution of bytes, or byte pairs for long enough messages, will often work. Exceptions include already compressed plaintext, and plaintext which really is cyphertext.

It is impossible to detect if the right key was used in attempting to decipher a payload consisting exclusively of cyphertext for some other cipher (including OTP, or AES-CTR), as this ability would match the modern definition of an attack of the other cipher.

The actual question turns out to be about building a demonstrably secure protocol intended for selective decryption. Such situation occurs in e.g. satellite internet or TV, and many network applications.

If hiding who the packets are for is not a security objective, it can not harm to include a label in clear in each packet, identifying the key that enciphered the packet, since that's public data. That's the practice in many TCP/IP protocols, where the label is that of the TCP/IP session, thus of the session key. That allows the receivers to decipher the packet with at most one key: the right one, if and only if they hold it. That saves effort/energy. Addition per comment: the tag must somewhat be decided. A sequential number would be fine, if practical (and again if that can be made public). Using a (first-preimage-resistant) hash of the key value would also do, if the hash and cipher are unrelated. The hash can be truncated to save bandwidth, but must be next to $(r-1+2\log_2m)$-bit wide if $m$ keys are around in order to limit the residual risk that two keys get the same tag to $2^{-r}$. An issue (more practical than theoretical) is that hashing a random value and checking if a (truncated) hash is among the keys might well become the best brute-force attack for an adversary, therefore the keys must be at least $(n+\log_2m)$-bit for $n$-bit security.

A situation that can be encountered (e.g. in satellite TV) is that many different receivers need the same large data set. In order to save bandwidth, an option is to encipher all the packets of such large data set with a random key dedicated to this set, and send (previously) that dedicated key enciphered with the key of each intended recipient. The label of the dedicated key can be in clear in the packets for the data set, and in the previous packets for the dedicated key value.

In the rest of this answer, I consider that hiding who the packets are for is an objective. I'll disregard side channel leaks from receivers (which in practice could very well reveal if a receiver uses or disregards a packet, contrary to the objective).

One option (already discussed) is to encipher the packets in a mode with integrity, such as AES-GCM. We do not need to modify this mode, thus can reuse its security analysis. Main issues with this approach: every holder of a key will need to check the integrity of every packets with its key(s), that's effort/energy; and modes with integrity require more effort/energy and bandwidth than pure confidentiality modes.

Another simple and unobjectionable thing is to start all plaintext packets with constant data (e.g. 12 bytes at zero), have all receivers decipher all ciphertext packets with their key(s) and stop wasting effort/energy on this packet/key pair when it is determined that the plaintext does not match the condition. If the cipher is secure by modern standards (CPA), adding this known plaintext demonstrably does not harm. Addition per comment: padding (or better prefixing) the plaintext with a cryptographic hash of the secret key before encryption would also work, but I see no clear advantage compared to the simplest solution. Don't put the bare secret key in the plaintext, that could conceivably have bad interaction with the cipher (e.g. AES-128's first step is a XOR of plaintext and key, so enciphering the key is a slightly special case).

If we go into something bidirectional (e.g. with acknowledge or retries), then things get more complex, and quite hard, in particular because the mere existence of packets sent by receivers will tend to be revealing of something we try to hide. And again, we should fear side channels.


Comparing elliptic curves over prime fields against EC over binary fields In which scenarios we go for prime fields or binary fields? Please indicate why we would choose one over the other.

Binary fields were developed since they yield more efficient implementations. This is especially true given the Intel PCLMULQDQ instruction. Note, that there are special types of Binary fields that are even more efficient, like Koblitz curves.

However, in general, our confidence in the security of these curves is less than for prime-field curves. Thus, in general, my preference is to use prime-field curves unless there's a special reason why not to.


How does one calculate the cryptoperiod? NIST Special Publication 800-57 defines a cryptoperiod as

  the time span during which a specific key is authorized for use by legitimate entities, or the keys for a given system will remain in effect. A suitably defined cryptoperiod:

  Limits the amount of information protected by a given key that is available for cryptanalysis,
  Limits the amount of exposure if a single key is compromised,
  Limits the use of a particular algorithm to its estimated effective lifetime,
  Limits the time available for attempts to penetrate physical, procedural, and logical access mechanisms that protect a key from unauthorized disclosure
  Limits the period within which information may be compromised by inadvertent disclosure of keying material to unauthorized entities, and
  Limits the time available for computationally intensive cryptanalytic attacks (in applications where long-term key protection is not required).

The standard goes on to describe risk factors affecting cryptoperiods:

  Among the factors affecting the risk of exposure are:

  The strength of the cryptographic mechanisms (e.g., the algorithm, key length, block size, and mode of operation),
  The embodiment of the mechanisms (e.g., FIPS 140-2 Level 4 implementation, or software implementation on a personal computer),
  The operating environment (e.g., secure limited access facility, open office environment, or publicly accessible terminal),
  The volume of information flow or the number of transactions,
  The security life of the data,
  The security function (e.g., data encryption, digital signature, key production or derivation, key protection),
  The re-keying method (e.g., keyboard entry, re-keying using a key loading device where humans have no direct access to key information, remote re-keying within a PKI),
  The key update or key derivation process,
  The number of nodes in a network that share a common key,
  The number of copies of a key and the distribution of those copies, and
  The threat to the information (e.g., who the information is protected from, and what are their perceived technical capabilities and financial resources to mount an attack).

It then goes on to list other factors that might affect cryptoperiods, such as the consequences of exposure, whether the key is used for communications or storage, and the cost of key revocation and replacement.

Specifically for a symmetric key wrapping key, for example, the standard recommends:

  The recommended originator usage period for a symmetric key wrapping key that is used to encrypt very large numbers of keys over a short period of time is on the order of a day or a week. If a relatively small number of keys are to be encrypted under the key wrapping key, the originator usage period of the key wrapping key could be up to a month. In the case of keys used for only a single message or communications session, the cryptoperiod would be limited to a single communication session. Except for the latter, a maximum recipient usage period of 3 years beyond the end of the originator usage period is recommended.

My specific question is what constitutes "very large numbers of keys" and "relatively small number of keys" in the above recommendation?
More generally, is there a standard formula to compute the optimal cryptoperiod taking all the risk factors listed above into account?

As a specific example, please consider the following scenario:
1. Protection consists of AES-256 in CBC mode and HMAC based on SHA-256
2. 100,000 keys issued per month with this protection to manufacturers, for personalisation of consumer units
3. Probability of compromise is thought to be "low"
4. Ability to exploit compromise is thought to be "difficult"
5. However, confirmed compromise will entail recall of affected consumer units to their original factory

This is all about the question of risk assessment.  Are you willing to risk all devices together so that if one key is compromised, they all have to be returned?  What is the cost of one return, 100 returns, or 100,000 returns?  What is the expense of issuing a master key?  Of issuing ten master keys?  Of issuing a thousand?

Do you have an estimate for how hard it might be for an attacker to compromise a device and extract the key?  Is it a year's effort?  Is the payout worth it to an attacker to spend a million dollars to obtain your keys?  If he breaks it once for a million dollars, does cracking a second key cost him another million, or does it only take him an additional four hours?

Cryptoperiod doesn't enter too much into this discussion, other than you should also consider "time" as one of the factors.  If someone hacks the key out after a year of owning it, does that mean all your 2012 model devices are compromised?  Or if you don't change the keys every period, that means every device you make from 2012-2017 are all equally at risk from a single compromise.

Where time plays a more important role is in the length of protection needed for your secrets.  Consider a DishTV receiver.  The session key is only needed as long as the transmission lasts, because most Dish pirates don't record an encrypted stream in hopes of decoding it next year after cracking the keys - they only want their Dish to work right now.  Those keys don't need the same duration of protection that a long-term valuable (like a credit card number) requires.

The large number/short period vs. small number/long period idea is one way to help you estimate the overall number of exposure per key.  If you're deploying an encrypting radio to 100,000 people, and they're each going to use one session key per radio per day, that's X amount of traffic.  If you deploy encrypting radios to 100 people, but each goes through a thousand session keys per day, it's the same amount of traffic.  If you think you can only afford to risk one million session keys per primary key, your cryptoperiod would be 10 days.


How to perform Stampery.com's Merkle Proof? I am using the Stampery API to anchor hashes into different Blockchains. I wanted to independently verify that my hash with the given Merkle Proof from Stampery.
I tried to follow their Whitepaper but with no success.

What I've tried so far is the following:

Hash:
265D0E134C56080CBD9049427C39C5B6425FDC909FC16072FC4AA0D6957B7264

Merkle proof:
R 4C83C6F2C253CD8B44A3EDEB076B65877BEBA0DCA2B85497C3B7E74785EC5618
R 9F016BF9C9CD4C4F55D171C211666B214C38C7FBDDCED9BC5D2D4239E6C7CE19
L 5461D61A21A6EF783737F328DA8BB8BF5D24804B8574F0E6CBEC076D026C2FBE
R FD894CD6289981AEEC0CE250C841257276FE56D2A003BFE482B2E669BA4A93AC

Merkle root:
16DA7D280DC9B527985F8749636DFB5E3C6B3856A4C7F7CB3E8BA6AEC9F33EB7

Code:

var mP = [
    "4C83C6F2C253CD8B44A3EDEB076B65877BEBA0DCA2B85497C3B7E74785EC5618",
    "9F016BF9C9CD4C4F55D171C211666B214C38C7FBDDCED9BC5D2D4239E6C7CE19",
    "5461D61A21A6EF783737F328DA8BB8BF5D24804B8574F0E6CBEC076D026C2FBE",
    "FD894CD6289981AEEC0CE250C841257276FE56D2A003BFE482B2E669BA4A93AC"
];

r = SHA3( SHA3( mP[2]+SHA3( SHA3(hash+mP[0]) +mP[1])) +mP[3] );

with $r \neq merkleRoot $. Here I simply applied the SHA3 (Keccak) algorithm (as mentioned in the paper) successive, taking into account the L and R from the Merkle Proof. I guess, that the Ls and Rs decide the order of the operands of the SHA3 function.

I am not sure what I am doing wrong and would be happy for any help!

Edit:
With the help aesedepece I got a minimal node version running:

var crypto = require('crypto');

function SHA256(x) {
    var buf = new Buffer(x, 'hex');
    return crypto.createHash('sha256').update(buf).digest('hex');
}

var hash = "265D0E134C56080CBD9049427C39C5B6425FDC909FC16072FC4AA0D6957B7264";
var mP = [
    "4C83C6F2C253CD8B44A3EDEB076B65877BEBA0DCA2B85497C3B7E74785EC5618",
    "9F016BF9C9CD4C4F55D171C211666B214C38C7FBDDCED9BC5D2D4239E6C7CE19",
    "5461D61A21A6EF783737F328DA8BB8BF5D24804B8574F0E6CBEC076D026C2FBE",
    "FD894CD6289981AEEC0CE250C841257276FE56D2A003BFE482B2E669BA4A93AC"
];

var merkleRoot = "265D0E134C56080CBD9049427C39C5B6425FDC909FC16072FC4AA0D6957B7264";

var r = SHA256(SHA256(mP[2]+SHA256(SHA256(hash+mP[0])+mP[1]))+mP[3]);
console.log(r);

You seem to be doing everything right. The problem here is that you are using the verification process from BTA v5 on a proof generated by BTA v6 (the LTS version of our API). The v6 whitepaper is here.

Put simply: you'll need to use SHA256 instead of SHA3:

r = SHA256(SHA256(mP[2]+SHA256(SHA256(hash+mP[0])+mP[1]))+mP[3]);

Also make sure your hash functions operate on a byte level, not on the hexadecimal representation of the hash digests.

Please don't hesitate to ask for clarification!