How do I detect a failed AES-256 decryption programmatically? I have implemented a simple encryption/decryption program based on AES-256 in CBC mode1.

Actually, it is more precise to describe it as a compression+encryption / decryption+decompression program.

If one provides the wrong key to the decryption+decompression function, the decompression stage will explicitly fail, as expected, since the decrypted content (being based on the wrong key) will be just noise.

I would like to modify the decryption phase of the scheme so that it detects on its own that the wrong key has been used, before it proceeds to the decompression phase. I am looking for a scheme to support this functionality that does not weaken the overall cryptographic strength of the framework.

A naive approach would be to generate the encrypted content as2

AES256_CBC(key, iv, SENTINEL_STRING + plaintext)

where SENTINEL_STRING is a string that the decryption phase can know in advance. While I am being naive about it, I could make the SENTINEL_STRING be equal to the key, for example.

I imagine there are pretty standard ways to solve this problem. In fact, for all I know, the design of AES-256-CBC already has built into it a way to check that decryption succeeded.

I hope someone can enlighten me on these matters.

Also, if this problem is common enough to have a generally accepted name (suitable as search engine fodder) please let me know.

1 For what it's worth, my current implementation of this uses Python's pycrypto module, but an earlier implementation used Perl's Crypto::CBC package. Both versions can reciprocally decrypt+decompress files compressed+encrypted by the other. I bother mentioning all this to stress the fact that this question is primarily about AES-256-CBC in general, and not about any specific implementation of it.

2 I hope my ad-hoc notation here is not too stupid. I mean it as a shorthand for "encrypt the string SENTINEL_STRING + plaintext with AES-256 in CBC mode, using the key key and initialization vector iv".

You should use an authenticated encryption mode.  There are several reasons for that, but one (relatively minor) one is that it automatically gives you the ability to detect incorrect keys, since the authentication will fail.

If you insist on using a traditional non-authenticated encryption mode, or if you'd like to have some way of distinguishing "incorrect key" from "corrupted ciphertext", you can include a key check value together with the ciphertext, and verify it before attempting decryption.  There are several possible ways to implement one.

A traditional method is to encrypt an all-zero block using the raw block cipher (i.e. "ECB mode") and use the resulting ciphertext as the key check value, but note that this makes it possible for an attacker to tell whether two messages have been encrypted using the same key by comparing the key check values.  Alternatively, assuming that you're using an authenticated encryption mode anyway, you could just generate the key check value by encrypting an empty message using the same mode.  Assuming that you're using a unique nonce / IV for each encryption, as you should be, this should eliminate the information leak by making every key check value also unique.

(BTW, note that compressing data before encryption can leak (extra) information about the plaintext.  Basically, this happens because all general-purpose encryption schemes necessarily leak information about the length of the plaintext, and compression makes the plaintext length depend on its content.  Padding reduces this leak slightly, but does not eliminate it.  This has been used in actual attacks.)


How is the Swiss post e-voting system supposed to work, and how was it wrong? I read that the Swiss post had an e-voting solution developed, made it possible to obtain the source code for review, and that vulnerabilities were found.

Apparently we are not talking about the inherent and well-known issues of e-voting: it can't prevent purchasing of vote, and penetration of the voter's device can allow turning a vote around. Nor are we talking about the (reportedly laughable) code quality for the IT infrastructure, or its vulnerability to Denial of Service attack.

No. It was found a cryptographic flaw of some kind, by three independent teams:

Sarah Jamie Lewis, Olivier Pereira and Vanessa Teague: Ceci n’est pas une preuve, The use of trapdoor commitments in Bayer-Groth proofs and the implications for the verifiabilty of the Scytl-SwissPost Internet voting system (see introduction)
Rolf Haenni: Swiss Post Public Intrusion Test: Undetectable Attack Against Vote Integrity and Secrecy (referring page).
Thomas Edmund Haines (NTNU).

How was the proposed system supposed to work, and what was wrong with it or its implementation ?

We can stand reassured by the officials: the deployed e-voting systems can't have this flaw.

In the Swiss Post electronic voting protocol, after voters submit ballots, they are scrambled individually and shuffled together so that they cannot be traced back to voters to find who voted for whom—variously called ballot secrecy, privacy, or anonymity—before they are tallied.

But since the ballots are bits in an electronic system, not physical artifacts, it would be easy to fabricate shuffled ballots inside the magic vibrating silicon crystals in the computer that implements the shuffler.  So the shuffler must also print a receipt that anyone in the world can use to verify that it is just a shuffling and not any other kind of alteration—part of universal verifiability of the election—while still keeping it secret who voted for whom.

The method of universal verifiability in the Swiss Post protocol, as in any electronic voting protocol with ballot secrecy, involves a lot of complicated math.  And it turns out that the way the math was designed enables the vote shuffler to trivially forge a receipt for a fraudulent ‘shuffle’ that changes the outcome of the election.

How does it work?

Let $m_1, m_2, \dots, m_n$ represent filled-out ballots in an election.  We want to keep the ballots secret, but compute the vote tally, and let the public verify the vote tally.

The poll workers see who submitted each ballot $m_i$, so we first encrypt the ballot as $c_i = E_k(m_i, \rho_i)$ to conceal it from the poll worker who puts it in the pile of ballots, where $E_k(m, \rho)$ is a randomized public-key encryption scheme with randomization $\rho$.  Randomization means the poll worker can't just check whether $c_i = E_k(b)$ for each possible ballot $b$ to recover what $m_i$ is.
The vote counter, who knows the secret key, then takes the pile of encrypted ballots, decrypts them, and tallies the results.

Since the poll worker could pass along who voted in which order, we enlist the aid of a vote shuffler to shuffle the votes into the order $c_{\pi(1)}, c_{\pi(2)}, \dots, c_{\pi(n)}$ for a secret permutation $\pi$.*
Since the vote counter could eyeball $c_{\pi(i)}$ to discern whether it is the same as $c_j$ and thereby recover what $\pi$ is, we also ask the vote shuffler to scramble each vote without changing the ballot it conceals.

If $E_k$ is homomorphic in the message and randomization, meaning $$E_k(m_1 m_2, \rho_1 + \rho_2) = E_k(m_1, \rho_1) \cdot E_k(m_2, \rho_2),$$ then we can scramble the votes by $$c'_i = c_{\pi(i)} \cdot E_k(1, \rho'_i) = E_k(m_{\pi(i)}, \rho_{\pi(i)} + \rho'_i)$$ for secret randomization $\rho'_i$.*  Then we pass $c'_1, c'_2, \dots, c'_n$ on to the vote counter.

Members of the public only have their own receipts $c_i$, which without the private key are indistinguishable from one another and from the $c'_i$.  To have confidence that the vote counter or vote shuffler isn't fraudulently changing the outcome of the election by replacing $m_i$ by some malicious $\hat m_i$, the system must be verifiable to members of the public.†

The canonical example of a homomorphic randomized public-key encryption scheme is Elgamal encryption $E_k(m, \rho) := (g^\rho, k^\rho \cdot m)$ where $g, k, m \in G$ are elements of a group $G$ in which discrete logs are hard, and the secret key for $k$ is the exponent $x$ such that $k = g^x$.  Here multiplication of ciphertexts $(a, b) \cdot (c, d)$ is elementwise, $(a \cdot c, b \cdot d)$.

There have been many systems over the years, of varying degrees of efficiency, to prove that what the vote shuffler sends to the vote counter to tally is, in fact, the set of $c_{\pi(i)} \cdot E_k(1, \rho'_i)$.‡  One of them is Bayer–Groth (full paper).  There's a lot of cryptidigitation building on decades of work to make an efficient non-interactive zero-knowledge proof—a receipt that any member of the public can use offline to verify that the $c'_i$ are in fact the $c_{\pi(i)} \cdot E_k(1, \rho'_i)$, without learning what $\pi$ or the $\rho'_i$ are.

The key part in question is the use of Pedersen commitments to commit to exponents $a_1, a_2, \dots, a_n$ with randomization $r$ by sharing the commitment $$\operatorname{commit}_r(a_1, a_2, \dots, a_n) := g_1^{a_1} g_2^{a_2} \cdots g_n^{a_n} h^r,$$ where the group elements $g_1, g_2, \dots, g_n, h \in G$ are independently chosen uniformly at random.

The commitment itself gives no information about $(a_1, a_2, \dots, a_n)$ without $r$ because all commitments are equiprobable if $r$ is uniform—that is, Pedersen commitments are information-theoretically hiding.  But the commitment and randomization $r$ enable anyone to verify the equation for any putative $(a'_1, a'_2, \dots, a'_n)$ to get confidence that they are the $(a_1, a_2, \dots, a_n)$ used to create the commitment in the first place: if you could find a distinct sequence $(a'_1, a'_2, \dots, a'_n) \ne (a_1, a_2, \dots, a_n)$ and randomization $r'$ for which $$\operatorname{commit}_r(a_1, a_2, \dots, a_n) = \operatorname{commit}_{r'}(a'_1, a'_2, \dots, a'_n),$$ then you could compute discrete logs of $h$ and $g_i$ with respect to one another—a pithy summary of which is that Pedersen commitments are computationally binding under the discrete log assumption.  (Proof: If $g_1^{a_1} h^r = g_1^{a'_1} h^{r'}$, then $\log_{g_1} h = \frac{a'_1 - a_1}{r - r'}$.)

The Bayer–Groth shuffler uses Pedersen commitments to commit to one $\pi$ and to the randomization values $\rho'_i$ in the receipt that the public can use to verify the set of votes submitted to the vote counter.  If the vote shuffler could lie and claim to use a permutation $\pi$, while they actually use a function that repeats some votes and discards others, then they could fraudulently change the outcome of the election.  The Lewis–Pereira–Teague paper goes into some details of how this works.

One way to look at this reliance on Pedersen commitments is that the discrete logarithm problem seems hard, so we just have to choose the commitment bases $g_1, \dots, g_n, h$ independently uniformly at random.

The obvious method to pick group elements independently uniformly at random is to pick exponents $e_1, \dots, e_n, f$ independently uniformly at random and set $g_1 := g^{e_1}, \dots, g_n := g^{e_n}, h := g^f$.  This is what the Scytl/Swiss Post system did.
Another way to look at this is holy shit, the exponents $e_1, \dots, e_n, f$ are a secret back door, knowledge of which would enable the vote shuffler to commit essentially arbitrary vote fraud—just like the Dual_EC_DRBG base points.

The election authority could mitigate this by choosing commitment bases using another method, like FIPS 186-4 Appendix A.2.3, which probably makes it difficult to learn the back door exponents, and which can be verified; this is allegedly what Scytl has elected to do to fix the issue, although I have no idea whether they have published the hash preimages necessary to conduct the verification.

This may sound like a trivial mistake: oops, we forgot to zero a secret.  But it illustrates a deeper problem.

The commitment bases $g_1, \dots, g_n, h$ serve as a common reference string in a standard technique (paywall-free) for converting an interactive zero-knowledge proof system into a non-interactive zero-knowledge proof receipt like the vote shuffler is supposed to print out.

In an interactive proof system, the verifier might choose an unpredictable challenge—like which tunnel to come out of in the story of Ali Baba and the 40 thieves—which the prover must answer correctly.  What if we want to make a non-interactive proof receipt that we can publish on a web site for anyone in the public to download and verify?

In some protocols, like signature schemes such as Schnorr's derived using the Fiat–Shamir heuristic, the challenges can be replaced by a random oracle: a random function that the prover can evaluate on the transcript so far to imitate an unpredictable challenge that the verifier might have submitted, but that the prover has no control over.  To instantiate such protocols, we choose a hash function like SHAKE128 that we hope has no useful properties the prover can exploit to forge fraudulent proofs.

Addendum: This post was getting too long already, but two weeks after the flaw detailed here was reported, the same researchers reported another fraud-enabling flaw in the misuse of the Fiat–Shamir heuristic—the designers neglected to feed in the entire transcript of committed values into the hash function (‘random oracle’), which is crucial to the security of the Fiat–Shamir heuristic.  That flaw also appeared in the New South Wales Electoral Commission's iVote system based on Scytl's software, despite the NSWEC's public claims to be unaffected (archived).
Similarly, in some protocols like Bayer–Groth we can use a common reference string: a predetermined bit string chosen randomly and known in advance to the verifier and prover.  To instantiate such protocols, we need a system to pick a random string in advance with negligible probability that the prover can exploit properties of, like we get with FIPS 186-4 Appendix A.2.3.  If the prover can influence the common reference string, the proof means nothing.

This is part of the security contract of a cryptosystem.  To get any security out of AES-GCM, your obligation is to choose the key uniformly at random and keep it secret and never reuse it with the same nonce.  To get any security out of a Bayer–Groth vote shuffler, the verifier and prover must agree in advance on a common reference string that the prover has no control over.  In the Scytl system, the prover chose the common reference string.  Not only did this violate the security contract, but it demonstrated a profound failure to understand the basic premises of the non-interactive zero-knowledge proof system they used.

The public evidence is unclear about whether the authors knew this would serve as a back door, and the Lewis–Pereira–Teague paper cautions that this could be a product of incompetence rather than malice—the technical nature of the flaw was known internally since 2017 (archived) but it's unclear the whether consequences were understood.  It could have been incompetence on the part of NIST that they adopted Dual_EC_DRBG—NIST recognized early on that there was something fishy about the base points and was told not to discuss it by NSA.

The first order of business is not to argue about whether the software vendor Scytl was malicious or incompetent, but to be taken seriously enough by election authorities to demand real scrutiny on designs, not a sham bug bounty hampered by an NDA just before deployment, and to review the process of how we got here to ensure that designs with back doors like this must never even come close to being deployed in real elections because they enable extremely cheap arbitrarily massive unverifiable vote fraud.

(One can argue whether the larger problems arise from undetectable centralized fraud in electronic voting; distributed fraud in voting by mail; or voter suppression by gerrymandering, felony disenfranchisement, and closure of polling stations.  One can argue about other IT issues, about the importance of paper trails and mandatory risk-limiting audits, etc. Such arguments should be had, but this question is not the forum for them—consider volunteering as an election worker instead or talking to your parliament!  This question is specifically about the technical nature of the misapplication of cryptography, whether negligent or malicious, by Scytl and Swiss Post.)

* We assume that there is an omniscient mass surveillance regime monitoring the every action of the vote shuffler to ensure they do not collude with anyone else to reveal secret ballots.  The omniscient mass surveillance regime is also honest and would never dream of colluding with anyone themselves—not wittingly.

† We assume that the public consists entirely of people with PhDs in cryptography, like the country of Switzerland.

‡ The vote counter must also be able to prove that the tally it returns is the sum of the plaintexts of the encrypted ballots that are fed to it, which we will not address here—the specific back door under discussion here is in the vote shuffler.


Converting Letters into Numbers for Creating an Authenticator In Section 2.2 of DJB's Polynomial Evaluation and Message Authentication, he describes the construction of the first provably secure authenticator, which was the work of Gilbert, MacWilliams, and Sloane.

Fix a finite field $k$. The legitimate sender generates 9 independent
uniform random secrets $r1, r2, . . . , r8, s ∈ k$. The sender meets
the legitimate receiver in private and tells the receiver the same
secrets $r1, r2, . . . , r8, s$. Later the sender wants to send a
message $m$ to the receiver through a public network, where $m$ is a
sequence of 8 components $m1, m2, . . . , m8 ∈ k$. The sender
transmits $m$ together with the authenticator $a=m1r1+···+m8r8+s ∈ k$.

Fine.  Let's say the entire message looks like this:

sorry mrjoh nsony ourf light hasbe encan celed

This message is conveniently broken into a sequence of eight components.
What I cannot figure out is the simple question of how to represent the letters/blocks numerically for the computations shown above.
What is the best way?

Normalize the input and encode it using UTF-8. That gets you octet strings. Then the particular block size depends on the system you're using. For Poly1305, treat 16-byte long octet strings as little-endian integers. RFC8439 provides the way to convert a message composed of bytes into appropriately sized blocks (for Poly1305, other such systems need different sizes):

o ...divide the message into 16-byte blocks.  The last one might be shorter:

o  Read the block as a little-endian number.

o  Add one bit beyond the number of octets.  For a 16-byte block, this is equivalent to adding 2^128 to the number.  For the shorter block, it can be 2^120, 2^112, or any power of two that is evenly divisible by 8, all the way down to 2^8.

o  If the block is not 17 bytes long (the last block), pad it with zeros.  This is meaningless if you are treating the blocks as numbers.


What is blindness and forgeability in Chaum's blind signature scheme? I am going through the voting protocols. I know how blind signature works (Blind Signature), but why is blind signature - unconditionally ”blind”, conditionally ”unforgeable" (as highlighted in the following paragraph). How do you define blindness and unforgeability? Please explain. If possible give an illustration.

There is a possibility of guaranteeing the anonymity of voting unconditionally by means of conventional, i.e. classical cryptography, based on mathematical encryption. The corresponding voting protocol is based on the principle of ”sender untraceability”, meaning such a communication scheme, where the recipient of several messages from several senders cannot determine which message came from which sender. Such a communication can be realized with unconditional security in the sense that the recipient is unable to establish any relation between the messages and the senders, even being in possession of infinite computational power. However, the very property of untraceability creates, in the case of voting, an additional problem of determining which ballots come from legal voters, since illegal participants can send ballots in an untraceable way. This problem is solved by a special ”ballot issuing” protocol (based on the technique of ”blind signature”) providing each legal voter with an ”unforgeable” and ”blind” digital ballot, which is used for sending a vote. The term ”unforgeable” means that the ballot cannot be cloned, while the term ”blind” means that the ballots are in no way related to the identities of legal voters. The ballots in the ballot issuing protocol are unconditionally ”blind” but only conditionally ”unforgeable”, that is a person in possession of rich enough computational power is able to vote instead of legal voters. Thus, the property of ”non-exaggeration” is realized by the overall voting protocol in a conditional way only.

It (Blind Signature) is unconditionally blind, because if you take a blind message $m\cdot r^e$ and then sign it, you get $m^d \cdot r$ which distributes like a random element in a subgroup of $Z^{*}_{N}$ so even if you have unlimited computational power you can't extract $m^d$ from looking at $r \cdot m^d$. Even if you factor $r \cdot m^d$ you won't know for sure which parts belong to $r$ and which to $m^d$.

However if you have infinite computational power you can just find $d$ from $(N, e)$, hence it is conditionally (computationally) un-forgable.


AES-128 - encrypted public domain text I work with Historical Geographic Informations Systems on the academic level. I note this to give you an idea of my technical knowledge when it comes to computing, but that most of my knowledge of cryptography is a little outdated I'm more familiar with say the caesar cipher, the Enigma Machine, VENONA, etc from reading about them history and much less with modern encryption systems like PGP or AES.

I came across a text file of an encrypted public domain work which use AES-128 (XML encryption standard). From my initial research on google a brute force attack is unfeasible at that bit length. My question is if I already know what large portions of the encrypted text says when decrypted, because its a public domain work, is that something that can be use to decrypt the file?

if I already know what large portions of the encrypted text says when decrypted (..can it be used..) to decrypt the file?

No, beyond validating a candidate key. With modern ciphers, knowing large portions of the plaintext does not help decipher the rest. They are designed to be immune to Known Plaintext Attack, and even to Choosen Plaintext Attack. And as far as we know, AES-128 in CBC mode (as prescribed in the XML encryption standard) achieves that goal well.


How to glean info from a message that simply has the letters shuffled? Suppose someone had published a several hundred page (sensitive) book, but had randomized all of the letters in an order known only to them (e.g. with a vector of random numbers of the same length as the book's characters).

This initially strikes me as relatively riskier than something of comparable simplicity (like a one time pad) since the letters are all in the clear.  But, I can't quite see how an attacker would benefit much from that information.  Are there known attacks on this sort of thing to learn things about the text?  What could be learned?  Could one maybe at least tease out an idea of what the book was about?  At what message lengths (if not all) could it be a big problem?

Hopefully this doesn't qualify as asking the community for "peer review of a cryptographic scheme"!

What you are describing is called a transposition cipher.

First of all, it would be easy to detect which method you are using since the frequency distribution of your cipher text will be the same as the language of the plain text.

I think the biggest problem with using only transposition as opposed to a combination of both substitution and transposition is that you do not need to manipulate the whole message in order to find the key (i.e the order in which you shuffled it) finding how one word was shuffled reveals how the whole plain text was shuffled.

Another weakness is that even if you do not have the correct key, being close to it already reveals a lot of information.

A way to break this cipher would be to take a small chunk of cipher text and shuffle it around until you find some anagram to a known word, then solve the anagram.

Edit :

After rereading the question, if you were to shuffle your text randomly as you said in your example it is similar to using a one time pad for the exception that the key to the pad would be draw from a different distribution since you probably will not have equal amounts of each letter of the alphabet in your book.

Let $m$ be the book and $c$ be the shuffled book you can derive a key $k$ such that $|k| = |m|$ and $m\oplus k = c$.

$k = m\oplus c$.


What is the computational cost of guessing symmetric keys for two ciphers that decrypt to the same input? A message m is encrypted with two symmetric keys, resulting in two ciphers c,

c1 = encrypt(m, key1)

c2 = encrypt(m, key2)

What is the computational cost of guessing symmetric keys for both ciphers that decrypt to the same message?

I stick to a symmetric, non-authenticated cipher; and unless otherwise specified I consider it as a black box.

By an entropy argument, for the problem to be consistently solvable, we need $m$ to be slightly larger than the key size if $m$ is known, or slightly larger than twice the key size if $m$ is unknown (I'll suppose that); otherwise, chance is that there are multiple solutions, and we have no way to find which is correct.

Things  depends on if $m$ is given or not, and if the cipher is deterministic (e.g. a block cipher, or one in ECB mode) or randomized (e.g. a stream cipher or a block cipher in CTR mode).

If $m$ is given and the cipher is deterministic, we can enumerate keys $K$ among $2^k$ (say incrementally), encipher $m$ with $K$, and conclude that $K$ is neither the desired $K_1$ nor $K_2$ when the ciphertext matches neither $c_1$ not $c_2$ (which is, most of the time). Our explored $K$ will include both $K_1$ and $K_2$ with probability $1/2$ after exploring $2^{k-1/2}$ keys (rather than $2^{k-1}$ for one key). The expected number of encryptions to find both keys is $2^{k+1}/3$ (rather than $2^{k-1}$ ), an increase by $1/3$. The expected work is increased slightly more (because of the extra comparison).

Per request: The number of encryptions is $\max(K_1,K_2)+1$. The keys behave as two uniform and independent discrete variables in $[0,2^k[$. As $k$ grows, the ratio of the expected number of encryptions to $2^k$ thus converges (quickly) to the mean value of the largest of two continuous variables in $[0,1[$. Thus a first-order approximation of the expected number of encryptions to find both keys is
$$2^k\int_{x=0}^1\int_{y=0}^1\max(x,y)\ \mathrm dx\ \mathrm dy=2^k\int_{x=0}^1\left(\left(\int_{y=0}^x x\ \mathrm dy\right)+\left(\int_{y=x}^1 y\ \mathrm dy\right)\right)\mathrm dx\\=2^k\int_{x=0}^1\left(x^2+1/2-x^2/2\right)\mathrm dx=2^k(1/6+1/2)=2^{k+1}/3$$

If $m$ is given and the cipher is non-deterministic, we can enumerate keys $K$ as above, decipher $c_1$ and $c_2$ with this key, and compare against $m$. As above, our explored $K$ will include both $K_1$ and $K_2$ with probability $1/2$ after exploring $2^{k-1/2}$ keys. However, until we have found one of the key, we need to decipher twice with each $K$. The expected number of decryption is $2^k$, twice as much as for one key. The expected work might be increased rather less, depending on internals of the cipher (e.g. for AES, the derivation of round subkeys can be shared between the two decryptions in the phase where neither key is available).

If $m$ is unknown, we can use a Meet-in-the-Middle attack: we decipher $c_1$ using all (or most) $K$, building a dictionary of possible $m$; then we decipher $c_2$ enumerating $K$, until we find the resulting $m$ in the dictionary. The expected number of decryption is $2^{k+1/2}$, three times as much as for one key and known $m$. A lot of memory is necessary, but there are workarounds at the cost of only moderately more work; see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website)

If we "open" the cipher's black box, things change, possibly sizably. In particular, for ciphers allowing on-the-fly encryption/decryption, we need not fully encipher/decipher a large $m$ in full. And for some ciphers (e.g. 3DES), there might be shortcuts.


Does a key derivation function always generate an even distribution of bits in the resulting key? I am a student of crypto.  During our study course, we went into the AES-128 algorithm.  All the examples given used an initial key k, 128 bits and we only briefly touched on the key derivation of PBKDF2.  We looked at the key as a series of bits of fixed length and discussed the security and so forth.

If the 128-bit key is generated from a function that takes a password as an input, will the distribution of 0 and 1s across the resulting key k always be random?

Let's say I have a dictionary of 'real' passwords from say a leaked website (a good sample size of say 1M), and put these passwords through a PBKDF2 function and recorded the keys k1, k2, through kn (where n=1,000,0000).

If I were to draw a histogram of frequency of bits 0 through 127 being set or not, if the keys were indistinguishable from random I would expect an even number of bits being set across the board.  Picture if you will, balls falling through a matrix and landing in 1 of 128 slots.

My questions are, is that the case?  Is it possible to see a skew (i.e. do the resulting keys bunch in one area of the spectrum of bits, maybe a curve of sorts?

My rationale behind asking is that is the resulting keys were to bunch to a particular resulting key type, it would narrow the key space to attack the AES-128 encryption.

Therefore, is it true to say that the AES-128 is only as good as the password derivation function having been used to form the key to begin with?  If the resulting keys are poor, the key space would narrow?

It will be uniformly random for such a simple statistical test. The problem is that you are treating the probability of bits having a particular state as independent of each other. You would need to look at the conditional probability distributions of certain bits being set given other bits.

The entire joint distribution of output and input bits for a function that maps $\{0,1\}^a \to \{0,1\}^b$ requires on the order of $2^{a+b}$ memory to store. Clearly it becomes prohibitive to store and sample it for even a small function that maps 32-bits onto another 32-bits through a fixed transformation (i.e., without including any key bits that define a particular permutation).

The full conditional distribution of a function completely determines it's output. It can be seen as a transition probability matrix in a Markov model. Because of this, the distribution will encode any bias of the function, such as a preference to produce certain bit patterns (with probability).


Argument of Knowledge - Definition I've recently understood the difference between Interactive Proofs and Arguments, but even if several standard variations of IP are well known and thoroughly described in textbooks (Goldreich for instance) Arguments are not so well documented.
In particular I'm having a hard time to find a well established definition for the notion of argument of knowledge (I understand that intuitively the extractor has access to a PPT prover with auxiliary input) that could also possibly be cited
thank in advance

The notion of proofs (resp., argument) of knowledge was introduced in [GMR] (resp., [BCLL]), but the definition in both the papers is more intuitive than formal. Attempts were made at more formal definitions in [FFS] and [FS]. The culmination of these lines of work (I believe) is [BG], which is what I would recommend reading since (i) it post-dates the other works and (ii) it provides a good summary of the previous definitions (see Appendix A). [BG] focuses on proofs of knowledge, but the definitions for arguments of knowledge is similar (see §4.7).
Addendum. As @Yehuda Lindell points out, the textbook definition in [G] is worth looking into and it seems that the definition there closely follows [BG] (see the historical notes in §4.12.1).
[BCLL], Brassard, Crépeau, Laplante and Léger, Computationally Convincing Proofs of Knowledge, STACS'91
[BG] Bellare and Goldreich, On Defining Proofs of Knowledge, Crypto'92
Feige, Fiat and Shamir, Zero-knowledge proofs of identity, STOC'87
Feige and Shamir, Witness indistinguishable and witness hiding protocols, STOC'90
Goldwasser, Micali and Rackoff, The Knowledge Complexity of Interactive Proof-Systems, STOC'85
Goldreich, Foundations of Cryptography, Volume 1


Security of block cipher PRP(k⊕m)⊕k Let $\mathcal S=\{0,1\}^n$ be the set of bitstrinsg of $n$ bits (for security parameter $n$). Let $P$ be a public Pseudo-Random Permutation of $\mathcal S$, efficiently computable in both directions.
Construct a block cipher $E$ with message and key domains $\mathcal S$ as
$$\begin{align}
E:\mathcal S\times\mathcal S\to\;&\mathcal S\\
(k,m)\mapsto\;&E(k,m)\underset{\text{def}}=P(k\oplus m)\oplus k\\
\end{align}$$
What can we prove about the security (under Chosen Ciphertext Attack, or orther) of that block cipher?
Update: that's known as the single-key variant of the Even-Mansour scheme. The original scheme has two independent input and output keys. The reference article is Shimon Even and Yishay Mansour's A construction of a cipher from a single pseudorandom permutation, in Journal of Cryptology, 1997, originally in proceedings of Asiacrypt 1991.
Note: I still welcome a reference, or better a proof, for the single key variant.

Can one break (find a practical distinguisher of) $E$ for the following candidate instantiation of $P$?
Restrict to $n$ with $p=2^n+3$ prime (see A057732 for values, some multiple of $8$ and even $16$). Let $e$ be $3$ (resp. $5$) for odd (resp. even) $n$, which insures $\gcd(e,p-1)=1$. Assimilate elements of $\mathcal S$ to integers. Define
$$\begin{align}
Q:S\to\;&\mathcal S\\
m\mapsto\;&Q(m)\underset{\text{def}}=((m+2)^e\bmod p)-2
\end{align}$$
That's a permutation of $\mathcal S$, but not a good enough PRP for the application (that makes an interesting exercise. Hint: What's $Q(m)+Q(2^n-1-m)$ ?)
Let $a$ and $b$ be two $n$-bit nothing-up-my-sleeves constants, e.g. $a=\left\lfloor\pi\,2^{n-2}\right\rfloor$ and $b=\left\lfloor2^{n-1/2}\right\rfloor$. Define
$$\begin{align}
P:\mathcal S\to\;&\mathcal S\\
m\mapsto\;&P(m)\underset{\text{def}}=Q((Q(m)+a\bmod 2^n)\oplus b)\\
\end{align}$$
Vague rationale: insert the non-linear $x\mapsto (x+a\bmod 2^n)\oplus b$ between two instances of $Q$ providing the diffusion. $a\ne0$ is necessary for security, but so far I have no break for $(a,b)=(1,0)$.
Note: I only created a security system so clever that I can't imagine a way of breaking it. The most clueless amateur can, as observed by Bruce Schneier. That second part of the question if thus off-topic, and I'd understand downvotes!

What can we prove about the security (under Chosen Ciphertext Attack, or orther) of that block cipher?

This is the single-key Even-Mansour construction as was already noted in the comments of the question. The latest analysis I could find of this construction is by Orr Dunkelman, Nathan Keller, and Adi Shamir: "Minimalism in Cryptography: The Even-Mansour Scheme Revisited" where they argue that any successful attack satisfies $DT=\Omega(2^n)$ with $D$ being the number of queries to the encryption oracle and $T$ being the number of queries to the permutation itself. This means that the product of these two numbers of queries scales exponentially in the width of the permutation for any attack with constant success probability. This result was also proven in the original work by Even and Mansour for the two-key case.
As for the candidate construction for a public random permutation, one should first note that this model is very close to the random oracle model (but with a permutation instead of a function). This means that any candidate construction can only offer (indirect) heuristic security. I don't have an attack on the permutation at hand though. However this is a model that is sometimes used in cryptography, e.g. in MPC applications, where one would use AES with a fixed key for such needs.


It is on the curve. Used the sageMath code supplied here for the NIST P-256 curve ( aka secp256r1). Test it online here
# Finite field prime
p256 = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF

# Curve parameters for the curve equation: y^2 = x^3 + a256*x +b256
a256 = p256 - 3
b256 = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B

px = 0x7d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef
py = 0x8cc6dd01e747ccb8bedaae6e7fb875d036ce7e4e6231b75b93993b15202829ac

print("The x-coordinate =", px)
print("The y-coordinate =", py)
print(py^2 % p256 )
print((px^3 + a256*px + b256) % p256)

outputs:
79438795822128695252942075663504569320626776578533931102248002205388342529032
79438795822128695252942075663504569320626776578533931102248002205388342529032

Note 1: The u2f standard can be found FIDO U2F Raw Message Formats
Note 2: there is no need to take the square root. Just compare both sides in the modulus of the curve. This eliminates extra square root calculations on the field.
A little elliptic curve;
In the finite field based Elliptic Curve, we take a finite field $F$ (prime field or finite field extension) and define a curve equation by $$y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$$ This is Weierstrass equation.
If the field $F$ has characteristics different from 2 or 3 then the Weierstrass equation can be turned into the short form.
$$y^2 = x^3 + Ax +B$$
The equation is the standard short Weierstrass form. We don't want a singular curve so we check that the curve discriminant is non zero by $$2A^3-27B^2 \neq 0.$$
The points of the curve form an abelian group under the geometric interpretation with an identity element call $\mathcal{O}$, it can be the point at infinity like in secp256r1 or $(0,1)$ as the Edwards curves. The geometric interpretation of point addition turned into arithmetic over the field $F$.


Is there a way to do single key-pair asymmetric encryption? All of the information on asymmetric encryption I can find uses key-exchanging to get a mutual symmetric key.

What I am trying to do is encrypt a message with a public key and have it only readable by someone with the private key.  I don't even want the sender to be able to read it after it's been encrypted.  I don't care about the identity of the sender, only that if someone compromises the sender's computer, they can't derive a symmetric key and decrypt what was previously sent.

Is this possible?

Yes, RSA is an example of a cryptosystem where this is possible. The message is encrypted using the recipient's public key only and even the sender could not decrypt it.

However, in the comments you mention that you would like to minimize storage requirements. RSA would require e.g. 2048 bits for just the message. In comparison, with ECIES sending a one-time key with the message you are looking at a minimum of about 512 bits for a one AES block message, 256-bit curve and 128-bit MAC.

So it is not really wasteful to do it like CodesInChaos suggested.


Why does Laravel only support AES-256-CBC? Modern Laravel uses OpenSSL to provide AES-256-CBC encryption along with a MAC. However, I was under the impression that this is not a particularly secure approach.

Why does Laravel only support AES-256-CBC?

While I'm not using this feature for sensitive data, I'd still like to follow best practices.

I see two reasons:

The addition of good libraries/modes is quite recent (Libsodium is only available since 7.2+ and AES-XXX-GCM with 7.1+).
Encrypted messages in Laravel don't have a version marker that would allow more than one scheme to coexist on a given installation. It mean that a given site must stick with one encryption scheme / key or all the existing encrypted messages will become unreadable. It makes upgrading encryption in Laravel quite hard.

...and since the current scheme (AES-256-CBC + HMAC-256) is fairly competent, Taylor is sticking with it.


Can RSA be securely used for "blind decryption"? Assume we have the following setup:

A client with trusted storage and computing capabilities (e.g. a smartcard)
A server with trusted computing and short-term storage capabilities (e.g. RAM + CPU, possibly with something like Intel SGX). The server has no trusted large-scale long-term storage capabilities and may only store small amounts of data confidential and integrity protected (like the HTTPS private key).

The problem is: The server should be able to be shut-down and started-up, no passwords should be involved and the server has no HSM, yet the server should be able to provide somewhat secure access to some data without the clients needing to decrypt it themselves (for complexity reasons). So the storage need to be encrypted and the transfer (-> TLS) as well.

The solution is now (what I call it): blinded decryption.

The server uses some homomorphic encryption scheme (e.g. EC-ElGamal or RSA) with the message space $\mathcal M$. He chooses a random $k\in \mathcal M$ and uses $H(k)$ ($H:\mathcal M \rightarrow \{0,1\}^{256}$) as the key for the authenticated encryption of the data. The server now either stores the (asymmetric) encryption of $k$, called $\mathcal E(k)$ in his trusted area of the drive(s) or may store it in an untrusted section (with back-ups) if server authentication is required and the private key for this authentication is already stored in the trusted area.

For the temporary unlock of the encrypted data, the server loads $\mathcal E(k)$. Then he blinds it using some operation $f(\cdot,\cdot)$ (multiplication for ElGamal and RSA, addition for EC-ElGamal) using some random $r\in \mathcal M$ as $c=f(\mathcal E(k),\mathcal E(r))=\mathcal E(g(k,r))$ with $g(\cdot,\cdot)$ being the "inner homomorphism" (same as $f$ in many cases). The $r$ is kept available in trusted short-term memory and the $c$ is sent to the client.

The client decrypts $c$ using his trusted device and returns $c'=g(k,r)$ to the server. Finally the server unblinds $c'$ using his $r$ and uses the obtained $k$ to derive $H(k)$ and allow access to the data.

Now (finally) the question:
Given the above and standard assumptions (RSA-assumption, DDH-assumption in ECC and $\mathbb Z_p^*$,$H$ is a random oracle, the symmetric encryption is secure and authenticated,...) is it safe to instantiate $\mathcal E$ with textbook RSA?

As pointed out in the comments, every good question about "is this secure?" requires a threat model, so here's mine:
The security of the whole protocol is broken if an attacker is able to learn the secret symmetric key $H(k)$ while it's valid. The attacker may not compromise the server (i.e. he can't control/spy on RAM / CPU and may not learn the stored $\mathcal E(k)$). An attacker not breaking into the server may have successfully attacked the client (except for the trusted device) and he may be able to completely modify and read the network traffic. I think an attacker without having broken into the server may be computationally unbounded.

If not clear until now, the instantiation of $\mathcal E(k)$ is $\mathcal E(k):=k^e \bmod N$ with $e,N$ being standard RSA parameters.

Let's try to simplify and abstract your protocol a bit.  Instead of your server and client, we just have two parties, let's call them Sally and Charlie.

Charlie has a key pair $K = (K_i, K_u)$ for a suitable asymmetric cryptosystem $\mathcal E$.  We assume that this cryptosystem is partially homomorphic, such that $\mathcal E_K(a) \otimes \mathcal E_K(b) = \mathcal E_K(a \odot b)$, where $\otimes$ and $\odot$ are two group operations.
Sally knows the public half $K_u$ of Charlie's key pair, so that she can compute $\mathcal E_K(a)$ given a plaintext $a$, but not the private half $K_i$ that would let her compute $a$ from $\mathcal E_K(a)$.
Sally has a message $\mathcal E_K(m)$ encrypted with Charlie's key pair, and wants to decrypt it without revealing the decrypted message $m$ to Charlie (or to anyone who might impersonate him).
Charlie wants to help Sally decrypt her message, but does not wish to reveal his private key $K_i$, or anything equivalent to it, to Sally (or to anyone who might impersonate her).

The protocol you've suggested amounts to Sally picking a random element $r$ uniformly from the group of all possible plaintexts, encrypting it using $K_u$ to get $\mathcal E_K(r)$, and sending $\mathcal E_K(m) \otimes \mathcal E_K(r) = \mathcal E_K(m \odot r)$ to Charlie.  Charlie then decrypts the message, and sends $m \odot r$ back to Sally, who applies the group inverse $r^{-1}$ of $r$ to obtain $m = (m \odot r) \odot r^{-1}$:

  $S:\ $choose $r$ uniformly at random, compute $E_K(r)$ and $r^{-1}$;
  $S \to C:\ \mathcal E_K(m) \otimes \mathcal E_K(r) = \mathcal E_K(m \odot r)$;
  $C:\ $decrypt $\mathcal E_K(m \odot r)$ to get $m \odot r$;
  $C \to S:\ m \odot r$;
  $S:\ $compute $m = (m \odot r) \odot r^{-1}$.

The first security claim (that Charlie cannot learn $m$) should be easy to prove, regardless of the specific cryptosystem used.  Since the plaintexts form a group, and $r$ is chosen uniformly at random from that group, $m \cdot r$ is also uniformly distributed, and so reveals no information about $m$ to anyone who doesn't know $r$.  Indeed, even if Sally repeats the protocol with several different random values $r_i$, and so reveals $m \odot r_i$ to Charlie, this will give him no additional information as long as all the $r_i$ are uniformly chosen and independent of $m$.

The tricky part is the second claim, and especially the part about Charlie not revealing "anything equivalent to $K_i$" to Sally.  After all, in the protocol as described, Charlie is acting as an unrestricted decryption oracle!

It seems to me that, for this protocol to make sense at all, we need at least the following assumptions:

Sally cannot be compromised in any manner that would directly reveal $m$ to the attacker; she can only be made to disclose $\mathcal E_K(m)$.
Access to Charlie is strictly limited, so that even if an attacker obtains $\mathcal E_K(m)$, they cannot simply query Charlie for $m$.

The latter assumption may indeed make sense in your scenario, where Charlie is physically connected to Sally (and only intermittently so connected, being securely stored at other times), if we also assume that Sally is resistant to active compromise (i.e. she may certain data items, but an attacker cannot modify her behavior).  That's a pretty huge assumption in practice, but if you're willing to make it, the protocol described above seems like it should work.

(That said, if you're really willing to make all those assumptions, why not simply have Charlie store $m$ and provide it directly to Sally upon request?  I'm having some trouble coming up with a reasonable attack scenario where that wouldn't be secure, yet the protocol above would be.)


WinZip AES-256 vs PGP If I use the AES-256 option in WinZip to encrypt a file, is it any less safe or less secure than using PGP encryption?

WinZip allows enumeration of the file names contained within.  Try WinRAR or 7zip instead. WinZip AES-256 also uses CTR mode.

Both PGP and AES-256 in CTR mode are both currently considered "strong."

Can you provide more details about what exactly you're looking to do, or in what context you are evaluating safety and security?


Is a PRG more costly than AES or any other encryption standard? I know that there are many encryption standards that take a key and sometimes an IV to produce a cipher-text (the most prominent one is AES). These standards usually involve many rounds of addition and multiplication. However, using an OTP is much easier than this. You XOR the plaintext with your pad, this is the only requirement computation-wise. However, the OTP comes with the problem of a key-stream as long as the plaintext. This key-stream is supposed to be random. My question is, is this randomness more costly than the encryption standards that are in use? Why don't we use an OTP in every case? What is the downside?
Let's say I cannot afford to use encryption algorithms, but I have a stream of data that is nearly-random. If I use this as an OTP (I know this is not perfectly random), what do I sacrifice in return? What can be done to obtain the best pseudo-random characteristics from this arbitrary stream of data, to make it as qualified as it can get to be an OTP?

A one-time pad requires a true random sequence that is as long as the material you want to encrypt. If you have a pseudo-random sequence, then you don't have a one-time pad: you have a stream cipher. If you have a stream of data that is only “nearly random”, then you don't have a one-time pad, you have a broken stream cipher.

Concretely, if the nearly-random sequence isn't uniform, it means that there are biases: certain arrangements of bits are more likely than certain others. Whenever these arrangements are aligned with a pattern in the plaintext — for example English text contains more E than J, text in most languages contains more spaces than any other character, HTML tends to have a > shortly after each <, … — the pattern in the plaintext becomes apparent in the ciphertext. So certain patterns appear in the ciphertext more often than chance, they will reveal patterns in the plaintext.

To generate a cryptographically secure random sequence from a source of randomness that isn't perfectly uniform, you need to pass this random source through a cryptographically secure pseudorandom generator. One of the cheapest techniques to build a pseudorandom generator is to use an encryption algorithm such as AES in a construction known as CTR_DRBG. If all you want to do is to encrypt one message, then it's simpler and cheaper to encrypt the message with AES-CTR than do use AES-CTR_DRBG to build a key stream and to use that key stream to encrypt a message.

In addition, a one-time pad doesn't help with the authenticity of the message. If the message is modified in transit, there's no way to detect it. Encryption algorithms can be combined with authentication algorithm, and the cost of doing the two together is less than the cost of doing the two completely independently. The computational cost is only slightly less, but the cost in code size or in gate count is significantly less. For example, once you have the AES block cipher, it only takes a little additional work to build an authenticated encryption mode such as GCM or CCM.


how long does the cycle length have to be in stream ciphers? could someone tell me how long the cycle length must be in stream ciphers, so a security exists. how to compare the cycle length to the state space?

I investigate the algorithm spritz and I have the attainability of the states under investigation with key lengths of 1 - 10 and n = 6. now I have the values but I still do not know how to interpret them. the maximum cycle length for N = 6 is 660.390 and the smallest 12. But how should I evaluate this with regard to the safety? I hope I have described it somewhat better.

There's a bioinfomatics paper that might be of interest.  Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications suggests some values to the maximum run length of a PRNG.  Not strictly crypto, but I've not seen anything else.

In summary, it says that Knuth recommends a max. output of states /1000. However there is also a much more conservative limit of (states)^(1/3).

I'm not sure of how you exactly determined your baby Spritz cycles, but for comparison consider the grown up version with the full 256 byte permutation and assume that all states are achieved.  (This may not be possible due to the creation of weak states.) The conservative estimate would suggest that you could output ~10^167 bits of key material.

For N = 6, I estimate that you couldn't get a single safe bit from it if you follow the guidance above.


How to compute two EC point multiplication? I would like to know how to compute multiplication of two valid EC points over a curve E with generator G.

i.e. Given only P and Q points then how to compute R = P * Q

where $P = p G$, $Q = q G$ and $R = (p \cdot q)G$.

There is no standard "multiply two group elements" operation in an additive group. So you first need to define what you mean by $P*Q$. From the comments I gather that you want $P*Q = q P = p Q = (p \cdot q) G$.

The computational Diffie-Hellman (CDH) problem is:

  Given $P=pG$ and $Q=qG$ compute $(p\cdot q)G$.

which is clearly equivalent to your problem.

If the discrete logarithm (DL) problem is easy for the group, you can first solve $P=pG$ for $p$ and then compute $P*Q=pQ$. But on the curves we use in cryptography both DL and CDH are believed to be hard. While such groups may exist, I'm not aware of any groups in which DL is hard but CDH is easy.

Another problem of interest is the decisional Diffie-Hellman problem:

  Given three group elements $P=pG$ and $Q=qG$ and $R$ decide if $R = (p \cdot q) G$.

There are some curves for which the decisional Diffie-Hellman problem is easy while the computation Diffie-Hellman problem and the discrete logarithm problem are hard. These groups are know as gap-groups and are useful in cryptography, for example they're used in the BLS signature scheme.


Issues with Elliptic Curve Point Addition I'm trying to implement elliptic curve point addition in hardware. I've managed to create a working module using Affine coordinates however I've been reading about how points can be added by using Jacobian coordinates more efficently due to needing less modular inversions. I then found this repeated point doubling algorithm which I've attempted to implement in C.

I take the Jacobian coordinates returned from this algorithm and convert them into Affine coordinates using the modular inversions $x = X/Z^2$ and $y = Y/Z^3$. I get the correct point on the curve when calculating $2P$ with $m = 1$ however if I set $m > 1$ to calculate $4P$, $8P$ etc. I get the wrong points.

I'm wondering if I'm doing something obviously wrong? I've included my c code below. I'm fairly new to all this so I'm sorry if there is some obvious errors.

int extendedEuclid(int *c, int phi, int e) {

    int a[2] = {1,0};
    int b[2] = {0,1};
    int q;

    while(1) {
        q = phi / e;
        phi = phi % e;
        a[0] = a[0] - q*a[1];
        b[0] = b[0] - q*b[1];
        if(phi == 0) {
            c[0] = e;
            c[1] = a[1];
            c[2] = b[1];
            return;
        };
        q = e / phi;
        e = e % phi;
        a[1] = a[1] - q*a[0];
        b[1] = b[1] - q*b[0];
        if(e == 0) {
            c[0] = phi;
            c[1] = a[0];
            c[2] = b[0];
            return;
        };
    };
}

int jacobianDouble(int* x, int* y, int* z)
{

    int a, b, w, m = 1;

    *y = 2*(*y);
    w = pow(*z, 4);

    while(m > 0)
    {
        a = 3*(pow(*x, 2) - w);
        b = *x*pow(*y, 2);
        *x = pow(a, 2) - 2*b;
        *z = *z*(*y);
        m = m - 1;
        if(m > 0)
        {
            w = w*pow(*y, 4);
        }
        *y = 2*a*(b - *x) - pow(*y, 4);
    }
    *y = *y/2;
}

int main() {

    int x = 5, y = 4, z = 1, p = 97;
    int ans[2];

    jacobianDouble(&x, &y, &z);

    extendedEuclid(ans, pow(z, 2), p);
    x = fmod(x*ans[1], p);
    if(x < 0)
    {
        x = p + x;
    }

    extendedEuclid(ans, pow(z, 3), p);
    y = fmod(y*ans[1], p);
    if(y < 0)
    {
        y = p + y;
    }

    printf("x = %d\n", x);
    printf("y = %d\n", y);

    return 0;
}

All arithmetic operations in jacobianDouble should be in the finite field $\mathbb{F}_p$, i.e. all results should mod $p$, not plain integer arithmetics. Note division Y/2 is defined as $Y\cdot 2^{-1}$ where $2^{-1}$ is the multiplicative inverse of 2 modulo $p$.


Solving discrete logs modulo $2^n$ is easy.

You rely on this:

If we have (for odd $e$) $$(n 2^{k+1} + 2^k + 1)^e = b \pmod{2^\lambda}$$

then either:

$$(n 2^{k+1} + 2^k + 1)^e = b \pmod{2^{\lambda+1}}$$

or

$$(n 2^{k+1} + 2^k + 1)^{e + 2^{\lambda-k}} = b \pmod{2^{\lambda+1}}$$

That can be shown because $(n 2^{k+1} + 2^k + 1)^{2^{\lambda-k}} \equiv 1 + 2^\lambda \pmod {2^{\lambda+1}}$ (binomial theorem), and so $(n 2^{k+1} + 2^k + 1)^{e + 2^{\lambda-k}} \equiv (n 2^{k+1} + 2^k + 1)^e \cdot (1 + 2^\lambda) \equiv $ $(n 2^{k+1} + 2^k + 1)^e + 2^\lambda \pmod{ 2^{\lambda+1} }$

So, you can find your exponent by starting at the bottom, $9^1 = 9 \bmod 16$, and then extending it for increasing values of $\lambda$, until you hit $\lambda = 2048$


Public signature of challenges as authentication Assuming you trust a client's public signature keys, a simple authentication protocol would be to send a long random string challenge, and get the client to sign it
Since most of authentication still relies on more sophisticated protocols like sending some form of secret over the tubes and verifying it in the server, there must be some weaknesses in the above protocol that I am ignoring.
What issues is there with this approach? If you rely on HTTPS to send the challenge, most MitM attack surface is removed, am I correct?

What issues is there with this approach?

There are both theoretical and practical concerns with this kind of solution.
First, it is generally not seen as a good idea these days to just sign whatever the somebody else handed you, especially if you also use the signing key in other contexts. This is to prevent an attacker from sending you a "challenge" like "you, lurscher, authorize a wire transfer to me, SEJPM, with a value of 10k USD" and then me presenting this to your bank. There are ways to fix this problem though.
The more practical concerns though are usually more important in this context. Namely: Most servers simply don't have have a public key they are sure is associated with a given user. And if they do, how long do you think it will take until users start complaining or loosing their private keys? Using good old static authenticators (like passwords) is simpler. Additionally, from a server's perspective there is typically very little extra security gained from such an involved authentication strategy. You already assuming a secure channel after all and I can't think of a scenario right now where standard password transmission over HTTPS with server-side (basic) hashing would be significantly more secure than a public-key based solution (in a web context).
Outside of web contexts, yes, authenticating both parties with a public key is a viable strategy which is why TLS has built-in support to do so.


How can I break this block-cipher? So we've got to do this assignment for our study, but we can't figure out what to do, can someone help?

Assume that Alice and Bob want to communicate via encrypted email. To this end, they first meet in person
and agree on a common secret key k and block cipher $(P,C,K,E,D)$ with plaintext space $P$, ciphertext space $C$, key space $K$ , encryption function $E$, and decryption function $D$. Afterwards, all email communication will be encrypted by using this chosen key and block cipher. Furthermore, assume that Alice and
Bob choose a specific block cipher in ECB-mode with $P = C = K = \{0,1\}^{128}$ and with the property that
$$E_k(m\oplus m_0) = E_k(m)\oplus E_k(m_0)$$
for the key $k$ and all messages $m,m_0 \in P$.

Now, assume that one day, Alice is using her computer in her office at work and forgets to lock her computer while she is just quickly out of office to get her lunch. In the meantime, you as the hacker go into her office (which is also left unlocked) and get access to her computer. Although you cannot get access to the secret key $k$ (which is securely stored), you can use her email client to decrypt any ciphertext of your choice.

Since you do not have much time as Alice is already coming back to her office, you are able to decrypt
exactly 128 ciphertexts.

Which are the 128 ciphertexts that you would choose to decrypt so that later on you are able to decrypt all email communication encrypted under the key $k$ (although you’ve never seen that key)?
Describe how you successfully decrypt any encrypted e-mail by using your 128 decrypted ciphertexts
selected in (1). Concretely, this means that you need to explain, how you compute the plaintext $m$ of
an arbitrary ciphertext $c = E_k(m)$ that was encrypted under the above block cipher $(P,C,K ,E,D)$.

Hint. Since Alice and Bob use ECB-mode, we can assume, without loss of generality, that all e-mails have a length of 128 bits.

Since you only ask for help on your class assignment, I will not give you the whole answer, but will hopefully point you in the right direction.

You are able to decrypt any ciphertext you want, but only have time to decrypt 128. Let's think about this from another perspective. What if you already knew exactly what ciphertext you wanted to decrypt. Say the ciphertext is 126 zeros, followed by two ones (I'll denote this mathematically as $0^{126}11$). You could just ask for the decryption of that, easy enough.

How could you get the decryption of it, given the decryptions of $0^{127}1$ and $0^{126}10$?


Security level in HORS signature scheme I was reading the HORS One-Time-Signature scheme by Reyzin & Rezyin, but I could not understand how they derived their security equation $(rk⁄t)^k$. I understand that the total number of balls is $t$, and each time a signer signs his message, he reveals $k$ different balls. The attacker at this point and after one signatures, he knows $k$ elements (balls). After $r$ signatures, the attacker at most knows $rk$ out of $t$ elements. Then, why it was raised to power of $k$? and why is the security log of this equation?

Here's how it works:

After $r$ signatures, he learns, at most, $rk$ balls (actually, that's a maximum; however that is a conservative estimate).
Hence, the probability that a random ball has been revealed is $rk/t$
Now, he tries to generate a forgery; he picks a message that hasn't been signed, and translates that into $k$ balls.  He can generate a forgery if all these balls have been revealed; the probability that a specific ball is $rk/t$; these balls were selected independently, and so that probability that all of them has been revealed is $(rk/t)^k$

So, if the attacker tries to select random messages until he finds one that works, that'd take an expected $((rk/t)^k)^{-1} = 2^{-\log_2 (rk/t)^k}$ tries.  We express security levels in terms of powers of 2, and so the "security" of this system would be $-\log_2 (rk/t)^k$


How to calculate elliptic curve parameters? I'm having a rough time understanding the math behind elliptic curves.
I want to implement ECDH where user can define a, b, and p parameters of elliptic curve.

How can I calculate generator base point G? Is it any point that satisfies elliptic curve equation $ y^2 \equiv x^3 + ax + b \pmod p$?

Also, how can I calculate order n and cofactor h given the base point?

It is possible to find the desired values in an acceptable amount of time.

TL;DR: Find the curve order, factor it, select a (random) point until you have one with the desired order and calculate the cofactor as quotient of curve and point order.

First, you can use yyyyyyy's answer to find the order $n$ of the described curve using Schoof's algorithm. Please note that this order should be prime or a small multiple (4x-8x) of the a prime for enhanced security but it doesn't have to have those properties for the schemes to work.

In the next step, you need to actually factor that order. This is feasible as this order usually will be around 500 bits of length (or a lot less if you're not going for the 256-bit security level), which can be done and was done for FREAK. Of course, if the curve order is prime or a small multiple of a prime (4x-8x) the factorization may not need to be obtained with the GNFS but may be either given (prime case) or findable by trial division (small multiple case).

Finally you just select a curve point and determine its order until you hit one with the desired order $t$ which will also yield the cofactor as $h=n/t$. Usually you'll want to have $h\leq 8$ and usually you'll also start with the points having small x-Coordinates and try all incrementally until you reach one fullfilling your conditions.

The algorithm for this can be found in a variety of places in the literature and I'll quickly restate the one from the Handbook of Applied Cryptography, assuming we're testing the point A and that $n=p_1^{e_1}\cdot p_2^{e_2} \cdot\cdot\cdot p_k^{e_k}$:

Set $t\gets n$
For $i$ from $1$ to $k$ do the following:

Set $t\gets t/p_i^{e_i}$
Compute $A_1\gets t\cdot A$
While $A_1\neq \mathcal O$ do the following: compute $A_1\gets p_i*A_1$ and set $t\gets t\cdot p_i$

Output $t$ as the order of $A$

Please note: I strongly recommend against using custom curves where the parameters are chosen by the user. These may be vulnerable to attacks documented in the safe curves project. Standardized curves (like Curve448 or Curve25519) should be preferred for easier implementation and better analyzed security properties.


Order of cascaded ciphers Does the order of a block cipher cascade (e.g. in TrueCrypt) make a difference to the security provided, assuming independant keys?

For example:

Plaintext -> Rijndael -> Serpent -> 3DES -> Ciphertext
Plaintext -> 3DES -> Serpent -> Rijndael -> Ciphertext

The same ciphers, just ordered differently.

My intuition says no, and that the security will be at least that of the strongest cipher, but I can think of a few situations (e.g. timing attacks) where this might make a difference. I can't think of a concrete case where you could exploit this ordering, though.

Yes, order of ciphers would matter in some practical scenarios, in particular if an adversary can subject the implementation to a DPA attack.

Consider the scenario where the same plaintext is encrypted several times using the same key, using some chaining mode other than ECB, a random IV, and the cipher in contact with the plaintext (on either the encrypting or decrypting side) is vulnerable to DPA. The known random IV allows recovering that cipher's key using standard DPA, and then a slight variant of DPA allows recovering the plaintext in all the subsequent blocks. It does not matter how the various ciphers are keyed, the plaintext can be short, but the key (of the attacked cipher) must be reused in many sessions.

Contrast that with the case where the cipher in contact with the plaintext is DPA-protected. Perhaps the others (in particular, the one in contact with the ciphertext, which is most exposed) can be broken, but (since the keys are independent), protection of the confidentiality of the plaintext remains at least as good a that of the cipher in contact with the plaintext.

Conclusion: if you must cascade block ciphers using truly independent keys for some reason (I can imagine an order from high-up, e.g. regulatory), and DPA is an issue, you want to put the one you are most confident with in contact with the plaintext. However if the ciphers share their key, that's the other way around: you likely want to put the most trusted one at the most exposed place, which is in contact with the ciphertext.

Update following Hunter's question: A situation where ciphers share their key would be a cascade of 3DES-CBC with 192-bit key (168 used), followed by AES-192, using the same 192-bit key for the two ciphers (a very poor choice when DPA attacks matter). Truly independent keys are chosen independently and randomly. Derivation from a single master key using a strong KDF is also fine if performed out of the reach of an attacker, assuming in particular no side-channel attack such as DPA can be mounted on the KDF.

Note: if the first encryption scheme in a cascade leaks information about the plaintext through the length of the ciphertext (e.g. has a built-in compression scheme), then the cascade might not be secure (as pointed in this comment to a related question). That does not apply in the context of the question, though.


How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$? Given a cryptographic hash function $h$, for example SHA256, how hard is it to find plaintexts $a,b,c$ such that
$$h(a)\oplus h(b)=h(c) \text?$$

This partial answer establishes (rather trivial) lower and upper bounds for the asymptotic hardness of the problem, assuming $h$ behaves like an $n$-bit wide random function.
If one hashes $m$ messages $M$, then computes $f(i,j,k)=h(M_i)\oplus h(M_j)\oplus h(M_k)$ for $(i,j,k)\in\mathbb {Z_m}^3$, that's $m^3$ results, with most values duplicated at least 6 times for large $m$. Odds that zero is never reached by any $f(i,j,k)$ are about $(1-2^{-n})^{m^3/6}$ for large $m$, for any choice of the $M$ by an adversary who can't distinguish $h$ from a random function.
Therefore, if $m\approx2^{n/3}$ hashes have been computed, that can not lead to a solution of the problem with odds better than 16% for large parameters.
The expected hardness of the problem in the question is thus at least $\mathcal O(2^{n/3})$ times the work for a hash. Also, an infinitely powerful adversary could succeed with $\mathcal O(2^{n/3})$ queries to an oracle implementing the hash.

The above leads to an explicit algorithm with non-vanishing odds of success that performs $(2^{n/3})^3=2^n$ evaluations of $f$, thus has cost $\mathcal O(2^n)$ $n$-bit operations; it requires $\mathcal O(2^{n/3})$ $n$-bit words of memory. We can do much better.
One option is to fix $a$, then find collisions for the function
$$g(x)=\begin{cases}h(x) & \text{if }x\text{ is even}\\h(x)\oplus h(a) & \text{if }x\text{ is odd}\end{cases}$$
This search can be can be made with cost $\mathcal O(2^{n/2})$ hashes and modest memory, using Floyd's cycle-finding, or Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).
Notice that if $g(b)=g(c)$ with $b\ne c$, then $(a,b,c)$ is a solution of the problem of the question if $b$ and $c$ have different parity, which (for random $h$) has odds about $1/2$ for each collision exhibited.
The expected hardness of the problem in the question is thus at most $\mathcal O(2^{n/2})$ times the work for a hash.


Basic question on interaction with HSM using PKCS11 I am a beginner on cryptography, I've been reading about PKCS11 and usage of PKCS11 on HSM's

I understand the concept of HSM,

I read about the HD wallets in bitcoin how keys are hashed and combined and hashed again to form a tree, branch, sub branch private + public key list

my question if I use an HSM that has the PKCS11 interface can I do all these key creation, hashing, combining adding on the hsm without exposing private keys to the host machine ?

No, the operations on the key itself are not standardized and not supported by the PKCS#11 standard. There are some key derivation mechanisms, but even the NIST specified ones have hardly any support (which is kind of ironic, as key management is of course one of the main reasons to buy an HSM in the first place).

These operations are pretty specific to BitCoin and are therefore not standardized. It is of course possible to extend the base functionality of PKCS#11 with custom mechanisms. But in general HSM's will not be created with BitCoin wallets in mind.

Probably easier to create a BitCoin specific hardware module interface with your own software support. Some HSM's do allow custom code to be loaded, so you do likely not have to create your own hardware for that. Smart cards can be programmed as well. Prepare for a steep learning curve though.


What does that mean, that A5/1 is clocked? What does that mean, that A5/1 is clocked? What happens if the clocking bit agrees with the majority bit?

The clock term comes from electronic engineering; in each clock, the cells of LFSRs ( flip-flops) are clocked and the data moves. In the shift registers, the data moves from one to another in one direction. As we can see from the below, each flip-flop has a clock input where each has the same clock.

In the LFSRs ( Linear Feedback Shift Register) there is also the feedback that is calculated from the selected tap point is fed the beginning.
Normally LFSR's are clocked for each clock so that new feedback is calculated and the LFSR is shifted so that new output is formed. If you don't clock, then no new feedback is calculated and no shifting occurs, too. The old output is still active. To achieve this in electronics the clock is also controlled by logic. In programing that is way easier (see bottom).
Consider the first LFSR ( index names are free to choose and it is reflected)

When clocked it will become;

See that the data of the cells are shifted to the right and the new value to the left is feedback values calculated from the active taps.
A5/1, which is terribly broken, has three LFSR where each of them has clocking bits, (8,10,10) shown orange on Wikipedia's image. At each clock, the majority is formed from those values.
The majority of the $n$ binary variable means the most occurring value. For three bits, just count the number of ones $c$ if $c > 1$ then the majority is *one ( i.e. number of ones > number of zeros) and the majority bit is $1$, otherwise the majority bit is $0$.

If the majority bit matches the LFSR's clocking bit, then the LFSR is clocked otherwise not clocked.
A simple code can be described for each LFSR as
majority = (L1[8] AND L2[10]) xor (L1[8] AND L3[10]) XOR (L2[10] AND L3[10])

def clockLFSR1(majority):
    if L[8] == majority:
        self.applyClock()

def clockLFSR2(majority):
    if L[10] == majority:
        self.applyClock()

def clockLFSR3(majority):
    if L[10] == majority:
        self.applyClock()


Qubit / Qutrit - Is there a theoretical limit on how many orthogonal states a quantum bit has? Seems like a quantum bit with $3$ orthogonal quantum states is called a qutrit - and they have been demonstrated practically.
In comparison with $n$ qubits that have ~$2^{n}$ states, these have ~$3^{n}$ states.

Is there a theoretical upper-limit on how many orthogonal quantum states a quantum bit has?
How would we call that unit of quantum information?

There is, in principle, no limit to the dimension of the state space of a quantum system. This includes infinite dimension (usually countable, i.e. a separable Hilbert space) and any large but finite dimension. In the context of quantum information, systems with a state space of dimension $d\geq 2$ are usually called qudits.

It's also important to mention that physical implementations of larger dimensions are harder to bolt down, and particularly it's harder to have a system of dimension $d>2$ that doesn't talk to more states of the system. This is because qubits are realized by restricting some larger system (usually infinite-dimensional) to only two states, by suitable physical considerations, and it is generally quite challenging to really cut out all the other states. Trying to restrict to three or more states while keeping the restriction clean is, generally speaking, harder.

In principle, though, there's nothing stopping you from having any large dimension you want on your system, but then you don't call it a 'bit' anymore.


Discrete Logarithm Problem or just integer exponentiation problem? In reading the following paper,

https://ai2-s2-pdfs.s3.amazonaws.com/35eb/afbaab34223bca50a7be2f5915fddf918fc7.pdf

Generate two primes $p$ and $q$ such that $q|p-1$. Pick a generator $g$ of $Z_p^{*}$. $g$ is declared as public.

$c_1=g^r$ where $r \in Z_q^{*}$

As far as I understand, $g$ is integer ranging from 0 to p.
If there is another meaning for $Z_p^{*}$, please let me know.

Given $g,c_1$, find $r$.

Is it discrete logarithm problem? or just integer exponentiation problem?

As you can see in their abstract, they are assuming that "the
standard Computational Diffie-Hellman problem is intractable", thus this means that you may necessarily break their scheme by solving the Discrete Logarithm problem, since the Computational Diffie-Hellman (CDH) problem can be solved easily if the DLP can be solved.

The CDH problem is the following:
for $G$ a cyclic group of order $q$, with $g$ one of its generator, given $(g,g^a,g^b)$ with $a,b \in \{0, \ldots, q-1\}$ randomly chosen, one want to compute the value $g^{ab}$.

If computing discrete logs in $G$ were easy, then the CDH problem would be solved, since one would be able to compute:

$b$ by taking the discrete log of $g^b$;
$g^{ab}$ by exponentiation: $g^{ab} = (g^a)^b$

However, it is important to note that the CDH and DLP problem are not necessarily equivalent! Hence, it may be possible once to solve the CDH problem without being able to solve the DLP or it may also be possible that both will be proven equivalent some day, as Maurer already proved it to be true under certain conditions regarding the smoothness of integers in given intervals.

So, if you want to consider their scheme as being an instance of the DLP, you may, however it may be simpler than the DLP.

On the other hand, the problem you are stating, being given $c_1, g$, find $r$ for $c_1=g^r \mod p$ is an instance of the DLP.

So yes, you can reverse their public keys directly if the DLP is easy.


Establish a secure connection between a Bluetooth Low Energy device and an Android App using ECDH Im very new to security and trying to learn how to establish a secure connection between a android application and a Bluetooth Low Energy device with limited hardware performance.

The procedure:

App:

Generate private/public keys with ECDH Key Pair Generator and elliptic curve spec "sect163k1" using java.security.* (https://gist.github.com/ymnk/fec39e033394ee2ec47c)
Send public key to BLE Device
Generate secret master key from apps private key and the public key from the BLE Device using ECDH (https://docs.oracle.com/javase/7/docs/api/javax/crypto/KeyAgreement.html#generateSecret())
Store secret master key in database. (never shared)
Encrypt data with secret key using AES/CBC with integrity (using https://github.com/tozny/java-aes-crypto)
Send data to BLE Device to be decrypted with the device secret master key

BLE Device:

Generate private/public keys with ECDH Key Pair Generator and elliptic curve spec "sect163k1" (or another curve)
Send public key to App
Generate secret master key from apps public key and BLE Device private key using ECDH
Store secret master key in device (never shared)
Encrypt data with something like EAS/CBC with integrity
Send data over to app to be decrypted with apps secret master key

Would this keep the communication between both parts safe? Second time the connection is established the same shared secret could be used to encrypt the data, in order to improve performance. Its a 1:1 relationship between the device and the logged in account in the app so I could also use the shared secret to verify the right user is connecting to the BLE device.

With this protocol, I see three issues right now.

In step 2 both devices just send their public keys. Now an attacker could go ahead, intercept the keys from either part, pretend to be the other one and relay all the trafic over himself. This is a classic man-in-the-middle attack against Diffie-Hellman.
You use "AES-CBC with integrity". This does look very bad for a mode of operation. It seems to be (from a quick glance) $E_K(m)=E_K^{CBC}(m\parallel H(m))$ at best which is also called hash-then-encrypt, which is highly nonstandard and potentially dangerous. Upon further inspection of the source code (thanks to Isaac Potoczny-Jones in the comments) it turns out to actually be an HMAC-SHA256 applied on the ciphertext which is standard encrypt-then-authenticate.
You use sect163k1 which is a Binary Koblitz curve over a field of size $\approx 2^{160}$, thus a brute-force attack would take $\approx 2^{80}$ operations which is considered dangerously weak these days. If you have to (perfomance-wise) you can do it, but it's certainly not the robust 128-bit security level you normally expect.

As for mitigations, I strongly recommend you to use a more standard secure channel protocol (like TLS). If your platform does not natively support it, it may be time to either require an upgrade or bring your own library.


What is the largest bit RSA encryption to be cracked? This article shows a 4096 bit key being cracked by using a microphone and listening to your computer's cpu. I do not know if this is true at all.

I am doing a presentation on RSA Security and I would like to include the largest RSA encryption to be cracked.

TL;DR:
This is not the same kind of attacks. You cannot compare factoring and side channel.

All unfactored parts of the numbers $2^n  − 1$ with $n$ between 1000 and 1200 were factored by a multiple-number-sieve approach in which much of the sieving step could be done simultaneously for multiple numbers, by a group including T. Kleinjung, J. Bos and A. K. Lenstra, [...] n=1199 on December 11, 2014

source

The paper of this attack is RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis by Daniel Genkin, Adi Shamir and Eran Tromer. Given the quality of the article and the names of the researcher, it is really hard to doubt the paper content. But be wary that press tend to make things worse than they actually are. e.g. a year ago, we had a paper on Freestart collision for full SHA-1, immediate press emphasis: SHA-1 is broken, we have a collision!
In the paper you can read:

Modern RSA security standards mandate key sizes of at
least $2048$ bits (i.e., $1024$ bit primes $p$;$q$) in order to achieve adequate levels of security [BBB+12]. For concreteness, in the following we consider even larger keys, of size 4096 bit (and 2048-bit primes), which
should be secure beyond the year 2031 [BBB+12]. We show an attack that can extract whole 4096-bit RSA keys within about one hour using just the acoustic emanations from the target machine.

The choice of the size of the 4096 bit number is more as a Proof of Concept that it is possible to do it with big number. You could assume that they can even do it with 8192 bit keys...
What you must show in your talk, is that even if this 4092 key has been broken, it is not the same kind of attacks. Here we are in the case of a physical attack rather than a factorization attack. It is the same as comparing side-channel attacks on AES as opposed to the usual cryptanalysis.
I suggest you have a look at the RSA challenge and Integer factorization records.
Some graph you might also be interested in:

Also related:

Why has the RSA factoring challenge been withdrawn?
How big an RSA key is considered secure today?


One time pad: why is it useless in practice? The symmetric cryptosystem one-time pad (OTP) seems to be very beautiful since it is perfectly secret according to Shannon. Many books, however, point out the main drawback: one must create a secret key the same length as the plaintext. For this reason, the concept of perfect secrecy has these days been abandoned, and we prefer other cryptosystems.

Now, for example, suppose I want to encode my text message with the ASCII scheme, and moreover suppose that this plaintext is 10 gigabytes long, therefore (using an OTP) the key must be the same length, 10 gigabytes. I think, however, this is a ''sustainable price'' because I'm sure that the ciphertext can't be attacked.

Practically, I don't understand why having such long keys with an OTP is a big disadvantage if we reach "the dream"-- namely, perfect secrecy. Nowadays the storage of information is very easy, so what is the real problem? I can, for example, share the "long key" in person.

Actually, the problem with OTP isn't the storage of the pad (although secure erasure of the parts of the pad you used is trickier than it looks), and it isn't the pad generation (although, again, that's trickier than it looks), but the secure transport.

After all, it's not enough for you (Alice) to have the secure pad, you also have to give a copy to the guy (Bob) you're sending the message to, and you need to send it in a way that's secure.

That's the real reason OTP's aren't used that often; OTP's would require meeting with the other side directly, or alternatively using a trusted courier; we rarely want to put up with the expense with either, especially since there are cheaper alternatives available.


Is Ed25519 really constant-time as widely implemented? Despite the frequent claims that Ed25519 is more secure against side-channel attacks than (for instance) signatures performed over NIST P-256, I noticed that most implementations (including the original submissions) rely on table look-ups performed with secret index to achieve high performance.

That is notoriously a big no-no, but I see that concerns are waived due to the use of conditional move constructions.

For instance, the fundamental construct is often:

void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
{
  int i;
  crypto_uint32 mask = b;
  mask = -mask;
  for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]);
}

where mask is either all 1s or all 0s.

I am not totally convinced by this construction.

For instance, when implemented in C, what are the chances that the compiler deobfuscate this into a branch?

For an assembly implementation, what is the chance that XOR by a mask depends on the number of 1s set in the mask?

Is safe to use this approach beyond Ed25519?

For instance, when implemented in C, what are the chances that the compiler deobfuscate this into a branch?

At first glance, it sounds unlikely.  For example, if you're worried about the compiler translating this as:

 if (b) {
    for(i=0;i<32;i++) r->v[i] = x->v[i];
 }

well, that would be a valid transformation only if the optimizer could deduce that b could only be 0 or 1; depending on how the caller is written, that could be difficult.

Now, there are additional steps that the quoted code could take, such as:

volatile crypto_uint32 *dest = r->v[ix];
volatile crypto_uint32 *src = x->v[ix];
for(i=0;i<32;i++) dest[i] ^= mask & (dest[i] ^ src[i]);

(the volatile attributes would specifically prohibit the optimizer from eliding the memory accesses).

However, ultimately, we can't be certain that the optimizer doesn't insert unexpected branches (or other side channel issues) into our code; for example, the  optimizer could insert logic at the beginning some code of the form:

 if (b) a_do_nothing_call();

We generally assume that the optimizer won't do that sort of thing without a good reason.

  For an assembly implementation, what is the chance that XOR by a mask depends on the number of 1s set in the mask?

The answer to that would depend on the side channels you are concerned about.  We assume that, with an assembler, the instructions you write are pretty much the instructions the CPU will execute, and we generally assume that the XOR instruction on the CPU doesn't access memory conditionally, or change the amount of time taken based on the data.  However, if we're concerned about DPA style attacks (by which I mean an attack that depends on the actions of the gates that make up the CPU), there is some leakage - not typically a large amount, but some.  The techniques we've been discussing wouldn't necessarily be sufficient, and we would need to use additional techniques (in this case, probably some sort of blinding).


Can I base a public-key cryptosystem only on a hash algorithm? Could I base a public and private key system on just using a hashing algorithm? For example:
privKey = sha256( randomGenerator() )
pubKey = sha256( privKey )

Why do I need to use different algorithms? For example, RSA or ECC?

There is actually a system for hash based signatures being standardized, see here.
Hou have described a system where the public key is derived from the private key in such a way that the private key cannot be recovered from the public key. However, it is unclear what operations you can perform with the public key that can only be reversed by persons having the private key. Without such operations the derived public key is useless.
Public keys and private keys do need to have a mathematical relation so that they can be used for encryption / decryption, key agreement or signature generation / verification. Such schemes are based on a specific mathematical problem such as the discrete logarithm problem (DLP) or the RSA problem - factorization of a number that is a product of two or more prime numbers.


Secure method of encrypting data within a database I'm designing a program which makes queries to a database stored locally which could potentially contain a lot of sensitive information. As such the information must be kept secure as possible from any possible attack. I plan on doing this by encrypting the data by AES-256 in CBC mode. The encryption / decryption key will be kept secure.

My question is, using this scheme, how should the database be encrypted to ensure the data is kept secure against attacks? Originally I planned on encrypting the database cell by cell (with each row having 10 or so columns) and storing a unique, randomly generated IV for each row.

However, to my understanding of the generated stream this could cause problems as I would be using the same key + IV combination to encrypt / decrypt all the cells of this row. This would allow an attacker to potentially compute the XOR of two cells and reveal enough information where they could decrypt the entire row (two-time pad). I know this is more of a problem in CTR mode but I have read that it could also be a problem in CBC if two of the cells began with the same sequence of bytes. Please correct me if I misunderstand the concept of this type of attack as I am still a little unsure of its exact mechanism.

Encrypting the entire database itself is not very pretty and obviously will cause performance issues if the database is large enough. Therefore, the only other method I could think of is having EACH CELL have a unique, random IV which on the surface seems like a lot of extra data to have to store but I will go this route if need be.

Just as a side note; this program isn't being implemented anywhere in which security will be an issue. It is more of a side project for myself to learn the intricacies of cryptography and ways of defending against attacks. Thank you for all your help in advance!

Using the same key and IV for different, independently encrypted cells is a bad idea, regardless of which encryption algorithm you use. It would allow attackers to find either XORs of cells (with CTR) or at least equality of prefixes (with CBC).

If you are going to use authenticated encryption, you need to choose whether the MAC applies to each cell independently (which adds data anyway) or the row as a whole.

If you choose the row as a whole, you might want to encrypt the whole row as one, too, since you'll need to read all of it anyway. But if the MAC verification is much faster than decryption, you might still want per-cell encryption with a row-wide MAC.
If you choose per-cell MACs, you are already adding significant data, so you might be able to get away with a per-cell IV too. Or you might be even more determined to avoid adding any extra data, depends on your requirements.

If you end up wanting to do per-cell encryption, but can't have per-cell IVs, CTR is probably your best bet. With CTR the IVs don't need to be random, just unique, so you can calculate the per-cell IV as an offset from the row IV/nonce. Just make sure your offset algorithm will always result in a unique input to each CTR block. E.g. if cells can be at most 256 blocks long, you could use the rightmost byte within the cell, the next one for a cell index and the rest for the row nonce.

CBC is also an option, if you can derive a per-cell IV from the row IV in an unpredictable way. E.g. using $HMAC(k, r || i)$, where $r$ is the row IV and $i$ the row index. That's slower, though. (You could also use the block cipher to derive it.)

Regardless, you should also make sure that the key and IV will differ when a cell is overwritten. With a per-row IV that means the whole row needs to be rewritten with a new IV.

All in all, it's probably simpler to either just have the whole row encrypted and authenticated as a whole or have each cell with their own IV and MAC. Those options allow you to just use an authenticated encryption mode, too.


Possible to decrypt every fragment of an ecrypted file on its own? I have a project where I want to encrypt a file and split it up into several fragments and place these files on different systems. I want to do it on mobile phones as well, so I chose poly-chacha20 as encryption. In my tests it was faster than AES based encryptions. The concern of my tutor is now, that because of the nature of stream ciphers, it would be possible to decrypt each of the several fragments on its own, as long as you have the key, which would be a no go. In my tests I could decrypt the starting fragment, but not the fragments after that, so I'm not sure what is correct now. Is it possible to decrypt every fragment with the given key? Or is it needed that you have all the fragments first before decrypting them?

Unless I'm misunderstanding something this should be fairly easy to do.
The scheme of a stream cipher is the following :

                    Key
                     |
                     v
               +------------+
               |            |
     IV -----> |  Chacha20  +-----+
               |            |     |
               +------------+     |
                                  |
                                  v
MESSAGE ------------------------> +------>  CIPHER TEXT

Thus you have :
$$K_{stream} \oplus Message = CipherText$$

If afterward you split your $CipherText$ into blocks of $n$-bits. Then you will notice that the first $n$ bits of the $K_{stream}$ are used to encrypt the first $n$ bits of the $Message$ resulting into the first $n$ bits of the $CipherText$ and so on...

Therefore, in order to decrypt a $block$ on a separated device, you need to know its position into the full $CipherText$ (how many bits are present before), generate the $K_{stream}$ from the $Key$ and $IV$, drop the first $n$ bits of this $K_{stream}$ where $n$ is the position of the $block$ in the full $CipherText$, and then you can start decrypting your $block$.

Remarks:

you don't need to know the length of the full $CipherText$ but only the number $n$ of preceding bits.
you will need this number anyway when you will want to recombine the blocks on a single device.


How should I calculate the entropy of a password? If part of the password is a whole regular English word, does the entropy of that part depend on the number of English words in existence, the number of English words known by the choosing algorithm, the number of English words assumed by the attacker?

Does the language matter, is the average entropy per word in German, French, Italian, or Spanish significantly different from the average entropy in English?

Does a numeric digit always have an entropy of $\log_2(10) = 3.321928$?

Entropy is a measure of what the password could have been so it does not really relate to the password itself, but to the selection process.

We define the entropy as the value $S$ such the best guessing attack will require, on average, $S/2$ guesses. "Average" here is an important word. We assume that the "best attacker" knows all about what passwords are more probable to be chosen than others, and will do his guessing attack by beginning with the most probable passwords. The model is the following: we suppose that the password is generated with a program on a computer; the program is purely deterministic and uses a cryptographically strong PRNG as source of alea (e.g. /dev/urandom on a Linux system, or CryptGenRandom() on Windows). The attacker has a copy of the source code of the program; what the attacker does not have is a copy of the random bits that the PRNG actually produced.

Entropy is easy to compute if the random parts of the selection process are uniform (e.g. with dice or a computer with a good PRNG -- as opposed to a human being making a "random" chance in his head). For instance, if you have a list of 2000 words and choose one among them (uniformly), then the entropy is $S = 2000$. Entropy is often expressed in bits: an entropy of $n$ bits is what you get out of a sequence of $n$ bits which have been selected uniformly and independently of each other (e.g. by flipping a coin for each bit); it is a simple logarithmic scale: "$n$ bits of entropy" means "entropy is $S = 2^n$" (and the attack cost is then $2^{n-1}$ on average).

If you think of a password as two halves chosen independently of each other, then the total entropy is the product of the entropies of each half; when expressed with bits, this becomes a sum, because that's what logarithms do: they transform multiplications into sums. So if you take two words, randomly and independently (i.e. never ruling out any combination, even if the two words turn out to be the same), out of a list of 2000, then the total entropy is $2000\cdot2000 = 4000000$. Expressed in bits, each word implies an entropy of about 11 bits (because $2^{11}$ is close to $2000$), and the total entropy is close to 22 bits (and, indeed, $2^{22}$ is close to $4000000$).

This answers your question about digits: a decimal digit has entropy 10, as long as it is chosen randomly and uniformly and independently from all other random parts of the password. Since $10 = 2^{3.321928...}$ then each digit adds about 3.32 extra bits to the entropy.

If a human being is involved in the selection process then calculating the entropy becomes much more difficult. For instance, if a human chooses two digits and the first digit is '4', then the probability that the second digit is '2' is quite higher than $\frac1{10}$. It could be argued that it is also difficult for the attacker: he will also have more work to do to sort the potential passwords so that he begins with the most probable. But this becomes a psychological problem, where the attacker tries to model the thinking process of the user, and we try to model the thinking process of the attacker: it will be hard to quantify things with any decent precision.