Personal ledgible quick cipher The problem:

When I'm writing or reading information (be it on a screen or a physical medium) the information is vulnerable. So long as I'm not alone, anyone can simply glance at my screen or journal and instantly read what's written there (like addresses, phone numbers, and plaintext passwords/device pins)

My goal:

I want to create/utilize some sort of text-obfuscation system or cipher system that makes it impossible for the casual observer (>99.99% of people) to tell what I'm writing or reading at a glance.

The challenges and conditions:

Reading and writing speeds shouldn't be more than 50% slower with practice (I should be able to type this obfuscated text at 50 wpm and read/skim-read at several hundred)
I'm not a math-savant so any obfuscation/encryption operations need to be doable with minimal math and without a computer
From a security standpoint, the obfuscation/encryption doesn't need to be extremely secure, it only needs to be good enough that your average Joe (again, >99.99% of people) could spend several minutes reading over my shoulder without figuring out what I'm reading or writing

Potential solutions I've thought of:

Teach myself an uncommon written language like Esperanto or Klingon which very few people can read
Replace the symbols I use to write letters with alternatives, like Elian-script

My question:

Surely, this is a problem people have grappled with before. Besides operational-security solutions like making sure nobody's looking at your screen or using a polarizing filter, what solutions are out there?

Teach myself an uncommon written language like Esperanto or Klingon which very few people can read

That's not a bad idea. Although if you had to choose one I'd personally advise you to use Klingon instead of Esperanto. The amount of worldwide Esperanto speakers is about 1 in 4000 (0.03%), whereas Klingon is spoken (fluently) by only 20 - 30 people.

The goal of Esperanto (as you might know) was to introduce a universal language with the intent of making the learning process fairly easy, some might even say that Esperanto is very easy to learn. Many words are derived from European languages:

  [...] took most of [...] Esperanto root words from languages of the Italic and Germanic families, principally Italian, French, German,
  Yiddish, and English. A large number are what might be called common
  European international vocabulary, or generic Romance

  - Esperanto etymology (Wikipedia)

It's likely that European speakers can recognize some words from Esperanto and maybe in rare instances connect the dots to gain contextual knowledge of a text.

Additionally, there are numerous Klingon & Esperanto online translators (if anybody should get hold of a text).

  Replace the symbols I use to write letters with alternatives, like Elian-script

That's probably a good method. If you do this every day it should be fairly easy for you to learn reading and writing in a cipher and obviously you can invent such a cipher yourself.

However, I have to say that it's unlikely to go beyond a monoalphabetic substituition cipher. Polyalphabetic substituition ciphers are rather hard to do fast by hand / mentally for numerous reasons.


Number of keys when using symmetric and asymmetric encryption? Quoting part of my homework/assignment:

  How many keys are required for secure communication among 1000 person if:

  Symmetric key encryption algorithm is used?
  Asymmetric key encryption algorithm is used?

My guess:

For symmetric they each need to maintain and transfer their own key, so probably $1000 \times 1000$, and for asymmetric maybe just $2000$, each having one public one private.

Is that correct?

For the symmetric key, you can approach this problem as a complete graph with order 1000. With the vertexes representing people and the edges representing the symmetric keys. Then each vertex would have degree 999 and, applying the Handshaking lemma, the number of edges would be:

$(1000 \times 999)/2 = 499500$

So they would need 499500 symmetric keys to have a secure communication between all of them.

For the asymmetric keys, each one would have 2 keys, so a total of 2000 keys.


Why is prime factorisation computationally intensive compared to normal factorisation? Why do we use prime factors in asymmetric algorithms compared to other factors?

For example:

  lets say we use two prime numbers p = 53 and q = 59   our public key
  in RSA algorithm would be p * q = 3127

  while it is difficult to find the private key from this using prime
  factorisation, I feel it is equally difficult to find the factors for
  some   normal number too

  like p = 52, q = 58 where public key would be p * q = 3016

but why is prime number preferred over the others, is it because how the algorithm works? Think I am missing something trivial.

The problem are not prime factors, the problem are large prime factors. There are many rather efficient factorization algorithms (such as Pollard's rho) that are good at finding small factors. Actually in RSA we want $p, q$ to be approximately of the same size so this disproportion cannot be leveraged to factor $p*q$.

If you have a $p, q$ primes then $p*q$ has only two factors, smallest one is equal to $p$ or $q$. If $p,q$ are composite then the smallest factor of $p*q$ is smaller (upper bound on the factor is only $min(\sqrt{p}, \sqrt{q})$). Thus using composite numbers reduces your problem to much smaller instance. Moreover if your numbers have really small factors (such as $2$) then the reduction is even more straightforward (e.g. I can decide to divide $3016$ by $8$ just by looking at binary representation of $3016$, then it remains to factor $377$ which is almost 10 times smaller).


TLS 1.3 Ciphersuite SHA Level As I like to make my tin-foil hat using only the finest quality metal, I was overjoyed to see that Firefox/NSS (I'm using Arch Linux) has recently added support for the P-521 ECDH group in compatibility with TLS 1.3 (albeit not part of suite B).
It has supported ECDSA public keys using the secp521r1 named curve for a long time and AES256 (in some form) for a very long time.
For the first time in a very long time (or possibly ever) it seems to me that it is now possible to actually achieve 256 bits of effective symmetric security taking into account the weaknesses in other components of the crypto stack.
I am basing this assumption on an oft cited academic paper [did not see the need to dig it up for this question but it was put together by top men] that set out the corresponding public key length in RSA and EC terms for a given symmetric key length. This paper effectively says 2048RSA is roughly equivalent to 112bits and that EC key lengths are roughly half the strength of symmetric keys (i.e. secp256k1 == 128bits).
Now, TLS 1.3 has a maximum SHA2 level of 384bits and Firefox does not exceed the standard in this respect. The specific cipher suite am deploying is ECDH-AES256-GCM-SHA384 (w/ P-521).
My question to crypto.SE is- what am I losing in terms of encryption security by having client browsers supporting a max of SHA384?
My question has two supporting addenda/subqueries:
Firstly, the checksum would seem irrelevant to me given I'm using an AEAD (AES256GCM) cipher. What am I missing here?
Secondly, in case somehow I'm missing the point and (speculating) the SHA384 somehow refers to authentication with respect to the ECDH component of the stack- is my risk here (assuming my attacker can find collisions for SHA384 but NOT for SHA512) that my attacker can inject false messages into my communications or could it (very remotely) strengthen my attacker's ability to decrypt my communications?
Finally, I'm well aware that the weakest link in my attack surface area is in so many other easier places than the cryptographic primitives, however, for the sake of good tin foil and for my OCD, it would be really lovely to get some guidance.
Finally- oh how it would be nice for every browser and every crypto library in the world to support AES, Threefish, quantum resistant algos, Ed448 (Big one that I would trade the others for), SHA3, Twofish, etc. Add all this bloat in and leave it to implementers to configure and choose wisely.

Firstly, the checksum would seem irrelevant to me given I'm using an AEAD (AES256GCM) cipher. What am I missing here?

Well, what you're missing is what TLS does with the specified hash.  Contrary to your assumption, it does not append a hash to each record; as you point out, that'd be silly.
Instead, it uses it for two purposes:

Within the Key Derivation Function, that is, as a part of the infrastructure that maps P521 shared secrets and public data to actual keys

To summarize the exchange transcript (to detect downgrade attacks)

Which leads us into your next question:

is my risk here (assuming my attacker can find collisions for SHA384 but NOT for SHA512) that my attacker can inject false messages into my communications or could it (very remotely) strengthen my attacker's ability to decrypt my communications?

If the attacker is attempting to listen into a negotiation between two honest parties, he doesn't get to chose what is hashed; that means that a collision attack wouldn't apply (because a collision attack assumes the adversary has the capability to select both values that hash to the same one).  And, even if the adversary were able to inject his chosen plaintext (e.g. via a Javascript applet), that wouldn't help, because what is hashed is selected by the TLS implementations and not the applications.

My question to crypto.SE is- what am I losing in terms of encryption security by having client browsers supporting a max of SHA384?

It wouldn't appear that you're missing much at all; other parts of the system would appear to be more vulnerable.


Encoding vs. Compression vs. Encryption In what ways does encryption differ from proprietary/secret compression schemes and codecs?

OK, there seems to be some confusion with regards to terminology, so let's try to clean that up. I'll try and define things myself, but also provide the more formal Wikipedia definitions.

Encryption. Encryption usually is the process of concealing information solely based on the secrecy of some smaller value, which is called "a key" most of the time. Modern schemes allow for advanced functionality, such as operation on unknown data and guaranteeing the data integrity. Algorithms are not secret with encryption *.
*Except if you experience snake-oil crypto from which you should run. fast.

Wikipedia's definition:

  In cryptography, encryption is the process of encoding messages or
  information in such a way that only authorized parties can read it.

Compression. Compression algorithms are techniques that exploit redundancy in data to reduce the size of the data representation. This redundancy may be of strict mathematical nature or also of psychological nature (e.g. humans don't hear beyond 20-30kHz so you can strip that out as part of the compression). Compression algorithms aren't meant to conceal data, but may do so, if the compression algorithm is secret - until somebody reverse-engineered the algorithm.

Wikipedia's definition:

  In signal processing, data compression, source coding, or bit-rate
  reduction involves encoding information using fewer bits than the
  original representation. Compression can be either lossy or lossless.

Encoding. Encoding is the process of changing data representation. The same data may be represented in different encodings (such as binary, hex, decimal, base64, DER, BER, ...) which aren't (usually) meant to change the data's meaning. Size expansion / reduction may of course be a result of a different encoding. Encodings aren't meant to conceal data, but may do so, if the encoding / decoding alorithm is secret - until somebody reverse-engineers the algorithm.

Wikipedia's definition:

  An encoder is a device, circuit, transducer, software program,
  algorithm or person that converts information from one format or code
  to another, for the purposes of standardization, speed or
  compressions.

Codec. Most of the time a codec is a special compression format, usually paired with a defined encoding.
Wikipedia's definition:

  A codec is a device or computer program for encoding or decoding a
  digital data stream or signal. [...] A codec encodes a data stream
  or signal for transmission, storage or encryption, or decodes it for
  playback or editing.


In search of a pedagogically simple example of asymmetric encryption routine? (I am not a cryptography expert; I do write software)

I am working with some youth (ages 11-13) and wanted to explore for an hour or so some basic cryptography. Doing symmetric ciphers is pretty straightforward. It's easy to explain the various "two key" metaphors of asymmetric encryption, but I'm finding it hard to find a good easy-to-work mathematical example of asymmetric encryption. There are lots of good examples of RSA broken down, but even with small numbers you get into "big" numbers fast because of the power functions.

Is there a good example of a "toy" algorithm to illustrate the asymmetric encryption/decryption process?

Asymmetric encryption: What?

Alice wants to be able to receive messages sent by anyone, posted on a public website or whatsapp group, that only her will be able to decipher. Traditional cryptography would require that the sender and her share some secret (key or password), used for encryption and decryption.

In asymmetric encryption, Alice generates and keep a secret private key, and openly shares a corresponding public key. Anyone with Alice's public key can encipher a message to her. Alice's private key is necessary to decipher it.

Asymmetric cryptography also includes digital signature: Alice signs data with her private key, then anyone with Alice's trusted public key can verify that she signed that exact data. All this was thought impossible until the 1970's. It is now commonplace, e.g. in web browsers.

Asymmetric encryption: How?

It's done with mathematics. Only a computer can realistically perform the computations. One of the commonly used method is ElGamal encryption. We can illustrate that with a little Python.

We'll use Python's pow(a, x, n). It computes "a to the power x modulo n". In this, "a to the power x" means x copies of the number a multiplied together; and "modulo n" means that we keep what remains when dividing by n.

Take pow(2, 4, 10) for example. "2 to the power 4" is 2×2×2×2, that is 16. When we split 16 things among 10 persons, each gets 1 and it remains 6.
Therefore, pow(2, 4, 10) yields 6.

Alice will chose a private key at random, and compute her public key as
PublicKey  = pow(2, PrivateKey, n). This is easy and fast in Python, but computing PrivateKey from PublicKey is believed infeasible by even the most powerful computer, when n is a large-enough safe prime, and PrivateKey is random and large. n is typically made public, like this. We'll use something just as safe but easier to key-in:

# Setup
import secrets                      # needed for randbits
n = 2**4096 - 3**2542 + 3547696     # some public 4096-bit safe prime

# Alice generates her keys
PrivateKey = secrets.randbits(400)  # generate secret Private Key
PublicKey = pow(2, PrivateKey, n)   # compute Public Key

# Barnabé got PublicKey and wants to send a message to Alice
M = "Surprise for you in my locker, code 47918. Barnabé"
# turn M into an integer m, at most 500 bytes
m = int.from_bytes(bytes(M, 'utf-8'), byteorder='big')
assert m.bit_length()<=4000         # bark if message is too large

# encryption of m into Ciphertext
x = secrets.randbits(400)           # number used once
r = pow(2, x, n)                    # Alice need this to decipher
s = pow(PublicKey, x, n)            # shared one-time secret
c = (s%(2**4000)) ^ m               # produce ciphertext using XOR

# remove Barnabé's secrets
del M, m, x, s

# Alice receives ciphertext c and r, and deciphers that using PrivateKey
s = pow(r, PrivateKey, n)           # shared one-time secret
m = (s%(2**4000)) ^ c               # decipher using XOR
# turn integer m into a string M
M = str(m.to_bytes((m.bit_length()+7)//8, byteorder='big'), 'utf-8')
print(M)                            # show the deciphered message

# remove Alice's secrets, except her PrivateKey which can be reused
del s, m, M

The values of s computed by the sender during encryption is pow(pow(2, PrivateKey, n), x, n), that used by Alice during decryption is pow(pow(2, x, n), PrivateKey, n), and thanks to  mathematical properties of pow these are the same.

Summary: with asymmetric encryption, nothing secret is needed to send a confidential message. We can do with some clever math, a trusted computer able to generate random numbers, and the trusted public key of the intended receiver.

Pedagogical notes

While I believe that a sizable fraction of a 17yo audience would be able to grasp/appropriate/extend the above, only a small fraction of 11-13yo would. Thus I think the best with such young audience is to explain what asymmetric encryption does (and if possible digital signature, which is at least as useful). Illustrate that using key generation/encryption/decryption boxes with the corresponding Python code inside as small characters or truncated, and the values exchanged shortened with ellipsis, but do not dive into exactly what the code does. But give access to material (source code) showing how this is done and allowing to reproduce it. Those ready for that might use it.

ElGamal encryption is a direct transposition for encryption of Diffie-Hellman key exchange, one of the first asymmetric cryptosystem published. It is using that for all positive integers $a,n,\text{PrivateKey},x$,
$${\left(a^\text{PrivateKey}\right)}^x\equiv a^{\text{PrivateKey}\,x}\equiv a^{x\,\text{PrivateKey}}\equiv{\left(a^x\right)}^\text{PrivateKey}\pmod n$$
and, for $n$ a large safe prime and most $a$ including 2,  if $x$ and $\text{PrivateKey}$ are chosen at random, with $a$, $n$, $a^\text{PrivateKey}\bmod n$ and $a^x\bmod n$ public but $\text{PrivateKey}$ and $x$ are large random unknowns, then $a^{x\,\text{PrivateKey}}\bmod n$ is believed computationally indistinguishable from random in $\Bbb Z_n^*$ except for 1 bit of information. If we spare some high-order bits, the low-order ones are a shared secret, which we use for symmetric encryption using XOR.

This is not toy cryptography. That's IND-CPA secure asymmetric encryption in the academic sense. Parameters give a very high security level. The later has no penalty in a pedagogical context since the computations can't be done by hand anyway, and the code remains fast enough on anything running Python 3.

However, it must be noted that ElGamal encryption, and the code, have serious shortcomings:

There's nothing to prevent alteration of Alice's public key on its way to Barnabé, and that allows an attack. Barnabé could be tricked to use some adversary's public key instead of Alice's, and then the adversary could decipher the message and access Barnabé's locker.
There's no authentication: Alice is not sure that the message is from Barnabé. Anyone can encipher any message towards her.
There's worse: an adversary can subtly alter the message and get some information. For example: guessing that the message ends in Barnabé (because he always do that), an adversary could alter the ciphertext so that what Alice deciphers ends with a different name. Alice might try and fail to open that other person's locker; and if the adversary rigged that locker to beam Alice's attempted code, the attacker now can access Barnabé's locker before Alice can. More generally, the scheme lacks IND-CCA2 security.
Secure storage of keys and key distribution are not illustrated.
Ciphertext transmission/reception is eluded.
The code is not protected against implementation attacks (e.g. padding oracle, timing and side-channels).

Small parameters would limit the message size, or make the code more complex. That would also be teaching kids to make unnecessary compromise (in the same spirit, I have not limited the message to ASCII, and it's size is range-checked, because we should promote sound coding habits when possible). However, there can be imperatives to use smaller values, like adapting the demo code to an environment without built-in support for large integers, or actually transferring the values between individuals on paper. In that case, perhaps limit message to 24 bits (3 bytes, good for 3 or 4 characters), change n to 2147481143, 2**4000 to 16777216, and use random integers in range [1, 1073740570] for PrivateKey and x. Of course, all security is lost: a programmable calculator can find the private key.

I have refrained from introducing RSA, because it uses heavier math (we need modular inversion and the little Fermat theorem to explain why it works), and RSA is harder to implement. Worse, most pedagogical implementations have a fundamental shortcoming: a guess of the plaintext (e.g. a name on the class roll) can be verified from the ciphertext. Independently, the parameters are typically so small that this check can be made letter by letter; and re-encrypting the ciphertext a small and fixed number of time is enough to decipher without any guesswork. Also the modulus can be factored, typically by hand (perhaps with Fermat's method).

My point of view is that it is best not to mislead an audience, especially a young one, into believing they understand how asymmetric encryption works, or that it can be done with 10-digit numbers. It took centuries of effort to devise it, and that's because it's hard.


Prove monoalphabetic cipher is a valid symmetric cipher I should prove mathematically that:

$D_k(E_k(p))=p$

I know

$E_k(p)=c=(p+k)\bmod26$

and

$D_k(c)=p=(c-k)\bmod26$

Substituting the two formulas to the initial assertion I have

$((p+k)\bmod26-k)\bmod26=p$

And applying the $\bmod$ property twice I have

$((p \bmod26+k \bmod26)\bmod26)-k)\bmod26=p$
$((p\bmod26+k\bmod26)\bmod26)\bmod26-k\bmod26)\bmod26=p$

But from here? How can I get rid of all that bunch of $\bmod$ to have $p$?

The lemma you need for this is that $$((a \bmod m) + b) \bmod m = (a + b) \bmod m \tag{1}$$ for all integers $a$, $b$ and for all positive integers $m$.  In other words, this lemma says that, if you're going to add (or subtract) a bunch of numbers together and then reduce the sum modulo $m$, it doesn't matter whether or not you reduce any (or all) of the summands modulo $m$ first.

The easiest (and most usefully generalizable) way to prove the lemma (1) above is via the notion of modular congruence.  Basically, we define $a$ and $b$ to be congruent modulo $m$, written as $a \equiv b \pmod m$, if $a = b + km$ for some integer $k$.  From this definition, it immediately follows that $$(a \bmod m) \equiv a \pmod m$$ and, in fact, that $$(a \bmod m) = (b \bmod m) \iff a \equiv b \pmod m.$$

We can also show that the modular congruence relation $\equiv$ obeys many of the same algebraic laws as normal equality.  In particular, we can show that it is transitive, i.e. that $$a \equiv b \text{ and } b \equiv c \implies a \equiv c \pmod m,$$ and that it is compatible with addition in the sense that $$a \equiv b \iff a + c \equiv b + c \pmod m.$$

Applying these properties of modular congruence, we can see that $(a \bmod m) \equiv a \pmod m$ implies $(a \bmod m) + b \equiv a + b \pmod m$, which then implies lemma (1).

  Bonus exercise: Also show that modular congruence is compatible with multiplication in the sense that $$a \equiv b \implies ac \equiv bc \pmod m.$$

Now that we've proven lemma (1), the rest is simple: $$\begin{aligned}
D_k(E_k(p)) &= ((p + k) \bmod 26) - k) \bmod 26 \\
&= (p + k - k) \bmod 26 \\
&= p \bmod 26.
\end{aligned}$$  If $0 \le p < 26$, then $p \bmod 26 = p$, and we're done.  (We do need to make this additional assumption for the encryption to be reversible, since it would not hold if $p$ could take other values!)

Of course, we could've also skipped lemma (1) entirely, and just appealed directly to modular congruence, and in particular to the fact that $$E_k(p) = (p + k) \bmod 26 \equiv p + k \pmod{26}\,\,$$ and $$D_k(c) = (c - k) \bmod 26 \equiv c - k \pmod{26},$$ from which it follows that $$D_k(E_k(p)) \equiv p + k - k = p \pmod{26}.$$


A fast non-cryptographic hash function that is "strong enough"? I'm designing a simple one-time-password mechanism for authentication against a possibly-insecure server - i.e. I don't want to use symmetric shared secrets.

The first idea that came into mind was using a hash-chain with a cryptographic hash function, where each device has a random $\text{key}$ and broadcasts
$H^n(\text{key}), H^{n-1}(\text{key}), H^{n-2}(\text{key}), \ldots, H^{1}(\text{key}), \text{key}$.
However, storing the whole chain requires too much memory for my needs.

I found some techniques here and here to store only few elements from the chain ($H^{n-k}(\text{key}), H^{n-2k}(\text{key}), H^{n-3k}(\text{key}), ...$), and calculate the elements in between dynamically.
This converts the "space problem" to a "calculation cycles problem" - unfortunately all the cryptographic hash functions that I've checked require too many cycles (=too much power consumption) for my needs, considering the fact that I have to calculate them multiple times in order to save a significant amount of space.

I consider using less secure hash function for the dynamic hash calculation.
This hash will be used only for the elements "between" $H^{n-k}(\text{key}), H^{n-2k}(\text{key}), H^{n-3k}(\text{key}), ...$ so it has to be "unbreakable" only for $k$ time - suppose a key is generated every minute, finding $k$ sequential preimages in $k$ minutes should be "really hard" (but finding them in $10k$ minutes may be possible).

I don't care about second preimage resistance, or defending against very resourceful attackers.

Do you have any suggestions for a hash function? What about SipHash-2-4?

So what you need is a fast cryptgraphically secure hash function?
There are some.
If you're in hardware Keccak might be an option as it uses many bit-permutations.

If you're in software there are Skein and Blake2b/s/bp/sp. Skein was the fastest hash-function of the SHA-3 competition and Blake2 is the successor to BLAKE, the second fastest hash-function in the SHA-3 competition.

You might find this page helpful.


What does the〈 〉notation mean in this situation? I was looking at solutions for a problem but I noticed it said $\langle2\rangle$ and was unsure of what that meant.

From Homework 5 (PDF)

From the context of the exercise, it appears that $\langle x\rangle$ is meant to denote a canonical representation of the integer $x$ as a bitstring of length $n$.

If this were not the case, those inputs and outputs would not be in the correct  domain and range respectively.

Likely this notation was defined somewhere in the lecture notes, but I cannot find them at the moment.


what's the purpose of passphrase in hybrid cryptography? What's the purpose of a passphrase in hybrid cryptography? can it actually be used for authentication or if i put in another signature algorithm will it be like, two authentications?

Some systems like SSH will use passphrases to control the use of private keys: instead of storing the private key unencrypted on disk it's stored encrypted (symmetrically) by a key derived from a passphrase. That ensures that only an authorized user can use the SSH key pair to access a remote system.
There's no requirement for passphrases in hybrid cryptography in general. EG TLS doesn't use passphrases and involves hybrid cryptography (asymmetric key exchange + symmetric encryption).


What is the intuition behind AES or SPN? I'm new to cryptography and have just encountered AES and SPN. I would like to know how the S-box, permutation step and the MixColumn step help improve security. It seems to me (perhaps mistakenly) that the security is provided solely by the key and that the substitution, permutation and MixColumn steps are redundant.

I know I must be wrong, but can't put my finger on it.

Also, is there a small example of AES which can be implemented by hand?
I think seeing it would help with my understanding of the concept.

The s-box and linear round operations would be entirely redundant if AES were only ever used to encrypt 128 bits per key (i.e. if you changed keys for every 128 bit block).  Because then you would have the one-time pad, which is secure just by xoring the key with the message.

However, ciphers like AES are based on computational complexity (rather than information theoretic security), and purport to securely encrypt plaintext that vastly exceeds the length of the key.  The claim of security is that realistic opponents, using realistic amounts of computational resources, have only a vanishingly small chance of recovering any information about the plaintext or the key.  Or in other words, recovery of unknown plaintext information that has been encrypted with AES and an unknown key is supposed to be a computationally hard problem.

If AES did not have highly non-linear s-boxes, then the problem would be very easy, as daniel points out in his answer.  This is because AES would then be an entirely linear system (linear in the Galois finite field of characteristic 2), and given a small amount of plaintext (just one or two blocks worth should be sufficient) we could use Gauss-Jordan elimination to solve the system and thereby recover the unknown key (or at least enough of it to decrypt and encrypt whatever we liked).

If AES did not have the linear operations (the byte permutation step and MixColumns step), then it would be easy for a different reason.  Those steps provide 'diffusion', whereby information about one part of the 128-bit block is  'mixed' with information from other parts of the block.  If there was no mixing, then each 8-bit section (byte) of the 128-bit block would be 'segregated' from every other byte.  So differences in one byte in the input plaintext would result in differences in only that same byte of the output ciphertext (which can reveal information about the plaintext).  Also, you would only have to guess that small part of the key that interacts with a single byte in order to 'decrypt' that byte, and it is much easier to decrypt by brute-force-guessing a small part of the key rather than the entire key.

Together with the s-box, this diffusion means that after just a few rounds, every single bit of the output is a very complex, high-degree, non-linear function of every single bit of the input and the entire key.  Highly non-linear systems of equations are much harder to solve than linear systems of equations.

That said, the reason why AES uses that particular s-box and those particular linear steps has to do with the methods of cryptanalysis in use at the time it was designed.  AES was carefully designed to resist two very powerful types of attack called differential cryptanalysis and linear cryptanalysis (and some related variants) that broke many block ciphers in the generation prior to AES.  To have an 'intuitive sense' of why AES is the way it is, you need to understand those two attacks.


Proving that you have $k$ keys out of $n$ without revealing which keys they are I'm looking for a cryptographic algorithm where Alice can prove that she has at least $k$ private keys out of $n$ to Bob, without revealing which keys she knows.

As I wrote in a comment, I believe your solution only works with some public-key schemes, because usually a full-blown public encryption scheme must include randomness to allow encryption of low entropy plaintexts without others being able to guess and encrypt. (Still, it would probably allow verification of key-ownership in some such schemes if access to the underlying primitive like unpadded RSA is assumed.)

A patched solution is for Bob to use Shamir Secret Sharing to share a symmetric key, which he uses to encrypt all the necessary information to reproduce the public-key ciphertexts. That is, he creates a symmetric key, computes the shares and encrypts them using each public key. He then encrypts both all the coordinates and the steps taken to encrypt them, including any randomness the schemes may use, using the symmetric key.

(He does not need to reveal any coordinates in plaintext, but should encrypt all the public keys if Alice does not know them. This means the scheme reveals to Alice which the other public keys were if she has the $k$-subset.)

Alice will be able to verify that the coordinates are on the same polynomial and that they were indeed encrypted using each public key.


Can I replace DH by a post-quantum key exchange in IBAKE for post-quantum identity-based authenticated key exchange? IETF RFC 6539 IBAKE - Identity Based Authenticated Key Exchange describes a Hybrid key exchange using both Identity based cryptography and a standard ephemeral elliptic curve Diffie-Hellman key exchange.

Since that protocol already is a hybrid could one replace the elliptic curve Diffie-Hellman exchange from IBAKE with something like SIKE or some other PQC scheme and use that for an effective PQ Hybrid?

It seems like a PQ exchange inside of IBAKE would give users long term protection against quantum computers.

The security proof for the original IBAKE protocol is found in IBAKE: Identity-Based Authenticated Key Exchange Protocol.  The IBAKE scheme described there uses an Identity Based Key Exchange to authenticate an ephemeral elliptic curve Diffie-Hellman key exchange.  The scheme uses two different elliptic curves one for the ephemeral elliptic curve Diffie-Hellman exchange (ECDHE) and a pairing friendly curve to serve as the basis for the Identity Based Key Exchange.  The security proof requires that the ephemeral key exchange be secure but it does not rely on any particulars of the ephemeral key exchange being used.  Therefore on could replace the quantum vulnerable ECDHE with a quantum secure key exchange like
SIDH or New Hope and the proof of security of the protocol will still hold.

Using SIDH instead of a Lattice Based Key exchange would keep the protocol packet sizes within a few hundreds of bits of the original IBAKE scheme.  Using and ephemeral SIDH (SIDHE) in place of ECDHE in IBAKE would lengthen the useful lifetime of IBAKE until an adversary actually has a quantum computer because the SIDHE exchange would protect against the well know "store then break" attack.


Why many passes at file removal? Why file removal tools offer gost 2 passes and British 3 passes or even gutman 35 passes options? In which case the single pseudo random pass is not enough?

This has to do with the physical nature of the storage device. Simply deleting the reference still leaves the data available for recovery. Writing once over randomly might still leave chunk traces of data which could be pieced together.

It is not generally considered easy to recover information overwritten once, and for your own pc... being donated or sold... once is probably enough. Depending on your own scale of paranoia you can use more passes.


What makes a hash like SHA1 resistant to collisions? I have been reading about SHA1 and SHA256 and how they actually hash a string of text to a unique hashed message. But what I dont understand is what makes them resistant to collisions.

Whats the best way to find a hash collision?
What makes a hash algorithm resistant to collisions?
If we find 1 collision because it has to be caused by a particular input, cant we just discount that SHA result as a possible candidate for a problematic hash and assume most other results will be fine?

Collisions will always happen because of the infinite sized input space and finite sized output space (the pigeonhole principle). So the goal is that collisions can not be found in any less time then simply trying random inputs until a collision is found - it's not possible to have a compressing hash function where collisions do not exist, they must exist and so we have to settle for making them hard to find instead.

  What makes a hash algorithm resistant to collisions?

The first thing is actually the padding of the message. If this is not done, collisions are usually trivial to produce.

The output of the function for any input should be unpredictable. Any degree of predictability in the output can be used to search for collisions faster then brute force.

In the worst case, the hash is completely linear and collisions can be computed from a simple expression.

In the best case, the value of any particular bit in the hash output cannot be guessed with probability better then 50%.

The exact, specific, best way to produce a hash function that produces unpredictable outputs doesn't really have an exact answer. There are a variety of ways to attempt to predict the output of the function, such as linear and differential cryptanalysis for example. Hash functions are designed with these kinds of attacks in mind.

Ideally the authors of the function would determine what the best possible attack is, then simply configure the function parameters to be large enough to where the attack does not apply anymore. While it is hard to know what the best possible attack is, with the right design strategy you can ensure a high level of resistance against the known classes of attacks.

  What is the best way to find a hash collision

This depends on the particular hash function in question.

If it is a non-cryptographic hash, there may exist a simple expression that will allow you to calculate collisions outright with no search effort required.
If it is SHA1 you are curious about, then you would want to read about the recent attacks on SHA1
If it is some other hash function, then you would need to locate some pre-existing research that analyzes it (or perform such analysis yourself if it is a construction of your own).

  If we find 1 collision because it has to be caused by a particular input, cant we just discount that SHA result as a possible candidate for a problematic hash and assume most other results will be fine?

It's not really clear what you are asking: It sounds like you are testing some other hash function and wondering if, despite finding a collision, it's safe to "assume" it's not broken somehow and other collisions can't be found.

If that is the case, then no, it is not safe (or reasonable) to make that assumption. If the hash is padded correctly and has an sufficiently large output size, then you should never witness a collision for it. If you do, then other collisions will probably follow eventually (attacks get better, not worse).


RSA signature scheme In RSA signature scheme, it is a common practice to 'sign' the hash value of the message so that the length can be fit.

Question: If we have $s=m^d \bmod n$ where $d$ satisfies $ed \equiv 1 \pmod{n}$ and we also know $s$ and $m$, is this still considered secure?

The main problem here is that signature is malleable. Given signatures on $m_1$ and $m_2$ allows you to construct a valid signature on $m_1m_2$ by multiplying the signatures. Therefore, the answer is no. When you hash you don't have $H(m_1m_2)=H(m_1)H(m_2)$, so hashing destroys this algebraic structure that connects messages and signatures.

EDIT: I'm assuming the question is whether you can sign without hashing when the messages to be signed are already intergers modulo $n$, i.e. you don't need to hash your messages to make them elements of this group.


How slow is the hash used for Mac FileVault encryption? Certain password strength estimators (for instance, zxcvbn) give estimates that vary with the speed of the hash and the assumed resources of the attacker. I am curious what hash is used by the MacOS FileVault encryption on MacBooks, and whether it should be considered a "fast" or "slow" hash for the purpose of estimating the speed of an attack on it.

More specifically, how many hashes per second could a good modern GPU perform, for the purpose of cracking a password protecting a FileVault drive?

Modern FileVault is a relatively slow hash. hashcat supports attacking FileVault 2 hashes as mode 16700.

As an example of real-world attack capability, if a seven-character password were truly randomly generated, then it would take a little more than seven years to fully exhaust on a rig with six reasonably fast GPUs:

$ hashcat -a 3 -m 16700 -w 4 filevault.hash ?a?a?a?a?a?a?a
hashcat (v5.1.0-1685-gf946e321) starting...

CUDA API (CUDA 10.1)
====================
* Device #1: GeForce GTX 1080, 7006/8119 MB, 20MCU
* Device #2: GeForce GTX 1080, 7027/8119 MB, 20MCU
* Device #3: GeForce GTX 1080, 7037/8119 MB, 20MCU
* Device #4: GeForce GTX 1080, 7027/8119 MB, 20MCU
* Device #5: GeForce GTX 1080, 7037/8119 MB, 20MCU
* Device #6: GeForce GTX 1080, 7027/8119 MB, 20MCU

[...]

Session..........: hashcat
Status...........: Quit
Hash.Name........: FileVault 2
Hash.Target......: $fvde$1$16$84286044060108438487434858307513$20000$f...704191
Time.Started.....: Wed Mar  4 20:23:59 2020 (11 secs)
Time.Estimated...: Tue May 12 22:42:02 2026 (6 years, 69 days)
Guess.Mask.......: ?a?a?a?a?a?a?a [7]
Guess.Queue......: 1/1 (100.00%)
Speed.#1.........:    59646 H/s (273.90ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#2.........:    59243 H/s (275.66ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#3.........:    59351 H/s (275.32ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#4.........:    59343 H/s (275.15ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#5.........:    60227 H/s (271.48ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#6.........:    59819 H/s (273.29ms) @ Accel:16 Loops:1024 Thr:1024 Vec:1
Speed.#*.........:   357.6 kH/s
Recovered........: 0/1 (0.00%) Digests
Progress.........: 3932160/69833729609375 (0.00%)
Rejected.........: 0/3932160 (0.00%)
Restore.Point....: 0/735091890625 (0.00%)
Restore.Sub.#1...: Salt:0 Amplifier:2-3 Iteration:0-1024
Restore.Sub.#2...: Salt:0 Amplifier:2-3 Iteration:0-1024
Restore.Sub.#3...: Salt:0 Amplifier:2-3 Iteration:0-1024
Restore.Sub.#4...: Salt:0 Amplifier:2-3 Iteration:0-1024
Restore.Sub.#5...: Salt:0 Amplifier:2-3 Iteration:1024-2048
Restore.Sub.#6...: Salt:0 Amplifier:2-3 Iteration:1024-2048
Candidates.#1....: 1arieri -> 1p8xana
Candidates.#2....: 1(ZDERI -> 1uxMONA
Candidates.#3....: 1w9zana -> 1YiQUS1
Candidates.#4....: 1TdWERI -> 1#UDERI
Candidates.#5....: 1r0qwon -> 1kF~~~1
Candidates.#6....: 1O_ !!! -> 1@[1199
Hardware.Mon.#1..: Temp: 44c Fan: 80% Util:  0% Core:1784MHz Mem:4513MHz Bus:8
Hardware.Mon.#2..: Temp: 36c Fan: 81% Util: 19% Core:1759MHz Mem:4513MHz Bus:4
Hardware.Mon.#3..: Temp: 47c Fan: 80% Util: 42% Core:1860MHz Mem:4513MHz Bus:16
Hardware.Mon.#4..: Temp: 45c Fan: 80% Util: 33% Core:1759MHz Mem:4513MHz Bus:4
Hardware.Mon.#5..: Temp: 37c Fan: 80% Util: 52% Core:1898MHz Mem:4513MHz Bus:1
Hardware.Mon.#6..: Temp: 43c Fan: 80% Util:100% Core:1784MHz Mem:4513MHz Bus:1

Started: Wed Mar  4 20:23:47 2020
Stopped: Wed Mar  4 20:24:12 2020


Padding Oracle Attack CBC Mode: If the set of characters of plaintext is known, then can you speed up the process Consider AES-256, 128-bit blocks, and PKCS#5 Padding.
During a Padding Oracle Attack, a manipulated byte of cipher text is sent to the oracle and we eventually hope to find out what that respective byte of plaintext was.
If I know the set of possible characters in the plaintext will only be lowercase english letters, then is there any way in which I can speed up the deciphering process? If so, then specifically what would this look like?

I will assume you generally understand the mechanics of the padding oracle attack. Say we have some ciphertext block $c_i = c_{i-1} \oplus E(k,m_i)$ and we want to find the last byte of $m_i$. Let $b$ denote the last byte of $m_i$, which we are trying to find.
Consider ciphertexts of the form $(c_{i-1} \oplus \texttt{00} \cdots \texttt{00} g,c_i)$, where $g$ is a single byte. Such a ciphertext decrypts to $m_i$, except the last byte has been changed from $b$ to $b \oplus g$. When the server decrypts, it sees a string that ends in byte $b \oplus g$ --- does this string have valid padding? In most cases, it has valid padding only when $b \oplus g = \texttt{01}$ (lets assume that $m_i$ doesn't end in $\cdots \texttt{02}\,b$ or $\cdots \texttt{0303}\,b$, etc). When the server tells us which choice of $g$ leads to valid padding, we can solve for $b = \texttt{01} \oplus g$.
If you know that $b$ is one of only 26 possible values, then there are only 26 possible values of $g$ that you need to try -- compared to the general case where you have to try all 256 choices of byte $g$. I only mentioned the case of finding the last byte of the plaintext, but the same logic applies for any byte.


Is the context of "constant time" algorithms inclusive when you have a clock control? There is generally a push to make algorithms and components constant time to be resistance to side channel attacks.  For instance, AES-NI instructions take as many cycles as rounds; however, I can lower the CPU voltage and increase the clock speed until I see errors on the result.  The circuits are only constant time if they satisfy the critical path propagation between latch boundaries.

When I read a paper that specifically says that it robust to side channel attacks because the algorithm is constant time, is the assumption that one does not have clock/voltage control?

To elaborate a bit on the boundaries that I mention, consider the following image that represents a pipeline of logic:

In the image, there is a logic cloud that is operating on n-bits of information with a result.  This is much like what a multiplicative inversion module looks like in hardware where you load the starting value and you then "latch" the result.  The fundamental idea is that the clock line, CLK, is slow enough that you satisfy the worst-case propagation condition electrically.  If I decrease the process voltage, and keep the clock the same speed, I can violate the path requirements.  If I increase the clock speed for the same voltage, I also violate the requirements electrically.

When I read a paper that specifically says that it robust to side channel attacks because the algorithm is constant time, is the assumption that one does not have clock/voltage control?

Generally, when we mention side channel without context, we actually mean a side channel in software. I.e. an adversary has (only) the ability to run code on the same CPU. Moreover, the adversary does not have physical access to the executing CPU.

In your case—underclocking the CPU and screwing around with the power supply—you are manipulating the CPU itself. In my book this would be considered a fault attack, which is a technique in hardware side channel analysis. Hardware side channel analysis is super-powerful, and because so much is possible it has a less obvious defined attacker model.

So it kinda depends on the context. Most of the time the literature will be about software side channels (time, cache, etc.). But when you are reading a CHES paper, it's probably about hardware.


Using a hash function as a random number generator Using MD5 or SHA1 for instance, and applying integers (as seed so to speak) to the hash function, in sequence, and only keeping, say, the first 64 bits of the resulting hash, do we always have a probability close to $1/{2^{64}}$ to have $$\text{hash}_{64}(n) = \text{hash}_{64}(n+1)$$ for every $n\in\big[1,2^{64}]$?

Caveat: that answer is written with my mind in Vulcan mode. That is, I'm answering the question as taken literally (in the first part); or in only a minor variant (second part); and ignoring the question's title, which I find unrelated, especially given the limited span of $n$.
The probability considered is $0$ for each of the many different common ways to define $\text{hash}_{64}(n)$ as the first 64 bits of the MD5 or SHA-1 of integer $n$. Whether $0$ is "close to $1/2^{64}$" is a matter of opinion.
For a few other definitions of $\text{hash}_{64}(n)$, that probability is $1$, which is not "close to $1/2^{64}$" by many accounts.
Justification: it is considered the probability $p$ that for every $n$ in $\big[1,2^{64}\big]$ it holds $\text{hash}_{64}(n)=\text{hash}_{64}(n+1)$.
For fixed function $\text{hash}_{64}$ this is a probability that a certain determined fact holds or not, and thus $p$ is either $0$ or $1$ depending on the function $\text{hash}_{64}$. This also holds (perhaps with a different $p$) if we change every to some.
For the many different common ways to define the function $\text{hash}_{64}$ for an integer parameter as the first 64 bits of the MD5 or SHA-1 of that integer, that probability is $0$. For example, if we define $\text{hash}_{64}$ to be the first 64 bits of the SHA-1 of the shortest big-endian decimal representation of $n$ encoded in ASCII, then $\text{hash}_{64}(1)$ is the SHA-1 of the single byte 0x31, that is b6589…8410ch, while $\text{hash}_{64}(2)$ is the SHA-1 of the single byte 0x32, that is da4b…0b0ch, thus they do not match.
We could try with MD5 and SHA-1, various common bases (including 2, 8, 10, 16, 64, 256, 232), common suitable alphabets (ASCII, EBCDIC, binary, bytes) and common variants (uppercase or lowercase hex, various base64 idioms), endianness (big, little, various mixed), and width for $n$ (fixed to say 64 with some exception for $n=2^{64}$, 65, 72 or 96 bits, adaptive according to $n$ with various steps like even which is common with hex). But I'm not convinced that we would find any such $\text{hash}_{64}$ with $\text{hash}_{64}(1)=\text{hash}_{64}(2)$. And I'm ready to bet the house $\text{hash}_{64}(2)=\text{hash}_{64}(3)$ won't hold in addition.
When we average the probability asked over all the possible definitions of $\text{hash}_{64}$, we get $2^{\left(64-2^{70}\right)}$. That's a ludicrously small number, yet not zero.

Now perhaps we should instead consider the probability $p$ that for a random $n$ in $\big[1,2^{64}\big]$ it holds $\text{hash}_{64}(n)=\text{hash}_{64}(n+1)$.
That probability $p$ is $k/{2^{64}}$ for some integer $k$, which can be computed with significant but feasible effort from the exact definition of $\text{hash}_{64}$.
When we average $p$ over all the possible definitions of $\text{hash}_{64}$, we get $1/2^{64}$; thus "close to $1/2^{64}$" for sure.
We can also define the probability $p_k$ that $p$ is $k/{2^{64}}$ for a random function $\text{hash}_{64}$, which is a plausible model for the various $\text{hash}_{64}$ that the question considers. The largest $p_k$ is $p_1$ (meaning $p=1/{2^{64}}$ is the most likely), with $p_0$ extremely close second, both extremely close to $1/e\approx36.8\%$. $p_2$ is about half that, and $p_k$ goes down fast as $k$ grows, down to $p_{2^{64}}=2^{\left(-2^{70}\right)}$, then $p_k=0$ for $k>2^{64}$. It holds $1=\sum p_k$.
We see that $p$ is in the 3-element set $\{0,1/2^{64},1/2^{63}\}$ with probability about $5/2e\approx92.0\%$. We can say $p$ is very often "close to $1/2^{64}$".


How to add ciphered numbers under benaloh's scheme? In the answer for Is it possible to subtract/multiply numbers using homomorphic encryption? it says:

To add two encrypted numbers, one could use Benaloh, Damgård–Jurik, or several other known partially homomorphic cryptosystems. (Many of these "addition-only" cryptosystems can also be tweaked to support subtraction.

But I couldn't write down a way to sum two ciphered numbers with Benaloh's scheme neither find the mathematics for this on the forum.
So, how to sum numbers ciphered under benaloh's scheme without decrypting them?

From here, it says that encryption in Benaloh's scheme takes the form:
$$E_r(m) = y^mu^r\bmod n$$
I'll actually write it as:
$$E_r(m;u) = y^mu^r\bmod n$$
Where $m$ is the message (in $\mathbb{Z}_r$) to be encrypted, and $u\in\mathbb{Z}_n^*$ should  be uniformly random. The other parameters $y, r, n$ are of course important for the scheme, but will not be important to discuss the additive homomorphic properties of the scheme.
The trick here is to note that messages are "in the exponent". So if we want to add the messages, we'll have to multiply the ciphertexts. If we do this, we'll see that:
$$E_r(m_0)E_r(m_1) = (y^{m_0}u_0^r)(y^{m_1}u_1^r) = y^{m_0+m_1}(u_0u_1)^r\bmod n = E_r(m_0+m_1;u_0u_1)$$
This will be a valid Benaloh ciphertext of $m_0+m_1$ (we technically should verify that $u_0u_1$ is distributed uniformly randomly over $\mathbb{Z}_n^*$, but this is not difficult).
Note that this homomorphic property is very similar to that of (unpadded) RSA, where ciphertexts take the form $E(m) = m^e\bmod N$. Of course there is the difference here that RSA must be padded to be secure, and this padding ususally removes the homomorphic property.


Minimum distance between polynomials in ring-LWE Let $R_q=\mathbb{Z}_q[x]/\langle f(x)\rangle$ where $f(x)=x^n+1$, as in the ring-LWE problem.

Let $a(x)$ be chosen uniformly at random from $R_q$.

Question: Is there any theorem that lower bounds the distance between any two polynomials of the form $a(x)s_1(s)$ and $a(x)s_2(x)$?

In other words, what is the value of $d$ such that $$||a(x)s_1(x)-a(x)s_2(x)||\geq d$$ except with negligible probability, for any two polynomials $s_1(x),s_2(x)\in R_q$ and where $||\cdot||$ is the usual $L_2$ norm?

I'm assuming $n$ is a power of $2$ and that $q$ is an odd prime larger than $n$. I'm discarding the trivial case $s_1 = s_2$.

If you consider everything $\mod q$, then it is most likely over the choice of $a$ that there exists $s_1 \neq s_2$ such that $\|a s_1 - a s_2\| = \sqrt{n}$. Indeed, $a$ is invertible in $R_q$ with probability about $1 - n/q$. Take $s_2 = s_1 - a^{-1}$, then you have $a s_1 - a s_2 = 1 \mod q$ and the embedding norm of $1$ is $\sqrt{n}$.

If you do not consider this $\mod q$, i.e. you work in $R=\mathbb Z[x]/⟨f(x)⟩$, then you are precisely asking for the minimal distance $\lambda_1(\mathfrak I)$ of the ideal lattice $\mathfrak I$ generated by $a$. For such an ideal lattice, we can estimate rather precisely this minimal distance. A simple lower bound is
$\lambda_1(\mathfrak I) \geq \Delta_K^{1/2n} \cdot N(a)^{1/n}$, where $N$ denotes the algebraic norm of $a$ (that is, the product of all its embeddings), and $\Delta_K$ is the discriminant of field $K = \mathbb Q(x)/(x^n+1)$. The reason is that the minimal vector $x$ must generate a subideal of $\mathfrak I$, so $N(x) \geq N(a)$, and $\|x\|^n \geq \Delta_K^{1/2} N(x)$. An upper bound is also given by Minkowski's theorem.


Is there difference between Algebraic Homomorphic Encryption and Fully Homomorphic Encryption Schemes? Is there difference between Algebraic Homomorphic Encryption and Fully Homomorphic Encryption Schemes?

It seems that the answer depends on who you ask. Some would say that they are the same. Personally I feel there is a difference. To me, an algebraically homomorphic cryptosystem is one that supports unlimited multiplications and additions of ciphertexts due only to the mathematical structure. A fully homomorphic cryptosystem is one that supports unlimited multiplications and additions of ciphertexts. Thus all algebraically homomorphic cryptosystems are fully homomorphic, but not the other way around.

Given this distinction, none of the existing fully homomorphic cryptosystems are algebraically homomorphic. All existing systems take a somewhat homomorphic cryptosystem and use some tricks to make them fully homomorphic (most commonly Gentry's bootstrapping idea).

PS. I read a paper recently which made this distinction, but cannot seem to find it. I'll keep looking so you'll have a reference other than me.


How to play Mental Skull "Skull" or "Skull and Roses" is a table top game. The rules can be found here.

I was thinking of how I could play this game P2P. At first it seemed easy: Each time I had to place a card face down I would make a choice hash it, send it to my opponent, and then when it needed to be checked you could give out your answer and it could be verified by hashing it. The problem is that without all players revealing all of their card at the end of a round, there is no way to verify that someone didn't put down more than one skull, or put down more roses than they had. This problem seems like a simplified version of mental poker to me, so I am hoping someone with more knowledge on the subject would know how to play this game without a trusted third party.

In case the link provided goes dead here is a synopsis of the rules:
Each player gets a hand of 4 cards: 3 rose cards and 1 skull card. At the start of each hand each player places one card from their hand face down. Next players take turn place another card from their hand face down on top of their previously placed cards. When it is your turn instead of placing another card face down you are also allowed to "challenge". To challenge you announce a number of less than or equal to the number of cards placed down. You now enter a new phase of the game where players take turns naming larger and larger numbers until someone either decides to "pass" (not naming a larger number), or someone names a number equal to the number of face down cards. When the "challenge" phase is over the last player to call a number has to flip over that many cards. If the player flips over a skull he has to discard a rose card for the rest of the game, however if he does not flip over a skull card, he gets a point. Everyone now collects the cards they played face down, and a new round begins. First player to two points wins.

Assuming that it's sufficient to catch a cheating player after the round is over, this seems trivial to implement using only bit commitments.

Let $\mathsf{Com}$ be a bit commitment scheme.

At the beginning of each round:

Each player  $P_i$ chooses a random index $j\gets \{1,2,3,4\}$, computes
$$
c_i^k := \begin{cases}\mathsf{Com}(0)&\text{if } k\neq j\\ \mathsf{Com}(1)&\text{if } k= j\end{cases}
$$
for $k\in \{1,2,3,4\}$, and publishes $(c_i^1,c_i^2,c_i^3,c_i^4)$. These commitments represent their randomly shuffled cards.

**Placing cards:*
Whenever a player wants to play a card, they simply broadcast an index $k$. This signifies that they placed the card represented by $c_i^k$.

Flipping cards:
When the player who won the challenge wants to flip a card, the player who played it simply opens the corresponding commitment.

Once the game has concluded, everyone opens all of their commitments and it can be checked that they indeed committed to exactly one $1$ and three $0$s.

If you want to catch cheating players immediately, you can add a non-interactive zero knowledge proof to the first message, pricing that the commitments are to exactly one $1$ bit and three $0$s.

The hiding property of the commitment scheme should prevent anyone from knowing any (but their own) placed cards, while binding prevents players from opening cards they did not play.


DGK Cryptosystem Key Generation and Decryption Issues I detailed here the DGK (Ivan Damgård, Martin Geisler and Mikkel Krøigaard) cryptosystem, and I managed to get it to work, most of the time...

The BIG problem that I am facing at the moment is that the key generation algorithm sometimes produces bad keys. The paper states that:

we generate $h$ of order $v_p v_q$ modulo p and q
we generate $g$ of order $u v_pv_q$ modulo p and q

That sounds simple enough, right? But what does it mean? The naive approach (and I'm going to provide it only for $h$, since it works similarly for $g$) is this:

If $h \in \mathbb{Z}_n^*$ must have order $v_p v_q$, then the following conditions must be met:

$h^{v_p} \neq 1$
$h^{v_q} \neq 1$
$h^{v_p v_q} = 1$
Must ensure that $h \in \mathbb{Z}_n^* \Rightarrow gcd(h, n) = 1$
Also, we make sure that $h > 1$

Now, I have tested this approach and it seems to take quite a lot of time to produce a "good" value (perhaps I had an error in the code or I have no idea why it takes forever), so another approach would be to use the Chinese Remainder Theorem to obtain $h$ (and $g$):

Compute $h \in \mathbb{Z}_n^*$ of order $v_p v_q$ modulo p and q $\Rightarrow h = h_r^{p_r q_r u} \pmod n$, where $h_r$ is a random number in $\mathbb{Z}_n^*$ and $p_r$, $q_r$ are the random components of p and q. In order to obtain p and q, we choose 2 random primes, $v_p$ and $v_q$ and we compute $p = p_r u v_p + 1$ and $q = q_r u v_q + 1$, such that p and q are prime.
$n = p q$ and $\mathbb{Z}_n^* \simeq \mathbb{Z}_p^* \times \mathbb{Z}_q^*$
h represented in $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$ is $(h_p, h_q)$
$h_r$ represented in $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$ is $(h_{rp}, h_{rq})$
$h^{v_p v_q} \overset{\mathbb{Z}_p^* \times \mathbb{Z}_q^*}{\longleftrightarrow} (h_p^{v_p v_q}, h_q^{v_p v_q}) = ((h_{rp}^{p_r q_r u})^{v_p v_q}, (h_{rq}^{p_r q_r u})^{v_p v_q})$

$h_p^{p - 1} = 1 \pmod p$ and $h_q^{q - 1} = 1 \pmod q$
$p - 1 = p_r u v_p$ and $ q - 1 = q_r u v_q$

$(h_p^{v_p v_q}, h_q^{v_p v_q}) = (1^{q_r v_q}, 1^{p_r v_p}) \overset{\mathbb{Z}_n^*}{\longleftrightarrow} 1 \pmod n$

From the above math, it seems obvious that if I choose $h = h_r^{p_r q_r u} \pmod n$, where $h_r$ is a random number and I ensure that $h \in \mathbb{Z}_n^* \Rightarrow \gcd(h, n) = 1$ and $h > 1$, then I should get a "good" $h$ of order $v_p v_q$, but not of order $v_p$ or $v_q$ in $\mathbb{Z}_n^*$.

Unfortunately, for some reason, this does not work well. I often get $\gcd(p_r q_r u, n) \neq 1$, which means that no matter what is the value of $h_r$, $h_r^{p_r q_r u} \pmod n = 1$. Because of this, I added another condition while generating p and q: $\gcd(p_r, v_p) = 1$ and $\gcd(q_r, v_q) = 1$. Although it seems to avoid the above issue, I am unable to explain it. Also, now I've hit another issue: It looks like I sometimes end up with g of order $v_p$ in $\mathbb{Z}_p^*$, which messes up the decryption algorithm: $E(m,r)^{v_p} = (g^{v_p})^m\pmod p$

Does anybody have any idea how to fix his? I'm almost sure that I have to impose extra conditions while generating p and q, but I am unable to figure it out and it would really be great to understand what exactly is going on... Is there a cleaner way to generate numbers of a certain order modulo n?

Just in case someone else is trying to implement this cryptosystem, I wish to share the implementation that I am currently using. Someone helped me pick another approach for generating $ h $ and $ g $, and, intuitively, it seems secure.

In order to generate $ h $ and $ g $, I now apply certain algorithms described in the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone

Specifically, I use Algorithm 4.83, Chapter 4: Selecting an element of maximum order in $ \mathbb{Z}_n^* $, where $ n = p q $:

INPUT: two distinct odd primes, $ p $, $ q $, and the factorizations of $ p - 1 $ and $ q - 1 $.

OUTPUT: an element $ \alpha $ of maximum order $ lcm(p - 1; q - 1) $ in $ \mathbb{Z}_n^* $, where $ n = p q $.

Use Algorithm 4.80 with $ G = \mathbb{Z}_p^* $ and $ n = p - 1 $ to find a generator $ a $ of $ \mathbb{Z}_p^* $.
Use Algorithm 4.80 with $ G = \mathbb{Z}_q^* $ and $ n = q - 1 $ to find a generator $ b $ of $ \mathbb{Z}_q^* $.
Use Gauss's algorithm (Algorithm 2.121) to find an integer $ \alpha $, $ 1 \leq \alpha \leq n - 1 $, satisfying $ \alpha \equiv a \pmod p $ and $ \alpha \equiv b \pmod q $.
Return $ \alpha $.

For completeness, here are the two algorithms referenced above in Algorithm 4.83:

Algorithm 4.80, Chapter 4 : Finding a generator of a cyclic group:

INPUT: a cyclic group $ G $ of order $ n $, and the prime factorization $ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} $

OUTPUT: a generator $ \alpha $ of $ G $

Choose a random element $ \alpha $ in $ G $
For $ i $ from $ 1 $ to $ k $ do the following:

Compute $ b \gets a^{n/p_i} $ (N.B. $ \pmod n $)
If $ b = 1 $ then go to step 1.

Return $ \alpha $.

Algorithm 2.121, Chapter 2 (Gauss's algorithm):
The solution $ x $ to the simultaneous congruences in the Chinese Remainder Theorem (Fact 2.120) may be computed as $ \sum_{i = 1}^{k}{a_i N_i M_i \pmod n} $, where $ N_i = n / n_i $ and $ M_i = N_i^{-1} \pmod {n_i} $. These computations can be performed in $ O((\lg n)^2) $ bit operations.

Fact 2.120, Chapter 2: (Chinese remainder theorem, CRT) If the integers $ n_1 $, $ n_2 $, ..., $ n_k $ are pairwise relatively prime, then the system of simultaneous congruences

$ x \equiv a_1 \pmod {n_1} $

$ x \equiv a_2 \pmod {n_2} $

$ \vdots $

$ x \equiv a_k \pmod {n_k} $

has a unique solution modulo $ n = n_1 n_2 \cdots n_k $.

In order to apply Algorithm 4.83, we require the factorizations of $ p - 1 $ and $ q - 1 $. The standard approach would be to just factor the random ~200 bit factors $ p_r $ and $ q_r $. On the other hand, assuming that we don't break the security assumptions, we can use $ p_r = 2 p_r' $ and $ q_r = 2 q_r' $, where $ p_r' $ and $ q_r' $ are random primes of the required size. After ensuring that $ p = 2 p_r' v_p u + 1 $ and $ q = 2 q_r' v_q u + 1 $ are also primes, we may compute $ h $ and $ g $ with the above algorithms:

First, we compute $ h_r $ and $ g_r $ of order $ LCM(p - 1, q - 1) = (p - 1)(q - 1) / GCD(p - 1, q - 1) = 2 u p_r' v_p q_r' v_q $ in $ \mathbb{Z}_n^* $ with Algorithm 4.83
$ h $ must have order $ v_p v_q $ in $ \mathbb{Z}_n^* $, so we set $ h = h_r^{2 u p_r' q_r'} \pmod n $
$ g $ must have order $ u v_p v_q $ in $ \mathbb{Z}_n^* $, so we set $ g = g_r^{2 p_r' q_r'} \pmod n $

And that about wraps it up. Please feel free to add comments if more explanations are needed.

PS: The factor $ 2 $ is required for $ p - 1 = 2 p_r' v_p u $ and for $ q - 1 = 2 q_r' v_q u $ because the product of three odd primes is odd, and, thus, by adding one, we get an even number larger than 2, which can't be prime, but both $ p $ and $ q $ need to be prime numbers.


Why are some group representations much easier to compute discrete logarithm for? The multiplicative group mod $p$ is isometric to the additive group mod $p-1$, yet computing discrete logarithms in the additive group is easy and completing discrete logarithms in the multiplicative group is usually hard.

What is it about group representation that makes group representation matter so much for the complexity of computing discrete logarithms?

Well, the group being isomorphic doesn't imply that the isomorphism is efficiently computable. If $G \simeq H$ via $\phi : G \rightarrow H$ and $\phi$ is computable, then indeed, DLOG is no harder in $G$ than in $H$ because you can transform the instance.

In the case you mentioned, we have $G = \mathbb Z/(p-1) \mathbb Z$ and $H = (\mathbb Z/p\mathbb Z)^\times$. A efficient morphism $\phi: G \rightarrow H$ is known, it called `fast exponentiation'. So DLOG is no harder in $G$ than it is in $H$. But computing a reversed morphism $\psi: H \rightarrow G$ seems harder...


How is the initial permutation of DES created? I am creating a program in C language with DES (Data Encryption Standard) functionality, but don't know how to apply the initial permutation.

Is it achieved by swapping the values? If "yes", then how is the index of the original message created?

The Inital Permutation is defined in the DES specification. This spec numbers bits from 1 to 64 in big-endian reading order. The table gives the bit numbers in the 64-bit block input, to be selected to build the L and R registers:
58  50  42  34  26  18  10   2      L, bits  1 to  8
60  52  44  36  28  20  12   4      L, bits  9 to 16
62  54  46  38  30  22  14   6      L, bits 17 to 24
64  56  48  40  32  24  16   8      L, bits 25 to 32
57  49  41  33  25  17   9   1      R, bits  1 to  8
59  51  43  35  27  19  11   3      R, bits  9 to 16
61  53  45  37  29  21  13   5      R, bits 17 to 24
63  55  47  39  31  23  15   7      R, bits 25 to 32

This table is extremely regular: each value is 8 more than the value on its right, if any. More: the transformation is a near transposition, and becomes one if we make a left/right mirror, and bring the lines with octets of R before the corresponding lines for L.
That regularity comes from the initial implementation of DES in hardware: the plaintext was loaded sequentially as 8 octets, with at each of 8 loads each of the 8 bits of an octet entering an 8-bit shift register, 4 of which for L, 4 of which for R, with these 8 shift registers clocked simultaneously. A natural software implementations can mimic that (among other possibilities).
For the highest performance in software, see Richard Outerbridge's implementation. That uses a general technique to implement transpose using wordwide operations, tunes it to the slightly irregular transpose that IP is, and (in some variants) performs a 32-bit rotate by 1 bit of L and R than can speed-up the rest of DES.
Other than easing hardware implementation, the initial and final permutation have no know design purpose. They do not increase (or decrease) security of DES. They slow software implementation a little, but there is no indication that's explicitly among the design goals (which broadly are to make DES fast, and secure from all attacks except brute force, see this).


With EC secp256k1 is there a way of transforming a function of the private key to a function of the public key? A key pair has a private key $D_A$ and a public key $Q_A$.

$D_A$ is an integer less than the curve's $n$.

Is there any (boolean) function of the private key $f(D_A)$ which can be transformed into a function of the public key $f'(Q_A)$?

i.e. are there any relationships between private keys which can be calculated knowing only the public keys?

We aren't aware of any sich relations. In fact, one assumes that the group of elliptic curve points behave like a Generic Group.
A generic group is a group, where the encoding of the elements are chosen as a random values.


GPG vs PGP vs OpenSSH and management of them What is the main difference of the three?
Can I use only one of them for everything (e.g. GPG for SSH authentication)

If I encrypt my private key with a pass-phrase, is it strong enough so that if someone steals my laptop or private key, I'm safe?

If not, what about encrypting my private key with the scrypt algorithm?

What is the main difference of the three? Can I use only one of them for everything (e.g. GPG for SSH authentication)

GnuPG is an free and open-source implementation of the OpenPGP standard.
Symantec PGP is a proprietary implementation of the OpenPGP standard.
The OpenPGP standard defines ways to sign and encrypt information (like mail, other documents and code/software).
OpenSSH is about connection securely to remote computers. For authenticating you need some secret, usually this is a passphrase or SSH key.

With OpenPGP, you hold a secret (private key) which also can be used for authenticating yourself. It needs software support for that, and I haven't heard of some code doing this for (Symantec) PGP, but there is a way doing this with GnuPG.

  If I encrypt my private key with a pass-phrase, is it strong enough so that if someone steals my laptop or private key, I'm safe?

Your password encrypts your private key. The key is safe as long as your password is safe. If your password is too weak (dictionary-attacks, not long enough, easy to brute-force for other reasons), your key is vulnerable, too.

Think about how valuable your key is for an attacker and choose fitting security measures like storing your key offline (in the and of this answer).

  If not, what about encrypting my private key with the scrypt algorithm?

If doing so, security depends on the password you're using for scrypt and scrypt's algorithm. You can achieve the same amount of security with a good OpenPGP password, so there is no need for additionally encrypting your key.


How do herding attacks on hash functions work? I read this paper Herding Hash Functions and the Nostradamus Attack, 2005 of Kelsey and Kohno on herding attacks but I do not understand how it works.
Would anyone be able to give me a summary of how herding attack as well as the diamond tree structure works?
It is mentioned "In the diagram, the attacker starts with eight different first message
blocks, each leading to a different hash value; he then searches for collisions between pairs of these
hash values, yielding four resulting intermediate hash values". What does it mean by searching for collisions between pairs of these hash values? Hashing 8 different message blocks will produce 8 different hash values so how would there be a collision?

Herding attack is introduced by Kelsey and Kohno in 2005. The attack is applicable to hash commitments. Nostradamus's example from the article is key of the idea. First Nostradamus produces the MD5 (MD is enough) hash of the future prediction of S&P500 before the business year finishes. After Nostradamus publish his message with precise closing prices of the S&P500's companies with some garbage text after it. The message has the same hash the committed hash.
At first, to achieve this, Nostradamus need pre-image attack on MD5, which has still $2^{123.4}$ complexity achieved after this work in 2009 (Finding Preimages in Full MD5 Faster Than Exhaustive Search). Instead of pre-image attack, this work introduces a new required property; Chosen Target Forced Prefix Pre-image resistance.

In the first step, Nostradamus has a Chosen Target by committing n-bit Hash value, $H$.
In the challenge step, the challenger provides $P$ to Nostradamus as Forced-Prefix so that the hash $H = Hash(P\mathbin\|S) $ where $S$ is the suffix (garbage).

The Herding
The herding attack uses a diamond structure to find the hash. The below figure uses 8 different starting messages, one can consider this all possible outcome of the prediction of the Nostradamus prediction.
Remember that, this attack utilizes the Merkle-Damgard structure of the hash function. MOD constructions divide the hash into the block ( for example 512-bit blocks for MD5) after the appropriate padding. Each block then used in the compression function in order.

In the above figure, the first 512-bit part of each message is hashed. Then the crucial part begins. This is actually internal collision on MD construction. Randomly generating 512-bit block to see that $C(h[0,0], m_i) = C(h[0,0], m_j)$ where the $C$ is the internal compression function. With the generic collision, this has $8 \cdot2^{n/2}$ complexity. And as mentioned in the article A diamond structure is essentially a Merkle tree built by brute force.
The committer actually can do better than this instead of a fixed structure for collision finding, one can go dynamically. In the generalized form mapping $2^k$ hash nodes in the diamond structure to $2^{k-1}$ they generate $2^{n/2+1/2-k/2}$ candidate block parts and looks for the collisions altogether. This has  $2^{n/2+k/2+2}$
This attack can also be applied to longer messages - elongated Diamond structure.
The complexity of the attack on MD5 with 41 diamond width and 48 suffix length requires $2^{87}$ complexity. On impractically long suffixes the attack on MD5 with 5 diamond width and $2^{55}$ suffix length requires $2^{69}$ complexity.

Andreeva at al. go beyond this work on Herding, Second Preimage and Trojan Message
Attacks beyond Merkle-Damgard, 2009.


How does ccrypt work? On many Linux/GNU distributions CCrypt (ccrypt) by Peter Selinger is available as a command line utility to encrypt files. How does the protocol work and is it secure?

Note: this should not be confused with the  CCCrypt API by Apple.

Initialization

Key hash function hashstring

Configuration: E is Rijndael with a block size and key size of 256 bits
Input: keystring
Output: hash

The keystring is padded up with bytes valued zero and split up in blocks of 256 bits $S_0$ to $S_n$;
The key blocks $K_0$ to $K_n$ are generated, where $K_0$ consist of $S_0$. The following blocks - if any, most passwords are shorter than 32 bytes - are defined as follows: $K_i = r(K_{i-1})\oplus S_i$ where $r$ is the full subkey derivation of Rijndael-256/256;
A hash block of 256 bits is initialized to zero:
A hash block of 256 bits is initialized to all zero's, lets call this $H_{zero}$, then $H_0 = E(K_0, H_{zero})$, $H_i = E(K_i, E(K_{i-1}))$ for $i > 0$. In other words, the hash block is repeatedly encrypted with itself using the generated key stream $k_i$;
The output is $H_n$.

An answer by Peter Selinger - the creator and current maintainer - showed that the subkey derivation in step 2 is included on purpose. The source code from which this description has been derived does not show any comment or indication that this is the case. To replicate the functionality in another language it may be required to alter an existing Rijndael implementation as the result of the subkey derivation may not be returned to the caller.

Key derivation from the password

Key derivation simply consists of applying hashstring to the password. The password simply consists of a null terminated string of C char. Lets call this key $R$.

Nonce derivation

The nonce derivation consists of the performing the hashstring method over an ASCII string consisting of the following:

gethostname(host, 256);   /* ignore failures */
host[255] = 0;
gettimeofday(&tv, NULL);  /* ignore failures */
sprintf(acc, "%s,%ld,%ld,%ld,%d", host, (long)tv.tv_sec, (long)tv.tv_usec,
   (long)getpid(), count++);

in other words the input of haststring consists of a comma separated ASCII string of the hostname (255 characters max), the seconds in time-of-day, the microseconds in the time-of-day, the process ID and a static / process-wide counter.

Lets call the result $N$.

Creation of IV

The first 4 bytes/characters of the nonce are replaced by the following magic: c051, lets call this $N'$. Then the resulting value is encrypted using key $R$: ${IV} = E(R, N')$

Encryption

Encryption consists of a simple CFB mode using key $R$ and initialization vector $IV$, where the IV is prefixed to the ciphertext.

Decryption

The IV is first decrypted using key $R$ to validate if the if the magic is included in the nonce. The magic therefore acts as a key check value. After that the ciphertext is simply decrypted in CFB mode.


Need help with padding I'm programming a file encryption software based on blowfish (which uses 64bit blocks). I will need a mechanism for padding, but I'm not sure how to implement that properly. All of the approaches I've seen so far could only be applied to text, where characters like 0x00 cannot contain data and thus can be used for special purposes. Since I'm planning on encrypting all file types I cannot rely on special characters which could be easily confused with real data.

Consider ANSI X.923 padding for example, how would the decryptor know that the
sequence 00 00 00 04 is not some special data but padding?

I came up with two of my own solutions, but since I'm not a cryptoanalyst I don't know how strong they are...

1) The very first byte of the encrypted file will be the padding number (the number of actual data bytes in the last block). Yes, I'm giving it away and anyone with a hex editor will be able to see it. The last block is padded with random bytes. I feel like this is a big weakness since I'm not encrypting my padding number. Is this really a weakness and why?

2) The very first block of the encrypted file will contain the padding number and a bunch of random bytes. The decryptor will know exactly where to find the padding number (first byte of the first block). Once again, the last block is padded with random bytes. Is this a good approach?

3) Any other methods I can use?

Thanks in advance.

Consider ANSI X.923 padding for example, how would the decryptor know that the sequence 00 00 00 04 is not some special data but padding?

Because padding is always used. Thus if the file before padding was 41 42 43 44 00 00 00 04, it would be padded 41 42 43 44 00 00 00 04 00 00 00 00 00 00 00 08 then encrypted.

This rule, or similar ones differing on how the padding octets other than the last are generated, are common and fine when padding octet strings.

For the most general problem of padding arbitrary bit strings, one of the simplest and most general is bit padding, which appends a single 1 bit, then zero to b-1 0 bit(s) as necessary to reach a multiple of the blocksize $b$ (in bits). That can be designated as ISO/IEC 9797-1 padding method 1, but this standard does not prescribe un-padding. This should fail is there's not at least one block; removes final 0 bit(s) in the last block, and fail if that exhausts the last block; finally, remove the final 1 in that last block.

When restricted to octets in big-endian convention, bit padding becomes appending a 80 octet, then zero to b/8-1 00 octets as necessary to reach a multiple of the blocksize.

Use a simple padding rule, and always apply it; complexity and exceptions are the enemy of practical security. Whatever the method, beware of padding oracle attacks on decryption, and off-by-one coding errors in implementations.


synchronization of counters in HOTP How is synchronization of counter values achieved in the HOTP protocol?

As I understand it, the server increments its counter value only if a match (of  the OTP value) is found. What happens at client side?

Suppose server verifies 50 successful attempts from client which implies counter value at server is 50. What if a fresh request comes from a different client with counter value 0?
The server could only check for counter values 50,51,52 if window size is 3,or 50-100 if window size is 50. In both the cases there will be no match as client side counter value is 0.

There is no "fresh client" with HOTP. The whole counter business is based on the idea that there is a single client, who maintains his counter which is more-or-less synchronized with the server counter. The synchronization window is just a way to cope with small unsynchronization events which come from realistic situations (e.g. your 3-year-old played with your car keys and pushed the "unlock button" a few dozen times).

If you want several clients, each client has his own counter, and the server must maintain one counter per client.


Cryptographic security of PHP mt_rand() function using Mersenne Twister algo At stackoverflow this question has been asked. It uses additional random entropy and a hash method (among others) to try and create a cryptographically secure pseudo-random number generator for PHP. PHP seems to use a Mersenne Twister algorithm with a large internal state and high period, but Wikipedia assures me that Mersenne Twister is not cryptographically secure.

Q: Could somebody please indicate what vulnerabilities there are using the PHP Mersenne Twister implementation as if it was cryptographically secure?

Additional Q: It would be very nice if somebody could go over to stackoverflow to see if the solution of H M is any better than using the default method and if it can be improved. Of course, the only really good way is to hold it against BSI and NIST test suites, but any improvement on the default implementation may be useful.

The source code in the stackoverflow question should be pretty easy to read, even for persons that are more mathematically inclined. Just as reference, I've included the source of the current methods within Zend PHP (which indeed seems to lack any kind of cryptographical algorithms).

Code is a partial copy of the Zend source for cryptographic analysis only. The ZEND source is protected by the PHP 3.01 license.

PS the initialization of the algorithm is just 32 or 64 bit, which is why I proposed at least to reseed it thouroughly on stackoverflow, but I wonder if that would be enough, as I've unfortunately proposed on stackoverflow (mostly because creating self defined cryptographic algorithms by users is frowned upon).

basic_functions.h

#define MT_N (624)

php_uint32   state[MT_N+1];  /* state vector + 1 extra to not violate ANSI C */
php_uint32   *next;       /* next random value is computed from here */
int      left;        /* can *next++ this many times before reloading */
zend_bool mt_rand_is_seeded; /* Whether mt_rand() has been seeded */

rand.c

#define N             MT_N                 /* length of state vector */
#define M             (397)                /* a period parameter */
#define hiBit(u)      ((u) & 0x80000000U)  /* mask all but highest   bit of u */
#define loBit(u)      ((u) & 0x00000001U)  /* mask all but lowest    bit of u */
#define loBits(u)     ((u) & 0x7FFFFFFFU)  /* mask     the highest   bit of u */
#define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */

#define twist(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))

/* {{{ php_mt_reload
 */
static inline void php_mt_reload(TSRMLS_D)
{
    /* Generate N new values in state
       Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */

    register php_uint32 *state = BG(state);
    register php_uint32 *p = state;
    register int i;

    for (i = N - M; i--; ++p)
        *p = twist(p[M], p[0], p[1]);
    for (i = M; --i; ++p)
        *p = twist(p[M-N], p[0], p[1]);
    *p = twist(p[M-N], p[0], state[0]);
    BG(left) = N;
    BG(next) = state;
}
/* }}} */

/* {{{ php_mt_srand
 */
PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)
{
    /* Seed the generator with a simple uint32 */
    php_mt_initialize(seed, BG(state));
    php_mt_reload(TSRMLS_C);

    /* Seed only once */
    BG(mt_rand_is_seeded) = 1;
}
/* }}} */

/* {{{ php_mt_rand
 */
PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
{
    /* Pull a 32-bit integer from the generator state
       Every other access function simply transforms the numbers extracted here */

    register php_uint32 s1;

    if (BG(left) == 0) {
        php_mt_reload(TSRMLS_C);
    }
    --BG(left);

    s1 = *BG(next)++;
    s1 ^= (s1 >> 11);
    s1 ^= (s1 <<  7) & 0x9d2c5680U;
    s1 ^= (s1 << 15) & 0xefc60000U;
    return ( s1 ^ (s1 >> 18) );
}
/* }}} */

Well, the chief vulnerability is that if an attacker is given a large enough sample of Mersenne Twister output, he can then predict future (and past) outputs.  This is a gross violation of the properties that a cryptographically secure random number generator is supposed to have (where you're supposed to not even be able to tell if the random bit string could have been produced by the RNG in question).

As for how this weakness may be exploited, well, consider if you use the output of the MT as a keystream for a stream cipher (that is, you exclusive-or it with the plaintext to form the ciphertext).  Then, if the user sees an encrypted message, and correctly guesses a part of the plaintext which is 2496 characters long, he can then immediately recover the internal MT state (and decrypt the entire message).  Even worse, if the user has a section of ciphertext 19968 characters long for which he knows that the corresponding plaintext had all MSBits clear (say, he knows that section was standard ASCII), then he can then use that to decrypt the entire message (even though he initially had no idea beyond that what the contents of that section were).

The first weakness (2496 bytes of consecutive outputs allows the attacker to recover the MT state) is fairly straightforward to explain; we examine the last four operations of the MT immediately before the output:

s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );

If we look closely, we see that these operations are all invertible; that is, if we were given a 4 byte output of the MT, we can compute the value s1 had before these operations took place.

Now, what MT does is update its state, and then output its entire state (disguised by the above transformation).  Now, an attacker can invert this transformation, and so directly observe the MT state.  All he needs is 624 words of output (or 2496 bytes), and he has learned the entire state; he can advance the MT forwards (or backwards; the update function is invertible), and generate as much output as he wants.

Now, one possible nit is for this straight-forward approach to work, these 2496 bytes must correspond to one MT reload cycle; that is, start at a multiple of 2496 bytes from the start of the stream).  While this would be easy to work around (if we're given 4991 consecutive bytes of output, then there will be a 2496 byte section that lives entirely within a reload cycle), it turns out that we needn't bother, because it's broken even worse than that.

The second weakness is that, if we can get just about any sample of 19968 bits of output, we can also recover the MT state, and it doesn't matter of all those bits are from the same MT reload cycle, or spread across multiple.  As for how this works, well, when we examine the MT update and disguise functions, we see that they're all linear in GF(2); this means that all outputs are linear functions of the 19968 initial state bits.  Hence, if we get 19968 output bits, we can form 19968 linear equations on the initial state bits, and solve that set of linear equations.  That gives us the initial state, and from that, we can compute everything.  Now, some sets of 19968 linear equations might not turn out to be linearly independent; in practice, all that means is that we might need a couple extra known bits, or just deal us having a couple of different possibilities for initial state; neither of these are significant difficulties for an attacker.

Hence, the bottom line is that Wikipedia is right, Mersenne Twister is not even slightly cryptographically secure, and should not used as if it were.


Feistel-Network - why wire crossing? In Feistel-Network, there would be a wire-crossing at the end (for the next round). Which insufficiency would occur, if the wire crossing would be omitted?

Let's look at a picture of a generic feistel cipher

Notice that no keying material is used during or after that final swap. So, we can conclude that the final swap does not impact security at all.

So, why include it? It is so that all rounds will be identical. This could help with some implementations. That is all.


Securely testing the presence of an item in a list without exposing the list Not even sure what terms would describe what I'm looking for, but the general idea:

  Given a list of strings of a finite length, determine whether or not a test string belongs to the list. Then, produce a new list of strings containing the difference of the original list and the test string.

In pseudocode, this would probably look something like:

def list = envelope(["string1", "string2", "string3"])

def validate( collection, test ) {
    if ( contains( collection, test ) ) {
        return remove( collection, test )
    } else {
        throw Exception
    }
}

// In Use
validate( list, "string2")
-> envelope( ["string1", "string3"] )

validate( list, "string4")
-> Exception

One person told me this sounded like the way a blockchain works, but given everything I've read and my rudimentary understanding of blockchain, I'm skeptical. Is there another process or protocol available that I can use to make the above function?

You could use convergent encryption for this.

For each item to be inserted, compute its hash, then encrypt it by deriving a key from that hash. Insert the ciphertext (discarding the hash/key).
To test for the presence of an item, hash it, encrypt, look for matching ciphertext.

You would likely want to use something like a hash table or a search tree (dictionary or set), instead of a flat list, to avoid $O(n)$ scan when looking for an item.

Note that the user can brute force / dictionary attack the scheme by encrypting chosen items and checking them against the list.


Why is SHA-1 considered broken? Is there a known pair of distinct bit strings (A,B) such that SHA-1(A) == SHA-1(B)?

If the answer is no, then how can SHA-1 be considered broken?

We call a primitive broken, if there is any attack faster than bruteforce/what we expect of an ideal primitive. Broken does not mean that there are practical attacks.

Even when there were no known collisions in SHA-1, we still called collision resistance of SHA-1 broken, because there is a theoretical attack that can find collisions using fewer than $2^{80}$ calls to SHA-1.

In particular an $n$ bit hash function should have at least the following properties:

$2^n$ pre-image resistance (both first and second pre-image)
The generic attack is simply trying inputs until one fits the hash
$2^{n/2}$ collision resistance
The generic attack is generating inputs, and comparing their hashes against each other. The birthday problem tells you once you have about $2^{n/2}$ different values, two of them will likely be the same. In case of SHA-1 this that finding a collision takes about $2^{80}$ operations.

A function getting broken often only means that we should start migrating to other, stronger functions, and not that there is practical danger yet. Attacks only get stronger, so it's a good idea to consider alternatives once the first cracks begin to appear.


What is a good AES mode to use on file encryption? I'm new to encryption and cryptography, I was wondering if there is a good or best suited AES mode for file encryption (Planning on zipping a folder and encrypt it as a file). If there is, how complex is it and is it easy to implement on python (preferred language)? Thank you.

Since you zip the directory before encryption, we can assume that the compressed directory now is random file. You can use CBC mode or CTR mode. However, these modes are not providing any authentication.

You should use authenticated encryption mode as AES-GCM.

There is another issue waits for you. How do you derive cryptographic keys from the user's password? The common method is using a KDF function as PBKDF2 or Argon2.

You generate a random AES key and encrypt the zip file with it. After the encryption, encrypt the AES key with the key derived from the user's passwords with KDF and store it together with the encrypted file.

For the random bytes generation, at least, you should use urandom.

Python has AES-GCM and PBKDF2. You can find the example codes as here and here


cofactor matrix in Hill cipher I have been reading these slides about Hill cipher.

And there it says that the value of K is the following:

\begin{equation}
K=
\begin{pmatrix}
11&8\\3&7
\end{pmatrix}
\end{equation}

Now I need to calculate $K^{-1}$, so for that reason I calculate the adjoint matrix by using the cofactors. For what I know it should be:

\begin{pmatrix}
7&-3\\-8&11
\end{pmatrix}

but in the slides it appears that is:

\begin{pmatrix}
7&-8\\-3&11
\end{pmatrix}

which is different from the one I calculate, what am I doing wrong?

I think the adjugate matrix is the transpose of the cofactor matrix.

(Btw, I do not think this is a crypto question.)


Different kind of PGP keys or IDs, how to interpret them? When people say "Here's my PGP key", they tend to come up with all sorts of different stuff.

Sometimes they provide an 8-digit hexadecimal number, which seems to be a key ID (although I'm not sure).

I've also seen cases where people provide a 16-digit hex number, or even a 40-digit number (printed as 10 fields of 4 hex digits).

I've also seen cases where people send a file, containing the usual stuff:

-----public key-----
....
(whole lot of base64 encoded data)
....

I can deal with the latter, but I have no idea how to obtain the key from the other formats. How do I go about this?

Exchanging full RSA keys can be very inconvenient, as they consist of very long numbers. In the OpenPGP ASCII-armored version, my public key (without any user IDs and certifications!) already is very long stream:

mQQNBFDaK/sBIADm2gjnw7aPoNIoCy7gj85btwZU+zGkvtGonznlLrXELdU6zR3u
VHNCn9vAl6OoU32r+suFvGdX+7MjiPbGKwJFOvICpAVh6bV55+hdqJbS02cpPmJH
1BrrUAmm6ZVEybGd+II1pTI6Mt/SAI1E/59VIBdC/1AwsxQtCTFeyaLqTdyd1FhQ
chkjcvdRHLb4cEqldAGqBL7SbiSNOP3p+vX8iwRN6PQ/erAGseawHnunuNIna+tA
t4te/MkI2uxT0KjsfF/NWHCB2aXt++egP8jGSaHRsVOlfHRVA3hHcUDlnW9DZRvG
QabHFcZvfcXAlNIRYKUzDIHEwpavAmHeGNhc2GNmDcDRF56741grVLNQT58vxK5o
dBLlC8ANckvE5ymdIKVPm+t5q10kFOAATcnmDV0oBt+15vzI3f+88yCoY904UWdY
LwTbNMiszIB4ngNfzdLWeXPOCDs4CYa9BBKb1VkVtWn6NTE7m0/urrAP3Mb9qTwz
AlBVHvDPo6BG2yVqoCVzDBNOjb7czO3cns2M8sThizD2gvdKUV5Bq7THp6MFAzP0
Wbad3JLVIn65BNzVKJYhC7rGAU2QjlRbXq+P08NsewNbFC/E3fct249PM5xVl4lW
vcsqBo1o+iuHuzb7tvveht1N79n3V+pPISLj8QCb9rEI09MJ93IQbn5yuyPCgXe6
/OiNyiv3QxY/x3zImLiiuSurbw1E0ILyX/qm+36XVSpewduXk2yen8x+eMmLWRfS
ZhyPXHFbO8am7niF1AuZjnIfhETsiyqAGmYmb9d7nL6GwCrvA7QCHrRl/EDd4r2a
Un2q6QYXQ78Wj6Ys1/jH49GkFUhBKl0PfLKtKPiPwL71wb6sD6nA30Ix6hMGreZk
B1697KPVLCP4v87xyrMJFNgXC2FBKML3PlokOyrZzbXLRM78yHmoBl13Tu3UZkFK
O1TV7cFzQScHMd+yBGN/AmVUF8Br2bExtuIvQqoQbj6gPIEk5xGWvGzSbR9LcAng
VRUHDlOy3dUd8QuhJANPk6knHZR0OT0C5c2Wzvcznr5ros5PQ8XZFCOJTaNLfc7u
9TGe/FVG3d7RMyB/9ILhS5ef3VarGzuyiYwwsC3P+w/3lHt+PhzVQRfeq0WrB+RK
3bfweIm30k1g8xJuQ0mg2JmmICYL/uihWVREZNOZZPboFBV8dZec+hif1tfuqchV
qVsy3cMuhg/K/EJafVbA3o59Z9IYIC3XN7NGoYYXuzbLgaDtVxGdcWTg8D4a1FaD
cEkeAR/Mm9FxVDK01itXatol/ZB0oBCrYS0DLdYQ/YWrAfoqR7Av7uY+hQiwvIo3
+lVlQGsr7rlhv/oNrf2P2M5aKPOdp2vPIEqpABEBAAE=
=pzM1

For this reason, the public key gets hashed into the key's fingerprint. From RFC 4880, 12.2 Key IDs and Fingerprints:

  A V4 fingerprint is the 160-bit SHA-1 hash of the octet 0x99,
     followed by the two-octet packet length, followed by the entire
     Public-Key packet starting with the version field.  The Key ID is the
     low-order 64 bits of the fingerprint.

Long and short key IDs are the last 16 respectively 8 digits. Again with my own public key as an example:

fingerprint: 0D69 E11F 12BD BA07 7B37  26AB 4E1F 799A A4FF 2279
long id:                                    4E1F 799A A4FF 2279
short id:                                             A4FF 2279

As the fingerprint and key IDs are derived from the public key through hashing, you cannot "convert them back" to the public key. So while they cannot be used immediately for cryptographic operations and must query a key server using them as search token, you can exchange them more easily, for example on business cards. Be aware that short key IDs are insecure and should not be used.


Question about the location of the r-torsion in the quotient group used in the Tate pairing I'm working through Pairings for Beginners by Craig Costello, and am trying to understand the Tate pairing.

He defines $rE = \{r*P | P \in E(\mathbb{F}_{q^k})\}$ and then forms the quotient group $E(\mathbb{F}_{q^k})/rE$. He then claims:

  if $r^2 || \#E(\mathbb{F}_{q^k})$, then $E[r] \cap rE = \{\mathcal{O}\}$.

where $\cdot||\cdot$ means divides, but just once, and $E[r]$ is the r-torsion.

My question

Why is this true? I definitely agree that $\mathcal{O}$ is in this intersection, since $r[P] = \mathcal{O}$ for any $P$ in $E[r]$, but I don't see why this should be the only element in the intersection. Moreover, if there were some point $Q \neq \mathcal{O}$ in $E[r] \cap rE$, then $Q$ would have order $r^2$, which by Lagrange's Theorem, would be possible under the assumption that $r^2 || \#E(\mathbb{F}_{q^k})$.

The group $E[r]$ is isomorphic to $\mathbb{Z}/r \mathbb{Z} \times \mathbb{Z}/r \mathbb{Z}$, which has $r^2$ elements, all of order $r$. Since your element $Q$ has order $r^2$, $E(\mathbb{F_{q^k}})$ has also a cyclic subgroup of order $r^2$.
This group has $r (r-1)$ elements of order $r^2$ which cannot be elements from $E[r]$. This implies that $\#E(\mathbb{F_{q^k}})$ must be at least divisible by $r^3$.