What is the theoretical and practical status of mental poker? I'm able to find a lot of scattered papers on the development of mental poker since RSA proposed the initial solution but no recent report (i.e. after 2005) on what is the status of the problem, eg:

What are the remaining open problems/challenges?
Can we call it solved? For example, has the "dropout" problem been solved (e.g. [1] suggests so, but has it been verified?)?
Have the performance problems been solved ?
Is there an implementation of the algorithms / protocols ?
What is the latest performance improvements (e.g. is [2] up to date to the fastest protocols known)?

[1] http://crises-deim.urv.cat/webCrises/publications/isijcr/lncs3592dropout.pdf
[2] http://www.nongnu.org/libtmcg/libTMCG.pdf

All the know problems have been solved and currently there is, at least, one practical and secure Mental Poker protocol.

Check this patent application:

METHOD AND APPARATUS FOR EFFICIENT AND SECURE CREATING, TRANSFERRING, AND REVEALING OF MESSAGES OVER A NETWORK
Application number: 13/086,208
Publication number: US 2011/0202766 A1
Filing date: Apr 13, 2011

The protocol described is called MPF (Mental Poker Framework).

Detailed answers to your points:

  What are the remaining open problems/challenges?

The main problem still unsolved is how to enforce players to act (show a card, bet, pass) before a certain time limit, in a purely peer to peer network, since a timestamping service would add a TTP to the protocol.

Also I have my own unproven conjecture: Semantic security is incompatible with abrupt drop out tolerance (without a threshold scheme). Both cannot be present at the same time in a MP protocol.

  Can we call it solved? For example, has the "dropout" problem been solved (e.g. 1 suggests so, but has it been verified?)?

Since a deck that is encrypted with players private keys cannot be recovered if a player quits (at least not without a threshold scheme), one way to solve the drop out problem (as shown in the patent) is to create a fresh new deck, where the cards that were in possession of the player that has left return to the new deck.
This is done by creating a new shuffled deck and then removing the cards that were in possession of the players, without revealing which cards are removed. This is the best possible solution.

  Have the performance problems been solved?

Yes, it takes less than 10 seconds to shuffle a 52 card deck by 6 players using the algorithm published in the patent.

  Is there an implementation of the algorithms / protocols?

I have my own implementation, but it's not tidy enough to put in public domain. I should.

  What is the latest performance improvements (e.g. is [2] up to date to the fastest protocols known)?

IMHO the last performance improvements come to what I called Simultaneous Zero Knowledge Proofs. In SimZNK all parties cooperate to prove their private operations (shuffle and re-encryption) are correct.

If a player tries to cheat, then the player having cheated is detected at the end of the shuffle stage (when all players have shuffled the deck, but before the game starts).
Afterwards, the process can be restarted without having leaked any private information of any value.

This verification scheme is much faster than verification (either by interactive or non-interactive ZNPs) after each player shuffle and re-encrypts the cards.


Should we run PBKDF2 for every plaintext to be protected or should we run PBKDF2 only once? I am going to store secrets from users. The secrets need to be stored confidentially. For this question, I am concerned only with confidentiality (not integrity).

Here is how my encryption scheme is:

We start with a 20-character randomly generated alphanumeric password.
A new 128-bit salt is generated randomly for each user secret to be stored.
The 20-character password and the 128-bit salt is passed through a HMAC-SHA256-based PBKDF2 function to derive a new 256-bit encryption key for each user secret to be saved.
A new 128-bit initialization vector is generated for each user secret to be saved.
The 256-bit encryption key and the 128-bit initialization vector is used to perform AES-256-CBC encryption of the secret and arrive at the ciphertext.
The salt, initialization vector, and the resulting ciphertext are all saved together.

I want to know if in steps 2 and 3, is it necessary to run the password through PBKDF2 every time for every new secret to be protected?

Or can we just run the password through PBKDF2 only once and use that key for all secrets to be protected?

Is there any provable benefit of generating a different key (with PBKDF2) for each user secret even if we start with the same alphanumeric password every time?

Assume you have an IND-CCA secure cryptosystem $E$ that runs a password through a slow KDF and implicitly handles salts and random IVs, a human-chosen password $p$, and messages $m_1$ through $m_n$ to encrypt. Is $E_p(m_1+m_2+\cdots+m_n)$ or $E_p(m_1)+E_p(m_2)+\cdots+E_p(m_n)$ better for this? Each invocation of $E$ is slow due to it running a KDF on $p$, but an attacker only needs to guess $p$ once. This means that both techniques are equally secure against an attacker assuming $E$ takes a constant amount of time, but the former is significantly faster for honest parties, so the former is better.

The purpose of a slow KDF is to make brute force of a weak, human-generated password difficult. You need to run it each time a password is input. Assuming only one password is being input, then it only has to be run through a KDF once. The output key can be used to protect as many secrets as you wish.

The reason is simple. If an attacker manages to guess the original password, they'll be able to use it again and again to decrypt all the data, whether or not the data was encrypted all at once or encrypted piece by piece by running the password through a KDF multiple times to generate multiple keys.


Is it possible to prove the time a message was produced? Say Bob wants to tell Alice a secret message, then they start some message exchanges protocol. At the end, Alice will receive the secret message and can be convinced that the message was not produced earlier (and obviously not later) than the time they communicated.

An attacker (Bob included) will try to win by forging the secret message before they start the message exchanges.

As for a real world scenario, consider the secret message a picture, showing something of Alice's interest. Bob sends this picture to Alice, Alice however, doubt the picture was taken a long time ago, so she challenges Bob to send as well some random angles of the things showing in the picture as she requested until she is convinced that the things showing in the picture are there at the time they communicate. Note that the things in the picture can be there a long time ago (e.g. an old house) , but the secret message (the picture showing the old house) was only produced at that moment.

The security of the above scenario is only based on Bob not knowing the random choice of the angles Alice will pick and the infeasibility of Bob quickly creating a fake picture at the said angle. Can cryptography provide something better than these?

Somehow I believe the "infeasibility to create variants of the secret message" is a must assumption to guarantee the proofs. So may be in real world this cannot be a simple plaintext message, but sound, picture, video, 3D model, etc., which are difficult to edit?

If the the message is generate by a one-way function then incorporating in the message a sample from a randomness beacon (such as https://www.nist.gov/programs-projects/nist-randomness-beacon) will prove that the message was generated at a time later than when the sample was taken.


Is there a perpetual 2-factor-authentication scheme that allows temporary password generation? Recall that current forms of two-factor authentication (2FA) rely on:

Something you know, i.e. your password

Something you have, i.e. your one-time password (OTP) generator on a trusted device

The procedure is as follows:

Client sends username (public)
Client sends password (private)
Client sends otp = HashOTP(client_seed, time())
Server looks up salt, salted_password_hash, and seed for username
Server compares HashPW(password, salt) against salted_password_hash
Server compares HashOTP(seed, time()) against otp
Client is authenticated iff all comparisons succeed.

The idea, of course, is that even if all the transmitted information is intercepted by an attacker, the attacker is unable to authenticate because he does not have the client_seed to generate a subsequently valid otp.
So far so good, except that interception of password permanently reduces 2FA to 1FA.
"Permanently" because the user will have no idea his password is compromised, and will therefore have no reason to change it.
So, ironically, not only is otp a "one-time password", but so is password itself. (!)
(Now, at this point, I'm sure some of you are ready to close the question, thinking, "But TLS should have protected the password during transit, and if the client itself is compromised, then the problem is invalid!"
If you're in that camp, well, realize that's not how the world works. A passive keylogger on the client could be secretly recording everything but the actual stolen credentials are likely to stay unused until a while after, when the user is unlikely to notice it. So it makes sense to render any such keylogger useless if possible.)
Given that the user will reuse password without even knowing that his 2FA is really 1FA, a theft of his device is all that stands between him and his account, and he is likely to think he is safe because he has no idea his password might have been compromised.
How, then, can we address this?
Initially I was thinking that the user could type his password into his trusted OTP generator and generate a single one-time password that will authenticate him without ever having to send his actual password.
But now it seems to me the server would need to know the password itself in order for this approach to work. In other words, it defeats the storing of hashed passwords—i.e., a server-side leak will now reduce all users' 2FA to 1FA, instead of a client-side leak.
Basically, it almost seems that 2FA is fundamentally 'single-use': any attacker with read-only access will reduce 2FA to 1FA, and the client and server can remain indefinitely unaware.
But I don't know if this is really the case.
Can we keep the two-factor nature of 2FA even after a client or server data leak, without otherwise weakening the system's security? How (or why not)?

If you use asymmetric cryptography you can make it work. The trusted device stores a private key and salt the user will type his password and it will get hashed with salt and get encrypted/signed and the result sent to server which has public key and the salted hashed password. The main problem is the trusted device now sends something much larger then the common short tokens used today. Also public key crypto is more computationally expensive, we know how to make the server side cheap but not both sides.
A server breach doesn't expose the private key, a trusted device breach doesn't expose the password and a loss of password doesn't expose the private key.


Algorithm for Boneh and Durfee attack on RSA I am trying to understand various attacks on RSA and I believe that they only way to fully understand the algorithm is to implement it. I am trying to implement the code in this paper (pdf) (Private Key $d$ less than $N^{0.292}$) but after spending hours I am having problem writing the algorithm needed to implement the code. A small hint to help me implement the code would be appreciated.

I am familiar with LLL (lattice reduction) and how RSA works, so just small hint would be really helpful.

I understand that we want to solve the polynomial $f(x, y) = x(A + y) - 1 = 0 \ (mod \ e)$ s.t. $x = k$, $y = -p-q$ and $A = N+1$, but I don't understand the shifting part and construction of lattice basis to be used in LLL.

Our goal is to find a root $(x_0,y_0)$ in $\mathbb{Z}_e$ of the polynomial $f(x,y) = x(A+y)-1$. Finding roots of a polynomial in any $\mathbb{Z}_n$ isn't an easy job, in order to solve the problem Coppersmith had the idea to reduce to problem to finding a root $(x_0,y_0)$ over $\mathbb{Q}$ of some other polynomial $f'$ related to $f$.

About Coppersmith method

His technique relies on building a lattice $\mathcal{L}$ whose entries are coefficients of some polynomials (x and y shifts) having the same root $(x_0,y_0)$ as $f$. Thanks to this property, every linear combination of x and y shifts will be solved by $(x_0,y_0)$. Once $\mathcal{L}$ is built, it can be reduced using LLL algorithm (the same matrix is represented in a different basis, computationally easier to manage due to small coefficients) and from that get two polynomials $g_1,g_2$ (as linear combinations of $\mathcal{L}$ elements) such that $g_1(x_0,y_0) = g_2(x_0,y_0) = 0$.

Why x and y shifts?

First of all, let's define what a shift is. Those are derived from different powers of $x$, $y$, $f$ and $e$. $g_{i,\phi}$ and $h_{j,\phi}$ are respectively $x$ and $y$ shifts:

$$g_{i,\phi}(x,y)=x^i f^{\phi} e^{m-\phi}$$
$$h_{j,\phi}(x,y)=y^j f^{\phi} e^{m-\phi}$$

Where $\phi \in (0,m)$, $i \in (0,m-\phi)$ and $j \in (0,t)$. Once $m$ is defined, it's easy to compute the set of shifts. Indeed, $m$ is the maximum degree of $x$ in shifts, whereas $t+m$ is the maximum degree of $y$.

That's all we needed: a bunch of polynomials (up to a certain degree) having the same root as $f$.


How to select "good" bits which pass NIST statistical tests x% of the time? I am trying to implement an algorithm where the first step is to select "good" bits using the NIST test suite. In particular, I have $k$ streams with $n$ bits each. The original paper Toward Sensor-Based Random Number Generation for Mobile and IoT Devices (PDF) states

  For a given bit to be ‘good’, it must pass at least 3 of the NIST tests at least 75% of the time.

What would be the best way to go about implementing this?

The NIST tests which I am using are the frequency test, frequency test within a block, runs test, longest run of ones within a block, DFT test, binary matrix rank test, and approximate entropy test.

From the question:

  I have $k$ streams with $n$ bits each. (..)
  The original paper (..) states "For a given bit to be ‘good’, it must pass at least 3 of the NIST tests at least 75% of the time"

I read "given bit" as meaning "any particular bit index in each of the $k$ streams"; and "of the time" as meaning "of each test run performed for bits at this bit index" (among possibly many such tests because $k$ exceeds the number of bits a given NIST test consumes). Thus the literal implementation could be:

for $i$ from $0$ to $n-1$ (each of $n$ bit index in a sequence)

$p\gets0$ (the number of tests passed for bit $i$)
for each of the NIST tests considered (out of 15 at the last count)

let $b$ be the number of bits required by the particular NIST test (e.g. 100 for the Frequency (Monobit) Test; 1000 for the DFT test)
$f\gets\lfloor k/4b\rfloor$ (the maximum number of times the test is allowed to fail)
for $j$ from $0$ to $\lfloor k/b\rfloor-1$ (each group of $b$ streams)

perform the test on the $b$-bit sequence obtained by keeping bit $i$ of sequences $j\cdot b$ to $(j+1)\cdot b-1$ (numbering sequences and bits starting from $0$)
if the test fails

$f\gets f-1$
(optional: fail quickly) if $f<0$

break from the loop for $j$

if $f\ge0$ (the particular test passed at least 75% of the time)

$p\gets p+1$
(optional: succeed quickly) if $p\ge 3$

break from the loop for NIST tests

if $p\ge 3$ (at least 3 of the NIST tests passed at least 75% of the time)

that bit $i$ pass the original paper's criteria; remember to use this bit in the future.

It is possible to adjust $b$ for each test as a function of $k$ so as to reduce the proportion $k\bmod b$ out of $k$ bits that are not tested, or splitting the $k$ bits almost evenly across sequences tested (within 1 for tests with no constraint on $b$).

NIST tests with $b>k$ succeed for 0 out or 0 time they are run, and accordingly the "at least 75% of the time" criteria is met; thus a test that does not run still accounts in the minimum of 3 tests that pass; I'm among those thinking this is a telltale sign that the criteria is profoundly unsound. Main problem really are:

As far as we can tell from the question, NIST tests are run unmodified, thus with low $p$-value (like 1%), making the 25% failure rate tolerated seemingly unjustifiable.
When any test consistently fails, the bit sequence has been distinguished from uniformly independent bits, yet it is sometime kept; this means we are not using the tests for what they are designed to do: test sequences against the null hypothesis that they are uniformly independent bits.
Treating all the tests equals (when they are designed to detect very specific defects) is a telltale sign of an absence of method.

My algorithm is only the literal implementation of what the paper prescribes. This shall not be interpreted as a recommendation; rather, the opposite: the rationale of the prescription evades me. Advice only binds who trusts it.


AES decryption vs encryption speed Let's consider the CTR mode. For a faster encryption/decryption, is it preferable to use the decryption operation of AES, or its encryption ?

Given the choice, it is preferable to use the block encryption operation of AES, since it often faster than block decryption (never slower AFAIK). For this reason, AES-CTR is defined to use the block encryption operation of AES exclusively; that's both for AES-CTR encryption and AES-CTR decryption, which are the same operation except for IV generation/input.

AES block encryption is faster than AES block decryption because:

MixColumns uses a matrix with smaller coefficients than InvMixColumns, thus is simpler to compute (that's particularly true for purely software implementations; hardware implementations sometime use the same number of cycles, including I believe Intel's AES-NI instructions).
during encryption, subkeys are needed in the order they are produced from the key, but during decryption that order is reversed, therefore on implementations (including hardware) that start decryption with the pristine key as input, some preliminary work is necessary before decryption can start (there's no known shortcut).

Here is for example a crypto library performance report (single-thread, software AES) showing speed differences.


Simulation aborted because the adversary doesn't use the random oracle I'm trying to construct a proof for an encryption scheme in the Random Oracle model. This encryption scheme is like a PKE scheme but with an additional function that kind of "alters" ciphertexts without changing the underlying message using some special keys (I don't want to go into the scheme details for not diverting attention from the actual question; let's call this function "Alteration", for simplicity). In principle, the scheme is designed in such a way that in order to create valid ciphertexts, you have to use a hash function $H$ at some moment during the encryption. I later use this fact in the proof to construct the decryption oracle: assuming that $H$ is a random oracle, I use the random oracle table to extract the necessary information for answering the decryption query, and if the adversary has not used $H$, then it outputs $\perp$. The adversary cannot distinguish this behavior from a real-world execution. So far so good.

The problem I'm facing right now is with the Alteration oracle. Everything goes smoothly as long as the adversary uses the random oracle. However, the adversary may query the Alteration oracle with a ciphertext constructed without using the random oracle, but the real-world version of the Alteration function is unable to detect such situation and simply outputs the altered ciphertext correctly. In the proof, the simulator cannot respond to the query since the adversary has not used the random oracles and the simulator does not have the required special key. The thing is that I don't see that these queries are beneficial at all to the adversary: the resulting ciphertexts would also be not valid, as the original ones, so their decryption would fail.

Therefore, in order to avoid a situation where the adversary could detect a difference between the simulation world and the real world, the only think I can think of at the moment is to abort the simulation in such situation. Of course, simply letting the proof go this way would invalidate it, since the adversary could make these problematic queries arbitrarily. I was thinking in trying something similar to the "artificial abort" technique used in the Waters IBE scheme. However, before continuing in that direction, I have the following questions.

Do proofs in the Random Oracle model generally require to handle the situation when the adversary is not using the Random Oracle (e.g., producing invalid ciphertexts)? If not, do you know any example of a scheme defined in the RO model where a similar situation occurs?

Your proof certainly has to work even if the adversary doesn't use the random oracle. One technique that you can try is to begin by proving a separate lemma that if the adversary doesn't ask a certain query first, then it definitely cannot succeed in distinguishing. Then, you proceed to prove the simulation conditioned on it asking this query.

However, if you can't prove this, then you may have to go back to the construction and change it. This reminds me of the double-encrypt-plus-NIZK way of getting CCA-secure encryption in the standard model. In that construction, the NIZK is needed since the simulator can only decrypt one of the two ciphertexts in the reduction, and cannot tell that the other is an encryption to the same. However, if it's not an encryption of the same, then in the real world this would decrypt to invalid. Nevertheless, you can't get rid of the NIZK. The simulator has to know what would happen in the real execution. Sorry for the pessimism.


Deterministic Authenticated Encryption with AES-OFB and HMAC I have an encrypted column in a database that stores sensitive information. The existing encryption scheme is deterministic and a database index exists on the encrypted value to allow searching.

I am upgrading the encryption scheme to use authenticated encryption, so the obvious choice seems to be AES-SIV. However, the data is accessed both from a Java app and from PL/SQL stored procedures so I am limited to the cryptographic primitives supported by Oracle's DBMS_CRYPTO package (SIV is not supported).

I read several questions on this site, mainly Why is synthetic IV (SIV) mode considered deterministic authenticated encryption (DAE)? and Is it okay to use an HMAC of the plaintext and a (possibly distinct) key as the IV for symmetric cryptography? and I have come up with the following design:

Use a 64 byte key, where there first 32 bytes are the HMAC key and the remaining 32 bytes are the AES cipher key.
Use HMAC-SHA512 on the plaintext to generate a the initialisation vector (use first 16 bytes only).
Encrypt using AES in OFB mode (since CTR mode is not available). OFB mode will preserve length and (I believe) avoid padding oracle attacks.
Concatenate the 16 byte IV and the ciphertext in the database column.

My questions are:

Does this design provide deterministic authenticated encryption?
Is there a better design that would allow searching on the encrypted data?

Does this design provide deterministic authenticated encryption?

This provides reasonable security as long as you limit the total volume of data encrypted to well below $2^{64}$ bytes.

Details.
The SIV theorem[1], roughly, is that if $F_{k_1}$ is a $t$-bit PRF, with PRF distinguisher advantage bounded by $\varepsilon_F$, and if $E_{k_2}$ is a randomized cipher, with CPA distinguisher advantage bounded by $\varepsilon_E$, then $$m \mapsto F_{k_1}(m) \mathbin\| E_{k_2}(F_{k_1}(m), m)$$ with decryption $$t \mathbin\| c \mapsto \begin{cases} m, & \text{if $F_{k_1}(m) = t$;} \\ \bot, & \text{otherwise,} \end{cases} \quad \text{where $m = E_{k_2}^{-1}(t, c)$,}$$ is a deterministic authenticated cipher with distinguisher/forgery advantage bounded by $\varepsilon_F + \varepsilon_E + q^2/2^t$ for any adversary making at most $q$ queries to $E$ or $F$.

Under standard conjectures about SHA-512, the PRF advantage of a $q$-query cost-limited adversary against a 128-bit truncation of HMAC-SHA512 with a 512-bit key is bounded by about $q/2^{128}$.
Under standard conjectures about AES, the IND-CPA advantage of a $q$-query cost-limited adversary against AES-OFB with a 256-bit key and messages up to $\ell$ blocks long is bounded by

$q^2 \ell^2/2^{128}$, if the IVs are unique, and therefore
$q^2/2^{128} + q^2 \ell^2/2^{128}$, if the IVs are chosen uniformly at random, as SIV hypothesizes.

Summing up, the adversary's advantage is bounded by about $$\frac{q}{2^{128}} + \frac{q^2 \ell^2}{2^{128}} + \frac{q^2}{2^{128}} + \frac{q^2}{2^{128}} = \frac{q + 2 q^2 + q^2 \ell^2}{2^{128}}.$$

I say ‘about’, because this excludes the probability of guessing $k_1$ and $k_2$, which, if they are 256 bits, is minuscule in comparison even in a multi-target attack on $2^{64}$ users; and this excludes the probability of an internal collision in HMAC-SHA512, which is also minuscule in comparison.  The dominating term $q^2 \ell^2$ is the total number of blocks encrypted.  Hence: keep the total volume of data encrypted well below $2^{64}$ bytes.  A limit of a few gigabytes should be fine.

The real SIV, as presented in the paper and standardized with CTR mode, also handles associated data with a custom tuple PRF construction, instantiated with AES.  The custom tuple PRF doesn't matter if you don't have associated data, and the instantiation with a PRP like AES instead of a PRF like HMAC actually hurts security a little (by the standard PRP/PRF switching lemma).

  Is there a better design that would allow searching on the encrypted data?

This looks to me like the easiest secure option with the tools you have at hand.

You could derive a fresh AES key for each message, and cut it down from 64 bytes of key material to 32 bytes of key material, but there's a cost—switching AES keys is more expensive than switching AES-OFB IVs, and you'd have to call HMAC-SHA512 twice or something—and there's no benefit to security unless you expand the tag from 128 bits to 192 or 256 bits.

You didn't ask, but you perhaps should have asked:

  Are there any implementation pitfalls to be aware of?

Make sure that you do not touch the unauthenticated plaintext except to compute the authenticator until after you have verified it.  Unauthenticated data is pure evil—don't touch it!
Make sure that you don't use PKCS7 padding or anything.  Make sure that the AES-OFB decryption cannot fail, because failure of the decryption distinct from failure of the authentication might leak information about the plaintext in a padding oracle attack like BEAST.
Make sure to write test vectors in another language to cross-check and perform self-tests.

Finally, encrypted database search is a goldmine for attackers even if they can't see the content of the encrypted field[2] (popular exposition).  Caveat data hoarder!


Encryption in which ciphertext is bigger than plaintext? Is there an encryption which would produce a ciphertext longer than the plaintext?
(please ignore block-chaining IV stuff, which would result in a data being generated from the plaintext).

The point in question is that a ciphertext generated $\{0,1\}^n$ seems inferior to one twice as long $\{0,1\}^{2n}$ in terms that more permutations are possible in the later one.

Yet if the plaintext was of a blocktype being $\{0,1\}^n$ it seems puzzling how the encryption would map bothways
$$\{0,1\}^n \to \text{encrypt} \to \{0,1\}^{2n}$$ and
$$\{0,1\}^{2n} \to \text{decrypt} \to \{0,1\}^n$$

I assume this question to touch on the necessary attriubutes of encryption that it is reversibility and deterministic behaviour both way.

There's no blockcipher providing this.

However if you want this kind of mapping there are two usage scenarios.

Strengthen the symmetric encryption. You could double the keysize by this construction. In "Applied Cryptography" Schneier suggested to combine two encryption algorithms so the ciphertext would be double the size of the plaintext.

Generate a pad $R$ at random, as long as your message
Calculate $P=R \oplus M$
Encrypt $P$ using one Cipher-Key-Pair
Encrypt $R$ using the other Cipher-Key-Pair

It might be possible to construct an online AEAD mode with intermediate tagging as one could basically authenticate each single block of the message. F.ex. using HMAC + CTR on 512-bit blocks one could encrypt the continous data stream using CTR and place the 512-bit HMAC tag after each 512-bit block. This might be nice, as you've got all the desireable properties of online encryption and intermediate tag verification that such modes provide. It might as well be possible to construct such a mode using a blockcipher (and maybe something like VMAC).

However for the first usage scenario there's no need as current blockciphers are secure enough and if you need larger blocksizes simply switch to something like Threefish.


In Fortuna, can I use ChaCha20 instead of a block cipher and Blake2b instead of iterated SHA256? In the Fortuna CSPRNG, can I use ChaCha20 instead of a block cipher and Blake2b instead of double SHA256, and still retain security?

My hypothesis is "yes" because:

The block cipher's only use is in CTR mode (i.e. as a stream cipher).  ChaCha20 is a PRF used in CTR mode.  In fact, I think this should increase security.
Blake2b is considered at least as strong as SHA256 and is immune to length-extension attacks, so the double hashing is not required.

The main advantage is performance.

TL;DR: Fortuna is a CSPRNG so you can replace components pretty arbitrarily, because you're not bound by compatibility requirements and the modifications should work, although there are some points that are note-worthy.

In Fortuna (PDF), AES-256 is used in exactly one place: To generate the keystream based on the current counter (the function is even called GenerateBlocks())

However, there's one potentially difficult thing with the way AES-CTR is used by Fortuna: Counters aren't reset upon re-key. So if Fortuna re-keys, it generates two blocks of key material and uses them as the new keys, but the counter used for this just gets incremented by 1 again and continued to be used.

This can be overcome by appropriately using the seeking mechanism of ChaCha.

In the end, AES-CTR in Fortuna fulfills the role of a pseudo random generator and thus is arbitrarily exchangeable by any other PRG, which includes block ciphers in CTR mode and of course also ChaCha. Whether using a different cipher will actually increase security depends on the amount of cryptanalysis on the new cipher, as 256-bit AES is already physically unbreakable for humans.

SHA-256d is used in two places in Fortuna: As a KDF to derive the new key from the old key and a given random string and separately as standard hash function to collect the pool entropy.

For both usages, a replacement of SHA-256(d) by Blake-2b is functionally equivalent, even though one may want to consider using Blake-2b in MAC mode (for the KDF part) or with some (distinct) personalization string for both operations.


If you are able to compute $m^1 \pmod{N}$, then you have (obviously) recovered the message $m$. So, you should be able to use the extended Euclidean algorithm to express $m^1 \pmod{N}$ in terms of $c_A$ and $c_B$.

Hint: It will involve exponentiations and multiplications.


Extending the size of input for SHA-2 function In the question Does a hash function necessarily need to allow arbitrary length input? many answers talk about the theoretical limit of the SHA-2 functions being $2^{64} - 1$ bit due to padding. I was wondering, is there a secure way to extend this? From the description, it seems that the $2^{64} -1$ bits is not a security restriction, but more a padding issue.
Would it still be considered safe to have an SHA-2 function that chunks the input data into $2^{64} - 1$ bits of hash size and use the hash of the previous chunk as a salt for the next chunk? Are there other options to extend the size of the input of those hash functions to arbitrary length?

$2^{64-1}$ bits that make 2.30584301 exabytes *. If you are not restricted to SHA256, then use SHA512 that allows files to have size at most $2^{128}-1$, or use SHA3 that has no limit.
The NIST must use a limit due to the artifact of the MD construction. SHA256 is standardized in 2001 along with SHA512. They have internal block size 512 and 1024 respectively, in order to reduce the change of internal collisions, double the output size double the internal size double the file limit!
If you want to extend the limit of SHA256, then you are out of standards. SHA512 is already beyond all.

Would it still be considered safe to have a SHA2 function that chunks the input data into (2^64 - 1) - hash size bits and use the hash of the previous chunk as a salt for the next chunk?

Yes, you can extend with this $h_1 = \operatorname{SHA256}(m_1))$ and $h_2 = \operatorname{SHA256}(h_1||m_2)...$
But safe is a vague term, safe against what? Hash calculation is free, SHA256 has a length extension attack that you may need protection. In theory, I'll not talk about the numbers, you will get more chance of internal collisions, that can theoretically reduce the second pre-image resistance, or read here
Another alternative is the Merkle Tree.

Are there other options to extend the size of the input of those hash functions to arbitrary length?

Use SHA3-256, or better use SHAKE128-256 or and SHAKE128-512

*What is Exabyte: An exabyte is $1000^6$ bytes.
This is a bit unrealistic to hash since;

OpenSSL hash time is approx 450 Mb per second for SHA256. Hashing 1 Exabyte will take 70466 years on my setup.

NSA's Utah data center is supposed to have 12 exabytes

Online storage and service companies like Google, Amazon, Microsoft, and Facebook are estimated to have at least 1,200 petabytes of storage, 1.2 Exabytes.


Additive Subspace Signature I realise there are homomorphic signatures for short messages, for instance with RSA encryption we have a signature scheme where $S(m_1 m_2) = S(m_1)S(m_2)$.

I would like to know if there's a signature scheme where the messages may be linear additive combinations of the basis vectors $(v_1, \dots, v_n)$ and where, if $v$ is in the subspace spanned by the basis vectors $(v_1, \dots, v_m)$ and the signatures $S(v_1), \dots, S(v_m)$ are known, it is possible to construct $S(v)$ from them.

The following papers constructs linearly homomorphic signature schemes.

Pairing based signatures:

https://eprint.iacr.org/2006/025.pdf
https://crypto.stanford.edu/~dabo/papers/netcode.pdf

Lattice-based signatures:

https://eprint.iacr.org/2010/453.pdf


How to break AES/CBC/PKCS5 when key and IV are reused? I'm doing a code review for a crypto solution that reuses the same key with a constant IV.  I want to demonstrate that this is not the right way to do things by figuring out the key and decrypting all of their test data.

I have access to lots of ciphertext.
I know the same key is used.
I know the same IV is used.
Cipher is AES/CBC/PKCS5
Plaintext is 16 bytes.
Ciphertext is 32 bytes (PKCS5 padding?)
I can put whatever plaintext I want through the system and then get that ciphertext.

What's the high-level pseudo code or process to break this system?

Well, there is no really good way; the encryption of the plaintext is $E_k( Plaintext \oplus IV)$ (followed by 16 bytes which are a deterministic function of the first ciphertext block). The AES function $E_k$ is designed to be totally unpredictable if you don't know the key, there's nothing to leverage there. The only thing that allows you to gain any advantage is that the encryption function itself is deterministic; that is, about the best you have available is:

Make a guess as to what the plaintext might be
Ask that be encrypted
Check to see if that ciphertext happens to match anything on your list
Rinse and repeat

Not by any means an ideal solution; however it's the best option you have available.

Now, if the plaintext had been longer than 16 bytes, you could use the above procedure to confirm a guess on the first 16 bytes of the plaintext, and then work on the next 16 bytes -- with your specified parameters, that's not an option.


Multi-Party Encryption for a Shared Document Is there an encryption algorithm/protocol where any of a pre-defined set of keys/passwords will succeed in decrypting a document? The number of keys can be fixed, say, 10 or 20 possible passwords.

The context is a single application (with a single embedded document), with no server-side component. It should be shareable amongst users, where any password, within a pre-defined set of passwords, will succeed in gaining access (decrypting the document).

EDIT: In thinking about this, can I append a (symmetrically) encrypted key to the document, where the password to decrypt this is a user's password? I.e. for each user, append the master-key after encrypting it with the users password. I'm not sure what algorithm is appropriate here, or whether this is at all secure.

Disclaimer: I'm fairly new to cryptography beyond the basic concepts and implementations - I don't know the terminology very well, and therefore I was unable to find a similar question posted.

Is there an encryption algorithm/protocol where any of a pre-defined
  set of keys/passwords will succeed in decrypting a document?

Not exactly a protocol, but there are formats out there that will allow this sort of thing. An example system using a similar appraoch would be LUKS which offers "key-slots" doing exactly what you want - but targeted at full disk encryption.

  [C]an I append a (symmetrically) encrypted key
  to the document, where the password to decrypt this is a user's
  password?

Yes you can, although usually these information are put in front of the document so you don't have to start at the end to gather the key and then jump to the front again.

  I'm not sure what algorithm is appropriate here.

I'm quickly describing what each key slots needs to hold. The extrapolation to 20 slots is then trivial.

The slots may hold an identifier so each user can quickly discover his slots. This may be a hash (SHA-3-256 or SHA-256) of the the email, or other appropriate identifiers.
The slots may hold algorithm identifiers for key derivation, for encryption and for authentication in case you plan on changing the format in the future.
The slots should hold a unique, random 16 - 32 byte salt each.
The slots should hold derivation parameters for the key derivation.
The slots must hold a unique, random IV of length 12 - 16 bytes each.
The slots must hold the encrypted document key and the encrypted IV for the document.

As for the algorithms:

The key derivation algorithms (in order of preference):

Argon2, the winner of the password hashing competition (PHC), will need at least two parameters and a salt along with the password, you may lack an implementation of Argon2 because it is fairly new
any other PHC recommendation (except Makwa), they are all fairly new and you may you not have an implementation, they all will need a salt and at least two parameters
scrypt, will need three parameters and a salt and is more likely to be available than Argon2 and the PHC recommendations and uses large amounts of memory
bcrypt, will need only one parameter and a salt and is likely to be available
PBKDF2-SHA256, is 100% available or you can quite easily implement it yourself

Encryption algorithms for the document key, the document IV and the document (in order of preference):

AES-GCM / AES-OCB, use AES-OCB if available but chances are you can't because of the patent, if available AES-GCM is your best option then
AES-CCM / AES-EAX, use these modes if possible or if necessary implement them yourself if you have access to an AES primitive.
AES-CTR + HMAC-SHA-256, use this mode in an encrypt-then-authenticate manner and only use it if you have AES and HMAC at your disposal but can implement EAX or CCM.
3DES-EAX / 3DES-CCM, use this if you have access to an implementation of 3DES (or just DES) and implement EAX / CCM on top.
TEA-EAX / TEA-CCM, use this if you don't have access to any implementation of any block cipher (highly unlikely)


RC4, finding key if we know plain text and ciphertext Having plain text A , and  cipher text B. Can we somehow retrieve key , when we want to decrypt text C which was also crypted with the same key?

The correct answer depends on whether you want to recover the key or the keystream. Let's first review how RC4 works:
RC4 Recap
RC4 takes a key as input and generates a cryptographically secure stream of pseudo random numbers:
$KS= RC4(k)$
To encrypt a plaintext message M, we simply XOR it with the keystream KS:
$KS= RC4(k)$
$C= M \oplus KS$
To decrypt the ciphertext, we have to reproduce the keystream by providing the same shared key as input to RC4:
$M= C \oplus KS$
Now, it is cruical that the same keystream is never used twice for encryptoin, since an attacker could learn the XOR of the two messages:
$C1= M1 \oplus KS$
$C2= M2 \oplus KS$
$C1 \oplus C2= M1 \oplus KS \oplus M2 \oplus KS= M1 \oplus M2$
Known-plaintext attacks against RC4
RC4 keystream recovery: This is a trivial thing to do once you are in possession of the plaintext:
$KS= C \oplus M$
This is normally not a problem since no one that has basic understanding of cryptography uses the same keystream to encrypt multiple messages. However, if I understand the description correctly, you have the following scenario:
$B= A \oplus RC4(K)$
$D= C \oplus RC4(K)$
If an attacker is in possession of A,B and D, it is trivial to extract the keystream generated by RC4(K) and decrypt the message C (at least up to the same length as A):
$C= D \oplus B \oplus A$
Example:
Let's say RC4 produces the following keystream:
KS= 11010110 00011010 01101011 10001110 11001101 11011111 01001010

With message A="hello" and C="secret!", you get the following ciphertexts:
A = 01101000 01100101 01101100 01101100 01101111
C = 01110011 01100101 01100011 01110010 01100101 01110100 00100001

B = 10111110 01111111 00000111 11100010 10100010
D = 10100101 01111111 00001000 11111100 10101000 10101011 01101011

By computing $A \oplus B$, you get the first 5 bytes of the keystream, which allows you to decrypt the first 5 bytes of C. Without the knowledge of the secret key or a longer plaintext-ciphertext pair you will not be able to decrypt the rest of C!
Note: You can already see in this example why it is a bad idea to re-use a keystream: the second byte of the ciphertexts of B and D are identical since they both encrypt the same character ("e").
RC4 key recovery: Recovering the secret key K is a much more difficult. There exist large classes of keys for which a small part of the secret key determines a large number of bits of the keystream. This is why it was recommended to throw away the first 256 bytes of the keystream (nowadays the recommendation is to not use RC4 at all). Observing enough plaintext/ciphertext pairs generated under a key can eventually be leveraged by attacks like the one by Fluhrer et al., leading to the recovery of the key by an attacker.


Distinguish between cipher-texts of text-book RSA and RSA/OAEP Is there is a possibility to identify from cipher-text that, this is been encrypted using a text-book RSA or RSA with OAEP padding. (By looking at the cipher-text only) ?

We can distinguish between ciphertext of textbook RSA and RSA/OAEP when textbook RSA is misused and insecure; or with knowledge of the private key.

With knowledge of the private key, we simply attempt RSA/OAEP decryption. If it succeeds, we bet for RSA/OAEP (and that will hold except for a vanishingly small proportion of possible plaintext); otherwise we know that's textbook RSA (with certainty, unless there's another option).

With knowledge of the private key, we can still succeed by exploiting weaknesses of textbook RSA; for example:

If we can obtain ciphertexts for the same unknown plaintext enciphered twice, we can compare these ciphertexts. If they match, we bet for textbook RSA (and that will hold with overwhelming probability, unless the random number generator of RSA-OAEP is badly broken). If they differ, we know that's RSA/OAEP.
With knowledge of the public key (assumed in this and the next two bullets), if we know / suppose that the plaintext is a name on the class roll, we try to encipher all names on the class roll (that requires the public key, but by assumption that's known to all), and compare each result to the actual ciphertext. If any match is found, we know with near certainty that's textbook RSA; otherwise, we bet for RSA/OAEP (with odds depending on how confident we are that the plaintext is a name on the class roll).
As suggested in comment: if the ciphertext is an exact power of the public exponent $e$, we know for certain that's textbook RSA. Otherwise, we bet for RSA/OAEP (with odds depending on how likely it is that the plaintext $M$ is small enough that $M^e<N$).
If we can obtain actual ciphertext for a single chosen plaintext, that allows a test.

Also, if we know or can find the size limit for the plaintext, that's also revealing: Textbook RSA usually can encipher messages up to $\lfloor\log_2(N)\rfloor$ bits or $\lfloor\log_2(N)/8\rfloor$ octets; while RSA-OEAP has a much lower limit, $\lceil\log_2(N)/8\rceil-2-2h$ octets, where $h$ is the hash size in octets ($h=32$ for SHA-256).


The exact definition of a symmetric encryption I have doubts for the definition of the decryption algorithm $D(.)$. I think I've already seen that the decryption returns a plaintext $M$ on input the key $K$ and $C=E_K(M)$.
I have also seen that the decryption algorithm returns either $M$ or the special symbol $\bot$.

Is the first definition valid in the case of symmetric encryption? Especially when we deal with non authenticated encryption...

The short answer is that if your encryption routine is a bijection, then the first is fine. However, if it is not surjective, then you need to define what on earth it means to decrypt an invalid element. This could be done by having elements with multiple preimages (as may occur in schemes using bad/misimplemented padding) or output an error symbol $\perp$.

Below the bar is a longer, rather more rambling answer, as initially posted.

This depends on the encryption algorithms in use. If the encryption algorithm is a bijection, then every possible $C$ must have a preimage. Examples of this include block ciphers like AES. In these cases, the decryption algorithm will output a message $m$ such that $E_k(m)=c$. Note that if $c$ has been tampered with by an adversary but is still the same length, then it will be possible to find a preimage under $E_k$ even though it was not produced as such. That is, in these cases:
$D_k(c)$ returns the unique value such that $E_k([D_k(c)])=c$.
In this case it would be fine to define decryption as having simply the message space as it's codomain.

However, theoretically at least, there is no reason my encryption scheme would need to be surjective (it doesn't need to 'fill' the ciphertext space).
For example, I can define a scheme where the message space $M = \{0,1\}^{128}$ and ciphertext space $C=\{0,1\}^{130}$ such that
$$
c = E_k(m) = 00||\mathrm{AES}_k(m)
$$
This would meet the security promises of AES (after all, it is just an embedding). However, consider the decryption function. Writing the ciphertext as $c=x||y||c'$, where $x,y$ are bits and $c'$ is a 128-bit bitstring, then
$$
D_k(c)=D_k(x||y|c')=\begin{cases}
\mathrm{AES}_k^{-1}(c')  & x=y=0
\\\perp & else
\end{cases}$$
In this case, whilst for all valid ciphertexts we can provide a decryption, there is no way any ciphertext valid can be generated that begins with anything other than $00$. So, when asked to decrypt such a message we must provide some form of error message, the standard for which is to use $\perp$ (as in contradiction).

In the case of authenticated encryption, we design our encryption routines such that it is hard to find an element $c$ of the ciphertext space that has a preimage $m$ unless that we have already calculated $E_k(m) = c$.  In these cases, the symbol $\perp$ demonstrates that the attempted decryption of a ciphertext that does not pass the authenticity check.

A possible reference for further related questions would be Section 2.1 of Katz-Lindell, but note that this is given in the probabilistic model. Most modern AE work is performed in a nonce-based setting.


Linear subspace and Affine subspace I am currently reading a paper titled "Another view of division property" and encountered the terms "Affine subspace" and "Linear subspace". I am new to the field and having some difficulties to understand the topics. Can anyone describeb or give any reference about it so that I can read that.

In general an affine subspace is not a subspace, it's just a translate (coset) of a subspace. This is because normally we expect $0$ to be in a subspace $V$, since due to closure $x-x \in V.$

If $a+V$ is an affine subspace for $a\neq 0,$ and $V$ a subspace then automatically $a$ is required to be not in $V.$ Otherwise $a+V=V.$


How to tell if a hardware RNG is rigged? On a related note of building my own RNG, as someone suggested to use several commericial solutions how can I check if it is rigged against me? (although I am still strongly biased to a homebrew solution that is designed to be hard to subvert, taking the shortest possible route from a quantum random source to the ADC)

While unfortunately that is not possible deterministically, if you have a small amount of "guaranteed trustworthy" randomness, you can use several untrusted RNGs together to generate an unlimited supply of good randomness (under some weak assumptions of non-signaling between the RNGs). This is called "randomness expansion" and I am not aware of any use in practice yet, unfortunately.

See these papers by Colbeck and Kent and Coudron and Yuen


blinding a hash vs. sending the hash directly So with blind signatures you have two parties - A and B. A has a message that they want B to sign so A creates a hash of their message, blinds it, and then sends it to B to sign. That, as I understand is how blind signatures work.

My question is...  what's the point of blinding, in that step? If all you're sending is a hash then that, in and of itself, should obscure the message. And if you wanted to protect against an attacker knowing when you're sending the same message you could send salted hashes to the signer B to sign instead of blinding the hash of the message.

Am I wrong?

You are wrong.  The purpose is to prevent linking the signing operation with the verification operation.

For instance, suppose that I have to identify myself when I ask B to sign the thing (maybe B charges me to create a signature; for instance, when blind signatures are used for e-cash, B is the bank, and B charges money to sign anything, since validly-signed coins are money).  Now suppose I want to be able to present the signature later so someone else can verify that the signature is valid.  The security goal for blind signatures is that I don't want the verifier to be able to collaborate with B to identify me.

If it is possible to link the signature (presented during verification stage) with the value presented during the signing step, then that defeats the security goal.

If you ask B to sign an unblinded hash, then security falls apart.  The verifier (who sees the signature) can pull the hash out of the signature, then collude with B to match that up to the person who originally presented the hash for signing.  In that way, the verifier could identify you -- something that's no longer possible if you use blind signatures and only send the blinded hash to B.  In particular, given a signature, it is very easy to recover the hash of the message that is being signed: part of the signature verification step involves computing this hash.

So, just sending the unblinded hash isn't good enough.  You need to blind the hash before sending it to B for B to sign, in the applications where blind signatures are sued.


How do we know if we have successfully decrypted something? Suppose for any given typical Bob, Eve and Alice encryption example where Bob and Alice exchange information using RSA. Bob encrypts his message using Eve's public key and sends his message off to Alice.

If I was Eve, suppose I attempted to brute force the private key, and kept doing it mathematically by computing the encrypted message to the power of x, where x is the private key I am trying to find.

When brute forcing the message, how do I know what I have successfully found it?

For any given number x, there is an output, by how do we know that we have found the private key? Does it just check that the output is an english based sentence, what if the output is just something that is another encoding and the output is jibberish again, how would Eve know?

Given $d$ we can factor $n$ as follows;

compute $k=de-1$
choose random integer $g$ $1 < g< n$
$k$ is even with $k=2^tr$ with odd $r$ and $t\geq 1$
compute $x = g^{k/2}, g^{k/4}, \ldots,g^{k/2^t} \pmod n$ until $x>1$ and $y=\gcd(x-1,n)>1$

the either $p$ or $q$ is equal to $y$.

If there is no solution find another random $g$.

Looking for all possible $d'$s by this way will be costlier than factorization methods. However, if there is a non-gibberish that you found, you can try to factorize with your $d'$ to see that it is actually $d$.


Security proof of FO(Fujisaki-Okamoto) hybrid encryption The proof of FO hybrid encryption is hard to understand. $\:$ Especially, how does the challenger

respond to the decryption queries when the challenger can only have some encryption queries?

Intuition

The intuition behind the proof is that a valid ciphertext is correctly generated and, thus, an adversary should query to the random oracles to generate random strings in the ciphertext.
In addition, notice that the hash value on an unqueried string is undetermined (to the adversary) in the random oracle model. Therefore, the chance to construct a valid ciphertext without querying to the random oracles is negligible.

How to answer a decryption query

Lemma 11 is the core of the proof. The knowledge (or plaintext) extractor without a secret key but with the tables of the random oracles successfully simulates the real decryption oracle with the secret key following the above intuition. In Appendix B, the knowledge extractor is described.

A ciphertext of the converted PKE is of the form $$(C_1, C_2) = (\mathsf{PKE.Enc}_{pk}(\sigma; H(\sigma,m)), \mathsf{SKE.Enc}_{G(\sigma)}(m)).$$
The knowledge extractor has the tables $T_G, T_H$ of the random oracles $G, H$.
The table $T_H$ contains $(\sigma_j,m_j,h_j)$, where $h_j$ is a returned value on the query $(\sigma_j,m_j)$. The table $T_G$ contains $(\sigma_i,g_i)$, where $g_i$ is a returned value   on the query $\sigma_i$.

the knowledge extractor, given a ciphertext $(C_1, C_2)$, picks up consistent pairs $(\sigma, m)$ from the tables $T_G$ and $T_H$, which satisfy the equation, $$(C_1, C_2) = (\mathsf{PKE.Enc}_{pk}(\sigma; H(\sigma,m)), \mathsf{SKE.Enc}_{G(\sigma)}(m)),$$
by re-encryption with $h$ and $g$ in the tables.
If discovered, the knowledge extractor returns $m$. Otherwise, it returns $\bot$.

You can find the proof in Appendix B of the paper.


ECDSA recover on arbitrary values If I were to supply arbitrary values to an ECDSA recover function on secp256k1, is there some likelihood that the function would fail to return some value for the public key?

I am specifically trying to create signatures for an Ethereum transaction whereby the private key is unknown to me (single use transactions). Please assume that I will choose the values for the signature to optimise success (I.e., only enter sane values).

Edit: to clarify what I’m trying to achieve, see this post https://medium.com/@weka/how-to-send-ether-to-11-440-people-187e332566b7. In summary: create a transaction with some invented signature, do ecrecover on that signature to find it’s public key (and Ethereum address), fund that address with another transfer then finally submit the original transaction. Achieves a net result of sending a transaction from an address without knowing it’s private key. Not overwhelming useful, but interesting nonetheless.

Yes.

Non-ethereum elliptic curve signatures result in the numbers r and s, both of which need to lie in the range [1,n-1], where n is the size of the order of the elliptic curve base point. See Wikipedia - Elliptic Curve Digital Signature Algorithm.

Ethereum transaction signatures, use the secp256k1 curve (which has a fixed n value) and requires the numbers v,r and s. r has the same range as above, however unlike standard elliptic curve signatures, s is restricted to the range [1, n/2+1] (see the Ethereum Yellow Paper - Appendix F). Any values of r and s outside these ranges will generate an invalid signature.

Assuming we stick to r and s values within this range, we must also supply a v value for an Ethereum transaction signature. EIP-155 specifies v = CHAIN_ID *2 + 35 or v = CHAIN_ID*2 + 36.

The r value represents the x-value of a point on the scep256k1 curve. Fundamentally, v, represents the parity (even or odd) of the y-value of the point given by r (i.e the corresponding x-value). This parity determines whether to use 35 or 36 in the specification of v above. The value v is used as the recoveryid or recid in this library for ECDSA recovery on line 89 which is used by go-ethereum. Incorrect v values may make this recovery incorrect and give invalid resulting public keys. Thus, if one were to keep v fixed, and randomize r and s (or equivalently, randomize all numbers) within their range of validities and we were to assume an equal chance of getting an odd or even number, we would expect on average, 50% of signatures to be invalid (because we have an incorrect parity).


ABC Conjecture's Impact on RSA Encryption A recent proof of the ABC Conjecture has been released by one Shinichi Mochizuki.  Now, I'm not well versed in mathematics but it would appear that this proof implies that finding prime factors could be greatly reduced in computation time.  Is that right?  Does this show that encryption that relies on prime factors can be cracked quicker?  And if so is it possible that such an algorithm could be produced from these findings to do so either now or in the future?

There are no known implications of the ABC Conjecture to RSA.  The ABC problem doesn't have even a superficial resemblance to the security of RSA.

(The only point of connection is the fact that they both relate to prime numbers, but that is extremely thin.  Much of number theory can say it is somehow related to prime numbers.  It'd be like assuming that recent improvements in building fast sailboats for the America's Cup has implications for the possible future availability of a flying car, since they both involve fluids.)


How to verify a number encrypted with an unknown key Alice and Bob are going to follow the protocol below.  Are there any crypto-constructions to help Bob verify the correctness of the answer he gets?:

Alice encrypts a set of numbers using some cryptosystem and a secret key (e.g. Paillier crypto-system).
Bob multiplies the ciphertexts to obtain an encryption of the sum of numbers.
Bob sends to Alice the ciphertext for the sum. Alice decrypts the sum with her secret key and then encrypts the sum with a key known by Bob.
Bob receives the sum encrypted with his key and decrypts it successfully.

Question: how can Bob verify that Alice didn't change the sum to a different number before re-encrypting?  Is some sort of zero-knowledge proof helpful?

You probably don't need to re-encrypt using the Paillier crypto system.

1) Alice encrypts $c_1=g^{m_1} r_1^n$ und $c_2=g^{m_2} r_2^n$ and computes $r_3=r_1 \cdot r_2$ and $m_3=m_1+m_2$, then sends $c_1$, $c_2$, $m_3$ and $r_3$ to Bob

2) Bob computes $c_3=c_1 \cdot c_2=g^{m_3} r_3^n$ - If the homomorphically computed sum matches the re-encryption Bob will believe that $c_3$ encrypts $m_3$

The basic idea is that $g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1 \cdot r_2)^n$

All cipher text operations are executed modulo $n^2$

This proof is backed up by Paillier's original paper.
Unfortunately the proof is not absolutely Zero Knowledge as the sum may give you information about the possible summands. However you may choose large similarly sized primes for the $r$s so an attacker would need an efficient solution for prime factorization (see other question here).


How well does scrypt perform on different architectures / OSes? The scrypt algorithm seems to be a prominent feature in the "CPU friendly" Bitcoin clones for the proof-of-labor part. I've heard claims that it's relatively slow on Windows and/or Intel compared to Linux/AMD.

Is this true? By how much? Does anyone have concrete data on this? Is there a difference between 32 bit and 64 bit OS?

Bonus : could it be implemented more efficiently (power consumption and/or hardware cost wise) on dedicated hardware?

I've heard claims that it's relatively slow on Windows and/or Intel compared to Linux/AMD.

The claim that it could be Windows/Linux is a little off. It is more likely to be Intel/AMD, if anything. This will be an implementation detail based on the relative costs of processor instructions on each architecture; for example inc instructions are cheap on AMD, but costly on core 2 processors (relative to the speed of processors. You won't notice this difference unless you measure it).

In order to see numbers I suggest having a read of the x86 latency measurements made during the development of libgmp. They're slightly dated, but give you a fair idea that in fact not all assembly instructions cost equal.

Does this mean scrypt performs better on one processor or the other? Not at all. It means the implementation of scrypt measured performs better on one processor or the other. You should be able to produce optimised versions of scrypt for each architecture. This is, internally, what libgmp does for your multiprecision arithmetic - the optimised code for your architecture is the one you link to.

I'm not really a compiler expert, so I can't really comment on the behaviour of C compiled versions, but to achieve full optimisation you'd likely need to start from the assembler output of a compiler anyway.


Why does "2xAES-256" provide "99.99%" security strength whereas "1xAES-128" provides "40%"? I recently was "directed" to FlipsCloud, a company selling security solutions (as far as I can tell).

In particular I've investigated their page and found a page on their "encryption features".

This page claims a few things (some of which deserve their own questions).

As for this question, I'm asking:

How can one construct the "security strengths" given on the page?

For everyone not wanting to visit this page, he's the chart in question in text form:

  Security Strength of Encryption Technologies
  2x AES-256 bit(CBC) 99.99%
  1x AES-256 bit(CBC) 50%
  AES-128 bit 40%
  RC4-128 bit 30%
  RC4-40 bit 10%

It's meaningless nonsense. I would be inclined to avoid spending any money with these people. If you scroll down on this page, you'll find a table labelled key size vs. time to crack, according to which their $2 \times 256$ bit encryption takes $3.31 \times 10^{112}$ years to crack, making it (apparently) superior to ordinary $256$-bit encryption (which can be cracked after a paltry $3.31 \times 10^{56}$ years).

I think you'll find that the values you cited are based on the exponents of these numbers (hence $10^{112} \rightarrow 100\%$, but $10^{56} \rightarrow 50\%$).

However, they don't explain why you should be concerned about your data remaining secure after the heat death of the universe.

Seriously, don't give your money to these clowns.


Difference between Asmuth-Bloom and Shamir's Secret Sharing Both Asmuth and Shamir are threshold based secret sharing schemes and perfectly secure.

In which point of view  Asmuth bloom secret sharing scheme is better than Shamir secret sharing scheme.

Could you please give me anyone reason Asmuth bloom secret sharing scheme is better than Shamir secret sharing scheme.

As has been commented, Asmuth-Bloom is does not always give a perfect scheme.  The original paper gives a condition on the primes to maximise "sharpness", which is what they call their measure of closeness to perfection.

A recent paper at Asiacrypt 2018 gives fairly detailed analysis of the differences, and they also construct a new scheme using similar techniques.  In the introduction they remark:

  In  a  word,  Shamir’s  scheme  is  ideal  and  easy  to  construct
  while  Asmuth- Bloom’s  scheme  is  not  ideal,  hard  to  construct
  but  more  natural  and  neat  in constructing  weighted  SS  scheme.

So while Shamir's scheme is very good for threshold schemes by most metrics, if one wants to construct secret sharing schemes for weighted threshold access structures then Asmuth-Bloom, these authors claim, has a more "natural" generalisation.  (Weighted threshold schemes are defined in the same paper, and are basically a way of fine-tuning the qualified sets of the access structure.)


Nonces being used in SSL and MAC to prevent replay attacks I'm a bit confused in the way nonces are used in these processes to prevent replay attacks.
Heres How I think it works during SSL:

Nonces are exchanged during stage one of the handshake protocol. Nonces of the other party will be different so the keys will be different. The random numbers are used to create symmetric keys using the master_secret. Even if Eve could use the same random numbers as in the previous connection, the server will most likely not, therefore the keys will be different in the attempted replay connection.

Is that correct? I'm a bit confused how they work in MAC.

Well, you have it right in how nonces are used to make sure that the keys in different SSL sessions; this effectively prevents someone from taking an SSL record from one session, and injecting it into another -- because the keys aren't the same, it won't pass the integrity tests.

However, that's not the only place we care about replay attacks; we can also be concerned about someone taking an SSL record from one session, and replaying it latter in that same session.  Because the keys are the same, we can't use the above logic.

So, what SSL transmitter does when it computes the MAC for a record is logically prepend the current byte count; that is, the number of bytes that have passed through this SSL connection so far.  This byte count is not sent over the wire, but it is implied.  When the receiver gets the record, it also logically prepends its current byte count (which should match the transmitter's); and so it should compute the same MAC.  After processing the record, both the transmitter and the receiver updates its current byte count (based on how long the record was).

Now, if someone should replay that record, the receiver would then logically prepend its current byte count (which would not match what the transmitter prepended when it originally generated the record); because that count is different, the receiver would generate a different MAC, and so the record would be rejected.

That gives you the answer, I want to close with one clarification; you mentioned SSL; well, the current version of the protocol is known as TLS.  There are several versions (TLS 1.0, 1.1 and 1.2); TLS 1.2 handles the byte count slightly differently; however it does the same job.  There's also something known as DTLS; for that protocol, the count (which is a count of records, and not bytes) is explicitly sent within the record.


AES encryption algorithm (MIX COLUMNS) During the mix columns step, getting the first element value is done using the equation

(1st*02)+(2nd*03)+(3rd*01)+(4th*01),

where *02 means shifting 1 bit to the right then XORing with 1b if the high bit for the 1st element is set.

What does (the first high bit of 'b4' for example) "is set" means?
Does the process change if it isn't set ?

Your confusion comes from learning the algorithm from it's implementation side and not from it's mathematical principles. First take a look on this wiki page. On the bottom you see the equations for MixColumns stage of the algorithm:

$$d_0=2b_0 + 3b_1+1b_2+1b_3\\d_1=1b_0 + 2b_1+3b_2+1b_3\\d_2=1b_0 + 1b_1+2b_2+3b_3\\d_3=3b_0 + 1b_1+1b_2+2b_3$$

Looks simple, but it's not. We are in Galois finite field so the "addition"
and "subtraction" are actually the same operation known as XOR and multiplication is very complicated and hard to reverse. Your question is actually about one of the "shortcuts" that can be done when implementing the Galois finite field multiplication. (Take a look at C# example here)

We can split the Galois multiplication into two steps.

First we take two values written in binary
$$0x53 \cdot 0xCA = 01010011b \cdot 11001010b$$
and we multiply them the same way as we would multiply two polynomials, keeping in mind that addition here is a XOR operation.
$$ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x)\\=\\x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x$$
and we convert it back to binary
$$11111101111110b$$

Then we take the result of the previous step and run it through a particular modulo operation. For Galois field we run modulo $x^8 + x^4 + x^3 + x + 1$ which can be written in binary form as $100011011b$ and in hexadecimal as $0x11B$

Smart heads thought about it and they actually found a way of doing both operations at the same time since modulo is pretty much a looped subtraction (in Galois field subtraction is the same XOR operation as addition)

That's why after applying that "shortcut" first we test if the most significant bit is equal to 1 (which is also called by some programmers that "the bit is set") and then we subtract (XOR) that $0x11B$. The value $0x11B$ is using 9 bits ($100011011b$) and when applying this shortcut we have just 8 bits available so we actually subtract (XOR) $0x1B$ ($00011011b$) When the most significant bit is equal to 0 (it's not set) the value is lower than $x^8 + x^4 + x^3 + x + 1$ and there is no need for subtraction (XOR).


AES-128/CTR/NoPadding HMAC vs Signature Is there a semantic difference between tagging AES_128/CTR/NoPadding ciphertext with a MAC (HmacSHA256) or Digital Signature (SHA256withRSA) when attempting to verify that the ciphertext has not been changed?
+-------------+
| Cipher Text |
+-------------+
| MAC         |
+-------------+

VS
+-------------+
| Cipher Text |
+-------------+
| Signature   |
+-------------+

Yes, there is an important one; The Non-Reputation;

Non-repudiation refers to a situation where a statement's author cannot successfully dispute its authorship or the validity of an associated contract

The HMAC key is a symmetric key therefore there is no non-repudiation. Both sides can not claim that the other side sends them the message $m$. I.e. They both can forge messages and claim that the other side sent them.
In the RSA case, the signer uses their private key and the receiver verifies it with the singer's public key. Therefore, the sender can not refute the message and this can be used as proof in the courts. This is the digital version of the physical signatures, signing a paper.
In other words, both have integrity and authentication however only public-keys have Non-Repudiation. HMAC (it is a MAC) protects against message forgery against an attacker who doesn't have the key. Public key protects against message forgery against all except the owner.

HMAC (MACs)
RSA signature (PKCS signature)

Integrity
Yes
yes

Authentication
Yes
Yes

Non-Repuditiation
No
Yes


Authentication protocols for authenticating devices to a server The requirement is to authenticate 1000s of devices to a server when the devices try to contact the server. The problem I face is that all authentication protocols require some kind of shared secret between the devices and the server. And for devices to know this shared secret, some reliable user has to manually enter the shared secret into the device. This manual step is undesirable. The goal is to have the devices start contacting and authenticate with the server with as little manual intervention as possible.

To elaborate a bit, two options I could think of are:

Inject a shared secret that only the server can the generate and verify(eg: a digital signature of a random string by the server) into the devices. The server and device use some standard authentication protocol using this shared secret.  But for bootstrapping this setup, a shared secret needs to be injected for each device manually by an user. I am wondering if there is a way to avoid this step.
The device and server agree on some obscure algorithm. The device would apply this obscure algorithm on some common entity that both the device and server know (like the Serial Number) and send to the server. The server will also apply the same algorithm and verify that it could generate the same secret. Here the shared secret is the algorithm. Although this option doesn't require someone to manually enter a shared secret, this option doesn't sound secure or convincing to me.

In general, are there standard protocols that solve this problem?

"The problem I face is that all authentication protocols require

some kind of shared secret between the devices and the server."

Similarly, the problem I face is that $\:1 = 0 \;\;$.

Since your post includes "(eg: a digital signature of a random string by the server)", I will assume

that the server has a signature key-pair and the devices alrady know that pair's verification key.

To start, the device generates a signature key-pair $\:\langle vk_{\hspace{.02 in}d}\hspace{.02 in},sk_{\hspace{.02 in}d}\rangle\:$, $\;$ and sends $vk_{\hspace{.02 in}d}$ to the server.

When it receives a value $vk_{\hspace{.02 in}d}$, the server generates a random value $\:\operatorname{token}\:$, $\:$ sends that along with

a signature on the pair $\:\langle vk_{\hspace{.02 in}d}\hspace{.03 in},\operatorname{token}\rangle\:$ to the device, and stores $\:\langle \text{current_time}\hspace{.02 in},\hspace{-0.02 in}\text{token}\hspace{.02 in},\hspace{-0.02 in}vk_{\hspace{.02 in}d}\rangle\:\:$.

The device tests the signature. $\:$ If the signature verification algorithm accepts, then

the device displays $\:\operatorname{token}\:$ and the user manually authenticates that value to the server.

When a value is manually authenticated to the server, it deletes all triples whose left entry is too old, where "too old" depends on how many triples there are, and for each remaining

triple whose middle entry was just manually authenticated, the server stores $\langle vk_{\hspace{.02 in}d}\hspace{.02 in},\hspace{-0.02 in}\text{context_from_the_manual_authentication}\rangle\:$ and then

deletes that triple and accepts the device as authenticated.

The server also deletes the oldest triple(s) whenever the list of

triples gets too long or the left entry in those triples is way too old.

Subsequently, messages from the device to the server can be signed with $sk_{\hspace{.02 in}d}$ and verified with $\hspace{.01 in}vk_{\hspace{.02 in}d}\hspace{.02 in}$.


Calculating the inverse modularity of the determinant for Hill cipher I'm trying to decrypt a message encrypted with Hill Cipher, but I don't understand how to find the determinant so it solves the equation $det * 1/det = 1 mod 26$.

The determinant for my key matrix is $62$.

Maybe the impossibility of solving the equation system uniquely was meant to strengthen the cipher. :D If everything was done correctly, there'll be multiple solutions. When you have some idea of how the plaintext may look like, it should be easy to determine it uniquely.

During the computation you have to divide something by 62 modulo 26, which is (as already stated) impossible. However, the nominator will always be even, and for any $a$, finding a solution to

$$62 * x \equiv 2a \pmod{26}$$

is as easy as finding the unique (mod 13) solution to

$$31 * x \equiv a \pmod{13}$$

Just note that for each $x$ also $x' = x+13$ solves the original equation.


Basic explanation of Elliptic Curve Cryptography? I have been studying Elliptic Curve Cryptography as part of a course based on the book Cryptography and Network Security. The text for provides an excellent theoretical definition of the algorithm but I'm having a hard time understanding all of the theory involved in ECC.

I'm looking for an explanation suitable for someone who has studied at undergraduate level in computer science. Can anyone explain how elliptic curve cryptography works in a simple, straightforward manner?

There are some widely used cryptographic algorithms which need a finite, cyclic group (a finite set of element with a composition law which fulfils a few characteristics), e.g. DSA or Diffie-Hellman. The group must have the following characteristics:

Group elements must be representable with relatively little memory.
The group size must be known and be a prime number (or a multiple of a known prime number) of appropriate size (at least 160 bits for the traditional security level of "80-bit security").
The group law must be easy to compute.
It shall be hard (i.e. computationally infeasible, up to at least the targeted security level) to solve discrete logarithm in the group.

DSA, DH, ElGamal... were primarily defined in the group of non-zero integers modulo a big prime p, with modular multiplication as group law. The characteristics we look for are reached as long as p is large enough, e.g. at least 1024 bits (that's the minimal size for discrete logarithm to be hard in such a group).

Elliptic curve are another kind of group, appropriate for group-based cryptographic algorithm. An elliptic curve is defined with:

A finite field, usually consisting in integers modulo some prime p (there are also other fields which can be used).
A curve equation, usually $y^2 = x^3 + ax +b$, where $a$ and $b$ are constant values from the finite field.

The curve is the set of pairs of values $(x, y)$ which match the equation, along with a conventional extra element called "the point at infinity". Since elliptic curves initially come from a graphical representations (when the field consists in the real numbers $\mathbb{R}$), the curve elements are called "points" and the two values $x$ and $y$ are their "coordinates".

Then we define a group law, called point addition and denoted with a "$+$" sign. The definition looks quite artifical, with all the business about tracing a line and computing the intersection of that line with the curve; but the bottom-line is that it has the characteristics required for a group law, and it is easily computable (there are several methods; as a rough approximation, it costs about 10 multiplications in the base field). The curve order (the number of points on the curve) is close to $p$ (the size of the finite field): the curve order is equal to $p+1-t$ for some integer $t$ such that $|t| \leq 2\sqrt{p}$.

Compared to the traditional multiplicative group modulo a big prime, elliptic curve variants of cryptographic algorithms have the following practical features:

They are small and fast. There is no known efficient discrete-logarithm solving algorithm for elliptic curves, beyond the generic algorithms which work on every group. So we get appropriate security as soon as $p$ is close to 160 bits. Computing the group law costs ten field operations, but on a field which is 6 times smaller; since multiplications in a finite field have quadratic cost, we end up with an appreciable speedup.
Creating a new curve is uneasy. Generating a new big prime is a matter of
a fraction of a second with a basic PC, but making a new curve is much more expensive (the hard part is figuring out the curve order). Since there is no security issue in using the same group for several distinct key pairs, it is customary, with elliptic curves, to rely on a handful of standard curves which have been created such that their order is appropriate (a big prime value or a multiple of a big enough prime value); see FIPS 186-3. The implementations are thus specialized and optimized for these particular curves, which again considerably speeds things up.
Elliptic curves can be used to factor integers. Lenstra's elliptic curve factorization method can find some factors in big integers with a devious use of elliptic curves. This is not the best known factorization algorithm, except when it comes to finding medium-sized factors in a big non-prime integer.
Some elliptic curves allow for pairings. A pairing is a bilinear operation which can link elements from two groups into elements of a third group. A pairing for cryptography requires all three groups to be "appropriate" (in particular with a hard-to-solve discrete logarithm). Pairings are an active research subject because they can be used to implement protocols with three participants (e.g. in electronic cash systems, with the buyer, the vendor and the bank, all mathematically involved in the system). The only known practical pairings for cryptography use some special elliptic curves.

Elliptic curves are usually said to be the next generation of cryptographic algorithms, in order to replace RSA. Performance of EC computations is the main interest of these algorithms, especially on small embedded systems such as smartcards (in particular Koblitz curves over binary fields); the biggest remaining issue is that public-key operations with group-based algorithms are a bit slow (RSA signature verification or asymmetric encryption, as opposed to signature generation and asymmetric decryption, respectively, is extremely fast, whereas analogous operations in the group-based algorithms are just fast). Also, involved mathematics are a bit harder than with RSA, and there have been patents, so implementers are a bit wary. Yet elliptic curves become more and more common.


Example of partial homomorphic encryption over $\mathbb{F}_{2^k}$? I'm looking for a partial additive homomorphic encryption over $\mathbb{F}_{2^k}$.

I know that, I can take an additive homomorphic encryption over $\mathbb{F}_2$ and just concatenate each bit that we encrypted.
(as suggested at :Additive homomorphic encryption over small fields)

But it seems very inefficiently, when  $k$ is not a constant.

All the other encryption schemes that I saw work over $Z_{pq}^*$ and some variants.

Thanks.

I think you are making a classical mistake: $\mathbb{Z}_{2^k}$ is not $\mathbb{F}_{2^k}$. Concatenating $k$ ciphertexts homomorphic over $\mathbb{Z}_{2}$ gives an encryption scheme homomorphic over $\mathbb{Z}_{2}^k \approx \mathbb{F}_{2^k}$, but this is not $\mathbb{Z}_{2^k}$ - intuitively, $\mathbb{Z}_{a} \times \mathbb{Z}_{b} \approx \mathbb{Z}_{ab}$ only when $a$ and $b$ are coprime.

So, if what you want is really an additively homomorphic encryption scheme over $\mathbb{Z}_{2^k}$, there is one: this paper describes an extension of the Goldwasser-Micali encryption scheme which does exactly this.

If, however, you need an encryption scheme over $\mathbb{F}_{2^k}$, then there is not really any alternatives to concatenating encryptions over $\mathbb{Z}_{2}$, except using an appropriate scheme based on LWE - but I'm not sure whether this would improve a lot over the "naive" solution, I do not have a good knowledge of lattice-based cryptography.


Can BPS be used to encrypt a single integer, and restrict the output to a certain range? As per specifications document,

"We have the natural restriction that at least two characters must be ciphered, i.e. $b \geq 2$"

where each character is represented by an integer of certain cardinality.  So basically a $2$ integer array is the minimum.

However say I want to encrypt a single input integer but restrict it to a certain range.  For example say the cardinality of the integer was $2000$ (so the range of possible values from $0 - 1999$).

Can this be done using BPS?  (i.e. Would it be acceptable to simply input an integer array of size one to the algorithm with the cardinality as the range I want?)

I am trying to encrypt a year, but in a way that does not result in a year greater than current year.

This can't be done in a straightforward way with just BPS, since the straightforward way will result in a year greater than the current one for roughly 80% of ciphertexts (since 9999 is the biggest four-digit ciphertext possible). However, using what's called a "rank-then-encipher" scheme, you can specify an input and output format using a regex, then build an FPE scheme on just the strings matching that regex. See this site for details.

EDIT: Also, I don't know BPS that well but I think the "integer of a certain cardinality" can just be a base-10 digit, so you can encrypt a four-digit year as four characters.


Which AES mode when using Poly1305-AES I am reading DJ Bernstein's paper on the Poly1305-AES mac (https://cr.yp.to/mac/poly1305-20050329.pdf). I understand that AES is needed to provide the array s. In its paper on page 5 we can read:

reads AESk(n) from s[0], s[1], . . . , s[15]

I understand that n is a nonce and k is the secret key. What I am not sure about is which AES mode is used (ECB, CTR, GCM...) ? Is the nonce the message being passed to AES or is it a real nonce and thus we need to pass another message to AES ?
I am quite surprised that I cannot find any details about the AES mode in its paper. Is it because there is a default plain AES mode ?
FYI, I am using the mbed_tls crypto library, but I don't find any relevant example in their documentation.

Yes, AES is just used as a 128 bit / 16 byte block cipher in this scheme. The paper specifies:

Poly1305-AES feeds each nonce $n$ through $AES_k$ to obtain the 16-byte string $AES_k(n)$.

There is no mention of AES without this key $k$ or nonce $n$. So, as far as AES - the block cipher - is concerned, $k$ is the key and the nonce $n$ is the data / message.
The reason that no mode-of-operation such as ECB / CBC is mentioned is that the specification uses the block cipher itself, without any mode. If you only have access to AES-ECB then you should use ECB without padding (or, if padding is always performed, just taking the first 16 bytes after feeding the nonce). You can use CBC with an IV using 16 zero valued bytes in a similar manner. Or you could use CTR with the nonce $n$ and an all zero plaintext of 16 bytes - probably makes most sense as CTR mode won't pad.

FYI the reason that you don't find an example in a TLS library is possibly that they use ChaCha20/Poly1305 where the ChaCha20 cipher is used instead of AES
From RFC 7905 section 1:

The variant of ChaCha used in this document has 20 rounds, a 96-bit
nonce, and a 256-bit key; it is referred to as "ChaCha20".  This is
the conservative variant (with respect to security) of the ChaCha
family and is described in [RFC7539].

From RFC 7539 section 2.8.1:
 otk = poly1305_key_gen(key, nonce)

...
 poly1305_key_gen(key,nonce):
     counter = 0
     block = chacha20_block(key,counter,nonce)
     return block[0..31]
     end

So here chacha20_block is used instead of AES - they did say it was nothing special right? Note that the encryption then helpfully starts with counter 1 instead of zero, so it is a simple continuation of ChaCha20...


How would I go about breaking Playfair cipher with the alphabet and the encrypted message? I was wondering how I could crack a Playfair cipher with only the alphabet and the ciphered message. Ive tried looking for tools online, but still no luck.

If by alphabet you just mean that you know the letters A-Z are being used apart from identifying I with J, the best place to start is by looking for common digraphs (pairs of letters). There are lists of the most common digraphs in English and if you have a long enough message you should be able to identify likely candidates. Indeed, if your ciphertext is long enough just digraph frequency will be enough.
For shorter ciphertexts, try to chain common digraphs together in the text to form words and guess less common digraphs. For Playfair note that recovering a digraph also gives you the reverse. Also specifically to Playfair, look for plaintext digraphs that contain the same letter (e.g. digraphs of the form E or E) the ciphertexts corresponding to these digraphs should give you strong clues to letters in the Playfair square that are in the same row and column as E. For example, if you see the digraph HE encoded as BX then there's a good chance X is in the same row as E and B is in the same row as B is in the same column.
Some good news is that there are many different Playfair squares that lead to the same encryption method.
Depending how much ciphertext you have, the rest is less science and more art. Don't be afraid to make wild leaps or assumptions, but equally don't be afraid to throw away large amounts of work and start again from scratch. A fuller treatment for breaking Playfair can be found in Chapter XXI of the classic text Cryptanalysis by Helen Fouche Gaines.


How does a chosen ciphertext attack work, with a simple example? Can someone please explain - using a simple example - how a chosen ciphertext attack works?

In a chosen-ciphertext attack, the attacker is assumed to have a way to trick someone who knows the secret key into decrypting arbitrary message blocks and tell him the result. The attacker can choose some arbitrary nonsense as an "encrypted message" and ask to see the (usually) different nonsense it decrypts to, and he can do this a number of times.

Having this capability obviously already allows the attacker to read an intercepted message, since he can just ask to have it decrypted. But in this attack his goal is more ambitious than that: he wants to deduce what the secret key is, such that he can encrypt messages himself, and also keep decrypting after his access to having things decrypted for him vanishes.

The attack is successful if if an attacker has a significant chance of being able to deduce the key after having "relatively few" blocks decrypted and without doing so much work himself that he could just as well have brute-forced it.

The term "chosen-ciphertext attack" does not in itself say anything about how the attacker chooses the nonsense blocks he asks to have decrypted, or what kind of computations he does in order to recover the key from the responses.

As a concrete example, suppose General A is sending messages to General B using a Vigenère cipher with an unknown key. The enemy is somehow able to intercept a message and replace it with some completely random letters of his own choosing, say NLLCJOVFXXHMLY. General B decrypts this and gets AKRUWNBXKWNEYX which is nonsense. Bemused, and not thinking this nonsense is worth keeping secret, he picks up a non-secure phone and calls General A: "What the hell do you mean with AKRUWNBXKWNEYX? Did they change the key without telling me?" But the enemy is eavesdropping on the line and now knows that NLLCJOVFXXHMLY decrypts to AKRUWNBXKWNEYX. He can then subtract the two sets of nonsense to get MATHMATHMATHMA, and now he knows the key.

(In this example, getting a single message decrypted was enough for the attacker to learn the key. In general one also considers attacks where the attacker needs to query for multiple messages, perhaps using the response to one somehow to construct the next one).


Fiat–Shamir: why do r and s have to be smaller than n? I have a question regarding the Fiat–Shamir identification protocol. In this source (pdf) for example it says on pages 9 and 10 that the random commitment $r$ and the private key $s$ have to be smaller than $n$ (the RSA-like Modulus). I am wondering why this has to be.

The verification works even if $r$ and $s$ are greater than $n$. Also, if $r$ is smaller than $n$, an observer could calculate $r$, using the equation $y=r*s^e$ mod $n$. If $e=0$, this is equal to $y=r$ mod $n$, and since $r<n$, this is the same as $y=r$, so if somebody gets to know $y$, he would also know $r$. I thought that somebody was not supposed to be able to get information out of the knowledge of $y$ or $x$.

Is there something I am getting wrong here?

Because we are working modulo $n$.  There's not much more to say.  There's no reason why any honest user would ever want to use a larger value.  You might want to review modular arithmetic and its use in cryptography.


How secure is AES-256, but with an effective key length of 56-bits? I need to encrypt a few drives using Kaspersky Total Security.  I however noted something peculiar, Kaspersky's description of their cipher is:

  Data will be protected using AES-256 encryption with a 56-bit effective key length?

Does this mean that they are using the same key generator that AES-256 uses but their key in reality isn't 256-bits long, instead 56-bits?

It would appear that this is as a consequence of the Wassenaar Arrangement (more detailed explanation). Basically, because cryptography falls under certain laws regarding munitions and arms trafficking there are restrictions on the strength of the cryptography you are allowed to sell (if the product is not a mass market product). It would appear that the limit on key size for symmetric algorithms is 56 bits. The exact verbage on the restriction is is:

  A "symmetric algorithm" employing a key length in excess of 56 bit

Source: Section 5. A. 2. a. 1. a (Page 87) of this document.

What I assume they do is something similar to zero pad a 56 bit key of random bits to a length of 256 bits so that the key is the correct size but the export restrictions are still met.

Edit: As otus points out, I neglected to mention that 56 bits is not a whole lot in regard to security. It's so small that EFF cracked a 56 bit DES key via brute force in 1998 with roughly $250,000 of custom hardware.


Discrete logarithm with unknown base I am trying to solve the well-known $g^x = y \pmod{N}$
but in this case only $g$ is unknown. What I know :

$x$ is a prime : $2^{16} + 1$
$y$ is known
$N$ is a large number that I managed to factor to two "less large" primes (like 38 figures each)

I found various methods to deal with discrete logarithm but it seems they are always intended to solve $x$. Maybe the answer is not that hard to find but this is a bit beyond my mathematical skill at this point :) Any help is appreciated.

This is actually an RSA decryption problem, not a discrete log problem.

In this case, $$g = y^{x^{-1} \bmod \phi(N)} \pmod N$$

If you have the factorization $N = pq$, where $p, q$ are both prime, this is essentially:

$$g = y^{x^{-1} \bmod (p-1)(q-1)} \bmod N$$

You can compute $x^{-1} \bmod (p-1)(q-1)$ (or, what would work equally well, $x^{-1} \bmod \text{lcm}((p-1)(q-1))$), using the Extended Euclidean Algorithm for computing multiplicative inverses.