Memory hard password based key derivation functions? How are memory hard functions designed for the purpose of password based key derivation? To protect against a brute force attack from a parallel machine.

What design could work well with Skein? The Skein paper (pdf) has a time hard PBKDF (basically hashing the password repeat very many times) but not a memory hard one.

Memory hard functions are designed so that the internal calculations rely on a relatively large state. The functions should not have shortcuts that allow an adversary to calculate the result without using of the state at once (at least not without incurring a very high overhead). That way it is impossible for fast hardware to be developed that does not require large amounts of memory.

There isn't one specific design for memory hard functions within PBKDF's. You can have a look at various existing designs (scrypt, Argon2) of memory hard PBKDF's for examples of memory hard functions.

Lets define 3 different methods, going from low level to high level:

Catena was mentioned specifically in the comments as it simply requires a generic hash method to function. If any secure hash function can be used then Skein should be a secure option.
KMAC by now has been defined as a secure HMAC replacement by NIST. So you could use scrypt with PBKDF2 where the HMAC is replaced by KMAC.
scrypt uses PBKDF2 as underlying CPU hard function. Simply replace the PBKDF2 function within scrypt with another CPU hard function such as Skein's PBKDF.

These are hints, providing the security proof is left to the reader.

Currently, a single GPU cluster can break almost 1000 billions ($10^{10}$) passwords/hashes per seconds, imagine what a state attacker or hackers team can do with hardware ASICs, supercomputers or botnets networks. Basically, a password of 16-17 characters ($2^{80}$ entropy) can be broken within hours or days with brute force, and we are not even in quantum age yet.

Things are going worse because hashes are usually generated on a single CPU, while the world CPUs number is increasing, so the availability for attackers.

There are two explanations for this:

Developers generate passwords hash too fast and without salt, so when the hackers recover the hash databases they can recover passwords by brute force. Or they try to generate hash with low entropy input.
GPUs use a lot of small cores to perform this task, if each core would use a lot of memory for the algorithm they will run out of memory soon.

The weak point in local encryption process is not the algorithm usually, but the hash key generated from password, if a person can remember 15 characters, then the attacker rather tries all variants of this low entropy input instead of breaking the 256bits random key that encrypts data. So if the encryption key is generated slow, there are less chances of a brute force attack of the system.

There are several known such stretching functions, like scrypt, bellow you can find a simple sample of how such a function can be made to avoid massive parallel computing attacks.

via: gist.github.com/anonymous/c0edbaf71e0be3d07db3 (Created Oct 22, 2015)

// HKF - Memory Hard Key Derivation Function v 1.4
// Adrian Pirvu - October 14, 2015
//
// A memory hard key derivation function without useless overhead
// 3.4s with 1G memory and 1 million rounds on first generation i7 CPU
// INPUT: password - up to 256 bytes; salt - no limitation;  megabytes: memory you intend to use; rounds: memory pickup rounds;
// OUTPUT: stretched key hash (current 256 bytes) - you can either simple hash to less this value or use part of it.
// Arc4 used as a one way random generator, but any stream cipher can be used
// No need to generate memory diffusion like others functions, I only make sure that the final hash that I get is irreversible and not biased
// No side attacks considered, if the attacker has access to your RAM then an activity tracking RAT already took your password or screenshots of your mouse clicks
// Tags: fast memory hard function, password hashing, memory hard key stretching, memory hard key strengthening, scrypt, bcrypt, sequential memory hard function
// Looking for feedback and some possible GPUs cluster tests. If anyone is interested in further development or a possible public project, please let me know.

#include "stdafx.h"
//#include <string.h>
//#include <time.h>
//#include <windows.h>

extern "C"
{

    unsigned int i = 0, j = 0, m = 0, z = 0;
    unsigned char s[256], k[256];

    void RngInit(unsigned char* key, int keyLength, unsigned char* salt, int saltLength);
    unsigned char RngNextByte();
    unsigned int RngNextInt();

    //unsigned int TEST_MEGABYTES = 1024;
    //unsigned int TEST_ROUNDS = 1000000;

    // return a hashable strengthen key of desired length from password and salt
    __declspec(dllexport) void GetHashKey(unsigned char* password, int passwordLength, unsigned char* salt, int saltLength, int megabytes, int rounds, unsigned char* output)
    {
        // dinamically allocates memory 4 * 1024 * megabytes
        int ROWS = 4 * 1024 * megabytes; // each row is 256 bytes (256 * 4 * 1024 = 1k * 1024 = 1M)
        int COLUMNS = 64; // * 4 bytes per int = 256 bytes
        unsigned int* box = new unsigned int[ROWS * COLUMNS];
        unsigned int tmp = 0;

        // init the random engine and get a temporary key
        RngInit(password, passwordLength, salt, saltLength);
        unsigned int key[64];
        for (int col = 0; col < 64; col++)
            key[col] = RngNextInt();

        // reinit the engine for safety and get a start key and the session salt
        RngInit((unsigned char*) key, 256, salt, saltLength);
        unsigned int pepper[64];
        for (int col = 0; col < 64; col++)
        {
            key[col] = RngNextInt();
            pepper[col] = RngNextInt();
            box[col] = key[col]; // first row is the start key
        }

        // fills the memory fast, with a bit of diffusion (we really don't need much)
        unsigned int random = key[34] * key[56] + key[62];
        for (int row = 1; row < ROWS; row++)
        {
            // breaks the row random and switch parts
            int index = box[(row - 1) * COLUMNS + 56] & 0x000000FF;
            memcpy((unsigned char*) &box[row * COLUMNS] + index, (unsigned char*) &box [(row - 1) * COLUMNS], 256 - index);
            memcpy((unsigned char*) &box[row * COLUMNS], (unsigned char*) &box [(row - 1) * COLUMNS] + 256 - index, index);

            // xor each number with the session salt and pseudorandom number
            for (int col = 0; col < 64; col++)
            {
                random = (2147483629 * random + 2147483587); // maybe something with longer period?
                box[row * COLUMNS + col] = (box[row * COLUMNS + col] + pepper[col]) ^ random;
            }
        }

        // start with the last row to avoid precalculations and algo redesign
        for (int col = 0; col < 64; col++)
            key[col] = box[(ROWS - 1) * COLUMNS + col];

        //clock_t start = clock();

        // intensively get random integers from memory and mix them into the pseudorandom key
        for (int rnd = 0; rnd < rounds; rnd++)
            for (int col = 0; col < 64; col++)
            {
                i = (i + 1) % 256;
                j = (j + s[i]) % 256;
                tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
                unsigned int sum1 = (s[i] + s[j]);
                unsigned int column = sum1 % 64;
                unsigned int row = (key[col] + sum1 + i + j) % ROWS;
                sum1 = sum1 % 256;

                i = (i + 1) % 256;
                j = (j + s[i]) % 256;
                tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
                unsigned int sum2 = (s[i] + s[j]) % 256;

                unsigned int total = (sum1 << (16 + (sum2 % 8))) + (sum2 << (sum1 % 8));
                key[col] = (key[col] + total) ^ (box [row * COLUMNS + column] + pepper[col]);
                //key[col] += RngNextInt() ^ (box [row * COLUMNS + column] + key[col]);
            }

        //clock_t diff = clock() - start;
        //char message[1000];
        //float seconds = ((float) diff) / CLOCKS_PER_SEC;
        //sprintf(message, "Seconds: %0.3f\r\n\0", seconds);
        //OutputDebugStringA(message);

        // build output
        for (int col = 0; col < 256; col++)
            output[col] = RngNextByte() ^ ((unsigned char*) key)[col];

        // cleanup
        for (int col = 0; col < COLUMNS; col++)
        {
            box[(ROWS - 1) * COLUMNS + col] ^= box[(ROWS - 1)* COLUMNS + col];
            key[col] ^= key[col];
            pepper[col] ^= pepper[col];
        }
        ROWS = 0;
        COLUMNS = 0;

        // should overwrite memory
        delete[] box;
    }

    // init RNG engine
    void RngInit(unsigned char* key, int keyLength, unsigned char* salt, int saltLength)
    {
        unsigned char tmp = 0;

        i = j = 0;
        for (i = 0; i < 256; i++)
        {
            s[i] = i;
            k[i] = key[i % keyLength];
        }

        j = 0;
        for (i = 0; i < 256; i++)
        {
            j = (j + s[i] + k[i]) % 256;
            tmp = s[i];
            s[i] = s[j];
            s[j] = tmp ;
        }

        // discard start to bypass key scheduler flaws, also mix the salt
        i = j = m = z = 0;
        for (int idx = 0; idx < 3000 + k[251] + saltLength; idx++)
        {
            i = (i + 1) % 256;
            if (saltLength > 0)
                j = (m + s[(j + s[i]) % 256] + salt[idx % saltLength]) % 256;
            else
                j = (m + s[(j + s[i]) % 256]) % 256;
            m = (m + i + s[j]) % 256;
            tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            z = s[(j + s[(i + s[(z + m) % 256]) % 256]) % 256];
        }
    }

    // obtain a random byte from Rng engine
    unsigned char RngNextByte()
    {
        unsigned char tmp = 0;

        // use RC4, is faster
        i = (i + 1) % 256;
        j = (j + s[i]) % 256;
        tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        return (s[i] + s[j]) % 256;

        //i = (i + 1) % 256;
        //j = (m + s[(j + s[i]) % 256]) % 256;
        //m = (m + i + s[j]) % 256;
        //tmp = s[i];
        //s[i] = s[j];
        //s[j] = tmp;
        //z = s[(j + s[(i + s[(z + m) % 256]) % 256]) % 256];
        //return z;
    }

    // obtain a random int from Rng engine
    unsigned int RngNextInt()
    {
        unsigned char tmp = 0;
        unsigned char output[4];
        for (int idx = 0; idx < sizeof(int); idx++)
            output[idx] = RngNextByte();

        return *((unsigned int*) output);
    }

    //// main function, for test purposes
    //int main(int argc, char * argv[])
    //{
    //  const char* password = "monkey";
    //  const char* salt = "superman";
    //
    //  unsigned char output[256];
    //  GetHashKey((unsigned char*) password, strlen(password), (unsigned char*) salt, strlen(salt), TEST_MEGABYTES, TEST_ROUNDS, output);

    //  //FILE* file = fopen("d:\\key.dat", "wb");
    //  //fwrite((void*) key, 1, 100000000, file);
    //  //fflush(file);
    //  //fclose(file);
    //}

}


Cryptography elements needed for a story Note: following Maarten Bodewes's answer, I edited this post to make it clearer.
I'm writing something partly driven by the need to crack a few encrypted files.
This is what needs to happen in the story:
There are two parties involved that are trying to crack them, party A and party B. Party A has had them for four years, and despite all attempts, they failed. Party B got the files later on and managed to crack them in less than two months of non-stop trying.
Party A has available state-of the-art tech, but party B are the good guys and this is a sci-fi story, so they have far, far better tech that nobody else has. The details of the technology aren't relevant to the story so I don't need to establish them.
Party B will eventually succeed; still, to keep a modicum of suspense up, it must still be possible for them to fail. By this I don't mean that something throws a spanner in their works; I mean that their decryption attempt, however more advanced than party B's, isn't guaranteed to work. In other words, party B can't just sit and wait until whatever they're doing is done knowing that at that point they will have the decrypted file.
This is what I need:

An algorithm such that, if you encrypt a file with it using a high-entropy password, is beyond any brute-force attempts using known methods and tech. (This is why party A fails.) I understand that AES-256 might be what I'm looking for.
An approach that will allow party B to succeed nonetheless. The fact that party B has much faster computers available than anyone on Earth is central to the story so you can assume that. However, if brute-forcing these files required ridiculous amounts of energy or other very unrealistic things, I'm not prepared to claim party B has any of that. Other approaches or situations that would give party B an edge—such knowing what algorithm was used, being able to guess details about the password, or knowing about possible key files—are certainly options I would consider. If quantum computers could plausibly break AES, that's another option I would consider because it's not too far-fetched for party B to have them. I just don't know if QC could actually do that.

Though quantum computers fit the requirements, I'm not sure they are the best option. A general purpose quantum computer capable of attacking modern encryption (RSA, AES) would have serious ramifications on society. It's not only applicable to this one cipher you are breaking.
Does it have to be the superior computing resources which gives the good guys the edge? Because I can think of several plausible storylines where the edge comes from a bright idea.
Option 1: Information about the passphrase.
If the good guys learn something about how the passphrase used to derive the encryption key was chosen they could easily reduce the search space time from millennia to months. For example the passwords are always lines from a book where some of the words are replaced with the first letter. Or something else. One way to learn such a pattern is they crack some other password picked by the same person which was encrypted with weaker encryption. The hero recognizes the pattern in this other password hypothesizes it may be a common method of selecting passwords and starts a brute force dictionary attack on the reduced space.
Option 2: General Cryptanalytic improvement.
Our hero is a master cryptographer. And uses an unknown but plausible cryptanalytic attack on AES to greatly improve speed. This attack could have greatly reduced runtime and it could work on only a fraction of the keys. It could be discovered that a sizeable fraction of keys have some undesired property which makes a superior attack possible (which still requires great computational resources) and they are unsure if the key happens to be such a weak key, they are likely to be able to quantify their success probability in advance.
Option 3: Identifying a flaw in how the data was encrypted
Whoever encrypted the data may have messed up. And accidentally left an easier route to attack it. It could be something like applying error correction after compression before encryption (the flaw in GSM). Or something which more directly leads to an attack like keeping a simple hash of the password. The heroes find this flaw and launch a more efficient brute force based on it.
Option 4: Attack the message not the key
Out heroes don't try to crack the encryption at all. They utilize knowledge of message and compression system used. and find what possible messages would result in desired size. Though if it's only size it's only viable if we had a small collection of possible messages and the attack will be quick. There are attacks on voice for example where we use size and timing to decipher words and phrases without breaking the encryption.

To be honest, there doesn't have to be anything clever here.  Simply trying brute force - i.e. try all combinations, on a good cipher will work for the narrative - that's because while it is true that you can't guarantee decryption before trying all keys, it is also true that Party B might win on the first try, or at least an 'early' one.  So B starts later, but has better tech so is catching up, but can't guarantee a win until it comes (suspense as requested).  The only issue with a good cipher is whether either of them would bother wasting their time - because it is unlikely either would succeed.  But they could - and this is fiction.


Why is the vector sampled from Gaussian or Subgaussian distribution in lattice-based cryptography? I have known that the vector is sampled from Gaussian distribution in lattice-based cryptography because the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ approximates to uniform distribution.

It is proved by below lemma.

  For any $s > 0$, $\mathbf{c} \in \mathbb{R}^n$, and lattice $\Lambda(\mathbf{B})$, the statistical distance between $\mathcal{D}_{s,\mathbf{c}} \mod{\mathcal{P}(\mathbf{B})}$ and the uniform distribution over $\mathcal{P}(\mathbf{B})$ is at most $\frac{1}{2} \rho_{1/s}(\Lambda(\mathbf{B})^*\backslash\{\mathbf{0}\})$. In particular, for any $\epsilon >0$ and any $s \geq \eta_{\epsilon}(\mathbf{B})$, the statistical distance is at most $\Delta(\mathcal{D}_{s,\mathbf{c}} \mod{\mathcal{P}(\mathbf{B})},\mathcal{U}(\mathcal{P}(\mathbf{B}))) \leq \epsilon/2$.

But if the vector is sampled from uniform distribution at first, the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ is uniform. So, I thought that Gaussian sampling is not needed for above reason, because Gaussian sampling requires large costs.

Another reason I think is that the smaller vector is preferred because almost lattice problem is about finding short vector and Gaussian variable has higher probability as closer to the center. Is it right?

If my thought is not correct, let me know the reason using Gaussian distribution in lattice-based cryptography.

You can't directly sample uniformly modulo a lattice unless you know what the lattice is. The Gaussian distribution can be sampled independently of knowledge of the lattice. This distinction is important in situations where the lattice is part of a cryptographic secret.


Simply put, what does “perfect secrecy” mean? I would like to ask for a clear (but maybe not so deep) explanation of what the term "perfect secrecy" means.

As far as I have researched and understood, it has to do with probabilities of assuming that a certain variable will be the key for a certain cipher text. And unless I'm confusing some concepts, the one-time pad is the only cipher known to have perfect secrecy, since no amount of resources would be enough to break it.

My notions of probability are kind of weak, which is why I don't understand most documents that speak of it.

Perfect Secrecy (or information-theoretic secure) means that the ciphertext conveys no information about the content of the plaintext. In effect this means that, no matter how much ciphertext you have, it does not convey anything about what the plaintext and key were. It can be proved that any such scheme must use at least as much key material as there is plaintext to encrypt. In terms of probabilities, it means that the probability distribution of the possible plaintexts is independent of the ciphertext.
We contrast this with semantic security, which I define by quoting the seminal 1984 paper of Goldwasser&Micali:

Whatever is efficiently computable about the cleartext given the cyphertext, is also efficiently computable without the cyphertext.

For two examples, I quote my answer to this related question:

When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two communicants, which basically means you have to give it to the other person through a perfectly secure protocol (eg by hand/trusted courier). So, actually it just allows you to have your trusted meeting in advance, rather than at the time of transmitting the secret information.
To illustrate this, consider what happens if one tries to brute force OTP? Since you have allowed an attacker infinite computational resources, he can keep guessing keys and calculating the appropriate plaintext until every key has been tested. Supposing the message was $b$ bits long, this would leave him with $2^b$ possible keys, each of which would generate a unique plaintext, making $2^b$ plaintexts. What is important here is that this means they would have candidate plaintexts corresponding to ever possible bit-string of length $b$. This means, even if you knew the message was "Meet me at the stadium at 2?:15" (where ? is 0,1,2 or 3), you still wouldn't have any idea what the ? was, because the possible plaintexts would contain this string with every possible value of ?.
Most cryptographic methods we use now are computationally secure. There are lots of different ways to do this, and I'll just sketch at a few of them. We might come up with a reduction to a problem conjectured to be hard (eg the Diffie-Hellman Problem or Discrete Log Problem). That is, we prove that "If you can break my cipher, you can solve [hard-problem]", meaning our problem is at least a difficult to solve as [hard-problem]. So, if the problem is indeed hard to solve, so must cracking our encryption be.

Put quite simply: It means it's impossible to tell if and when the message has been cracked or not.

So you can crack the message but you will never know if it is cracked or not.


Why does the prover in an interactive proof run in exponential time with the space of the computation? I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches.

In particular, I've been watching the following YouTube video which talks about interactive proofs as a way of verifying knowledge of a computation. On the slide appearing during time 11:55, it mentions that the prover requires exponential time in the space of the computation. Could anyone explain how this is the case?

I'm also confused as to the statement which says that every deterministic computation has an interactive proof.

I've tried reading the papers below but can't seem to find a clear explanation of these results. Any help would be much appreciated!

References:

  Lund, Carsten, et al. "Algebraic methods for interactive proof
  systems." Journal of the ACM (JACM) 39.4 (1992): 859-868.

  Shamir, Adi. "Ip= pspace." Journal of the ACM (JACM) 39.4 (1992):
  869-877.

The whole point of verifiable computation is to allow the verifier to verify that the computation was performed correctly without performing the computation himself. Since as usual we associate "polynomial-time" with "efficiently computable", if the computation takes poly time there is no point in using verifiable computation, since the verifier can just as well perform the computation himself.

In proof systems in general, if the verifier can determine by himself the truth of the statement in question, there is no need for a prover at all.


Is there any area where AES-CBC cannot be used ? If so, why? I would like to know the domains or specific applications where using AES-CBC is not advised due to any drawbacks like sequential encryption of AES-CBC ?

CBC does not perform authentication

This property makes it less suitable for places where authentication is required, basically any transport protocol. TLS uses CBC, but by default performs authentication over the plain text instead of the ciphertext, which opened up a host of attacks. CBC can be used here, but it is error prone and may require an additional key for calculating a (H)MAC.

CBC is more error prone than other modes of encryption to error oracles, even if padding oracles (see below) are not feasible. See the paper "Error Oracle Attacks on CBC Mode" by Chris J. Mitchell for more information.

CBC doesn't let you pre-calculate a key stream

Pre-calculated key streams let you XOR plaintext with the pre-calculated stream to provide encryption. For instance AES-CTR makes it possible to let you use very low latency encryption for protocols.

CBC doesn't allow you to perform parallel encryption

As each block is depending on the previous block, all the way up to the last block, it is impossible to perform AES using multiple threads at the same time. This is a performance bottleneck which may invalidate AES-CBC on many systems where performance is required (and that do not have implicit parallelism).

CBC doesn't allow you to skip bytes

As each block is depending on the previous block, it is not possible to start encryption in the middle of a stream (decryption is possible though). This means that CBC is less suitable for re-encrypting parts of a file. Nor does this allow you to easily skip frames in e.g. video or audio play back.

CBC requires padding or ciphertext stealing (CTS)

Padding has many issues: it requires additional block encrypts and will require additional space. If CTS is available (it isn't usually) it requires at least one block, although the IV may be used as well if that is send to the other side. Regardless, CBC may have issues where a minimum number of bytes need to be send, or when a minimum number of block encrypts is required.

Besides that, CBC with padding applied may be vulnerable to padding oracle attacks. These may even be present on applications that are protected with a MAC if decryption is performed before authentication is established. This includes all transport protocols.

CBC requires an IV that is unpredictable to an attacker

This may be an issue where no fast random number generator is available and/or where additional block encrypt (to create an encrypted IV) is not feasible or wanted. This may be an issue on embedded platforms. As it is not directly possible to use a counter, CBC cannot be directly used on places where the IV can be derived from some identifier present in the protocol. It is also tricky to use an IV that is smaller than the block size.

CBC ciphertext errors do not propagate much forward nor do they travel backwards

This is not a feature that is requested a lot, but where it is, CBC does not provide it. Instead a mode such as bi-IGE (bi-directional Infinite Garble Extension) must be used.

Single bit errors in the ciphertext may affect up to 129 bits of plaintext

On the other hand, a single bit error in the ciphertext will garble the a complete block + a bit in the next block. This means that CBC is less suitable in places where error correction is calculated over the plaintext. CTR would be more suitable in such situations.

CBC may fail harder if you use a key too long

If you use a key for close to $2^{n/2}$ blocks, you expect a collision which leaks a block's worth of data. In contrast, CTR-based modes fail more gracefully: as long as you don't reuse a counter value, they only lose indistinguishability at that point.

CBC is one of the five confidentiality modes of block cipher. It needs one IV (Initialization Vector). The IV must be same length to the blocksize of the algorithm (e.g. 128bit for AES). The IV is done exclusive-ORed with the first plaintext block P1. The result of the first XOR operation is C1. Next C1 is exclusive-ORed with the second plaintext block P2. And this process goes on till the last plaintext block is processed. So the reason way I'm saying this that CBC is all about giving the plaintext a non-recognizable look. It can be used in DES, TripleDES, AES and other block ciphers. If you want your plaintext to be simple then don't use it. The reason why AES is used is to keep data/file encrypted that is keep it secure and CBC (and the other modes as well) gives a little bit more security to AES.

EDIT:

As from fgrieu's and e-sushi's comment there is one area where AES-CBC mode should not be used that is when part of a large data is needed frequent processing (reading and writing).  If CBC is used then the whole data (starting from the fist block to the needed block) needs to be decrypted first to get the certain part of the data, since each block is depended on the previous cipher block. So choosing a different mode might help in this case.


How to do Hexadecimal multiplication in GF(2^8) I'm trying to do a hexadecimal multiplication in GF(2^8).
Now, I know the technique of shifting left the binary numbers in some cases, for example:

02 * 9E
0000 0010 * 1001 1110

you shift one time the 9E part, which results in the following:
0011 1100
and since it went above x^8, you must calculate the XOR operation with the Irreducible polynomial x^8 + x^4 + x^3 + x

and the result would be
0010 0110

I know how many spaces to shift when the first polynomial is a simple one, like
0010 or 0100, but how about when it is a little more complex?
Such as
0111 or 1011?? Hoy many spaces must i shift it?

0111 = 7, so i shift 7 times? or 2 because the greates expoent in the polynomial is 2??

Your help would be very much appreciated!

You cannot use (just) a bit shift to multiply by $7$.  Not in ${\rm GF}(2^n)$, and not in normal arithmetic either.

Shifting a number left by one bit always multiplies it by two, and shifting a number left by multiple bits is just equivalent to shifting it left by one bit several times.  So shifting a number left (by one or more bits) always multiplies it by a power of two.

To multiply a number by a factor that is not a power of two, you need both shifting and addition (which in ${\rm GF}(2^n)$ is actually bitwise XOR).  For example, $7 = 111_2 = 4 + 2 + 1$, so $7a = 4a + 2a + a$ for any $a$.  So, to multiply some number $a$ by $7$, you can first calculate $2a$ and $4a$ by shifting $a$ left, and then add those together with $a$ itself (always remembering that, in ${\rm GF}(2^n)$, addition is actually XOR and that any results with more than $n$ bits will need to be reduced modulo the field polynomial).

More generally, we can do general multiplication in ${\rm GF}(2^n)$ by splitting one of the numbers being multiplied into a sum of powers of two (which is really easy if we're working on a binary computer), use bit shifting (and modular reduction) to multiply the other number by those powers of two, and then add the results together.  Here's some pseudo-C code to illustrate this:

const int overflow = 0x100, modulus = 0x11B;  // AES GF(2^8) representation

int gf2n_multiply(int a, int b) {
    int sum = 0;
    while (b > 0) {
        if (b & 1) sum = sum ^ a;             // if last bit of b is 1, add a to the sum
        b = b >> 1;                           // divide b by 2, discarding the last bit
        a = a << 1;                           // multiply a by 2
        if (a & overflow) a = a ^ modulus;    // reduce a modulo the AES polynomial
    }
    return sum;
}

Note that you could easily turn the code above into a normal integer multiplication routine by replacing sum ^ a with sum + a and removing the last line in the while loop that reduces a modulo the AES polynomial after it has been shifted left.  Those are the only ways in which Galois field arithmetic, as used in this code, differs from normal integer arithmetic.

Also note that, while the code above should work (in the sense of producing the correct results), it's probably not something you should use in production crypto code.  Not only is it not particularly well optimized, but its running time depends on the value of b, which is generally not desirable if b might contain sensitive data that you don't want to leak.

(BTW, at this point you might be wondering if it wouldn't be more efficient, for example, to calculate $7a$ as $8a - a$ instead.  Unfortunately, while that would work fine in normal integer arithmetic, addition and subtraction in ${\rm GF}(2^n)$ work differently, and we actually have $8 - 1 = 8 + 1 = 9 \ne 7$.  But adding together distinct powers of two still works the same way in ${\rm GF}(2^n)$ as it does with normal integers, so we can still usefully work with the binary representation of numbers.)

I think you are trying to do the Mix Columns step of AES which involves multiplication in GF(2^8).
Please refer the the steps shown here using the peasant's method.
I know it should have been a comment but I do not have enough reputation to do so.


What should be the size of a Diffie-Hellman private key? I'm implementing the SRP-6 protocol, which relies on discrete logarithms for it's security (essentially Diffie-Hellman).

The RFC documents state:

  The private values $a$ and $b$ SHOULD be at least 256-bit random numbers, to give
  approximately 128 bits of security against certain methods of calculating discrete
  logarithms.

I can't seem to find any info on this – is it still valid advice?

Is the reason for this simply that the best known method for calculating discrete logs of $n$-bit numbers requires $2^{n/2}$ steps?

Well, yes, that is generally good advice about DH.

Here is some background on this: support you were given a value $g^x \bmod p$, and you were also told that $1 \le x \le A$ for some value $A$.  If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover $x$ in about $\sqrt A$ steps.  If we have as our security goal that it should take at least $2^{128}$ steps, then means that $\sqrt A \ge 2^{128}$, or $A \ge 2^{256}$, that is, we take our private exponent $x$ to be a random 256 bit number (note: in this context, we count it as a 256 bit number even if the msbit happens to be zero).

Now, there are a few other notes I want to leave you with:

There isn't much point in making the private exponent much larger than that; there is another avenue (Number Field Sieve) which also can solve the Discrete Log problem in time which is independent of the size of the exponent, but only depends on the size of the modulus.  For realistic modulus sizes, this will also be around (or, at least, not significantly more than) $O(2^{128})$ steps, so making the private exponent significantly bigger will just make your computations more expensive, without making the system any more secure in any real sense.
One minor point about SRP (as opposed to straight DH); the protocol does leak the LSbit of the initiator's private exponent (by leak, I mean that someone listening to the messages being exchanged can deduce that bit value).  I don't believe that that's a big deal (as it's only 1 bit, and nothing else is leaked).  If you want to be pedantic, I suppose you could have the initiator pick a 257 big private exponent (so there will still be 256 unknown bits).

The size of the modulus for ssh implementations of Diffie-Hellman (according to RFC4419 from 2006) should be between 1024 and 8192 bits.

This seems to be a bit off from what @poncho recommended (128 bits) in 2012.


Is a large random number cryptographically equivalent to the product of multiple smaller ones? Say I create a 256-bit key by taking a random number between $0$ and $2^{256}-1$.

Would it be cryptographically equivalent to generate $8$ numbers $r_1\dots r_8$ between $0$ and $31$, and combining them in the following way?

$$\mathit{rand} = 2^{r_1} \cdot 2^{r_2} \cdot 2^{r_3} \cdot 2^{r_4} \cdot 2^{r_5} \cdot 2^{r_6} \cdot 2^{r_7} \cdot 2^{r_8}$$

It would still add up to 256th power, but would it be secure of generating it this way? If not, then how to do it, how to generate big random number by combining smaller ones?

If you choose a number uniformly at random in the range $[0, 31]$, that's $32$ distinct values and thus $log_2(32) = 5$ bits of entropy.  If you choose $8$ such numbers, then you have $5 \times 8 = 40$ bits of entropy total, meaning that there are $2^{40}$ distinct combinations you could get.  It doesn't matter how you combine them, that's already far short of $2^{256}$.

And it gets worse, because you're multiplying numbers that you compute from your eight choices:

  $$\mathit{rand} = 2^{r_1}\cdot 2^{r_2}\cdot 2^{r_3}\cdot 2^{r_4}\cdot 2^{r_5}\cdot 2^{r_6}\cdot 2^{r_7}\cdot 2^{r_8} $$

Since multiplication is commutative ($a \times b = b \times a$) and associative ($a \times (b \times c) = (a \times b) \times c$), it means that many combinations among those $2^{40}$ distinct choices actually yield the same product after the multiplication.  E.g., if two sequences of random choices are permutations of each other their product is the same. In this case, it is even worse, since $\mathit{rand}=2^{r_1+\dots+r_8}$ is always a power of two: This means we are effectively sampling a $256$-bit number that has exactly one bit set, so there's only $256=2^8$ possible outcomes!

  If not, then how to do it, how to generate big random number by combining it from smaller ones?

Basically, by choosing digits at random in some base.  If you have $n$ randomly drawn digits $d_0, ..., d_{n-1}$ in base $b$, then $d_0b^0 + ... + d_{n-1}b^{n-1}$ is a uniform random number in the range $[0, b^n)$.  For example, to generate a 256-bit number at random, you could:

Choose 256 individual bits at random ($n = 256$, $b = 2$);
Choose 32 bytes at random ($n = 32$, $b = 8$);
Choose eight 32-bit machines words at random ($n = 8$, $b = 32$);
Choose four 64-bit machines words at random ($n = 4$, $b = 64$).

In practice, this is done by just concatenating randomly chosen bytes or machine words.

This depends on the unknown internal state of the generator. If you seed RC4 with one byte (the key) and generate eight bytes, it only has one byte of security.

If you use SHA-1 with a 512-bit key, hashing a counter, it will only have 160-bits of security, because the unknown internal state of the function is only 160-bits (the chaining value).

For AES-256, it has a secret internal state of 256-bits (the key).

There has been a large body of literature on random number generation, but your question isn't directly related to any of them.

To directly answer your question, a number between 1 and 32 is a 6-bit value. Usually people concatenate bit values to form a key. There is also a bias, none of those numbers include zero or the values between 33 and 63.


Security equivalence proofs for breaking RSA It is my understanding that while a practical solution to the factoring problem will definitely break RSA, it has never been proven that the security of RSA is equivalent to factoring.

In otherwords, theoretically, someone could mathematically break RSA without breaking the factoring problem.

Are there any problems for which breaking RSA would be equivalent to (besides the obvious RSA Problem)?

The summary in the Rivest-Kaliski paper does indicate that two specific problems are equivalent to the RSA problem itself.

Due to the algebraic properties of the field $Z_n$, if there exists any small fraction of weak cipher texts (i.e. a particular subset of cipher texts $C$ for which finding the solution $M$ to $C = M^e \pmod N$ is easy), then the RSA Problem is at most as hard as the running time of the adversarial procedure for decrypting the weak cipher texts times a polynomial factor. IOW: The RSA Problem guarantees that all cipher texts are equally hard to invert.
A similar argument applies to each individual bit of a RSA cipher text. If an adversary has a non trivial advantage to determine any bit of a RSA plain text $M$ given a RSA cipher text $C$, then all bits of $M$ are equally easy to determine.

Actually, this is an equivalence (see http://www.jscoron.fr/publications.html#joc2007) when ed <= N^2.


Good challenges for a crypto competition for teenagers I'm holding a cryptography workshop for teenagers (around 16 years old) at our university. As part of the workshop, I'm planning to run a crypto competition with prizes: there will be different tasks, each one will yield points, and the winners will get sweets.

However, for the amount of time I'm planning to kill with this game, I still need one or two more challenges. So far, what I have is:

Scytale: one band with letters on it and four potential objects - find out which is the right object so you can read the message and obtain the solution.
Caesar Cipher: Find out by how much the letters have been shifted to get the solution.
A transposition cipher (one where you write the text in a rectangle and then read the columns).
One with frequency analysis (they get the frequency table for the letters and a longer text which I chose to be pretty close to at least the most frequent values).

As you can see, these are all pretty basic stuff that can be done by hand. I don't really want to do anything that would require the kids to do any programming, although I suppose I could do something like install Cryptool2 on an old computer and have that as one station, if anyone has a nice idea that requires computer assistance.

I'm hoping that, among the community of crypto experts and enthusiasts here, some of you may have experience with running such competitions for kids and teenagers, and may be able to suggest some good challenges.  If you've organized something like this before, and know some suitable challenges that I haven't already thought of, please share them!

Perhaps you could do something with Visual Cryptography.
Maybe something like:

Gather a few low-resolution images (symbols or short text phrases), perhaps a few more images than you have kids
Use visual cryptography to split each image into 2 random-looking images, and print each random-looking image on its own piece of transparency paper
Shuffle the pile of transparency papers
somehow let the kids find matching pairs of transparencies that show the original symbol or phrase.

Is there some way to let kids produce Visual Cryptography image-pairs "by hand", without a computer?

Links and further reading:

"What is Visual Cryptography"
online visual cryptography generator
"Visual Cryptography Kit"
visual cryptography example
"Visual Cryptography and Bit-Plane Complexity Segmentation"
XOR with polarized film

Give every kid a deck of cards (2 decks of cards?) and a short (unique) text message on paper.
Each kid encodes the message -- by arranging the cards in some order; writing on the cards is cheating.
Then every kid decodes a deck of cards (arranged by some other kid) and write the message on paper.

Challenge the kids to come up with a better algorithm for encoding text that (a) is more robust against small, common errors, such as accidentally losing the first card, or (b) can encode a longer text message into a deck of cards, or (c) is faster to encode, or (d) better in some other way.


Should we sign-then-encrypt, or encrypt-then-sign? We regularly want to send messages that are both (a) encrypted, so passive attackers can't discover the plaintext of the message, and (b) signed with a private-key digital signature, so active attackers can't trick Alice into thinking that some message came from Bob when really the message is some (accidental or malicious) modification of a real message Bob sent or a message that was forged out of whole cloth by an attacker.
Is it better to (a) generate the digital signature from the (hashed) plaintext, and then encrypt a file containing both the plaintext message and the digital signature?
Or is it better to (b) encrypt the message first, and then generate a digital signature from the (hashed) encrypted file?
Or (c) combine encryption and public-key digital signatures in some other way?
A closely related earlier question ( Should we MAC-then-encrypt or encrypt-then-MAC? )
seems to focus on symmetric-key MAC authentication.
As Robert I. Jr. asked earlier,
Do the same issues with (symmetric-key) MAC-then-encrypt apply to (public-key) sign-then-encrypt?

Assuming you are asking about public-key signatures + public-key encryption:

Short answer: I recommend sign-then-encrypt, but prepend the recipient's name to the message first.

Long answer: When Alice wants to send an authenticated message to Bob, she should sign and encrypt the message. In particular, she prepends Bob's name to the message, signs this using her private key, appends her signature to the message, encrypts the whole thing under Bob's public key, and sends the resulting ciphertext to Bob. Bob can decrypt, verify the signature, and confirm that this indeed came from Alice (or someone she shared her private key with).  Make sure you use an IND-CCA2-secure public-key encryption scheme and a UF-CMA-secure public-key signature scheme (i.e., one that is secure against existential forgery attack).

Justification: The reason to do this is to defeat some subtle attacks.  These attacks are not necessarily a problem in all scenarios, but it's best to harden the approach as much as possible.  A complete explanation would take more space than is available here, but see below for a sketch of the reasoning.

For a detailed analysis about whether to sign first or encrypt first, the following is a good resource: Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.

I don't recommend encrypt-then-sign. It could work, but it has some subtle pitfalls in some contexts, because the signature does not prove that the sender was aware of the context of the plaintext. For instance, suppose Alice's SSH client sends the message "Dear SSH server, please append my public key to /root/.ssh/authorized_keys -- and you can know that I am authorized because I know the root password is lk23jas0" (encrypted then signed with Alice's public key), and the SSH server acts on it if the root password is correct. Then Eve can eavesdrop, capture this message, strip off Alice's signature, sign the ciphertext with Eve's own key, and send it to the SSH server, obtaining root-level access even though Eve didn't know the root password.

The only difference between these approaches has to do with hiding information about the sender. If you don't want attackers to know who the signer is, you need to sign-then-encrypt. In other cases it doesn't matter.


Why are RSA key sizes almost always a power of two? I know that other bit sizes are possible, e.g. this HTTPS server seems to have a 9000 bit key https://www.ssllabs.com/ssltest/analyze.html?d=qqq.gg, but it's very rare that one sees a key not of size 1024, 2048, 4096, etc. bits in common usage - what is the reason for this? Is it just customary, or is there a cryptographic advantage?

In RSA, the bit size $n$ of the public modulus $N$ is often of the form $n=c\cdot2^k$ with $c$ a small odd integer. $c=1$ ($n=512$, $1024$, $2048$, $4096$.. bit) is most common, but $c=3$ ($n=768$, $1536$, $3072$.. bit) and $c=5$ ($n=1280$..) are common. One reason for this is simply to limit the number of possibilities, and similar progressions are found everywhere in cryptography, and often in computers where binary rules (e.g. size of RAM).

The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with $n$. But the difficulty of computing the RSA public and private functions grows largely stepwise as $n$ increases (more on why in the next paragraph). The values of $n$ just below a step is thus more attractive than the value just above a step: they are about as secure, but the later is more difficult/slow in actual use. And, not coincidentally, the common RSA modulus sizes are just below such steps.

One major factor creating a step is when one more word/storage unit becomes required to store a number. When the storage unit is $b$-bit, there is such step every $b$ bits for the RSA public function $x\mapsto x^e\bmod N$; and a step every $r\cdot b$ bits for the RSA private function $x\mapsto x^d\bmod N$, with $r=1$ for the naïve implementation, and $r$ equal to the number of factors of $N$ when using the CRT with factors of equal bit size (most usually $r=2$, but I have heard of plans up to $r=8$). On any modern general-purpose CPU suitable for RSA, $b$ is a power of two and at the very least $2^5$, creating a strong incentive that $n$ is at least a multiple of $2^6$ ($r=2$ is common, and the only reasonable choice for $n$ below about a thousand).Note: $n=1984=31\cdot2^6$ is not unseen in the field of Smart Cards, because the next multiple of $2^6$ would break the equivalent of a sound barrier in a common transport protocol, ISO/IEC 7816-3 T=0. For a list of common RSA modulus size in this field, search LENGTH_RSA_1984.

As an aside, it is significantly simpler to code quotient estimation in Euclidian division (something much used in RSA) when the number of bits of the divisor is known in advance. This creates an incentive to reduce the number of possible bit sizes for the modulus. The two simplest cases are when the number of bits is a multiple of $b$, and one more than a multiple of $b$; the former won.

It is just customary, and enforced by products like GPG and OpenSSL which include code to block you choosing your own exact bitlength (they enforce padding or rounding, for no particular reason).  Here is the GPG code that enforces this, for example:

 if( nbits < 768)
   {
     nbits = 2048;
     log_info(_("Keysize invalid; using %u bits\n"), nbits );
   }
 else if(nbits>3072)
   {
     nbits = 3072;
     log_info(_("Keysize invalid; using %u bits\n"), nbits );
   }

 if(nbits % 64)
   {
     nbits = ((nbits + 63) / 64) * 64;
     log_info(_("keysize rounded up to %u bits\n"), nbits );
   }

 /* To comply with FIPS rules we round up to the next value unless
    in expert mode.  */

 if (!opt.expert && nbits > 1024 && (nbits % 1024))
   {
     nbits = ((nbits + 1023) / 1024) * 1024;
     log_info (_("keysize rounded up to %u bits\n"), nbits );
   }


Is there any semantic difference between predicate encryption and functional encryption? Predicate encryption(PE) arrived as a descendant of attribute based encryption. Attribute based encryption allows the encryptor to embody a policy to the ciphertext (Ciphertext-Policy based encryption) and the receipent to receive a key from a central trusted authority according to his attributes. If the attributes do satisfy the policy then the receipent can decrypts. Another less secure version is the key-policy based encryption whereby the encryptor associates with the ciphertext the attributes that he wills a potential decryptor to have and the key of the receiver comes with the policy. Because attribute based encryption reveals the policy(KP-ABE) and the attributes(CP-ABE) predicate encryption comes to solve this by allowing the receipent to apply a predicate if he owns a secret key of that predicate.

Functional encryption(FE)
As presented in the paper is a generalization of Identity based encryption, Attribute based encryption and predicate encryption. Instead of a predicate there is a function $f$ that evaluates the attributes of the ciphertext. At the paper the construction is given based on predicate encryption.

My question is what extra functionality FE provides in comparison with PE. Is there a drawback or a security leakage in PE that FE solves?
My intuition from the literature is that the contribution of FE is the generalization of the 3 previous mention crypto schemes(IBE,ABE,PE) into 1 scheme (research purpose for acceptance in a conference, not practical at all) and second is the area of applications. I understood that in PE if your secret key $sk$ lets you evaluate at $1$ a predicate $P$ over a ciphertext $c$ then you recover the plaintext but with the FE if $F_{sk}(c)=1$ then you learn the output of the function on the plaintext. I.e: the function might be a machine learning algorithm classifying spam so you learn if the message is a spam or no, but not the contents of the message. Is this correct?

PE is a subclass of FE.

This (from the other answer) is correct.

Also, from my understanding, your analogy is correct. PE returns the plaintext if the predicate evaluates to true. FE, on the other hand, returns a function of the plaintext.

We can say that PE is a subclass of FE, since we can use FE to implement PE. Just use the identity function.

Your example of $f$ being a machine learning function is an example of something that FE can do that PE cannot.

"Predicate-only PE" is a (more obvious) special case of FE. find the definition of "predicate-only PE" in this paper https://eprint.iacr.org/2007/404.pdf


Is it more weak to encrypt with the private key RSA? I have a simple question.

Is it more weak to encrypt with the private key against the public key with RSA ?

Like is it easier to "crack", "brake", "solve", "decrypt" when I encrypt with the private key against the public key. Is it really the same process of encryption?

(In both cases we assume that the "breaker" doesn't know any of the keys)

Edit:

To be more precise, is there something that differs in the process of encryption with any of these two keys.

Is the only difference between the public and private is that the private can generate public keys but the public key can not generate private? If I want to encrypt with the private or the public key the result is the same, the encryption is passing by the same steps and then results in a difficult breakable encrypted output?

RSA key generated with puttygen
PGP encryption / decryption

the "breaker" doesn't know any of the keys

That goes against the very name of the public key, and rationale for using RSA or any asymmetric cryptography. Let's assume it nevertheless in the first section of this answer.

  Is the only difference between the public and private (keys) that the private can generate public keys but the public key can not generate private?

No.

The two keys typically are not in the same format.
Further, in RSA

The exponent in the public key is customarily small.
The most common formats for private key include the factorization of the modulus, when the public key never does.
Depending on format of the private key and method of generation of the key pair, the private key allows to generate a matching public key, or not. Neither constitute a weakness of RSA.

The public key of any secure asymmetric cryptosystem never allows to generate a matching private key.

  (assume):

  RSA key generated with puttygen
  PGP encryption / decryption

PGP does not give any way to encrypt with a private key, nor decrypt with a public key. Neither does GPG, nor any reasonable OpenPGP implementation. The closest it allows is producing a signature, which leaves the message in clear or removes it. That's totally unsafe or dysfunctional from the perspective of confidential transmission of a message.
Note: When creating or importing a private key, PGP/GPG also generates or import the public key, and that what it uses to encrypt. Correspondingly, the passphrase normally required for private key use is not asked for encryption.

The closest feasible thing matching the question's description would be to swap the public and private key generated by puttygen, before somewhat feeding them to the encryption program. That's not quite trivial, because the two keys are not in the same format. But that's feasible: we change $e$ of the formerly public key to $d$ from the formerly private key, and change $d$, $d_p$ and $d_q$ of the formerly private key to the former $e$, that is $37$ as explained here.

If we do this, the newly made public key will look about normal, except for a large exponent instead of a customary short one ($37$ and $65537$ are common). Encryption will be possible (and measurably slower than usual). Decryption with the newly made private key will be possible (and measurably faster than usual). The question asks if that's less safe than normal encryption is.

Yes, that's less safe in the sense that now an adversary knows the normally secret $d$ in the private key (that's $37$). Thus if somewhat the normally public modulus $N$ gets public, it becomes trivial to decipher. Normally $N$ is in both keys, thus public; and further, encryption programs make no effort to keep $N$ secret: we can't rule out that with some encryption option, $N$ is sent in clear along the plaintext. Or that some attack allows the attacker to know $N$. For a start, PGP and GPG store $N$ in clear in the pubring file, not protected by a passphrase.

If we hypothesize that an attacker only has one ciphertext without $N$, I see no way to obtain $N$ or otherwise decipher or get any useful information about the plaintext.

This perhaps remains true if the attacker has multiple ciphertexts and knows some corresponding plaintexts, assuming hybrid encryption is used (as in OpenPGP). However, with textbook RSA encryption, $N$ can be recovered and security is lost.

[From this point onwards, we again assume the public key is public]

  Is it more weak to encrypt with the private key against the public key with RSA ?

Often that's impractical or/and unsafe (see above); but not necessarily. In fact, RSA as taught and practiced today reverses the public and private key compared to the key generation procedure of original RSA (Ronald L. Rivest, Adi Shamir, and Leonard  Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in Communications of the ACM, Feb. 1978). That reversal was originally made for performance reasons, and it turns out that it improves security compared to that in original RSA!

Original RSA has an almost unique characteristic among asymmetric cryptosystems: we indeed can exchange public and private key, and that does not compromise security (including when we reveal the key used for encryption, as designed, see final section). That's because original RSA

first selects the decryption exponent $d$ mostly randomly in a large set, then computes the encryption exponent $e$ from that, per the symmetric equation $e\,d\equiv1\pmod{\phi(N)}$
public and private keys are in the same format: the public modulus $N$ and an exponent.

It quickly became standard practice to first choose the encryption exponent $e$ (that is, reverse public and private key compared to key generation of original RSA): in Martin Gardner's A new kind of cipher that would take millions of years to break (in the Mathematical Games column of Scientific American, Aug. 1977), Rivest's MIT group used $e=9007$ in a then difficult challenge, implying that $e$ was chosen before $d$. Such small $e$ speeds computations involving that exponent (encryption and signature verification) by a large factor, broadening the practical uses of RSA; but it becomes unsafe to exchange public and private exponents.

It took some time to fully realize that original RSA's prescription "It is important that $d$ should be chosen from a large enough set so that a cryptanalyst cannot find it by direct search" is necessary, but insufficient for security. Selecting a random $d$ in $[2^{135},2^{136}]$ with $\gcd(d,p-1)=1=\gcd(d,q-1)$ blocks direct search of $d$, but would be unsafe for $p$ and $q$ 512-bit or larger primes (see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999).

In original RSA, decrypting is the same as signing, and both are encrypting with public key replaced by private key. However:

Original RSA's enciphering is insecure (among reasons: correct guess of the message can be verified with the public key, thus it is insecure to encipher a name on the class roll, a password, or a credit card number).
Original RSA's signing is insecure (for different reasons, including: an adversary can find signature of a message showing as any short desired text when printed as a C string; a few rightful signatures of some selected meaningful and sizable messages can be turned into forged signatures of other meaningful and sizable messages).

Weaknesses of original RSA have been fixed, but with modern RSA as practiced (or PGP/GPG and RSA keys), signing is markedly different from encrypting with public key replaced by private key. And many other common signature schemes have no encryption counterpart.

While modern RSA practice distinguish signing from encrypting with public key replaced by private key, it's possible to have the two use essentially the same padding. See Jean-Sébastien Coron, Marc Joye, David Naccache, Pascal Paillier, Universal Padding Schemes for RSA, in proceedings of Crypto 2002 (also there). Note: AFAIK it is not used in practice.

Glossary of things properly named:

In public-key cryptography, the public key is made public (the private key is kept secret).
In public-key encryption, encryption is with the public key (decryption is with the private key).
In public-key signature, signature verification is with the public key (signing was with the private key).

The strength of the cipher (against cryptanalysis) does not depend on which key of the pair is being used to encrypt your text.

In Public Key Encryption, we encrypt with private key for proving authenticity and we encrypt with public key for confidentiality. In the security domain, authenticity and confidentiality are equally important although they're used in different context. If encrypting with a the private key rendered a weaker cipher, then people wouldn't use their private key for signing (generating digital signature) to prove authenticity.

By the way, the followitn claim made by @fgrieu is entirely wrong:
 "PGP does not give any way to encrypt with a private key, nor decrypt with a public key. Neither does GPG, nor any reasonable OpenPGP implementation."

All functional crypto-system including PGP and GPG allow us to digitally sign a document or text. Signing an email is merely encrypting the hash of the text with the sender's private key. The receiver, on the other hand, proves the authenticity of the message by decrypting the ciphertext (i.e. the digital signature) with the public key of the sender.  For reference, you can take a look at: https://users.ece.cmu.edu/~adrian/630-f04/PGP-intro.html

Note: I couldn't make a comment on @fgrieu's post as I'm new in this community and do not have enough reputation score.


Security proofs for CBC mode I'm looking for different approaches to proofs for the security of CBC mode encryption. What are the best sources of information about this subject?

Here's a nice paper I came across a while ago: Wooding, Mark (2008), "New proofs for old modes", Cryptology ePrint Archive, report 2008/121:

  "Abstract: We study the standard block cipher modes of operation: CBC, CFB, and OFB and analyse their security. We don't look at ECB other than briefly to note its insecurity, and we have no new results on counter mode. Our results improve over those previously published in that (a) our bounds are better, (b) our proofs are shorter and easier, (c) the proofs correct errors we discovered in previous work, or some combination of these. We provide a new security notion for symmetric encryption which turns out to be rather useful when analysing block cipher modes. Finally, we pay attention to different methods for selecting initialization vectors for the block cipher modes, and prove security for a number of different selection policies. In particular, we introduce the concept of a `generalized counter', and prove that generalized counters suffice for security in (full-width) CFB and OFB modes and that generalized counters encrypted using the block cipher (with the same key) suffice for all three modes. "

If you can go through these lecture notes by Goldwasser and Bellare you will get the point


Why doesn't the formula work when checking two ECDSA signatures? There are two generated ECDSA signatures

X - Private key

S  = ((Z  + (X * R)) / K) mod n

S` = ((Z` + (X * R`)) / K`) mod n

G - Base point, of order n;

R  = K  * G
R` = K` * G

Why is this formula not working?

C = K - K`

R = R` + (C * G)

Where exactly do I make a mistake?

In ECDSA, the R value in the signature is not the elliptic curve point $kG$, but instead only its x-coordinate, that is, an integer.

So, what do you mean by R' + (C*G)?  In particular, what do you mean by the operator +?

If you mean "the + is an integer modular addition, that is, we take the x-coordinate of the point $CG$, and then add it (modulo $n$) to $R'$", well, that'll give you an integer that's unrelated to $R$ (as $R$ and $R'$ are related as elliptic curve points not integers, and integer addition and elliptic curve operations have little to do with each other)

If you mean "the + is an elliptic curve addition, that is, we find one of the points with x-coordinate $R'$, and add it (using the elliptic curve addition operation) to the point $C\cdot G$), well, that'll work half the time; there are (usually) two elliptic curve points with x-coordinate $R'$, and it'll work if the one you pick just happens to be the original $R'$ point.

Are you sure you understand how ECDSA or ECC work in terms of operations? The * and + operations are not actually multiplication and addition (in the last 2 equations). They are the ECC trapdoor function. You can see an animation of such a function here (it should be a gif):

The * and + operations just mean applying the trapdoor function x times.

In your example:

 R  = K  * G

Take the point G and apply the trapdoor function to it K times.

In ECC and ECDSA, a - operation (when refering to reversing the trapdoor function) is not possible in most scenarios, since that would mean reversing the trapdoor function, solving the Elliptic Curve Discrete Logarithm Porblem, making the cryptosystem obsolete (in most cases its not possible, but some attacks on weak curves exist).

You can find a bunch of python libraries to do these function multiplications like ECPy


Use of Lamport's Signature as a primitive Is Lamport's One Time Signature used as a primitive to construct any other cryptographic protocols?

I don't know of a use of Lamport's scheme precisely as Lamport originally published it; however if we include generalizations of the idea (such as Winternitz signatures), then it has been used as the basis of Hash Based Signatures, such as this proposal

Two caveats:

Lamport itself isn't fundamental; it's just the prototypical example of a one-way signature.
A one-way signature isn't a "primitive" any more than an RSA signature is; it might be more accurate to describe it as a "building block".

However, yes, one-time signatures are a keystone operation in Lu, Au, and Zhang's 2019 Linkable Ring Signature scheme.
(Ring Signatures allow users to sign a message as an anonymous member of a set of users; Linkable Ring Signatures allow multiple such signatures by the same anonymous signer to be shown to be such.)


Are cryptographic hash functions quantum secure? I was reading a paper related to post quantum cryptography. It says that RSA, ECC and ElGamal encryption schemes would be obsolete with the advent of quantum computers. But the hash functions can still be secure. I don't understand how one can unilaterally claim this security when hash functions themselves are not based on any hard problems. (I do have the knowledge of Merkel-Damgård and Keccak construction).

Are there hash functions considered secure just because nobody has come up with a quantum algorithm to solve it? Or are there any reduction to any well known hard problem? It there is please explain the reduction.

It is a bit dubious to claim that hash functions "are not based on any hard problem": inverting a standard hash function, or finding a collision, is itself a very hard problem.

The point of a reduction is to gather the cryptanalytic effort on a smaller number of hypothesis. The fact that RSA-OAEP is CCA secure under the RSA assumption is not a proof that it is secure, simply an indication that to study its security, it suffices to study the security of the RSA problem. As many other cryptographic primitives can be reduced to the RSA assumption, it saves a considerable cryptanalytic effort.

Now, such reductions usually rely on some nice algebraic properties of mathematical hypothesis, exploiting group structure, self-randomizability, and so on. These properties are common in asymmetric cryptography, because such additional structure is already necessary in the primitives it involves. But in symmetric crypto, on the other hand, such structure is typically avoided. A consequence of that is that you need way smaller primitives (in terms of bit size) and much less computationally expensive operations to achieve a (conjectured) given security level, but you loose the possibility of reducing many symmetric primitives to a small number of hypothesis.

Still, for the most widely deployed block ciphers and hash functions, the cryptanalytic effort that has been invested on studying their security easily matches the effort invested on "generic hypothesis" such as the discrete logarithm or the factorisation, because they are widely used in practice. Therefore, there is no reason to believe that, due to the lack of reductions, inverting SHA256 should be any easier than breaking RSA. In fact, because RSA has so much structure, most experts would probably be way more surprised by an attack that inverts SHA256 than by an attack that breaks RSA. Therefore, the fact that ElGamal and the kind enjoy "reductions" does absolutely not make them more secure - it only establishes links between hardness of different primitives.

That being said, quantum computers are not magical. We cannot say anything for sure about what we can or what we cannot break with them - for all we know, it could be that $P=NP$, and that all of cryptography can be broken using a classical computer. But our current knowledge gives us some intuition on the additional power they give over classical computers. And this intuition can be summed up as follow: it seems to give some additional power, but to still fall short on solving very hard problems (say, NP-complete problems) in reasonable time.

Some problems with a special structure (factorization, discrete log) typically fall in the category of problem for which quantum computers would give a very strong speedup, because they can be reduced to the task of finding the period of some function, which seems hard to do with a classical computer, but not with a quantum one. For unstructured problems, quantum computers seem to provide some non-trivial quadratic speedup, via the use of the Grover algorithm. But a quadratic speedup does not give an attack, it simply indicates that the size of the keys should be increased by a factor two to compensate for this speedup.

Hash functions are rather unstructured, so we currently do not see how to get more than a quadratic speedup over a classical computer to attack one. Therefore, we currently conjecture that a hash function with 256 bits of classical security would still have 128 bits of quantum security. For collision resistance, quantum computers provide an even less impressive speedup: the birthday attack gives a $O(\sqrt{n})$ attack, and it's quantum version seems only to make this attack $O(n^{1/3})$.

A hash is just a symmetric cipher run in a loop, encrypting the input using a key also from the same input, and often with extra stuff sprinkled in as you go (e.g. prime remainders in SHA-2).

I'm no expert, but whether or not any hash is quantum-resistant boils down
entirely to whether or not the symmetric cipher chosen for the hash is.

The SHA-2 cipher is secret (classified), so only the NSA (who invented SHA) know if it's quantum-resistant or not.


What are the approaches to private computations? I'm talking about the ability to safely run a virtual machine on a physical device that is not trusted. It is necessary that the owner can not access the data that the virtual machine operates on. I am interested in what theoretical or practical implementations exist without special hardware.

I know about homomorphic computations (this in theory fully satisfies my question), but for now it's incredibly slow. It will take many years before the protocols of homomorphic calculations just approach application in practice.

I also read about Intel SGX, which implements enclaves. The RAM stores only encrypted data, which is decrypted at the input to the processor and is again encrypted at the output. The disadvantage of Intel SGX is that you need special hardware. How could you do something like this without a special hardware? How can we store a key for decrypting data from RAM so that the owner of this physical device can not recognize this key?

If the VM actually has anything that needs protection, running the VM on untrusted hosts is not secure (period). There is nothing that will change that.

Going to homomorphic encryptions etc. implies that even the VM doesn't know any secrets, only the source of the data (outside of VM and host) does. In this case, having a VM or not isn't even relevant.
There are of course still problems with the authenticity of the results etc. - just encrypting is never enough.

Using Intel SGX from within VMs relies on the support/cooperation of the VM software - meaning, it might be useful for separating VMs fom each other, but it can not help VMS against their malicious host.
Given that VMs are, well, virtualized, any hardware support is useless in your scenario. If the host and the virtualization software can't be trusted, your VM is not secure.


Meaning of epsilon in proving a PRG is predictable/ un predictable I am quite confused, I have been following a course on crypto provided by Dan Boneh, this is the lecture I am confused with - https://www.youtube.com/watch?v=EjWap3szsPk time stamp 8:58 - 11:00

I don't understand the meaning of epsilon in this situation, I know epsilon is a symbol in math that is used for a positive number approaching 0.

What does he mean by the PRG is predictable if the probability is greater than 1/2 + epsilon for some non negligible epsilon?

if someone could explain this in a little more dept and in more laymans terms if possible would be greatly appreciated.

transcript - we say that G:K -> {0,1}^n is predictable if

∃ "eff" algorithm A and ∃ 1 < i < n-1 s.t

k <- K pr[ A(G(K) |1,...., i =  G(K) | i+1] > 1/2 + ε for some non negligible ε

we say that G is predictable if there exists a efficient algorithm A and there is some position 1 between 1 and n-1 such that we look at the probability that we generate a random key, if I give this algorithm the prefix of the output (the first i bits of the output) the probability that it's able to predict the next bit of the output is greater than half + epsilon for some non negligible epsilon.

Loosely, ‘negligible’ means small enough to ignore.  A difference in probability of $2^{-128}$ is likely small enough to ignore; a difference in probability $2^{-10}$ may not be.

Formally, in the language of complexity theory, a function $f\colon \mathbb N \to \mathbb R$ which assigns to each natural number $n$ a real number $f(n)$ is negligible if it goes to zero faster than the inverse of any polynomial—that is, if for any polynomial $p$, there exists a number $n_0$ such that for any $n > n_0$, $|f(n)| < |1/p(n)|$.

For example, $n \mapsto e^{-n}$ is a negligible function.

  Sketch of proof: Let $p(x) = x^d$; at what point $n_0$ do we have $e^{-n} < 1/n^d$, or $e^d < n^n = e^{n \log n}$, for all $n > n_0$?  We don't need to solve this exactly—it suffices to set $n_0 = d$; as long as $n > n_0 = d$, $n \log n > n > d$, so $n^n = e^{n \log n} > e^d$ and thus $n^{-d} > e^{-n}$, or $e^{-n} < 1/n^d$ as desired.  Finding the corresponding bound $n_0$ for other polynomials left as an exercise for the reader.

In the language of complexity theory, we usually consider ensembles of cryptosystems that scale with a security parameter, and we consider the asymptotics of the growth curves of the user's cost and the adversary's cost as the security parameter scales.

The same is true for algorithms more generally, which is why software engineers will casually talk of quicksort's $O(n^2)$ worst-case time but $O(n \log n)$ average time, because it's a useful proxy for estimating concrete costs—and, unlike a measurement in seconds or joules, it doesn't change if you move from one machine to another, which is helpful for understanding how it will scale if you feed it more and more data even if you use a slightly faster machine.

Of course, we must be careful not to lose sight of the concrete numbers without asymptotics: while it is proven[1] that multiplication can be computed in $O(n \log n)$ bit operations, you'll still get an answer faster in wall clock time using a naive $O(n^2)$ algorithm for any input that is possible to work with in practice.

Similarly, while the Blum–Blum–Shub pseudorandom generator has a polynomial-time reduction theorem relating the difficulty of distinguishing BBS output to the difficulty of factoring the BBS modulus, the concrete security of BBS[2] (paywall-free) is such that it costs $2^{43}$ bit operations to generate a mere 128 KB of data at a ~100-bit security level, using somewhat old estimates for factoring costs.  At 2.5 GHz, that takes a minute of computation.  In contrast, e.g., AES-256 can generate the same amount of data in microseconds at a much higher security level.

$\epsilon$ is just the bias of any PRNG such as $G:K \rightarrow \{0,1\}^n$ away from uniformly pseudo random. Ideally the long run next bit predictability of $G$ should be exactly $1 \over 2$.  In reality, it's $\frac{1}{2} + \epsilon$ as no one's perfect and we have to balance bias with efficiency.

Negligible = "too slight or small in amount to be of importance"

The concept of importance here simply means that if it's sufficiently large  we can stochastically measure $\epsilon$ by sampling enough output from $G$. If we can measure it, we can use it to create an advantage for ourselves in guessing the $i_{n+1}$ th bit of an output sequence. That then undermines the security of $G$.

If $\epsilon$ is negligible, we can't measure it using current resources and we can treat $G$ as secure distribution wise. Dan suggests the threshold values of $b$ in $\epsilon = \frac{1}{2^b}$ as 30 and 80 for non-negligible and negligible biases respectively. NIST use $b = 64$.

There's a bit more on negligible crypto concepts in What exactly is a negligible (and non-negligible) function?.


What is the difference between known-plaintext attack and chosen-plaintext attack? I am very confused between the concept of known-plaintext attack and chosen-plaintext attack. It seems to me that these two are the same thing, but it definitely is not.

Can anyone explain to me how these two differ?

It's the difference between an active and a passive attacker:

Known plaintext attack: The attacker knows at least one sample of both the plaintext and the ciphertext. In most cases, this is recorded real communication. If the XOR cipher is used for example, this will reveal the key as plaintext xor ciphertext.
Chosen plaintext attack: The attacker can specify his own plaintext and encrypt or sign it. He can carefully craft it to learn characteristics about the algorithm. For example he can provide an empty text, a text which consists of one "a", two "aa", ... For example: if the Vigenère cipher is used, it is very easy to extract the key length and recover the key by repeating one letter.

So the second type of attack is a lot more powerful.

Known Plaintext Attack

You sniff a lot of thhing about your victim but every of them is ciphertext so you don't know anything about them. And you learn o plan text of your victim by any means; but you don't know the plaintext is which ciphertext's. So you must solve this problem.

Choosen Plaintext Attack

You know a plaintext and you know the plaintext is which cipertext's. And you try to solve the algorithm of encryption system.


Why are recomended RSA key lengths so high? I was checking for authoritative sources to back up my recommendation of a minimum RSA key length of 1024 and was shocked to find that NIST 800-56Br1 and FIPS 186-4 both recommend at least 2048 bits with 3072 bits for TOP SECRET data.  I found that other sources have similarly high recommendations based on expected lifetime of the key.

These recommendations seem excessive in light of what I can find about attacks against RSA encryption.  As far as I can find, the most recent attempt to factor RSA numbers was the successful factoring of the 756 bit RSA number.  That was in 2009 and required, roughly, two years of effort with 100 computers and a team of mathematicians.  Those researchers noted that their methods would not scale to significantly larger RSA numbers, so other [and unknown] methods would need to be developed.

Given that each additional bit doubles the number of values, 1024 bits would have $2^{256}$ times as many possible values.  Even given very sparse utilization of that immense field, the effort required to attack a 1024 bit RSA key appears very far outside the reach of current capabilities.

Have I missed some more recent attacks?  I note that some of the recommendations I have found predate the 2009 paper.  Why would cryptanalysts believe that 1024 bit RSA keys would be insufficient when no one had even attacked the 756 bit key, which is vastly easier than 1024?

Can anyone point me to cryptanalytic work that demonstrates the risk to 1024 bit RSA?

RSA, and to a somewhat similar extent Diffie-Hellman, bases its security on the difficulty of factoring large numbers into primes. While a scheme like AES can use all 2n numbers, in order to break RSA, you need to guess prime numbers.

As there are far fewer prime numbers and the factors can be better guessed, we need far larger prime numbers than other schemes like AES. So each additional bit doesn't double the difficulty of brute forcing it. If you want to venture into the math, you can check out the Wikipedia page on RSA.

While no one (we know of) has managed to break 1024, it is always important to stay ahead of the curve. And since brute force isn't exactly 2256 times more difficult,we pick higher primes. Who knows what future improvements in mathematics could break 1024-bit keys.

With number field sieve and quadratic field sieve, it is easy now to break RSA keys less than 1024 bit and more so the concepts of quantum cryptography will break all myths of unbreakable security. So graduating to higer bit security is obvious choice. ECDH and EC RSA still give some respite in present times.


SHA256 output to 0-99 number range? Is it mathematically possible to take a SHA256 hash and turn it into a 0-99 number where each number in 0-99 range is equally likely to be picked?

As a 256 bit hash means the highest value possible is 2^256, this is not a nice or "round" number for the purposes of simplifying a hash down to ranges more natural for humans.

If you mean exactly as likely, no, because the number of possible hashes is not a multiple of $100$.  This is assuming all the hashes are exactly equally likely.  You can come very close just by taking $SHA256 hash \pmod {100}$  This will be within one part in $\frac {2^{256}}{100}$, which is a very small number.  If you want truly equal, check that the hash is in the range $[0,100\lfloor \frac {2^{256}}{100}\rfloor)$ and take it $\pmod {100}$  If it is above that, hash something else and try again.  Your odds of failing the check are very small, and your odds of failing twice are very small.
In the general case: if one wants a result in the range $0..n\text{-}1$ then use $\bmod n$ and discard if the output  $>n\lfloor  \frac {2^{256}}{n}\rfloor$ and try another input. This is called the discarding technique; it is commonly used to extract a number in a range from a (pseudo) random number generator.

You could simply just XOR all the bytes of the hash to one single byte (lets call it $b$ for now): $b = hash_0 \oplus hash_1 \oplus ... \oplus hash_{31}$. $b \in [0, 255]$. Calculate $b' = b / 2.55$. $b' \in [0, 100]$.


Can an Enigma-style cipher of sufficient complexity be considered secure today? Regarding the German Enigma machines, if I recall correctly, the reason they were defeated was because the Allies were able to generate a massive database of possible rotor settings, and because the day key was encoded twice in the beginning of each message.

Given that computers of today can simulate an Enigma-ish machine with an arbitrary number and complexity of rotors (for example, a rotor that only shows up every tenth character, or one that goes forward a different number each time), transmission errors are low, and binary data (not plain-text, but gzipped or base64'ed text) tends to beat frequency analysis, would it be possible to use an Enigma style cipher to encrypt data today, or would it be susceptible to similar pitfalls as the original Enigma cipher?

As a more general question, can other older ciphers be "re-invented" for computers and be viable in today's world?

Yes, if you are willing to throw enough resources at it. Only the most fatally flawed schemes cannot be rescued (in practical terms) given enough additional computation. Since you are even willing to enhance the rotor complexity, you could actually use it to implement a modern algorithm exactly. The ability for a rotor to advance "forward a different number each time" makes it sound like quite a programmable architecture.

But why would you want to? (other than it being a cool project of course) What you would end up with would certainly be many times less efficient than a modern cipher running on modern hardware. Additionally, an attacker who was able to develop custom hardware (FPGAs or ASICs) would likely have access to a far more efficient implementation than the defender.

An enigma machine is kind of like a physical-world one-time-pad -- the minutiae of the algorithm's physical construction are part of the algorithm itself, so the idea behind a system like that would be that Carol's knowledge of the algorithm in the abstract would not necessarily break the system for Alice and Bob -- Carol needs to get her hands the object itself to encypher and decypher.

That is a literal answer, I know; someone doubtlessly will fault my simplistic explanation w/r/t the actual Enigma cryptosystems' history.

(In some ways, the best cryptosystems are still like this: a bank's crypto standards and protocols are ideally robust enough that the nature of the implementation has to be kept secret... but the fact that you may have the key doesn't mean you can set your own balance arbitrarily -- for that you'd need a gigantic Flourinert-filled massive bank of vector units, or a tunnel-boring machine, or what have you.)


In English, are there any words which encrypt to other words under the Caesar Cipher? Are there any words in the English language which, when encrypted using the Caesar Cipher with any key, result in another English word? How may one go about determining which Caesar shifts are weakest in this context?

Actually, we have a four-way (that is, four words that will can be converted into any of the others with the right shift).  These words are:

ax, by, he, if

Other two letter words are:

am <-> my
at <-> pi
do <-> it
hi <-> no

We also have

the <-> max

I didn't do a systematic search for words over two letters; there certainly do appear that they are moderately plentiful

I've done a more systematic search over longer words; ignoring extremely obscure words, the best I found were

abjurer <-> nowhere
inkier <-> purply
fusion <-> layout
manful <-> thumbs
primero <-> sulphur
steeds <-> tuffet

(OK, 'tuffet' missed by 'obscure' criteria; I still liked it).

So, yes, there certainly are words can be be encoded into other words

Triplets and more of 5-letter with repeated letters
farre sneer toffs,
dolls groov jurry wheel,
aneer boffs hully narre,
cheer diffs jolly purre,
fizzy kneed loffe,

Triplets and more of 5-letter without repeated letters
ebola herod robyn,
gnarl taney xeric

Triplets and more of 6-letter words
alexir jungra whaten,
cleely pyrryl rattan vexxer
(As a bonus, the first one contains my name!)

7-letter shifts
abjurer nowhere,
bumpily unfiber,
chechen purpura,
fusions layouty,
primero sulphur,

8-letter shifts
corocoro wiliwili


mapping a 256 bit random number to a 3 bit number I am making a 2 player dice game that runs for n rounds. To create random dice roles im using a concept a understood from randao.

each user generates n sha3 hashes recursively of a random seed : e.g.

H[0] = sha3(sha3(seed))
H[1] = sha3(sha3(H[0]))
...
H[n] = sha3(sha3(H[n-1]))

During the nth round, we xor the H[nth] value of each user to be used as a random value for that round:random_result

My Question: What is the best strategy to map the 256 bit random_result to a 6 sided dice without completely botching the entropy?

Method 1 - Big Integer Math

Convert the 256 bit random_result to an unsigned big-integer. Divide by 6 and take the remainder. Your die roll result is the remainder plus one.

$6$ does not evenly divide $2^{256}$. It divides about $1.93\times10^{74}$ times with an exact remainder of $4$. That means values $1$-$4$ are over represented but by a negligible amount, since they're only represented once more than $5$ and $6$ over a gigantic range.

The bias towards low die rolls is much much much much less than $2^{-128}$, modern cryptography's slightly arbitrary threshold for the maximum detectable amount of bias in probability.

Method 2 - "Small" Integer Math

Let $M = 6 \times floor(2^{32} \div 6) = 4294967292$, ie. the largest multiple of 6 that fits into a 32-bit unsigned integer.

Split the 256 bits into 8 32-bit unsigned numbers. Find the first value one of those values less than $M$ and return one plus the remainder of its value divided by 6. This returns value has a value a range of values $[1, 6]$.

The reason for using values in the range $[0,M-1]$ instead of $[0, 2^{32}-1]$ is because the latter is not evenly divided by 6. Random numbers in the former range lead to a perfectly uniform distribution.

The probability of one 32-bit value being rejected is $p = (2^{32} - M) \div 2^{32} \approx 9.32 \times 10^{-10}$. All 8 are rejected with $p^8 \approx 5.66 \times 10^{-73}$ probability which is very unlikely. The exact probabilities happen to be $p = 2^{-30}$ and $p^{8} = 2^{240}$. Again, this is less than $2^{-128}$, so you shouldn't expect it to happen.

If it does fail 8 times you can derive more 256 bit numbers by hashing random_result concatenated with a counter. Or you can just use the final 32 bit value if the first 7 fail. The probability of that happening is small and the resulting bias is smaller.

The reason why I specify 32 bit numbers is for ease of implementation and for optimization reasons. There isn't any cryptographic relevance. 64-bit numbers and 64-bit division works as well, but it might not be available in some scripting languages and 32-bit division may be faster than 64 bit division on 32-bit and 64-bit architectures.

You could use 3 bit chunks. Then you could eliminate division entirely because 6 only divides 8 once. Rejecting an individual chunk happens with $1/4$ chance. Rejecting 85 times is less than $6.7 \times 10^{-52}$ or $2^{-170}$.

Method 3 - Seed a PRNG

This would be a really easy if CS-PRNGs were implemented in standard language libraries or popular add-on libraries with a similar API to those for non-secure PRNGs. Using standard PRNGs doesn't work for every application either because of statistical artifacts, small state space, predictability, or lack of a good seeding algorithm.

Edit: Avoid this method. I don't have a single example I can cite. There are too many ways it could go wrong.

No method has significant bias and therefore the entropy of the die roll has very close to $\log_2 6$ bits of entropy. (Assuming reasonably high entropy seed, like 128 bits of entropy. It doesn't need to have 256 bits of entropy.)

I don't think you want an answer based on entropy. I don't know what you mean by "botching the entropy" and I assume you don't know either.

For each method you can estimate entropy of the result by treating the entropy of the hash output about equal to $min(256, \text{seed-entropy})$ and calculating the probability of each outcome 1 through 6 by computing how many hash outputs map to that die-roll-value.

Since we already know the bias to be incredibly small we know that the die-roll result is about uniform. Since it is about uniform we know it has about the maximum entropy you can get out of 6 element discrete uniform distribution, $\log_2 6$.

This post has nothing to do with cryptography. Using of SHA does not automatically mean the question is related to cryptography. If one is developing a game that uses random generator based on a Geiger counter and an A-bomb, this doesn't mean the post is related to WMD or physics.

The most important thing in the OP is that each player gets equal chances. This has nothing to do with how (cryptographically) good the number generator is, how good the numbers are distributed, etc. Here is why.

A) Two players use the same device (smartphone, tablet, laptop, PC).
The both have equal chances to win, no matter how good the number generator is. This is obvious. If not, I'll answer your questions below.

B) Two players use different devices (smartphone, tablet, laptop, PC).
As Maarten Bodewes mentioned, a specific device and even specific OS version can be important. Numbers on one device may have better chance to win against the numbers on another device. Solution is easy: Make the applications on both devices communicate with each other. The applications should swap the generated numbers for each 2nd round: one round app uses its own randomly generated number, the next round it uses the number generated by the peer device, next round - own number, next round - again the peer number. Again, no matter how (cryptographically) good random generators on each device are, the players have equal chances.


Does CTR mode yield a PRF? Can the keystream generated by CTR mode be considered a pseudo-random function?

I give more information. Assume $f$ is a PRF. We define a function which takes 2 inputs, the desired length, and an arbirtrary value:

$F_l(r):=f(r\cdot l \cdot 1) \cdot f(r \cdot l \cdot 2) \cdot \cdots\cdot f(r\cdot l\cdot l-1)\cdot f(r \cdot l \cdot l)$ where $\cdot$ denotes the concatenate operation.

Is $F_l$ a PRF ?

It is not accurate to say that the keystream from AES-CTR is a pseudorandom function. However, it is a pseudorandom generator. Furthermore, the construction that you gave is close to working but it's unclear where the key fits in. I will therefore elaborate on what we can exactly say.

Let $F$ be a pseudorandom function, and for simplicity assume that the key length, input length and output length are all the same (and of length denoted $n$). We denote by $F_k(x)$ the output of the PRF on input $x$, with key $k$. Then, we have the following two facts:

$G(k) = F_k(0)\cdot F_k(1) \cdot F_k(2)\cdots$ constitutes a pseudorandom generator.
$F'_k(x) = F_k(0 \cdot x) \cdot F_k(1 \cdot x) \cdot F_k(2 \cdot x) \cdots$ constitutes a pseudorandom function. Note that in this construction, $x$ has to be shorter than $n$ to provide "space" for the counter.

You want the first case when you want a PRG using AES. Especially when you have AES-NI this is a very fast option.

You want the second case when you want a PRF with input length $n$ and a larger output length. There are a number of ways of doing this. Another way is $F'_k(x) = G(F_k(x))$ where $G$ is any PRG.

If $f$ is a block cipher, it is meant to be a PRP, not a PRF. However, the two are indistinguishable until about half the bit length, i.e. $2^{64}$ blocks for a 128-bit cipher like AES. (That's hundreds of exabytes.)

Since you consider the CTR mode as mapping a nonce to a keystream generated with that nonce, that is a pseudorandom function.

The concatenate operation you have in there is required. With addition or most other ways of combining $r$ and the block index you would get colliding inputs into the block cipher and it would no longer be PRF.