Inserting a backdoor into a cryptographic hash function I'm curious as to how a backdoor can be built into a hash function. What might it take the form of? What's probability of getting one that can be backdoored in a way that can actually undermine its security? Could this backdoor be asymmetric?

Here is a "backdoored" hash function:

Let $p = 2q + 1$ be a big prime of length $2048$ bits, such that $q$ is also prime. Let $a$ be an integer of order $q$ modulo $p$, i.e. $a \neq 1$ but $a^q = 1 \pmod p$; it can be shown that $a = 4$ is always a valid solution. Let $s$ be a (secret) integer between $1$ and $q-1$, and let $b = a^s \pmod p$.

Then define operation $\phi(x, y)$ such that input $x$ is a sequence of $2048$ bits, and $y$ is a sequence of $2042$ bits (not $2048$); the output is a $2048$-bit value:

Concatenate $x$ and $y$ and split it back into $u$ and $v$, such that $u$ and $v$ both have length $2045$ bits each: $$u || v = x || y$$
Interpret $u$ and $v$ as unsigned big integers, using some convention (e.g. big-endian). Note that both $u$ and $v$ are lower than $2^{2045}$.
Compute: $$z = a^u b^v \pmod p$$
$\phi(x, y)$ is the encoding of $z$ over exactly $2048$ bits (there again, using a fixed convention).

Note that $\phi(x, y) \neq 0$ for all $x$ and $y$.

Now that you have $\phi$, define a hash function $h$ as follows:

For input $m$, pad it with some "removable" padding sequence (e.g. a Merkle-Damgård compliant padding) so that the total length of $m$ is now a multiple of $2042$.
Split $m$ into $n$ blocks of $2042$ bits (denoted $m_1$, $m_2$, ... $m_n$).
Define $x_0 = 0$ (a sequence of $2048$ bits, all of value $0$).
For $i = 1$ to $n$, define: $x_i = \phi(x_{i-1}, m_i)$
Define the hash output $h(m)$ to be SHA-256($x_n$).

Let's see the security of this construction:

Preimages: for a given $t$, finding $m$ such that $h(m) = t$ implies, in particular, finding some $x_n$ such that SHA-256($x_n$) $= t$, so our function $h$ is at least as much preimage-resistant as SHA-256.
Second preimages: second preimages are a special case of collisions, so $h$ will resist second preimages at least as well as it resists collisions. Ideally we would want something better (i.e. resistance up to $2^{256}$ for second preimages, even though collisions can be found in effort $2^{128}$), but since collisions should be infeasible anyway, this is probably acceptable.
Collisions: suppose that $m \neq m'$ and $h(m) = h(m')$; $m$ yields a sequence of $n$ words $x_1$ to $x_n$, while $m'$ yields $x'_1$ to $x'_{n'}$. We suppose, without loss of generality, that $n' \geq n$. Then one of the following holds:

$x_n \neq x'_{n'}$ but SHA-256($x_n$) $=$ SHA-256($x'_{n'}$). We have found a collision on SHA-256.
There is an index $i$ such that $x_{i-1} \neq x'_{i-1}$ but $x_i = x'_i$. This means that we know integers of at most $2045$ bits $u$, $v$, $u'$ and $v'$ such that $(u, v) \neq (u', v')$, but $a^u b^v = a^{u'} b^{v'} \pmod p$. This implies that $a^{u-u'} = b^{v'-v} \pmod p$. Since $a$ and $b$ have order $q$ (greater than $2^{2046}$) and $u-u'$ and $v-v'$ cannot be both $0$, then $u-u'$ and $v'-v$ are invertible modulo $q$, and we can write $b = a^g \pmod p$ with $g = (u-u')/(v'-v) \pmod q$ (i.e. $g$ is the secret value $s$). We just solved discrete logarithm.
There is an index $j$ such that $n \lt j \leq n'$ and $x'_j = x_n$. By "rewinding" the steps this implies that either we find an instance of the previous situation ($a^u b^v = a^{u'} b^{v'}$ for $(u,v) \neq (u',v')$), or we have $x'_{j-n} = x_0$, which is not possible since $x_0 = 0$ and $x'_{j-n} = \phi(x'_{j-n-1}, m_{j-n}) \neq 0$.

Therefore, finding a collision on $h$ requires either finding a collision on SHA-256, or solving discrete logarithm modulo $p$. Since both are computationally infeasible (as far as we know), this function $h$ can be deemed "secure" as a hash function.

The backdoor is the knowledge of $s$. In all of the above, we used the $a$ and $b$ values "as is". The value of $s$ is not needed anywhere. However, if you know $s$, then you can compute collisions at will:

Generate two random blocks $m_1$ and $m'_1$. Compute the corresponding $x_1$ and $x'_1$.
Let $u$ be the first $2045$ bits of $x_1$, and $u'$ be the first $2045$ bits of $x'_1$.
Compute $k = (u-u')/s \pmod q$
If $k$ is less than $2^{2045}$, or greater than $q - 2^{2045}$, then you can find $v$ and $v'$ of $2045$ bits each, such that $v'-v = k \pmod q$, from which you can infer two blocks $m_2$ and $m'_2$ that match $(u,v)$ and $(u',v')$, respectively. You have your collision.
The condition on $k$ works with probability at least $1/2$. If you were unlucky, just try again with new random blocks $m_1$ and $m'_1$.

The above is thus a hash function with a backdoor. However, mind the fine print:

The backdoor is explicit. While the knowledge of $s$ is necessary to exploit the backdoor, everybody knows that it is there. Conversely, if you generate $a$ and $b$ as NUMS numbers (thus with $s$ convincingly unknown to everybody), then the hash function is "backdoorless" (but also useless).
When you exploit the backdoor, you produce two colliding messages $m$ and $m'$, from which anybody can recompute $s$. Thus, the backdoor is "one-shot".
The backdoor allows finding collisions, not preimages. A hash function designed to have a backdoor for preimages would need something else. Ideally you would use a one-way trapdoor permutation, but (to my knowledge) no such object is currently known, that would yield an output of suitable length (e.g. 256 bits).

The backdoor is possible. Imagine if we calculate the SHA256 of all combinations of a  256bit string, we already have a dictionary containing already a big subset of the SHA256 results. Once matched in the dictionary, the source can be replaced by the corresponding 256bit string. Now I agree and believe that bitcoin could be a conspiracy in that it helps to create SHA256 dictionaries!!! That could create messy conditions.


Zero knowledge proof of exponents Assume a cyclic group $G=\langle g\rangle$ of order $q$ and $g_1,g_2$ are two generators of $G$. Alice computes and sends to Bob

$m_1=g_1^{a_1}g_2^{x_1}, a\gets R $ is a uniformly random element

$m_2=g_1^bg_2^{a_2x_2}, a,b\gets R $  are uniformly random elements

A malicious Alice selects $a_1 \ne a_2$ and $x_1 \ne x_2$ while a benign one chooses $x_1=x_2$ and $a_1=a_2$.

Is there a way to prove to  Bob that in $m_1,m_2$: $x_1=x_2$ and $a_1=a_2$ in a zero knowledge manner? Recal that $a_1,a_2,b,x_1,x_2$ should be kept secret to Bob the verifier.

On assumption $x_1 = x_2 = x$ and $a_1 = a_2 = a$, introduce linear polynomials over $F_q$: $X(z) = x z + \eta_x$, $A(z) = a z + \eta_a$, $B(z) = b z + \eta_b$. Consider two group elements: $g_1^{A(z)} g_2^{X(z)} m_1^{-z}$ and $ g_1^{z B(z)} g_2^{A(z) X(z)} m_2^{-z^2}$. First element is a constant (zero degree in $z$) if and only if the assumption holds. Nothing unusual/new at this point yet. Second element is linear in $z$ if and only if assumption holds, and this might look like an extension of Schnorr protocol. Now evaluate polynomials at some $z$ chosen as a challenge and invoke Schwartz-Zippel lemma for a bound on soundness error. At last, Alice must not be able to solve DL in this group (computational soundness) and must not know linear relation with $g_1$ and $g_2$ (setup).

Aren't you curious!

I don't fully grasp why you designed your constraints the way you did. Either

you were given m1 and m2 and you wonder if it's possible to verify a1 = a2 and x1 = x2 in a ZK manner. In that case I won't answer your question but suggest looking towards Schnorr's scheme(s).
Or I can imagine the following scenario:

P knows a secret x1. In a first phase of ZKP (signing in), P proves knowledge of x1 with a witness computed from some random element a1.

On later notice, before executing some important actions, the verifier/server V would like to know if P isn't being a victim of session hijacking/XSS/CSRF or whatever. So it'll ask again for a ZKP of x2.

Of course you want x1=x2 to assert P still knows the secret/pass and in the same way, P will commit to some certain value derived from some random element b.

But, in case the password has been compromised/ could be retrieved in some way, you also want to assert that P still knows the random element a1, used in the first ZKP.

In that case, P can first do a ZKP to prove knowledge of a1, and another to prove knowledge of x.

Schnorr's scheme uses the discrete logarithm as you do, to prove knowledge of exponents. Except there's only one generator.

Please provide some feedback, I'm not at all satisfied with my "answer" and I'm not confident in my precise understanding of your question (do want a ZKP of exponents ? Or a ZKP for this particular setup ? Why this setup ? Are you forced to work with such constraints or does this reside in some bigger picture ? I like context :) Or maybe you're just curious ?)


nonce of AES-GCM in SSL It seems that the nonce of AES-GCM in SSL has 3 parts:

salt, 4 bytes, generated in handshake, not changed in whole session
nonce_explicit, 8 bytes, chosen by the sender and carried in each SSL record
inner_counter, 4 bytes, used in AES-GCM internal

Is it possible to use a more simple method to construct the nonce:

generate a 16-bytes IV in handshake
use this IV as counter for each cipher block in the whole session life, ignore SSL record boundary

then the sender need not carry nonce for each record, saving the bandwidth.

===

I read the RFCs again and found I misunderstood something.

Let me make the question clear.

AES-GCM algorithm: require the nonce is distinct.
AES-GCM specification [RFC 5116]:

It gives an recommended format (not required):

" When there are multiple devices performing encryption using a single
key, those devices must coordinate to ensure that the nonces are
unique.  A simple way to do this is to use a nonce format that
contains a field that is distinct for each one of the devices, as
described in Section 3.2."     [ Fixed + Counter ]

" In some cases, it is desirable to not transmit or store an entire
nonce, but instead to reconstruct that value from contextual
information immediately prior to decryption."
[ Fixed-Common + Fixed-Distinct + Counter ]
It is defined for protocols that uses record. I missed this before:

"Each AEAD algorithm MUST accept any plaintext with a length between
zero and P_MAX octets, inclusive, where the value P_MAX is specific
to that algorithm.  The value of P_MAX MUST be larger than zero, and
SHOULD be at least 65,536 (2^16) octets.  This size is a typical
upper limit for network data packets."

QUESTION: However if we ignore the specification, is it possible to treat the whole SSL session as a stream (ignore the record bondary), and use only one nonce (and use the nonce as counter) ?

AES-GCM in SSL [RFC 5288]: it uses the recommended format.

QUESTION: since it generates master-secret in each SSL session, it would not hanppen that "multiple devices performing encryption using a single key". Why does SSL use the recommended format (the Fixed part)? What's the function of 'salt'?

I know that since specifications of AES-GCM and SSL have been defined, we should just follow it.
I just wonder why it was defined like this.

Besides, maybe we could define an SSL-extension, so that the SSL client and server could use record-seq as nonce_explicit, and do not send it with record.

This is a trickier question than you might think.

The first thing to note is that your scheme doesn't respect record boundaries. TLS 1.2 seems to have been rewritten to use a random IV for CBC mode encryption for each record (to avoid certain attacks). It is therefore likely that the idea of TLS 1.2 is to respect record boundaries.

The document "AES Galois Counter Mode (GCM) Cipher Suites for TLS" - RFC  5288 - mentions "An Interface and Algorithms for Authenticated Encryption" - RFC 5116. This document specifies the use of a 4 byte salt and 8 byte random. That means that the nonce is 12 bytes total, consisting of the persistent part of 4 bytes and 8 bytes random. The GCM specification strongly recommends a 12 byte (96 bit) nonce/IV. This specification in turn is based on GCM ESP, RFC 4106, which specifies the use of GCM for IPsec. So in general the use of GCM in TLS 1.2 seems to follow previously established standards.

The specification of a per record random (explicit) part is of course in line with the cipher suites that use CBC based encryption. In this case however the IV only has to be 8 bytes instead of 16, which saves some 8 bytes as overhead. That's still 8 bytes more than your proposed scheme - which, again, doesn't respect record boundaries - but it's better than CBC.

Notes:

If you would change to a fully implicit nonce you should still keep to 12 bytes to keep within the GCM specifications. If you would specify 16 bytes IV then the GCM specification requires an additional GMAC. There seems to be no way of specifying a 16 byte counter to be used; the 4 least significant (rightmost) bytes are set by the algorithm itself.
Related, in your scheme it is impossible to use a GCM API that only allows 12 byte nonces (i.e. without the counter included in the IV). You would need some way of keeping track of the counter and a method of instantiating GCM with that full 16 byte counter.
In your scheme it would be impossible to parallelize encryption/authentication and decryption/verification unless you had a way to pre-compute the record payload.

In conclusion, although your scheme could work (it's more efficient and isn't likely to be insecure), it doesn't respect record boundaries and it would put additional requirements on the GCM library. Finally, it would not follow pre-established standards for the use of GCM in a transport protocol.

In TLS 1.3 (under construction at the time of writing) it seems that the record number may be used instead of the explicit random, which would require less overhead in the record header and less calls to the random generator.

Note that Figure 2 in RFC 5116 "An Interface and Algorithms for Authenticated Encryption" includes the counter in the nonce specification. I've made a report for an ERRATA on this as the GCM specification and the ESP documents both treat the nonce as a 12 byte value (so without the counter).

I just quickly read the TLS specification and the document that introduces GCM into TLS.

It is stated in the definition of GCM-ciphersuites that a 12-byte nonce is supplied (8 bytes per packet and 4 bytes from the handshake, as you correctly stated).

First I'd like to say: Very often there's a (very good) reason why a decision was made (like here) in something such important as TLS.

Technically your approach would work. (although not accepting record boundaries isn't nice. Maybe cut the stream at the end of a record and increment counter)

Now I'll tell you why TLS doesn't go with something like you proposed but rather with this system:
TLS also has to support CBC mode. (for legacy reasons :-( )
And as the protocol must be very similar for all ciphersuites (no matter wether CBC / GCM / ...) it must provide the most robust IV it can provide (as CBC strongly relies on unpredictable IVs and not just unique ones).

Now let's assume your scheme to work with CBC. You'd ignore record boundaries and hence (in most cases) the delivery and verification of a message has to wait until the next message was delivered, so it's common practice to give each message / record an own IV. But even a continous keystream isn't nice. It introduces dependecies between the messages you want to avoid. You want to be able to read any message if you know the key. If you'd make the IV secret you'd just have an extended key, which isn't a security risk, but might bring practical issues. Now the salt seems to be used to guarantee that IVs are unpredictable (as required by CBC), as an attacker can't know the salt in any case. As 32-bit randomness are fine to make an IV unpredictable the other 64-bits (to 96-bits) are generated separately (at random) for each message. (making it even more unpredictable) However GCM-TLS-Ciphersuite-Documentation allows usage of a counter in TLS (it was for packets I think) to be used as the 64-bit part, so we are back at your proposal which is (somehow) in TLS.

The reason I gave here are only good guesses. To find the real reasons behind all design decisions of TLS one would have to dig through thousands of mails in the archive of the IETF.


Is perfect forward secrecy (PFS) possible without public key cryptography I have an understanding of PFS as used in most key agreement algorithms as well as things like TextSecure protocol and ratchets. My undestanding is that PFS is not possible without asymmetric (public key) cryptography. Am I missing something? Can PFS be achieved with symmetric cryptography and preshared keys only.

Yes, perfect forward secrecy is possible using symmetric primitives alone.

Take for instance a set of one time pads:

Alice generates two identical stacks of one time pads and hands one of the stacks to Bob.
Alice encrypts a message with the first one time pad and then passes the ciphertext to Bob.
Bob decrypts the message with the first one time pad and then both Alice and Bob destroy the first one time pad. So long as all copies of the one time pad are destroyed the ciphertext is now undecipherable.
The next message is passed using the second one time pad and at the conclusion of that protocol round all copies of the second one time pad are destroyed. And so on.

This basic protocol achieves perfect forward secrecy.

Of course it's likely not a practical protocol for many applications as, for instance, it requires secure advance exchange of a set of one time pads and the message length is limited by the length of a one time pads which much be agreed in advance. Nevertheless you can start from this model and apply some basic cryptographic improvements such as:

replace each one time pad with a key and a stream cipher so now we just need to exchange a set of keys
replace the set of keys with a single key and a one way function to obtain the next key so now we just need one key (and of course you simply destroy the previous key each time you derive the next key).

It's not difficult obtain a relatively practical scheme assuming pre-shared keys. The security of this construction is not too difficult to bound (How secure is the stream cipher? How secure is the one way function?).

Technically no....

Diffe-Hellman isn't a public key algoritm but it does allow for key exchange. It is acually what is used in PFS... Public-key is not used to establish shared keys.


Is it possible to use crib drag on base64 cipher text? I am pretty new to the cryptography scene but I wanted to know if it is possible to use crib dragging on cipher text which doesn't contain words? This data would be encrypted using the same key with a one time pad and the data is encoded using base64 before it is encrypted.

For example,

key = [1, 2, 3, 4]
message1 = [C, B, D, K]
message2 = [H, K, L, U]
encryptedMessage1 = [D, D, G, O]
encryptedMessage2 = [I, M, O, Y]

(yes I know this isn't exactly base64)

So if we XOR these two encrypted messages together we may or may not get CBDK or HKLU based on the word used for cribbing and even if we do get one how can you verify that it is the correct message?

Again total noob and trying to teach myself. ;)

Yes, it is possible to use crib dragging. It is easy to prove this: you could just search for the base 64 encoded version of the crib. This would work even if you would simply use search for a recurrence of the crib every 4 characters because that's the amount of base 64 characters that are needed to encode 4 bytes. So the chance of success would be diminished, but it is still possible.

It is also possible to perform crib dragging over byte boundaries in base 64, but then you may need to check for multiple possibilities that could be valid. So the chance of success is much lower if you start in the middle of a base 64 character.

You can of course guess the characters before the crib itself as well, so the extended crib can still be moved across the boundaries. You'd need to guess up to 3 characters though.

No, it's really not base64 encoding :) If the key length is egal to the text, it's an one time pad encryption

  how can you verify that it is the correct message?

To answer your question, you can add for example at the begining of the message the sha-md5-crc32 hash of the clear text. The hash would be of course also encrypted.

@Stephen Collins: as the name implies, OTP is only used once. The mask is used only to decrypt a given message and cannot decrypt any other one. Xor gives an offset value to a specific character, if you use this same value on another character it will return you anything.


Generate random number which should depend on key i want to generate random number for example from [1..100]. The algorithm which would generates random number should work similarly like a "Linear congruential generator", like this:

$X_{n+1}≡(aX_n + c)\ (mod\ m)$

Where:
$c$ - increment should be something like 98979817
$a$ - should be used for security and should be great number
$X_n$ - initial number

However, I can't use this formula because my $m\ (mod m)$ is 100 so it's $m < c$ and $m < a$. While it should be $m > c$ and $m > a$.

Maybe there is something similar which is more secure than this?

Any Pseudo Random Number Generator using a Linear Congruential Generator, and no cryptography, is going to be unsafe, or at the very least unsatisfactory, per the criteria in our FAQ. Likely, a skilled adversary would be able to predict future output from some amount of past output with moderate work; at best, that won't happen, but there will be no sound argument that it is not possible. There are many more or less difficult to read papers making that point. A recent question, another there, further illustrate this. If the more secure requirement is to be taken any seriously, it is best to forget the LCG entirely, and use cryptography.

There should be three steps in a secure "Random Number Generator depending on a key" producing an output sequence uniformly distributed on the integers in $[1…100]$:

Stretching of the initial key. The purpose is to make brute force search of the key infeasible, or at least costly. That is superfluous if the key is already both wide enough (say 120 bit or more; 256 is aplenty) and chosen uniformly at random; in almost any other case, including when a human is expected to remember (or worse choose) the key, a deliberately slow transformation of that input is highly recommended. In many cases (notably: the combination of multiple users and use of password), the initial key should be salted while stretched. The standard building block for these functions is a Password-Based Key Derivation Function. A common one is PBKDF2; Bcrypt is much safer; the current state of the art is Scrypt.
A Cryptographically Secure Pseudo Random Number Generator, or equivalently the Keystream Generator of a secure Stream Cipher. We'll feed it the (possibly stretched) key (in the input named seed or key), and then it will output on demand practically any number of random-looking bits that we may want. The design of that cryptographic primitive strives to make that output computationally indistinguishable from random by an adversary not knowing the seed. There are a plethora of CSPRNG and Stream Ciphers to choose among, and the best choice depends on context. If it must be fast on any modern CPU, Salsa20 comes to mind.
Post-conditioning to obtain outputs uniformly distributed on the desired output interval $[u…v]$, here $[1…100]$. One simple suitable technique (slightly wasteful, but that does not matter since the CSPRNG is likely fast) is to:

Find the lowest integer $w$ such that $2^w\ge v-u+1$; here that is $w=7$, since $128\ge100$.
Obtain $w$ bits using the CSPRNG, forming an integer $r$ in range $[0…2^w-1]$, until $r<v-u+1$ (otherwise, discard $r$ and repeat this step).
Output $u+r$, and proceed to the previous step as needed to obtain more output.

If being simple and based on a LCG is important, and being secure is pointless as long as the output is good enough to pass some simple statistical test, the following procedure builds a LCG and post-condition its output (I assume the range $[u…v]$ has width no more than about $2^{16}$).

Choose $m=2^{64}$ (or a convenient higher power of $2$), $a=3141592621$, $c=1$ (this conforms to more detailed advice in TAOCP Volume 2, section 3.6; except that I kept $a$ unchanged, rather than taking the risk to scale it with $m$); the C or C++ type unsigned long long, if available, is suitable for implicit reduction modulo some appropriate implementation-dependent $m$.
Find $w$ from the interval $[u…v]$ as above (here $w=7$ for $[1…100]$).
Set $X$ to the key truncated to the bit width of $m$ (Repeat: security is out of scope! But still, it does not harm to feed other key bits in $c$, as long as it is forced to be odd).
Set $X$ to $a⋅X+c\bmod m$; in C that's X = a*X+c;.
Form $r$ in range $[0…2^w-1]$ from the $w$ high bits of $X$; in C that's r = X>>(W-w); where W is the bit width of the unsigned integer type chosen for X, and $m=2^{\mathtt W}$.
If $r\ge v-u+1$, proceed to step 4.
Output $u+r$, and proceed to step 4 as needed to obtain more output.

For your purposes the following should be adequately secure:
Choose $m$ as large as is convenient for the data type you're using.
Choose a random odd $a$ and whatever $c$ you like.
The sequence of successive X values will look random. To get your random number in the range 1 to 100 inclusive, calculate $1+(X_n \mod 100)$


Could a larger block size increase the security of the block cipher? I want to know if a larger block size increase the security of the block cipher?

TL;DR: a larger block size won't help to make the block cipher itself more secure, but it can be used to make the schemes using the block cipher more secure.

The block size basically determines the number of possible permutations: the possible ways to combine all the possible plaintext blocks with the possible ciphertext blocks. The number of permutations grows much faster per bit of the block size than the number of possible keys from the key size. In that sense it is unlikely that a larger block size will do much for the security of the cipher.

Modes of operation however do rely on the block size for other purposes. For instance, the counter size of AES-CTR is defined to be the same size as the input block size. That counter usually consists of a random nonce and a counter part, for instance 64 bits for the nonce and 64 bits for the counter. However 64 bits is not that much for a nonce; as the birthday problem applies you can only encrypt about $2^{32}$ ciphertext before the counter could repeat. Now this isn't a huge problem, but it would be avoided with a block size of 256 bits (or, indeed a tweak, or both).

Specific constructions could also require a larger block size. For instance a hash function generally relies on large state. To go from one large state to another a block cipher could be used. Obviously it would need to have a large state and a large block size itself. There are other ways to do this with a cipher with a smaller block size but it won't be as efficient.

Ceteris paribus.  All things being equal then clearly the block size affects the cipher security. That's why we're not using 32 bit Skipjack ciphers any more.  It increases the brute force effort to break and reduces the probability of block collisions.  Incidentally the same is true for hash functions.  This issue that slightly clouds the block width comparison is that a newer and wider block cipher tends to be a rewrite from scratch.  So AES <- DES and a direct comparison cannot easily be made.

A slight caveat though is that a cipher with a 2048 bit block size appears be just as impossible to brute force as a 256 bit cipher.  This begs the question when is the block width adequate?  AES' 128 bit block width seems to be holding up presently to attack, although it's anyone's guess how long this situation will last.

And now the cynicism and speculation.  AES' owes it's existence to US government policy.  It's unlikely that a 2048 bit cipher will be developed within the foreseeable future without that same governmental support.  It's not inconceivable that a new competition could be launched for a server level only cipher based on a 2048 bit block width.


How can I create an RSA modulus for which no one knows the factors? It's easy to create an RSA modulus where almost no one knows the factors: for example, I can generate two 1024-bit primes $p$ and $q$ and set $n=pq$.  If I publish $n$, I will be the only person in the world who knows, or can know, $p$ and $q$.

The (now defunct) RSA Factoring Challenge numbers were generated like this:

First, 30,000 random bytes were generated using a ComScire QNG
hardware random number generator, attached to the laptop's parallel
port.
The random bytes were used as the seed values for the
B_GenerateKeyPair function, in version 4.0 of the RSA BSAFE library. The private portion of the generated keypair was discarded. The
public portion was exported, in DER format to a disk file.
The
moduli were extracted from the DER files and converted to decimal
for posting on the Web page.
The laptop's hard drive was destroyed.

But all of this leaves me feeling unsatisfied because--despite claims that the laptop's hard drive was destroyed--I still worry about insiders who know the factors.

Is there a method which can generate an RSA modulus so that no one knows the factors?  This might seem a ridiculous question, but we do know composites of unknown factorization.  For example, many of the largest Mersenne composites have unknown factorizations (wikipedia).

I would be fine with a multi-party algorithm and an assumption that players do not collaborate.

One practical method: use a Java Card Smart Card. Load a trivial Java applet, made with the free Java Card Classic Development Kit, that generates an RSA key, and outputs the public modulus. Then either destroy the Smart Card, or zeroize it.

The applet will be so simple that it can be convincingly audited, either from source or from the tiny, well documented Java Card bytecode (RSA key generation itself is a few bytes in that, invoking the method built into the Java Card runtime supplied by the card/micromodule manufacturer, possibly calling a library supplied by the chip manufacturer). Some Java Card models are security-certified with similar usage and security demonstration in mind (though it might be hard to purchase these certified models in small quantities, and next to impossible to obtain their full documentation).

A difficult problem: convince oneself/the audience that what's loaded in the Java Card is really the audited applet, and more generally of the integrity of the gear handling the Java Card and the result it produces. In key ceremonies for Smart Cards where the integrity of the gear is paramount, it is common to install a bare OS to a virgin PC without network access from original optical media in front of the customer, but the Smart Card readers might not be scrutinized, even though that equally matters.

Also, there still is a risk that the card developers goofed at writing the RSA key generator. There are precedents:

section 6.1.1 in Petr Švenda, Matúš Nemec, Peter Sekan, Rudolf Kvašňovský, David Formánek, David Komárek, Vashek Matyáš: The Million-Key Question — Investigating the Origins of RSA Public Keys, best paper of Usenix Security Forum 2016. This one is a Java Card (but not an audited one that I could identify from its traceability data, which I obtained from the lead author).
Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, Nicko van Someren: Factoring RSA keys from certified smart cards: Coppersmith in the wild, in proceedings of AsiaCrypt 2014. Some part of it appears to be FIPS 140-2 certified, but likely the certification was abused so badly as to become meaningless.

Ah, and of course, it is hard to convince others that the number you exhibit was produced in that way. Not such a good answer..

This may be... hard.

Make an algorithm for this:

  Take a PseudoRandom Number Generator.

  Ask the computer to get $2^n$ such numbers, $a_1,a_2,...,a_{2^n}$ where $n$ is also a random number, with $2\leq n \leq10$ and $\log{a_i}=\log{a_j}$ .

  Divide those numbers into two halves, each having $2^{n-1}$ elements.

  Add all numbers in each half.

  Multiply the two numbers to get $n$.

This is very unwieldy, but secure.
I think.


Is it possible to generate a 6-digit number using 256-bit encryption? Reading through some documentation on a piece of software, it claims that a 4-6 digit number is created using a 256-bit encryption process for the purposes of access control. The whole process works as follows:

A 4-6 digit "start code" (key?) is chosen by the user and programmed into the client software and into the management software as a new "client software record".
Using the management software, a new access code that will open the client software can be generated by selecting the previously created client software record.

It is clear that the 4-6 digit start code is used to introduce some form of uniqueness to each instance of the client software, and that start code is used to generate the resulting access code which when entered into the start screen of the client software, will allow the software to open.

My question is how could that process be using 256-bit encryption?

One thing which is clear is that there are only 10^6 possible combinations to open the client software thus in theory it wouldn't make much difference whether encryption or hashing is used to generate an access code.

Why such as number only access control is used is beyond the scope of this question. I am aware that this is pretty poor access control for software. Am just intrigued by the claim of 256-bit encryption.

I believe the claim of using "256-bit encryption" is primarily being done for marketing purposes.

Despite the best efforts of industry experts there are many people with a limited understanding of cryptography, and they associate "bigger key sizes" with "better security."  (While this is generally true, it's a very narrow view that excludes many important security factors; besides, key size differences become almost trivial beyond a certain threshold.)  Sadly, that's a surprisingly large number of people.

Marketers know the money coming from people who don't understand the details spends just as well as money from people who do.

So what can you do about it, or what should you do about it?  Perform a security analysis reviewing what the product is capable of, given the facts you have.  Is six digits enough to stop people from guessing in the time limit given them?  Do they have a three-tries-then-lockout mechanism?  What is the value to you of the system they're protecting?  What is your risk exposure should it be violated?  Are there other access controls in place, and should there be?

Step 1: Contact the software provider or author. Say you want the exact details on how all these codes are generated.

Step 2: Wait for their reply. This will be something like: "That's proprietary/secret information, we can't release it to you."

Step 3: Conclude they're clueless about security [1]. So their security can probably be broken in 15 minutes by any competent person who chose to put in the effort!

[1] https://en.wikipedia.org/wiki/Kerckhoffs's_principle


Multiple NTRU public keys for the same private key? An NTRU public key is generated essentially by multiplying the inverse of a polynomial $f$ by a polynomial $g$. The polynomial $f$ is the private key; $g$ is discarded.

My question is: Is it insecure to hand out multiple public keys for the same private key, i.e. using the same $f$ but different $g$'s?

According to current knowledge, handing out multiple public keys (with independent numerators) for the same private key $f$ is not insecure, as long as the parameters are instantiated appropriately.  There is some small loss in concrete security, but nothing like an efficient attack is known.

The standard NTRU lattice for just one public key $h$ is \begin{equation} L_h = \{ (u,v) : u \cdot h = v \pmod{q} \}, \end{equation} and $(f,g) \in L_h$ is a lattice vector that is "unusually short" relative to what the Gaussian heuristic predicts for a "random" $2n$-dimensional lattice having the same determinant $q^n$ as $L_h$.  Essentially, this gap controls how hard it is to find the secret key using lattice reduction (smaller gap means harder to break).

With multiple public keys $h_i = g_i \cdot f^{-1} \pmod{q}$ that share a private key $f$, we can define a similar lattice
\begin{equation} L = \{ (u, v_1, \ldots, v_t) : u \cdot h_i = v_i \pmod{q} \}.
\end{equation}
This $(t+1)n$-dimensional lattice has determinant $q^{tn}$, so the Gaussian heuristic predicts a minimum distance of $\approx q^{t/(t+1)}$, yet
 $(f,g_1, g_2, \ldots, g_t)$ is an "unusually short" lattice vector in $L$.  The gap is typically larger than in the single-key case, making it concretely somewhat easier to find the secret key.  But as long as the gap is not huge (e.g., polynomial in $n$) and the dimension is large enough, algorithms like LLL/BKZ won't be able to find the secret key in any feasible amount of time.

Another reason is that, informally, from one public key $h$ we can generate many public keys $h_i$ having the same secret key, by multiplying $h$ by random small $g_i$.  The resulting public keys won't be distributed like "true" keys, nor will they be independent, but this at least give some intuition why it's hard to find the secret key from many public keys.

It's worth remarking that there's a close similarity here to LWE, where one can get an unbounded number of noisy random inner products with a secret vectors, and the number of such samples does not have a major effect on hardness (though it does have some).

According to this paper, two public keys are insecure if the corresponding private keys, $f$ and $f'$ are too close to each other*. It follows that public keys are insecure if $f=f'$ regardless of the $g$ values.

* $\|f-f'\| < min(\|f\|, \|f'\|)$


Why does CBC decryption with a wrong IV still give readable results? While developing some code that uses the .NET AesManaged algorithm, I made some mistakes but was surprised at the results.

My encryption was correct.  I was generating a random IV block and writing it to the file (without encrypting the IV).  Then I was encrypting the plaintext and writing it.

The decryption was wrong though... instead of reading the first block from the file an using it as an IV, it was just using a random IV and decrypting everything.  The first block came out gibberish but the 2nd (and subsequent) ones were decrypted properly!  Why would this be?

And even weirder... when I tried to fix it by encrypting the IV in the encryption code (instead of writing the IV unchanged) the decryption result was the same!  (gibberish then correctly decrypted blocks).

Although I eventually fixed my code, how do these results make sense?

This is what ciphertext block chaining is about - each plaintext block is XORed ("chained") with the previous ciphertext block before encrypting (and after decrypting).

The initialization vector then takes the place of the ciphertext block before the first block (since there is none).

So, mistaking the initialization vector as a ciphertext block does nothing wrong for decryption (other than that you'll get an additional garbage block of plaintext).

You did observe (part of) the malleability property of CBC: One can change the start of the ciphertext (including the IV), even prepend/remove blocks, and the result is still a valid ciphertext, and the plaintext block after the changed one will be changed in a predictable way.

This is used for some attacks on protocols using CBC, when they allow a chosen-ciphertext attack - search for the padding oracle attack, for example.
For this reason, you always (not only for CBC) should use authentication together with your encryption, for example in form of a MAC around your ciphertext (including the IV).

Can't you just put random text in the first 16 bytes of your plain text, encrypt using a random IV, then during decryption use any IV and just throw away the first 16 bytes of the result?


One Time Pad Low Bandwidth Doubt from the book Following is a sentence from the book "Cryptography and Network Security - Principle and Practices" by William Stallings [Fourth Edition]
Sentence -
"
... the 'one-time pad' is of limited utility, and is useful primarily for low bandwidth channels requiring very high security.
"
Can anyone please elaborate on low bandwidth , because I thing low bandwidth will make transfer of the key and ciphertext slower instead they should use high bandwidth isn't?
Book Link - http://uru.ac.in/uruonlinelibrary/Cyber_Security/Cryptography_and_Network_Security.pdf
Page Number - 79/983

For an OTP you need to distribute the OTP key stream out of band. That can be performed by e.g. bringing a data storage device to the other side. Let me explain.
The problem with an OTP key stream is that you cannot transport it over a secure transport channel without removing the claim of theoretical security. Similarly, you cannot simply distribute a seed for a PRNG, because the PRNG would have similar security as a stream cipher.
Because you cannot distribute an OTP without compromising its security it is limited to the amount of information that you distributed out of band.
How limiting this is depends on the application of course. Nowadays you can store several TB in a tiny flash disk. That's enough for many, many hours of video. Still, securely distributing such a disk would be troublesome; just sending it by regular post is obviously not a good option.
Another option would be to use quantum key distribution. However, implementations of quantum key distributions are not necessarily secure, and the speed may be a severe limit.
Fortunately, we've got a lot of ciphers that we don't know how to break, key ratchets and whatnot to give us practical security even for much smaller key sizes.

Let me re-quote:-

" ... the 'one-time pad' is of limited utility, and is useful primarily for low bandwidth channels requiring very high security. "

This raises four issues that divide opinion:-

What is low bandwidth? No one knows, yet OTPs are making quite a resurgence these days for things like secure phone communications and video conferencing systems, both detailed in this answer. That seems fast to me, and they're just getting faster every day. Channels already operate at Mbps. The raison d'être of a OTP is for ultra secure strategic communications, typically in textual form. It is not to encrypt 8K UHD movies. That is your limited utility.

The security is the highest theoretically possible given a correct implementation.  One time pad material is securely transmitted theses days in-band using quantum key distribution networks (QKDNs). See this answer as to how, and how theoretic security is maintained based on quantum physics. I have to reiterate, please do not conflate the theoretical security of a OTP/QKDN with how it can be attacked if someone is looking over your shoulder.  That's a common denominator that undermines all cryptography (AES etc.) not just OTPs/QKDNs.

There is an every growing market for OTPs distributed via QKDNs. Many organisations, nations and trading blocks are convinced that they're suitable and practical. This is a OTP distribution device machine thingie.

OTPs were deemed suitable for use in three world wars, which you can explore here and here.

And yes, you can pre-distribute OTP material on a flash drive provided you have  a means of making the random numbers in a truly random manner. That's not hard, and getting easier. And yes too, you can send it in the post provided you do it before your operation gets onto the radar. A meeting would be preferable, but that's almost implicit as if you're going to exchange ultra secure material, you might want to meet the recipients.


How to know which key was used for an AES encryption? I am starting a project where several categories of sensitive data have to be accessed within a table. Based on his role, a user can see clear text columns (not encrypted), accessible columns (decrypted for his role), and can't see the content of other columns (encrypted).
This implements segregation of duty (for example) :

Database administrator can only see clear text columns
Person A can only see person's details to validate data
Person B can only see revenue details to build statistics

Role management rules dictate which role uses which key, and keys are highly protected. But after a few years of people moving and roles adapting, how can I make sure the system still knows which key was used when?
I can imagine two solutions:

Build a solid log of keys usage
The key signature hash is present in the cryptogram

Even though I don't think one can guess the key from the hash, I'm afraid this would introduce a weakness...
How would you proceed?

I agree with your solution. Log that stores info about who and when is active with a particular role. You could use ID or name, but password hash seems ideal, to see when user changed the password, to not to show him his old data that he will try to decode with a new password. SHA3 is considered secure. If user makes a password and then sends SHA3(password) - there is no way for you to get the password out without brute force.
Could use SHA3(company name + password) to avoid easy guessing of known password hashes from the table. If someone gets the table, makes pre-calculated table with values like sha(12345) and scans the whole database, he is likely to find some matches.
Could also use SHA3(username + password), to avoid search for dublicates if the whole database is leaked or to show that even you cant search for dublicates. In addition to the previous bonus.
Could go further and use SHA3(your own secret + SHA3(username + password) to protect from all sides, leaked database and your own actions against the users. That is, user sends SHA3(username+password), but on your server you make SHA3(your secret+what user has sent you), and only that becomes public and is written in the database. One more way to make it better is a long generation time on the user side, like 100 or 100k steps of SHA3. But this is questionable for weak devices. Reason for this is mainly to prevent you to quickly crack users passwords with a dictionary, since you know how their response is calculated and what is there. One step further is to use algorithms that are hard to speed up on asics or GPU. https://en.m.wikipedia.org/wiki/Argon2
TLDR: use SHA3(your secret + 1000 chained steps of SHA3(username+password)), OR SHA3(your secret + argon2(SHA3(username + password)). Check if mobile device can handle it under 1 second.


Are there reasonably secure online voting implementations e.g. for student council elections? Assume a university want to elect the student council. This was done via paper ballot and there is a need to reach more students for voting, so electronic voting is on the table.

While researching existing solutions I came across Helios: helios voting and agora voting

Both seem to implement somewhat peer-reviewed schemes to do a online vote, but my impression is that the devil might hide in the details.

Has anyone here experience using these schemes?
We plan to implement such an online voting scheme and would authenticate the voters via the university LDAP. Which cryptographic obstacles or security problems could we face?

In short, my answer is no; keep paper ballot, they have essential virtues unmatched by electronic substitutes; in particular, giving voters confidence that the result of the vote is not grossly manipulated.
Full disclosure: I co-founded a (French) association towards citizen oversight of voting means, essentially opposing electronic voting for political elections. I take some pride in our contribution (however little) to an observed pause in the deployment of electronic voting machines in France since 2007.
Electronic voting has two different meanings:

voting in polling stations using dedicated electronic voting machines;
voting remotely by electronic means such as mobile phone, web browser.

The question seems to be about 2, and I'll focus on that. A major problem is that it does not propose any means to discourage vote selling or voting under duress. In most proposed systems, handing over one's credentials to vote (perhaps: during the closing of the polling time-frame) will do the trick.
Contrast with the traditional voting system used for political elections (in France, and many countries with a long history of voting, thus a long history of voting fraud, and fixes to the voting code to fight that). Voting takes places according to procedures carefully designed to discourage vote selling and threats to vote in some prescribed way, by making it hard (and prohibited) that anyone but the voter knows how the vote was cast (that goal is not reached for mail voting, instead this is purposely kept marginal by requiring formal prior declaration to police that normal voting can't be performed for some reason, like traveling). Towards that goal, complex measures have evolved over time:

generally, making it illegal and difficult to act in any way such as showing how one voted, or transferring one's right to vote to another person (voting requires an official ID with photo, in all but very small towns).
requiring the insertion of paper ballot materializing the vote in an opaque envelope in a voting booth ("isoloir" = isolating device) where no one but the voter is allowed;
making paper ballots with a distinctive sign invalid (and not counted); this is a countermeasure to the practice of marking the paper ballots handed for vote under duress/pay with a distinctive sign, so that the bribed/intimidated voter can fear that if s/he does not use that paper, it will get noticed at vote counting;
often, making the paper ballots available by multiple means (at the polling station, and by mail), so that voters can be seen not grabbing a ballot from the stack X at the polling station, but still actually vote for X by using a paper ballot for X that they brought secretly (ticking a choice with a pen would be superior to paper ballots in this regard, but may bring back the previous problem; also, separate availability of paper ballots at least helps the reading impaired).

Another issue with both forms of electronic voting is that it makes fraud by a very small group of persons conceivable, when the traditional voting system makes that impossible for large-scale voting with multiple independent polling stations (this argument thus does not apply to a small local student council with a single polling station):

Votes are cast in urns which remain observable from vote start till end of counting (French urns are transparent, in reaction to fraud).
Votes are counted locally at each polling stations; anyone is allowed to obverse counting and check what the tally at the polling station where s/he voted.
The tally at each polling station is made publicly available in print, so that any observer can check that the tally at the polling station where s/he voted was not modified, and check the addition of counts thus the election result (there is a hierarchy of two levels of publication, but the principle remains valid).

Most importantly, a rational person/voter can be convinced that the traditional system does not allow centralized fraud; but electronic voting systems which manage to keep what one voted secret do not meet (or even have) that goal, to my knowledge. At best, the organizers of an electronic election can be convinced that there was no fraud; that's not the correct objective (and it is not even really met by any practical system that I have seen).
Again restricting to voting remotely by electronic means, some usually poorly mitigated risks include:

Browsers (e.g. on university computers) modified to vote as asked by the voter as far as the screen is concerned, when the vote is really cast differently on the network side; that's far from rocket science.
A server pretending to be the real voting server(s) to the voter's browser, performing Man-in-the-Middle attack at some point on the network; if the cryptographic defense is https with TLS as in normal web browsers, that's defeated with a copy of the private key of the true server (certificates emitted by certification authorities in breach of CPS, which abound, would also trick most voters, albeit with a risk of being caught by an observer comparing the certificate shown by the browser with the real thing obtained out-of-band). The MitM machine can go undetected to a real voting server (and even inquisitive client) scrutinizing IP address and routing info, if the MitM machine is appropriately inserted in the network near either the real voting server or the targeted browser, and competently programmed; a university network is ideal grounds for such attack.
In many systems, plain subversion of the machine(s) counting the votes. Having several counting machines run by multiple parties helps, but what should be the rule when they do not agree?
Denial of service; it's easy to prevent voting by attacking the voting server or network infrastructure, and conceivable (especially if observers are allowed) to create some ESD/EMP that zaps the server.
Loss of secrecy of individual votes, threatened by:
penetration of the central computer(s) running the election; that's a problem the industry hardly knows how to tackle when the computer operators are trusted; and in this situation, we'd like not to trust them!
compromise of the voter's device (this is somewhat mitigated by the diversity of devices)
brittleness of web security practices; e.g. consider an https connection used for a "please confirm your vote" page visually showing the ballot selected: if there's a jpg image shown and no special precaution is taken, it is likely that mere analysis of the length of TCP/IP packets reveals the choice made.

Note: there's a simple countermeasure, mitigating 1, 2, 5.2 and 5.3, that I have seldom seen proposed: the voter would key-in a few digits, received secretly, different according to the vote cast. That would largely remove the browser and network from the attack surface. This is not without its own security problems, but the real reason why some proponents of electronic voting dislike it is that it is low tech, and acknowledges the need to distrust high tech in matters of voting.

Addition: any voting system, electronic of not, must balance between two antagonist goals:

Keeping individual votes secret, including to whoever runs the election; because otherwise, individual retaliation could ensue.
Making the outcome convincingly representative of the intention of voters, to as many reasonable persons as feasible; because the elected needs legitimacy.

We can reach either goal by a sacrifice of the other (if all individual votes are made public along the name of the voter as the election goes, the outcome is verifiable; if we choose the election's winner by stone/paper/scissor, voting in one's mind is enough).
Electronic voting complicates both goals considerably, particularly when you consider that whoever runs the election is an adversary (in the sense of that in crypto) trying to breach vote secrecy and accurate vote counting. Simply put, I do not see an even mildly-satisfactory solution.

For starters: you should look up posts and papers related to "LDAP Security" using your favorite search engine.

I will say I like the solution that crypto has come up with in the form of not being able to spend the same BTC twice. Something involving that and user verification would be ideal for online voting although those two are very different technologies. Luckily math has the answer.

Now, whether that will be a sustainable solution without any security issues is probably not realistic but you bring up an important point and something that needs attention not just in your domain but in other domains as well. Maybe "quantum" DNA verification and multifactor authentication…


What is the size of a 1024-bit RSA cipher compared to its plaintext? Let's assume we encrypt a 50000 bit plaintext with 1024-bit RSA and public exponent $e$ = 3: How big will its cipher be?
When we increase the exponent to let's say $e$ = 216 + 1 = 65537, how big will its cipher be then?

RSA is almost always used in hybrid mode, where AES (or another symmetric cipher) is used to encrypt the data itself, and RSA is then used to encrypt the random data key. That way RSA has only a static overhead: the modulus size (which is also the key size) in bytes. So for RSA-1024 that would mean an overhead of 128 bytes + whatever overhead is required for the symmetric cipher (which can be zero bytes if a stream cipher or stream cipher mode such as counter mode is used). In that case you'd have $50000 / 8 + 1024 / 8 = 6250 + 128 = 6378$ bytes if I'm not mistaken.
Using unpadded / raw or textbook RSA (i.e. RSA using only modular exponentiation) is insecure. So you always need to pad the plaintext message within RSA. In that case you would for instance use RSA-OAEP as defined in the later PKCS#1 standards. This padding scheme adds quite a lot of overhead. Generally we don't care about that, because there is plenty left over to encrypt a symmetric key when using hybrid encryption. However, if you'd use multiple RSA encryptions in sequence then you would have an overhead of 42 bytes and a payload of only 86 bytes, assuming a SHA-1 hash within OAEP for minimum overhead. A single encrypted partial message would still be 128 bytes. So you would have $\big\lceil 6250 / 86
 \big\rceil \cdot 128 = 73 * 128 = 9344$ bytes taken, an increase of $2966$ bytes (!)
A few notes to these calculations:

RSA as specified in PKCS#1 always sets the output of encryption to be the modulus size in bytes, even if the actual number is smaller. That way the size is always static and doesn't need to be indicated (unless the key size is not known in advance). If you would allow alternating sizes then you would need to indicate the output size of each encryption, or you would not be able to separate the resulting RSA ciphertext blocks.
RSA-PKCS#1 v1.5 padding can also be used. PKCS#1 v1.5 padding is an older, less secure scheme. PKCS#1 v1.5 padding has somewhat less overhead in the non-hybrid scheme.
RSA-KEM is another scheme for hybrid encryption. It doesn't encrypt a symmetric key; it encrypts a master secret used to derive a symmetric key and is arguably more secure. It doesn't add any overhead to hybrid encryption. It cannot be used to encrypt the message directly or in parts.
Message integrity / authenticity is not taken into account in above. If that's required generally we use a sign-then encrypt scheme which increases the plaintext message before encryption.
Generally other overhead is also present. For instance, CMS based encryption also indicates certificates and algorithms used to the receiver. So you cannot generally expect the plaintext message to expand only with regard to the RSA key size.
RSA-1024 has already been deprecated by NIST (for medium and long term encryption) and is generally considered too small. Note that increasing the key size actually has positive effects on the relative amount of overhead required (when concatenating RSA encryption of partial messages); a larger RSA key size would actually be beneficial w.r.t. size. Unfortunately, that comes at a price of ever increasing CPU requirements, especially for RSA decryption and (one time) key generation.

This depends on the exponent $e$ and the modulus $N$ which you are using.
In laymen terms "something power 3 is always smaller than something power 65537", for instance:
$x$$3$ $< x$$16$$+1,$ for $x∈ℝ$$+$
Or in general:
$x$$e$ $> x$$e-y$$,$ with $y>0$
It gets more complicated with the modulus due to its cyclic nature, however the maximum value of a modulus could potentially be bigger if the modulus is bigger:
$max( x$ % $N ) > max( x$ % $(N - n) ),$ with $n>0$
That being said, there can a maximum size of the cipher be calculated, for more infos see into Maarten's answer. In general, the ciphertext uses very nearly as many bits as there are in the public modulus $N$, considered RSA is used in a terminally safe way.
Which means that the ciphers length is usually (with common RSA implementations) not dependent on the size of exponent $e$, simply because $e$ is high enough to be divided by modulus $N$. However, without proper padding, using a small $e$ fails to achieve a product high enough to be divided by $N$. Let's have an example (calculated here):

Choose $e$ = 3
Choose an $N$ for which $ϕ(N)$ is coprime with e, which means an $N$ as the multiplication of 2 large primes $p$ = gcd($p$ - 1, $e$) = 1 and $q$ = gcd($q$ - 1, $e$) = 1, e.g. $p$ = 134113233377 and $q$ = 171012421319 (from this list) ==> $N$ = $p$ x $q$ = 22935028770720897164263 (76 bit)
Calculate that $d$ = 15290019180277181006379 (76 bit)
Enter these numbers in plaintext $M$ and compare it to their resulting cipher $C$:

   M: 1             -> C: 1                        (1 bit)
   M: 13            -> C: 2197                     (12 bit)
   M: 134           -> C: 2406104                  (20 bit)
   M: 1349          -> C: 2454911549               (32 bit)
   M: 13497         -> C: 2458735114473            (44 bit)
   M: 134975        -> C: 2459008378109375         (54 bit)
   M: 1349752       -> C: 2459019309075947008      (64 bit)
   M: 13497527      -> C: 2459023134921900302183   (72 bit)
   M: 134975276     -> C: 4975384384602091248435   (73 bit)
   M: 1349752761    -> C: 21423635623920893065273  (75 bit)
   M: 13497527614   -> C: 4504951087215542921902   (72 bit)
   M: 134975276143  -> C: 13105173284468409708818  (74 bit)
   M: 1349752761432 -> C: 258234696569487676944    (68 bit)

As you can see, the size of the cipher stops at 75 bit, so length($C$) ≤ l($d$) - 1 = l($N$) - 1
It's pretty obvious that this encryption is completely insufficient, not only because of the cipher size being too low for and below $M$ = 1349752, but even more so because the $M$'s 134, 1349, 13497 up until 13497527 all start with the numbers "24" (the $M$'s 134975, 1349752 and 13497527 even all start with "24590").
Let's do the same with another $e$:

Choose $e$ = 65537 (instead of 3)
Calculate that $d$ = 4510925444415510242433 (72 bit)
Enter these numbers in plaintext $M$ and compare it to their resulting cipher $C$:

   M: 1             -> C: 1                        (1 bit)
   M: 13            -> C: 17466161323880056389598  (72 bit)
   M: 134           -> C: 2107714247256743075865   (72 bit)
   M: 1349          -> C: 7477203662088274241639   (73 bit)
   M: 13497         -> C: 5132009836650541594940   (73 bit)
   M: 134975        -> C: 16541984621407927196414  (74 bit)
   M: 1349752       -> C: 20887420686729795448028  (75 bit)
   M: 13497527      -> C: 21682424773647631361120  (75 bit)
   M: 134975276     -> C: 3676623109854753818222   (72 bit)
   M: 1349752761    -> C: 22872817161688280222695  (75 bit)
   M: 13497527614   -> C: 18762631911648547002249  (74 bit)
   M: 134975276143  -> C: 21146132359162765255647  (75 bit)
   M: 1349752761432 -> C: 14030823333728076106071  (74 bit)

Again the size stops at 75 bit, so length($C$) ≤ l($d$) - 1 = l($N$) - 1
In this example, the ciphers size is always 72 to 75 bit and the encryption looks random as well, so $e$ is chosen sufficiently enough. What it also shows is that $d$ is no measure for the maximal length of the cipher, but only the modulus $N$ sets this maximal length.
For further explanations on the problems with a low $e$, have a look into this answer, giving reference to this paper. Basically it says that a low $e$ allows the reconstruction of the private key $d$ if some bits of $d$ are leaked. So even with proper random padding, $e$ = 3 should probably be avoided in RSA implementations (there are even further problems with a low $e$ e.g. in case of encryption with three distinct public keys, explained here, which only reinforces my point).


Symmetric Multi-Key Decryption Is there an encryption decryption scheme in which a group of people are all given different keys, and of which each key can decrypt a file. (I’m not talking about a scenario where a file is encrypted with a single symmetric key, and then the symmetric key is separately encrypted with each individuals public key.)

I’ve read articles about broadcast encryption and multi-trapdoors but I'm unsure if any of these would match the correct scheme so I’m looking for.

You don't have to use any special asymmetric construct. Just give the group keys and encrypt the file with a unique random key and than encrypt the file key many times using the keys of the permitted users.

You can give each user multiple keys some of them shared by relevant groups. To prevent encrypting a file with too many keys. These can even be done ad-hoc, assuming groups repeat themselves. you can create a group key encrypt it with the keys of the members and reuse it if you want to give that group access to another resource later.


AIS31 Software and Documentation I have learned that there are two main test suitcase for randomness (reference):

AIS 31 - German Federal Office for Information Security (BSI)
SP 800-90B - U.S. National Institute for Standards and Technology (NIST)

I was able to run NIST tests on my data. I was wondering if there is any software (and documentation) available for AIS31. I was only able to find general information about it.

See the page below

https://www.bsi.bund.de/DE/Themen/Kryptografie_Kryptotechnologie/Kryptografie/Zufallszahlengeneratoren/zufallszahlengeneratoren_node.html

I looked at it with the Google translator.

There are quite a few useful links there. If you want full blown code for tests, you'd probably need to write your own.

Related question:

https://security.stackexchange.com/questions/89020/what-comprises-the-ais-31-standard-for-trngs

An important point of AIS31 is §2.4.5, Additional Statistical Tests.  They subsume all other randomness tests, specifically mentioning SP 800-90B. So you would have to implement the theoretical tests AIS31 mentions yourself.  Although §2.4.5 implies that you can simply run with other standardised tests. For that reason I wouldn't bother with an implementation.  But if you do bother, you can test your code against /dev/urandom output, or binary expansions of the irrational numbers like $\pi, e, \phi, \sqrt{2}$ etc.
It's worth mentioning that these are not really the two main test suites. Diehard and Dieharder are also very common, depending on the size of the sample you can generate. With hindsight, you find that AIS31 is very uncommon in the wild for not having been implemented in a standardised code base.
There appears to be an implementation:-

But I don't know how to use it on Java 11 :-(

The direct link to an English version of the PDF document with the name "A proposal for: Functionality classes for random number generators, Version 2.0, 18 September 2011" can be found here.


Which risks are associated with deriving multiple keys from the same DH secret Z? NIST recommends Krawczyk's HMAC-based key derivation function (HKDF) in SP-800-56C (PDF). HKDF shall e.g. be used to create keys from shared secrets after Diffie Hellman key establishment.

NIST states in the same doc:

  Each call to the randomness extraction step requires a
  freshly computed shared secret $Z$, and this shared secret
  shall be zeroized immediately following its use in the
  extraction process.

Why is it not recommended to derive multiple keys from the same $Z$, e.g. why not derive a key for data encryption and a key for authentication from the same $Z$ using different info strings? If I still do it, what weaknesses might the derived keys be facing? Is it simply bad practice (without deep explanation) to do so since the derived keys obviously are related? Krawczyk seems to think that multiple derivations from the secret are expected use (see section 3.2 in RFC 5869, my interpretation).

Does salting the HKDF with a good random salt change my risks when deriving multiple keys from a single $Z$?

It depends on how you use HKDF to derive multiple keys.

Background: HKDF consists of two stages: first HKDF-Extract computes an intermediate value from the randomness source; then HKDF-Expand can be used to generate one or more session keys from the intermediate value.

The right way is to use HKDF-Extract once, and then call HKDF-Expand multiple times, with multiple different info strings.  In other words, to derive two session keys, you'd call HKDF-Extract once and HKDF-Expand twice.  If you do that, then this is a perfectly good practice -- it is exactly what HKDF was designed for.

The wrong way is to call the entire HKDF process twice, with two different salts.  Some implementations of HKDF might not separate out the two stages, and just combine them; if you used that, and performed the entire process twice (using HKDF-Extract twice and HKDF-Expand twice), then this is not the intended way to use HKDF.

Everything is fine if you use the "right" way, so for the rest of this question I assume you were asking about the "wrong" way.  There are two answers about whether this is a good idea: the "engineering" answer, and the "principled" answer.

The engineering answer is that, in practice, if you generate two keys using two different info strings, I suspect you'd probably get away with it without problems.  If we model the hash as a random oracle (admittedly a very strong "assumption"), then I suspect it might be possible to demonstrate that what you propose is OK.  Disclaimers: I haven't analyzed this, and I'm certainly not going to give you any guarantees -- if you do what you propose, cryptographers will wag their finger and say "tsk, tsk", and rightly so.  I suspect you'd probably get away with it (it's not the worst sin you could make), but if something does go wrong, cryptographers aren't going to take the blame -- it's all on you.

The more principled answer is that if you do what you propose, you are misusing the HKDF primitive.  The HKDF is only intended to be applied to a single $Z$ once.  It is intended to turn an unguessable value into something that looks uniformly random.  It has been analyzed for that use.  It was not designed to derive multiple keys from the same $Z$: it hasn't been analyzed for that kind of use case, since that's not what it was designed for.  So, you're throwing away the benefits you could get from the public analysis of HKDF if you use it in a way that it wasn't designed for.

Consequently, given that it is so easy to use HKDF the right way, you should probably do that.

The HKDF RFC contains formulations such as:

  The second stage "expands" the key K into several additional
  pseudorandom keys (the output of the KDF).

and:

  The second stage "expands" the pseudorandom key to the desired
    length; the number and lengths of the output keys depend on the
    specific cryptographic algorithms for which the keys are needed.

Both quotes appear already in the introduction (emphases mine).

As you already point out, Section 3.2 describes the info value and states:

  In particular, it may
    prevent the derivation of the same keying material for different
    contexts (when the same input key material (IKM) is used in such
    different contexts).

All these quotes taken together seem to rather strongly indicate that deriving several keys from the same IKM is a perfectly valid and even intended use case of HKDF.

However, there is also a rather strong caveat in the introduction:

  In many applications, the input keying material is not necessarily
    distributed uniformly, and the attacker may have some partial
    knowledge about it (for example, a Diffie-Hellman value computed by a
    key exchange protocol) ...

The concrete case of DH key exchange is thus even explicitly mentioned as one case where an attacker has partial knowledge of the IKM.

It would thus seem prudent to base the derivation of further keys on a new shared secret in this particular case of IKM.


What implementation properties of a hash function prevent safe truncation? Truncating a hash function's output should, in theory, not increase the likelihood of a collision more than you would expect based on the truncated output size. This makes sense when thinking about the the ideal hash function, a random function.

Since real-world hashes are not random functions, what properties of algorithms like sha2 make us comfortable with truncating, and what (popular) hashes exist out there that are known to have issues?

You really should never be truncating a hash.  Really you're talking about the difference between traditional hashing algorithms and cryptographic hashing algorithms.  A cryptographic hash algorithm has to not be predictable, while a traditional hash algorithm doesn't have that concern.  You aren't guaranteed perfect random distribution, so really you shouldn't ever be truncating a hash in any situation.

Could you specify a situation where people "feel comfortable truncating a SHA2 hash"?  I don't know what you're referring to.


Decrypt a public encrypted message and Sign a signature, how the math is different? As I understand, when you want to send a confidential message to someone, you encrypt the message with his public key. And he use his private key to decrypt the message.

At the same time, one can use his private key to sign a message, and other people use his public key to verify that it's him who sign it.

How the math is different between decrypt the message and sign a message?

The simplistic view that signing uses the same math as decryption is descriptive with textbook RSA; has some relation to practice in safe use of RSA; and is just wrong with most other common asymmetric cryptosystems, beside the commonality that a private key is involved.

In textbook RSA, the math to decrypt an encrypted message and compute a signature is the same: it is applied the textbook RSA private key function $x\to y=x^d\bmod N$, with $(N,d)$ the private key, and $x$ the encrypted message in decryption, or the message to sign in signature. Problem is, textbook RSA is unsafe for both encryption and signature.

When we move to secure use of RSA, the math becomes different:

To decrypt we check the bound of the cryptogram $x$, apply the above textbook RSA private key function, then

Extract the encrypted message from the result $y$, in a certain way that removes random padding that was added at encryption (and perhaps checking certain fields). There are at least two common classes of RSA encryption padding and corresponding decryption removal, defined in PKCS#1, and several implementation variants (not all are safe). That can be enough for very small messages (like few hundred bytes).
And/or what we really obtain is a secret key, which is then used to decipher the bulk of the message using symmetric-key cryptography (that's hybrid encryption).

To generate a signature we typically hash the message to sign then add redundancy in a certain way, then apply the above textbook RSA private key function to obtain the signature $y$ (in some variants we further keep $\min(y,N-y)$ ). There are at least three common classes of RSA signature padding: two in PKCS#1, and ISO/IEC 9796-2, which comes with several variations.

When we move to asymmetric cryptosystems other than RSA, one thing remains: the private key is involved in decryption, and/or computing a signature. Other than that, there is typically profound disjunction between decryption and computing a signature (one notable exception is the Rabin cryptosystem, which can be seen as a variant of RSA with even public exponent); and very often, one of the two features is just not offered by a particular cryptosystem.

For example, we have DSA, ECDSA, and Lamport signatures, but these cryptosystems do not offer encryption.

The converse can be true: we have Pailler encryption, but no useful signature analog. We have NTRUEncrypt, which latest versions are unbroken; but it is quite different from the related NTRUSign, and last time I checked work on the later stopped in the broken phase of multiple break/repair cycles.

Actually, the theoretical math is not really different:

Formally speaking, a public key cryptosystem is given by:

a set $M$ of possible plain messages, and a set $C$ of possible
ciphertexts; often $M=C$;
a set $K$ of possible keys;
for each $k \in K$, a pair of function $E_k: M \rightarrow C$
and $D_k: C \rightarrow M$ such that:

$D_k(E_k(m))=m$ for all $m \in M$ and $E_k(D_k(c))=c$ for all $c \in C$;
$\forall m \in M $ $E_k(m)$ is easy (and computationally fast) to compute, and $\forall c \in C$ $D_k(c)$ is easy (and fast) to compute;
knowing only $E_k$, it is computationally infeasible to find $D_k$;
knowing $k$, it is easy to find $E_k$ and $D_k$.

The functions $E_k$ and $D_k$ are called encryption and decryption functions associated with the key $k \in K$.

In practical application, a user Bob chooses a key $k \in K$ and computes the functions $E_k, D_k$; he then makes $E_k$ public (e.g. on the internet), and keeps $D_k$ secret. Thanks to property (4), it should be difficult for anyone except Bob to get $D_k$. Now, suppose that a user Alice wants to send a message $m$ to Bob, and wants no one else but Bob to be able to read it: she looks for Bob's public encryption function $E_k$ on the internet, computes $c=E_k(m)$, sends $c$ trough the communication channel, Bob receives it and computes $D_k(c)$, obtaining the original message $m$ (thanks to property (1)). Even if the communication channel is not secure, any eavesdropper (say Eve) cannot deduce the message $m$ from $c$, and $c$ is the only thing that pass trough the channel.

(For the sake of clarity: usually, when dealing with a specific public key cryptosystem, the functions $E_k$ and $D_k$ are obtained from $k \in K$ in a standard way: for example, in the RSA cryptosystem, $k$ is a triple $(n, e, d)$ and the $E_k(x)=x^e$ (mod $n$), while $D_k(x)  = x^d$ (mod $n$). It is clear that, if everyone knows that this cryptosystem is being used in a specific situation, keeping $D_k$ secret and making $E_k$ public is equivalent to keeping $d$ secret, and making $(n,e)$ public. This is why, in many situations, we will talk of a public key and a private key instead of a encryption function and a decryption function, but we should be aware this is exactly the same setting.)

Now, when instead of encrypting messages we want to sign messages, we just switch the use of $D_k$ and $E_k$:

Now Bob wants to put his signature onto a message $m$ (say, some kind of contract with Alice), so he computes $y=D_k(m)$ and send the pair $(m,y)$ to Alice. Everyone (included Alice) now can verify that the message was signed by Bob, simply computing $E_k(y)$ (recall $E_k$ is publicly known!) and checking this equals $m$ (again, by property (1), this is true if Bob did it right).

In conclusion, when we have a cryptosystem, it is easy to create a signature scheme, so actually the math is not different at all! And indeed, when we have an encryption system (RSA, ElGamal, NTRU,...) , we usually also have a corresponding signature scheme (RSA Signature, ElGamal Signature, NTRUSign,...)


BouncyCastle style ThreadedSeedGenerator I've written a BouncyCastle style threaded seeder and was wondering about the predictability of the data the program generates.

The reason I'm not simply using BouncyCastle is because security isn't a concern, I don't want to use a whole library just for one function, and this code is MUCH faster.

The idea is to make several threads which operate on a circular buffer (a simple array), where each thread performs a different operation on the data in the buffer. The randomness comes from thread scheduling irregularities in the OS.

How much randomness can I expect from a mechanism like this?

C# code:

using System;
using System.Threading;

class ThreadedSeeder
{
    static public ulong[] buffer = new ulong[1024];
    static public bool doThread = true;

    public ThreadedSeeder()
    {
        MakeThread(Add);
        MakeThread(Multiply);
        MakeThread(Xorshift);

        Thread.Sleep(10);

        doThread = false;
    }

    static private void MakeThread(ThreadStart a)
    {
        Thread b = new Thread(a)
        {
            Priority = ThreadPriority.Lowest
        };

        b.Start();
    }

    static private void Add()
    {
        int i = 0;

        while (doThread)
        {
            buffer[i & 1023] += (ulong)DateTime.UtcNow.Ticks;
            i++;
        }
    }

    static private void Multiply()
    {
        int i = 0;

        while (doThread)
        {
            buffer[i & 1023] *= 6364136223846793005;
            i++;
        }
    }

    static private void Xorshift()
    {
        int i = 0;

        while (doThread)
        {
            ulong y = buffer[i & 1023];

            y ^= (y << 13);
            y ^= (y >> 17);
            y ^= (y << 5);
            buffer[i & 1023] = y;

            i++;
        }
    }
}

The approach is deeply flawed in many ways.

It is very plausible that the whole buffer is returned at zero under heavy load, which is something that an attacker can often intentionally cause (e.g. with a flood of network traffic requiring high CPU load; starting a number of https connections comes to mind). That's likely to be a practical disaster.
Mechanism: the three threads launched by ThreadedSeeder are set to Lowest-priority, thus it is reasonable that they won't do anything before the Thread.Sleep(10). If the machine has higher-priority-than-Lowest things do during that pause, execution can proceed to doThread = false before the Add thread has ever tested doThread, thus with Add performing nothing related to buffer. The same could hold for Multiply and Shift too, but that's immaterial, as these threads can not un-zero buffer even if they run.
More generally there is little insurance about the number of times DateTime.UtcNow.Ticks is called; that could be very few, including less than once per buffer entry, thus always leaving all the other entries at zero. The busiest the machine, the more likely it is that a buffer entry has no, one, or very few readings of DateTime.UtcNow.Ticks to influence it.
I see no mechanism preventing Multiply or Xorshift from competing with Add about what element of buffer it operates on, and thus void a change Add makes meanwhile. This is an uncontrolled race condition, and it can loose some of the entropy gathered.
DateTime.UtcNow.Ticks can be closely approximated by adversaries. That's supposed to be the UTC time, which is not a secret. Further, common mechanisms such as RFC 7323 high-resolution TCP time stamps allow to find what a particular machine believes the UTC time is, even when it is poorly synchronized. And when the machine is under light load, with one CPU running each thread including Add at full blast, the difference between readings will be reasonably repeatable.
The transformation made from DateTime.UtcNow.Ticks to what is in each element of the buffer is one among relatively few public transformations. And each of these possible transformations is trivially reversible (modular multiplication by an odd constant modulo a power of two is reversible in Multiply, as well as each of the three bitwise operations in Xorshift). Combined with 4, it trivially allows a very selective distinguisher on each buffer element output whenever there is only a single DateTime.UtcNow.Ticks that influenced it, also revealing which transformation occurred. It looks like this could be extended to a few such influences.
Neither the code nor the text of the question shows any effort to create explicit diffusion of the entropy gathered: elements of buffer are never mixed. Absent such mixing or/and post-conditioning before use of buffer, some degree of 2/4/5 can be a practical disaster.
Timing execution won't gather any entropy in some precisely controlled execution environments, including VMs/simulators used by hardware engineers or reverse-engineering of malware. Ultimately, the state of buffer on output, and whatever is deterministically derived from that, will dependent only on when the task is launched.

In a nutshell, there will be  entropy generated but you can't really predict it's rate.  That said, it might be of the order of a few percent, based on experience. I got 10% but that involved much more computation and thus CPU jitter.

You need to measure it empirically. So run your buffer in  a long burst, then write that buffer data to a disc file. Repeat to get say 100KB of data.  Then find the strongest compressor you can. I use cmix, it's one of the stongest compressors in the world but requires a lot of RAM (32GB). Compress the data file, and the compressed size will represent the entropy content.  For safety, you might divide that value by 2.

You also need to then increase that disc file in steps, making it longer and longer.  Re-compress and the entropy should rise proportionately, proving that the entropy is not simply repeating itself.

A few percent entropy rate may not seem a lot, but it accumulates very quickly. So 0.01 bits/byte adds up and soon you have enough for a 256 bit seed/key.  With that thing you can then generate all the randomness you need. Simply SHA-256 more than 64 bytes of entropy and you're done.

I advise you to try this ASAP (today) and convince yourself that it works. Also have a look at CPU Time Jitter Based Non-Physical True Random Number Generator.  It's a working implementation, but your results will differ.

Note: You have to use compressive means to measure the unknown entropy as it will be highly correlated.  You have no real alternative as the common Shannon log formula won't work on this such data.  I've used this method previously and it works  well. There are decorrelation techniques often used that aid the application of Shannon's formula, but you don't have go down that route.


Why do cryptographers need loads of true random numbers? I've just read an answer to fastest-random-number-generator.  The answer is a couple of years old, but mentions a true random number generator capable of running at 300 gigabits per second.  It is re-linked here.  They might go even faster now. .

One time pads are out of favour.  There's no point storing these numbers for reruns as you might as well use a psuedo random number generator.  Most pundits on this forum suggest a maximum of 128 bits of true entropy for seeding.  So why would cryptographers need so many true random numbers? Or is it just a *issing contest between researchers?

Mostly, you do not actually need a lot of true randomness, as you observed. However there are at least some niche cases where you might want a fast TRNG.

Stateless implementations cannot use a typical CSPRNG. Something like a hardware token without writable storage, maybe. The intersection with applications that require a lot of speed is pretty small.
Long term key generation. People tend to want true random numbers when generating long term keys. That is not usually a frequent event, but perhaps something like a federated key store would need to do it often enough.
Latency. Even if you do not need gigabytes of entropy every second, getting e.g. 256 bits quickly can be important. Although again it is probably rare to need it and not be able to use a cache.

There are probably also use cases where the random numbers are used for non-cryptographic algorithms, but need to be both strong and non-deterministic. Maybe in gambling.

Mainly because you need a  large and random seed pool for using the more advanced ciphers. as the random numbers are commonly BIG BIG primes +  some big random_number.  If you have a small entropy pool ( seeding source pool) this is much harder to obtain / retain / confirm true randomness.


Implementing randomness extractors A randomness extractor is a function that takes an input sampled from high entropy distribution and outputs a value that is close to uniform distribution. It is slightly different from a PRG. PRGs take an input sampled from uniform distribution and output a larger length string which is computationally indistinguishable from uniform. Whereas randomness extractors take an input sample from high entropy distribution and output a smaller length string statistically close to uniform distribution.

In my scheme, I use randomness extractors. In the scheme, the extractor takes an element uniformly sampled from a subgroup of $Z_N^*$, where $N$ is a product of 2 large primes. The extractor needs to output a bit string. I want to implement the scheme but couldn't find any implementations of randomness extractors. Are there any randomness extractors in sagemath, or any other library?

Whereas randomness extractors take an input sample from high entropy distribution and output a smaller length string statistically close to uniform distribution.

Not quite.  A randomness extractor is not simply a function $F\colon A \to S$ such that $F(X)$ has small distance from uniform if $X$ has high min-entropy.  Rather, a randomness extractor is a keyed family of functions $F_k\colon A \to S$ such that if $K$ is uniformly distributed and $X$ has high min-entropy, then $F_K(X)$ has small distance from uniform.  In other words, the premise is that you already have a uniform random key.

So, there is essentially no reason to use a randomness extractor in a practical application.  Generally, either:

You have a secret with high enough min-entropy to do cryptography.

Great!  Use HKDF-SHA256 or your favorite KDF to derive keys from it for each cryptosystem you want to use.

You don't have a secret with high enough min-entropy to do cryptography.

No amount of cryptidigitation with randomness extractors will raise its min-entropy.  Just flip the coin a few more times.

Randomness extractors are essentially of theoretical interest only, so it is not surprising if you have trouble finding practical implementations of them labeled as such (although any universal hash serves as a randomness extractor with the leftover hash lemma).  If you actually want to do cryptography, just feed your initial secret with high min-entropy through a hash function like HKDF-SHA256 or SHAKE128.

There are weird and wonderful theoretic extractors in the literature, but in practice people end up using some form of generic hash algorithm.  You either write your own or use a recognised form. The implementation language can be anything that can do the following:-

Writing your own usually comprises some form of vector multiplication. So either a Toeplitz matrix, or just a rectangular matrix of  random bits/integers. You then apply the modulus depending on whether you're trying to output bits or octets. So using matrix $M$ on an input entropy vector $x$ gives $\operatorname{Ext}(x) = M \cdot x \mod n$, where $n$ would be the modulus, say 2, $2^8$ or a prime in some cases. The ID Quantique random number generators use the random bit wise mod 2 method.
The standard forms can be either cryptographic or non cryptographic hashes.  SHA*, HMAC, CRC*, Pearson, etc. The USB format OneRNG uses CRC16 and I'm partial to Pearson.

It doesn't really matter as the typical application of a randomness extractor means that the overall system state is not recoverable.

Although... You mention extracting from a sub group of $Z_N^*$.  It is unusual to extract from an algorithm, as what you  will have is a pseudo random generator.  If this is really the case, a cryptographic hash would be needed as state discovery would be mathematically possible. Forwards and backwards security would be compromised otherwise. However, I've never seen a formal randomness extractor and an algorithmic state mutator together in one construction.

An alternative is to stick with von Neumann (vN) if inversion is not possible due to some algebraic property of $Z$.  You then have to decorrelate $x$, create independent samples and only then apply vN. The most common decorrelation method is dropping higher bits from $x$ until autocorrelation levels become acceptable. Only you know your $Z$'s behaviour, so lower bits may have to be dropped instead. There is also FIR filtering across sequential $x_i$ values.  XOR of sequential $x_i$ values can also act as an ersatz FIR filter. If inversion is possible, simple vN will still be insecure for cryptography though.


Composing two one-way functions such that the result is not a one-way function Is it possible to have two distinct one-way functions (called, say, $h$ and $g$) such that their composition $h \circ g = [\, x \mapsto h(g(x)) \,]$ is not one-way?

The function $f$ introduced by Maeher in this answer to a related question should also do the job here (as both $g$ and $h$).  For convenience, let me quote that answer here:

Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$
From this function, we now construct a new function
$$f : \{0,1\}^{n} \to \{0,1\}^{n}$$ as follows:
$$f(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1),$$
where $|x_1|=|x_2|=n/2$.

As shown in Maeher's answer, $f$ is one-way if $h$ is.  However, $f(f(x)) = 0^{n/2}\Vert h(0^{n/2})$ is constant, independently of $x$ (except for its length $n$), and thus finding pre-images is trivial.

Ilmari's answer is incorrect.

$f(f(x))$ is not equal to $0^{n/2}\| h(0^{n/2})$. Instead it equals $0^{n/2}\| h(h(x))$ which is not necessarily easy to invert. In particular, if $h \circ h$ is also one-way then $f \circ f$ would also be one way.


If Blum Blum Shub is modified to use a prime modulus, is it still secure? The definition of the Blum Blum Shub cryptographically secure pseudorandom number generator is $x=x^2 \mod N$ where $N=p \times q$, $p \in \mathbb P$, and $q \in \mathbb P$. Supposedly, the security comes from an attacker not knowing the factors of $N$, but why can't I simply use a single prime number?

I suggest you read the paper about the generator, because that question is answered there:
A Simple Unpredictable Pseudo-random Number Generator, Blum, Blum, Shoup, 1986

They don't have any formal expression of what is called "state compromise extension" there, but they already state in the section 6. The $1/p$ generator is predictable on page 6 exactly the case of using a prime modulus.

Their main point is: Yeah, it might look nice and have nice properties, but you can "calculate forward and backwards in the sequence with about $2|p|$ digits of information."

For more details I suggest reading the paper.

Another reason is that the order of secret seed $x_0$ is a divisor of $p-1$. In the case with RSA modulus, the order is unknow and would contribute to the intractability of the problem.
This assumption could gives an advantage to an attacker to build a distinguisher assuming that $x_i=x_0^{2^i}$.


How secure is AES-256? The cipher AES-256 is used among other places in SSL/TLS across the Internet. It's considered among the top ciphers.

In theory it's not crackable since the combinations of keys are massive.

Although NSA has categorized this in Suite B, they have also recommended using higher than 128-bit keys for encryption.

So how secure is this cipher really? Should you assume the worlds top cracker-institutions are near or have cracked it already?

I wouldn't assume that the NSA has cracked AES ciphers. I would assume that most crypto systems that use AES have implementation flaws that the NSA exploits when they feel it is worth it.

In any case, when the only possible way a state can know something is by breaking a cipher, it's difficult for them to use that information; doing so would reveal that the cipher is broken. So in practice, a broken cipher is more likely to be used as a shortcut to find something that could be discovered (albeit with more difficulty) by other methods.

You might be interested in this recent story and commentary about NSA's crypt analytical capabilities.

We know, from Edward Snowden, that the NSA does, routinely monitor all traffic and can decrypt all standard encryption, such as SSL. So it is likely that they have methods to break AES.

So, if you are concerned about industrial espionage, AES is unlikely to be your algorithm of choice - this is not just because of NSA or GCHQ spying, any third party (retired spook, for example) who has the know-how can also decrypt most things. In fact there are companies for hire that will decrypt pretty much anything for you, using intelligence from the likes of the NSA or GCHQ.

The only known secure algorithm is the one-time pad.