Multiple key generator I need an algorithm for "key generator". It should be initialized with some secret data, such as a (hashed) passphrase, or something generated once by some 3rd-party code.

Given some small input it should be able to generate N bits in a deterministic way, which'd be used as a material for some key. The input consists of a needed key index, and, perhaps, some other flags and parameters.

Naturally the generated keys should not reveal other keys or the generator secret.

What is the preferred way to do this? Is it ok to just hash all the input?
I mean:

K = H(input | secret)

whereas H - is a common hash function (such as SHA-256)?

To be concrete, I need a sort of a DRBG, whereas:

I don't really care about preimage attacks and etc. It's not intended for message authentication. I believe there's no need in HMAC.
The generator must be immutable, i.e. should not mutate after each generation (like auto-hashing).
It should work in O(1) wrt the key index. In simple words, generating k'th key should be no harder than generating the first one.

I need an algorithm for "key generator". It should be initialized with some secret data, such as a (hashed) passphrase, or something generated once by some 3rd-party code.

This is called a Key Derivation Function or KDF. As your question indicates a pre-established secret with enough randomness / entropy a Key Based Key Derivation Function is what is required. KDF's that are used over passwords (that generally require strengthening) are called Password Based Key Derivation Functions or PBKDF's or password hashes.

Given some small input it should be able to generate N bits in a deterministic way, which'd be used as a material for some key. The input consists of a needed key index, and, perhaps, some other flags and parameters.

The small input is called the input key material (IKM or $K_I$), the N is generally called $L$ for the length of the output key material (OKM or $K_O$).
This input is generally called Info, OtherInfo or, for NIST, FixedInfo or Context depending on the standard used. There are a lot of impromptu KDF's so the terminology can change from one protocol / standard to another.

Naturally the generated keys should not reveal other keys or the generator secret.

That's the general idea of KDF's. They are commonly build from one way functions such as hashes or MAC's.

What is the preferred way to do this? Is it ok to just hash all the input?

It is important to be careful with regards to the input. One thing to make sure of, even if a standardized function is used, is that the input data cannot overlap, i.e. there should be a canonical representation of the Info data and the key.
For instance, if variable $x$ can consist of "A" or "AB" and variable $y$ can consist of "BC" or just "C" then two different combinations of $x$ and $y$ will be able to produce "ABC" if you just concatenate the two variables.
Furthermore, if an attacker can influence the input then you may also need to avoid length extension attacks or even attacks on the hash function. Otherwise, yes, it is fine to just hash the Info - or input as you call it.

To be concrete, I need a sort of a DRBG, whereas:

I don't really care about preimage attacks and etc. It's not intended for message authentication. I believe there's no need in HMAC.
The generator must be immutable, i.e. should not mutate after each generation (like auto-hashing).
It should work in O(1) wrt the key index. In simple words, generating k'th key should be no harder than generating the first one.

You don't want a DRBG. DRBG's are defined to generate pseudo random bits using seed information. However, many implementations will be seeded by the system, and may be reseeded at specific times. They also may not return the same random data if you ask it for, say two times 16 bytes or one time 32 bytes. They generally do not have a good means to supply a other info. If you are unlucky you may generate keys that cannot be recalculated and you lose all data; see for instance here.
KBKDF's do fulfill all of these requirements - except that quite a few are based on HMAC as it is immune to some of the attacks such as those that rely on collisions and length extension techniques.
Available KDF's
Currently one of the most advances KBKDF's is called HKDF. It is based on HMAC with a configurable hash function underneath. It consists of two functions: HKDF-extract and HKDF-expand, where the first one extracts (or compresses) the entropy in the input data to a fixed length pseudo-random key. HKDF-expand then uses this fixed length key to derive one or more keys of any length, using the info (counter etc.) provided. It is also NIST approved.
A more simple hash based KDF is called KDF1 (or MGF1 in the simple form with just the counter), KDF2 or KDF3 (which differ only minimally). It is defined in ISO-18033-2,  IEEE Std 1363-2000 with similar functions in ANSI X9.62, which are unfortunately all payware. It uses a hash function, a counter and possibly other Input to derive keys in a pre-defined way (although creating the "Info" needs to be canonical, as already explained).  I asked a question about it here and described the most simple form.
An alternative for KDF1 called KDM has been defined in NIST SP 800-56C Rev 1 which can be used both with a hash or MAC; it includes options for SHA3 and KMAC. Basically it is a re-ordered KDF1 which could be well suited for your purpose and has a publicly available document describing it. NIST SP 800-56A has some interesting information on what to put in FixedInfo (a renamed OtherInfo).
Otherwise any of the key derivation functions of NIST SP 800-108 which is comprehensively called "Recommendation for Key Derivation Using Pseudorandom Functions". It uses MAC's and includes some alternatives that are based on block ciphers instead of hashes.


shake-128 in 32-bits platform I am implementing shake in 32-bits microcontroller, so I would like to use bit interleaving.
I checked the code in: https://github.com/floodyberry/supercop/blob/master/crypto_hash/keccak/simple32bi/Keccak-simple32BI.c but I do not understand how is the bit interleaving transformation done in this code. Could anyone give an insight for understanding this.

Also, I compare the results of the function KeccakF for previous link and the 64-bit implementation (https://github.com/floodyberry/supercop/blob/master/crypto_hash/keccak/simple/Keccak-simple.c) and the result is not the same. they are supposed to be same or aren't they?

Thank you

The bit interleaving code looks like this:

{
    const UINT32 * pI = (const UINT32 *)in;
    UINT32 * pS = state;
    UINT32 t, x0, x1;
    int i;
    for (i = laneCount-1; i >= 0; --i)
    {
        x0 = *(pI++);
        t = (x0 ^ (x0 >>  1)) & 0x22222222UL;  x0 = x0 ^ t ^ (t <<  1);
        t = (x0 ^ (x0 >>  2)) & 0x0C0C0C0CUL;  x0 = x0 ^ t ^ (t <<  2);
        t = (x0 ^ (x0 >>  4)) & 0x00F000F0UL;  x0 = x0 ^ t ^ (t <<  4);
        t = (x0 ^ (x0 >>  8)) & 0x0000FF00UL;  x0 = x0 ^ t ^ (t <<  8);
        x1 = *(pI++);
        t = (x1 ^ (x1 >>  1)) & 0x22222222UL;  x1 = x1 ^ t ^ (t <<  1);
        t = (x1 ^ (x1 >>  2)) & 0x0C0C0C0CUL;  x1 = x1 ^ t ^ (t <<  2);
        t = (x1 ^ (x1 >>  4)) & 0x00F000F0UL;  x1 = x1 ^ t ^ (t <<  4);
        t = (x1 ^ (x1 >>  8)) & 0x0000FF00UL;  x1 = x1 ^ t ^ (t <<  8);
        *(pS++) ^= (x0 & 0x0000FFFF) | (x1 << 16);
        *(pS++) ^= (x0 >> 16) | (x1 & 0xFFFF0000);
    }
}

There is also the matching deinterleave code in the extract function.

I also wrote a Keccak/SHA3 class using that code (or something similar) as a base. For whatever reason I did not like the way that looked, and ended up writing my own, which ended up being 1.45X faster (just the interleave, not the hash) when compiled compared to my implementation of this interleave code, so there are faster ways to do it.

I also found it is easier to interleave/deinterleave the entire state during dev/testing when you absorb or extract as you can view intermediate values of the state working variables and compare to a reference implementation.


Does a key need to be signed if it is being used to decrypt a message that is already signed? I am trying to better understand authentication. Lets say I have posted my 128-bit AES symmetric key on some forum, encrypted asymmetrically to my friend using 256-bit ECC (25519). The forum isn't controlled by us so this key message could potentially be tampered with.

I then post a bunch of actual communication messages onto the forum that are encrypted with that AES key, and I sign them using a ECC 25519 signing key that my friend can safely use to verify the messages have not been tampered with.

Did I also need to sign my AES key message, or is it an adequate authentication check that the key decrypts my signed message correctly? If the key was tampered with it would fail to decrypt my message to something meaningful?

I am trying to better understand authentication. Lets say I have posted my 128-bit AES symmetric key on some forum, encrypted asymmetrically to my friend using 256-bit ECC (25519). The forum isn't controlled by us so this key message could potentially be tampered with.

Well first of all, note that encrypting with curve25519 isn't as trivial as encrypting with say RSA, you'll probably have to use ECIES or something along those lines. You usually see (and use) ECC used for digital signatures and key exchange, just so you're aware.

  I then post a bunch of actual communication messages onto the forum that are encrypted with that AES key, and I sign them using a ECC 25519 signing key that my friend can safely use to verify the messages have not been tampered with.

  Did I also need to sign my AES key message, or is it an adequate authentication check that the key decrypts my signed message correctly? If the key was tampered with it would fail to decrypt my message to something meaningful?

Let's consider what can happen if you don't sign your AES key. Worst case a malicious forum admin modifies your message and replaces your AES key with their own key (encrypted with your friend's public key). If they succeed and send messages to your friend encrypted with their own key one of three things can happen:

Your friend decrypts the message, sees e.g. some valid English text and says OK this message looks good, key must be fine.
Your friend does not decrypt the message because there is no signature on the message.
If the attacker did sign the message with their own key (since they can't forge your signature) your friend tries to verify the signature with your public key, which will fail (at which point your friend should discard the ciphertext).

In 2 out of 3 cases the attack will fail, but there is the chance that the attack will succeed if your friend is willing to decrypt ciphertexts without checking their integrity (known also as The Cryptographic Doom Principle). So it depends on what your friend does.

I recommend the a slightly different construction in this case. Assume you have private / public keypair $(sk_A, pk_A)$ and your friends is $(sk_B, pk_B)$, the notation $function_{key}$ means perform $function$ using the key $key$ and $||$ represents concatenation:

Generate two keys, one for AES ($k1$) and one for a MAC e.g. HMAC ($k2$)
Sign your generated keys ($sig = \text{Sign}_{sk_A}(k1 \text{ || } k2)$) and send the signature and keys encrypted to your friend: $\text{Encrypt}_{pk_B}(k1 \text{ || } k2 \text{ || } sig)$.

Your friend should decrypt, verify the signature, and then grab the keys.

To send a message $m$ to your friend encrypt it to yield $c = \text{AES}_{k1}(m)$ and then send the message $(c \text{ || } \text{HMAC}_{k2}(c))$. This is the "Encrypt-Then-Mac" construction, whose security you can read about more here.

Your friend should upon receipt of a message verify the MAC and if it is OK then decrypt the ciphertext.

Note that the authenticity of your messages is established from the MAC, which in turn is established by the fact that you used your private key to sign the key ($k2$) used when computing the MAC.


Plaintext for randomness evaluation of cryptographic algorithms? I’m running an experiment to test the randomness output of many cryptographic algorithms based on INST test suite to measure the randomness of their outcome.

However I’m searching to a sample data set to perform the experiment. Based on my understanding the data set should be non-random to be able to measure the randomness after applying the cryptographic algorithm.

What plaintext should I use for this?

If I understand you properly, you are going to test some cryptographical primitives by running them on some plaintext, and then taking the resulting ciphertext and giving it to a randomness test suite; your question is "what plaintext should I use?  If I pick a random plaintext, then the test results might reflect the randomness of the plaintext, and no anything the cipher is doing"

In which case, you want to select a maximally nonrandom plaintext.  For example, if you're testing CBC-mode encryption, a plaintext that consists of a long string of 0's would work; if you're testing a hash function (and so need a long series of plaintexts), using plaintexts of the form "0", "1", "2", "3", etc (for some simple encoding of those integers, say, in binary form) would work.

That said, unless the cryptographical algorithms you're testing are severely broken, you're not going to find anything.  An explicit design goal as that an attacker who can submit plaintexts of his choosing is unable to distinguish the output from randomness; it is quite unlikely that something as mindless as the NIST test suite would manage where a clever cryptanalyst cannot.


Using AWS KMS with AES GCM I am implementing client-side encryption for data stored in AWS DynamoDB, and was wondering about the correct use of AWS KMS for key management in addition to using AES/GCM.

I am using the master key stored in AWS KMS to generate a data key used for encryption. I am also using AWS KMS to generate a random number for initializing the IV.

My code looks roughly like so:

GenerateDataKeyResult dataKeyResult =
            kmsClient.generateDataKey(
                    new GenerateDataKeyRequest()
                            .withKeyId("masterKeyId")
                            .withKeySpec(DataKeySpec.AES_128)
                            .addEncryptionContextEntry("encContext", "aValue"));

ByteBuffer plaintextKey = dataKeyResult.getPlaintext();
ByteBuffer encryptedKey = dataKeyResult.getCiphertextBlob();

GenerateRandomRequest randomRequest = new GenerateRandomRequest().withNumberOfBytes(12);
GenerateRandomResult randomResult = kmsClient.generateRandom(randomRequest);
byte[] nonce = randomResult.getPlaintext().array();

GCMParameterSpec spec = new GCMParameterSpec(16 * 8, nonce);
SecretKeySpec secretKeySpec = new SecretKeySpec(plaintextKey.array(), "AES");

Cipher cipher = Cipher.getInstance("AES/GCM/NoPadding", "BC");
cipher.init(Cipher.ENCRYPT_MODE, secretKeySpec, spec);

byte[] aad = "Whatever I like".getBytes();
cipher.updateAAD(aad);

String data = "Hello, World!";

byte[] cipherText = cipher.doFinal(data.getBytes());

In theory that seems to work, but I am not fully confident in that I am using it correctly. In particular:

I will store the encryptedKey with the encrypted data, but can I use the same key for all rows or do I need to generate a new one for each one?
How does the AAD factor into this? Do I need to store it? Does it need to be unique per row?
Do I need to generate a new nonce for each row of data? Can I store it together with the data?

So far my assumptions are:

I can reuse the same key for all rows
I need to generate a new nonce for each row
I will store the nonce with each row, and additionally store the encryptedKey
The AAD is the same for all rows and I can generate it in a deterministic way so I do not need to store it

Am I in the ballpark regarding my assumptions?

(I also do apologize if the belongs in StackOverflow, I was a bit unsure of where to post this)

Yes, you are in the ballpark with your assumptions.

  I will store the encryptedKey with the encrypted data, but can I use the same key for all rows or do I need to generate a new one for each one?

No you can use the same key.

  How does the AAD factor into this? Do I need to store it? Does it need to be unique per row?

If you don't need AAD then you don't need to supply it. AAD means "additional authenticated data", i.e. any data you also want to be authenticated together with the ciphertext, which you want to keep in plaintext.

  Do I need to generate a new nonce for each row of data? Can I store it together with the data?

Yes to both.

Notes on the implementation:

GCMParameterSpec spec = new GCMParameterSpec(16 * 8, nonce);

You should not use "magic literals". Instead use something like Cipher.getBlockSize() * Byte.SIZE. You would of course need to define the cipher earlier. Same goes for the number 12, use a constant e.g. GCM_DEFAULT_NONCE_SIZE_BYTES.

byte[] aad = "Whatever I like".getBytes();
byte[] cipherText = cipher.doFinal(data.getBytes());

You need to specify an explicit encoding here. StandardCharsets.UTF_8 is popular, and not without reason.

Cipher cipher = Cipher.getInstance("AES/GCM/NoPadding", "BC");

Oracles provider also contains GCM, and that may perform much better than the Bouncy Castle one (which will always be programmed in Java). In general, don't specify a provider unless you really need to (and then you may want to make it configurable).


Modes of operation that simply uses the tweak of a tweakable block cipher What is the name of the mode in which we simply change the tweak for each block without the need for complex chaining modes? Is this mode secure?

Are there any other recommended modes for native tweakable block cipher like Threefish?

Many people want a "seekable cipher", which implies that they can't use chaining modes.(a) (b)
So far I've seen 3 ways to build such a cipher:

XTS: "XEX-based tweaked-codebook mode with ciphertext stealing (XTS)" is used in most modern "full-disk encryption" systems. (c)
CTR: "Counter mode (CTR)" (d)
OCB "Offset Codebook Mode (OCB)" (e)


Is it possible to increase the encryption security of a short key? If I encrypt a file with a short 4 digit pin is there any way to make it more secure. I've thought about hashing the 4 digit pin and using the result as the encryption key. I think this would work as long as the attacker didn't know that I was using this strategy but if they did they could just try the 10^4 hashing of the possible pins.

The hash idea isn't great. See Kerckhoffs's principle. The underlying secret is still the four digit PIN, which is only $4 \times -\log_2(10) = 13$ bits of security. And don't we all pick '1234' anyway?
You can use a key derivation function like Argon2 (there are others). That slows down hackers attempts at guessing your PIN. You could aim for something like one second on typical hardware. Still it could be brute forced after a mean time of an hour and a quarter on that same kit though.
Security could be further enhanced with an $n$ tries and you're locked out policy if there is a server involved with conditional logic. This would be implemented by also using the derived encryption key to encrypt a series of four check digits, say all zero. If they do not decrypt to all zero, it's the wrong PIN, so try again until lock out. This is how your ATM card behaves.
And a further further method would be to have an increasing/exponential delay between attempts. This would depend on your customers' acceptance though.

A longer pin is an option if the business allows it. Windows login PINs are six digits.


Is 2 a safe generator for elgamal encryption From what I understand here https://en.wikipedia.org/wiki/ElGamal_encryption and here: https://ritter.vg/security_adventures_elgamal.html, any number can be used as a generator. Is there something wrong with using 2 as the generator? Are there other constraints?

As far as we know, any generator of a given subgroup of $\mathbb Z_p$ is about as safe as any other one for ElGamal encryption; and $2$ is no exception. Argument (this is not a proof): ElGamal encryption is closely related to (and not harder than) the Discrete Logarithm Problem in that subgroup, and consistently solving the DLP with generator $2$ in the subgroup of $\mathbb Z_p$ that it generates is not much harder than solving the DLP with any other generator $g$ of the same subgroup. Close-to-a-proof of the later: If we could consistently solve the DLP with generator $2$ in that subgroup, and knew that subgroup's order $r$, we likely could solve $2^y\equiv g\pmod p$ for $y$, and then for $a$ in the subgroup we could consistently solve $g^x\equiv a\pmod p$ for $x$, by first solving $2^z\equiv a\pmod p$ for $z$ using the hypothetical method, then solving $z=x\,y\bmod r$ for $x$ which is easy.

However if would be wrong to conclude that $2$ can safely be used as the generator for any large enough $p$. Common wisdom is to use a subgroup which order $r$ is a large prime $q$ of at least $2b$ bits for security against effort $O(2^b)$ (and otherwise sound choices). It is not enough that the order of the subgroup is large: if $r$ was smooth, the Pohlig-Hellman algorithm would apply, and allow plaintext recovery for any ciphertext.
Note: I defer making a statement as to what exactly are the necessary conditions on $r$ and messages to reach IND-CPA security until I'm sure of what I write!

Update: a stronger argument in favor of the first assertion in this answer is given by poncho: being able to recover plaintext encrypted by ElGamal with generator $2$ (always, or extremely consistently) implies ability to do so with any generator $g$ of that same subgroup (heuristically always, or with possibly sizable odds), even if the DLP itself was insurmountable.


"proof of access" schemes What is the state of the art way when implementing a scheme challenging a party to prove they have access to certain data?

What I'm looking for something along the lines of

Give them (id-some-data, random-data, my public-key).
Request to return the signature of (some-data xor random-data) with my-public-key.
Give them (id-some-data, random-data).
Request to return hash(random-data + some-data)

So basically I'd like to verify if the other party has access to the requested data and prevent them from precalculating the proof of it.

What is the correct name for such schemes in the crypto world?

What would be the theoretical difference between the two schemes above? (other than probably higher "security" of the PubPriv key scheme compared to the hash functions available).

P.S.: I do know better than to implement own crypto ;) The above are just examples to explain what I'm looking for.

I'd go with hash(ProverPublicKey || RandomChallenge || Data) over your idea of hash(RandomChallenge || Data). Your scheme has the problem that the prover might challenge another party to prove that they have the data and forward that prove to the original challenger.

Related keywords are proof-of-retrievability, proof-of-ownership or proof-of-data-possession.


Fundamental difference between the constant, key, nonce, and counter bits in Salsa20/ChaCha20 or AES-Encrypt? The Salsa20 core function takes a 128-bit constant, 256-bit key, 64-bit counter, and 64-bit nonce and produces a 512-bit value.  Or more generically, it is a mapping from 512-bit values to 512-bit values.

Is there a reason specific input bits were chosen for specific purposes?  For example, if the some of the counter bit positions and key bit positions were swapped, would this result in a weaker cipher?  What if we used the constant bits as additional key bits?

What about AES-Encrypt?  If we view AES-128-Encrypt as a mapping from 256-bit values to 128-bit values, can we use whichever of the input bits we want for the key and IV input block without weakening it?

Edit: Clarifying my AES question: I wrote IV but I meant input block.  (Depending on the mode of operation, the input block might be an IV, plaintext block, counter, etc.)

And now that I think about it, it's clear that the key bits are different from the input block bits.  Given the output of AES-Encrypt and the input block, it's difficult to determine the key.  However, given the output of AES-Encrypt and the key, it's trivial to determine the input block: just apply AES-Decrypt.

Is there a reason specific input bits were chosen for specific purposes? For example, if the some of the counter bit positions and key bit positions were swapped, would this result in a weaker cipher?

No, there would be no real effect on security. The specific positions were chosen primarily to improve SIMD implementation performance. The Salsa20 and ChaCha core functions, ignoring the constant, can be thought of as a $f : \{0,1\}^{384} \rightarrow \{0,1\}^{512}$, so the exact locations for the various bits don't really matter as long as it is secure, which it is thought to be. In fact, the IETF variant of ChaCha uses a different nonce and counter size from the original version by Bernstein (96:32 vs 64:64, respectively).

Note that the positions do have some security implications. Section 3.2 of the ChaCha paper explains how the attacker-controlled words were more spread out in Salsa20 and gave an attacker extra flexibility, but made analysis of the cipher easier. ChaCha, on the other hand, keeps all attacker-controlled words (the nonce and counter, regardless of their size as long as they both sum to 128 bits) on the bottom row of the input matrix. However, the effect on security is extremely small for a standard number of rounds.

  What if we used the constant bits as additional key bits?

Now that would not be a good idea. The constant is important, although the specific value is somewhat arbitrary. Without the constant, an all null key, nonce, and counter would result in an all null keystream block. In theory, a completely random, uniformly-distributed key could be extended to use the counter bits and it would have a negligible chance of resulting in security issues, but that would violate the security properties of the cipher (after all, you'd have to create restrictions as to what a valid key is!).

  What about AES-Encrypt? If we view AES-128-Encrypt as a mapping from 256-bit values to 128-bit values, can we use whichever of the input bits we want for the key and IV without weakening it?

AES is completely different from Salsa20. It is a block cipher, so the IV (which, for most block modes, is nothing more to the cipher itself than an input message) and the key are fundamentally different.


Attacking unuauthenticated RSA In symmetric cryptography, a scheme is not considered secure if the data transmitted is only encrypted. The adversary will be able to modify messages to generate encrypted messages of his choice without having the key.

Is this applicable to asymmetric crypto such as RSA?

The attack is even more simple with RSA than with symmetric keys, because the asymmetric encryption key is assumed to be public.

Let me tell you a story involving Alice, Bob and Mallory :). Alice wants to send a message to Bob using RSA.

Alice encrypts the message using Bob's public key and sends it
Mallory performs a Man-In-The-Middle attack, and encrypts another message using Bob's public key (as it's public)
Bob received the new message thinking it comes from Alice, as there's no origin authentication.


How do applications set up secure communications through an untrusted middleman? I recently discovered Tox whilst looking for alternatives to Skype, and while the Tech FAQ goes into some details about algorithms used, etc. I don't understand how keys are securely exchanged.

I understand that at least the following takes place:

Asymmetric keys are used to exchange a symmetric key.
Symmetric keys are used for exchange of chat messages.

From reading this question, it seems that it's not possible to establish such a communication with no prior shared information. With that being the case, it seems that the user id (which is quite long) is the only piece of information shared between clients before establishing communication through the interim untrusted server. I assume this is used in some way to prove the identity.

My question, therefore, is how are symmetric keys exchanged in such a way that the interim server can't perform a MITM attack (by presenting itself to Client A as Client B, and by presenting itself to Client B as Client A)?

If my question has been asked before, please feel free to flag it as a duplicate.

There is no way to establish a shared key with a man in the middle attack and no trusted third party.

With a trusted third party, they can validate public keys so that the man in the middle can't send his.


Schnorr protocol - Proof or argument? Is Schnorr's protocol for proving knowledge for a discrete logarithm, truly an interactive proof or is it an interactive argument? If we let P to be unbounded, after she generates the commitment $t$ and receives the challenge $c$ she can try all $r$ such that $h^r=t \cdot z^c$(where $h$ is the generator of the cyclic group and $z=h^x$)

In addition, how can we make any security guarantees if the prover is unbounded?

I know how to extract the witness from two transcripts. My intuition as to why this extraction argument is sufficient for proving soundness is something like this(correct me if I am wrong):
If the prover can somehow cheat and produce two accepting transcripts, then she can extract $x$. This implies(by taking the contrapositive of that statement) that if she does not know $x$, then she cannot produce a transcript. Therefore, the protocol is sound.

However, in some sense we had to ignore the infinite computational power P has, while proving that statement. If she has infinite computational power, then she will always know the discrete log(because she can compute it). I guess my question is what is the purpose then for not bounding P?

Schnorr's protocol is an interactive proof of knowledge. The 'attack' that you provide does not contradict this: if the powerful prover that you describes can indeed try all $r$ such that $h^r = t\cdot z^c$, then she can as well try all $x$ and check for $z=h^x$. Put otherwise, this prover does indeed know the discrete logarithm of $z$: in fact, any 'unbounded' prover knows the discrete log of $z$.

The proof that a prover that provides an accepting proof must know the discrete logarithm is done by using rewinding, and showing that a simulator could extract this discrete log from its interaction is quite straightforward (repeat the last two flows twice, write out the equations, cancel the randomness introduced in the first flow, and you get the witness); furthermore, if you write it, you'll observe that it does not rely on any computational assumption - if the verification succeeds with non negligible probability, extraction will succeed as well, with comparable probability. This holds independently of the computational power of the prover.

EDIT: to answer your follow up question, yes, you got the intuition right: if the prover can produce two accepting transcripts, she must know $x$, as $x$ can be extracted from these transcripts. Your issue seems to be that a computationally unbounded prover can always compute $x$, hence he always 'knows' $x$ - so, how is that interesting to consider also unbounded provers in the security analysis?

The answer lies in the formal guarantee given by a proof of knowledge. While the intuition is that it guarantees that the prover 'knows' the witness, the actual guarantee is the following: if the prover produces an accepting transcript, then a simulator can (using rewinding) extract the witness. This is of crucial importance in many cryptographic protocols where the proof of knowledge is part of a larger system: the simulator will often need to extract the witness from the proof, to use it when simulating other parts of the protocol. Now, in an argument, which is only secure against computationally bounded provers, an unbounded prover could well produce an accepting transcript from which the simulator cannot extract a witness - by breaking the computational assumption on which the knowledge soundness relies. Hence, even though this unbounded prover does indeed know a witness (she is unbounded, so she can obtain all witnesses via brute force), she does not necessarily allow the simulator to extract it from successful transcript, hence the analysis of ant larger system in which the simulator would need this witness would break down.

In Schnorr's protocol, however, as the soundness is unconditional, the simulator is guaranteed to always succeed in extracting the witness from the prover, even if she is unbounded.


How much would removing enigmas biggest flaw improve it? Enigma's biggest flaw was that a letter could never be encrypted as itself. How much would enigma's security increase if it were possible that a letter could be encrypted as itself? I know that would void the method used by Turing and co.

Please give as much detail as possible in answers.

EDIT: clarifying improvement

The improvement is, in the simplest terms:

Once the signal has passed through the rotors and into the reflector, the rotors shift forward before allowing the signal back through, meaning that each encryption operation would use two shifts instead of one.

EDIT 2:
Also, with enigmas flaws removed, how comparable to modern algorithms would it's security be? And as another note, I'm not talking about modifying enigma back in WWII, I'm talking about a virtual software based mod now.

with enigmas flaws removed, how comparable to modern algorithms would it's security be?

With the specific change you specified, it would still (by modern standards) be considered "broken".

Here is how you can perform a distinguishing attack, and do a partial key recovery (recover the first two rotor settings with a good probability of recovering the third rotor setting) with about 400 characters of known plaintext.

I'll be assuming a 26 character rotor, however the attack scales to other sizes.

Here's how to recover the first rotor setting (and if you do recover a setting that works, that's a distinguishing attack):

In the encryption operation, the note that:

The plaintext character is sent through the first rotor: $A := R_i({Pt})$
The ciphertext character is sent through the first rotor after stepping it one position: $B = R_{i+1}(Ct)$
The mapped plaintext $A$ is different than the mapped ciphertext $B$

This holds because the internal rotors and the reflector do not step during the operation, and hence will never map a character to itself.

Note that this might not be true if the second rotor is stepped during the encryption operation; however that will occur only once every 13 character encryptions.

So, if we take a guess at an initial rotor setting, we can determine how all the plaintext and ciphertext characters are mapped.  Then, if we find two instances where the plaintext and ciphertext characters are mapped to identical $A, B$ values (and those locations are not multiples of 13 apart), we know that that initial rotor setting is impossible.

After 400 characters, the probability that an incorrect rotor setting will show as possible is approximately $2^{-13}$; as there are significantly fewer than $2^{13}$ possible settings for the first rotor, then with high likelihood, only the correct setting will remain as possible (and if no settings remain, then this isn't modified Enigma).

Now, that we've recovered the first rotor setting (and position), we can peel off the first rotor operation (by applying the now-know first rotor operation to the known plaintext/ciphertext), and use a similar attack to recover the second rotor (which is actually easier; we have a lot more information per rotor step).  And, if the third rotor steps during the 400 character encryption but not the fourth (probability >50%), then we can recover the third rotor (using the same trick)

Bottom line: this would be considered (by modern standards) totally broken


How to decrypt file on one machine which is encrypted on other machine? I have a doubt related to CryptExportKey and CryptImportKey.
I will try my best to define my problem by explaining the scenario that I want to implement.

I have two machines. On First machine, I create a Key-pair using CryptGenKey with ALGID=ALG_SID_RSA_PKCS then I exported the key using CryptExportKey with PUBLICKEYBLOB flag. I then send the blob to the second machine over the network. On first machine I then encrypt the file using CryptEncrypt with the same key (created previously with CryptGenKey). After encrypting the file, I send this file to the second machine.

So on second machine, I have key blob and the encrypted file. Now, I want to decrypt the file on second machine, using key blob.

On Second Machine, I am trying to import the key blob using CryptImportKey, it returns successfully but when calling CryptDecrypt, it gives an error 08009000d (NTE_NO_KEY, key doesn't exist).

Is it possible to decrypt the file on second machine.

Thanks in advance.

You are using an asymmetric encryption algorithm. By design of this, only the party that has the private key can decipher, and in your case that's the first machine only, because you exported the public key; this explains why you fail to decipher on the second machine.

There are at least two good options to fix this:

Encipher on the second machine, and decipher on the first machine; but you must somewhat manage that the public key is not altered during transfer to the second machine (which is not implied by "send the blob to the second machine over the network").
Generate the key (pair) on the second machine, export the public key and send it to the first machine, with similar requirements that it is not altered in transfer.

If your use case is to encipher (that is, protect the confidentiality of a message) on the machine that generated the key, then it is pointless that this key is for an asymmetric cryptosystem like RSA (a symmetric cryptosystem like AES will do), and you must somewhat manage to move the deciphering key to the deciphering machine in a way that protects that key's confidentiality (which is not implied by "send the blob to the second machine over the network", and typically is harder to achieve that ensuring that the key is not altered).

If your use case is to sign (that is, demonstrate origin and integrity of a message, in such a way that the check requires no confidential material), then generating the key pair on the machine that signs the message and exporting the public key is correct, but you still must somewhat manage that the public key is not altered during transfer to the second machine.


How do fast multiplication algorithms deal with cryptanalysis? Math algorithms like Karatsuba and derivatives - do they have any applications for cryptanalysis of asymmetric cryptography algorithms?  What if we have very fast multiplier? How can it help with extracting the secret key from encoded text?

Since Karatsbua is often the default multiplication method for any library with big integers, this is surely used in cryptographic algorithms - whenever large integers are involved. Typical examples for this are RSA, DH key exchange, DSA, all elliptic curve cryptography, etc.

The runtime of Karatsuba depends only on the lengths of the numbers and not on the actual number itself, reducing $n^2$ single-digit multiplications (for long multiplication) to $\approx n^{\log_2 3}$ (exact number depends on the input lengths) and some additions (also only depending on the length of the numbers). So if we can assume constant runtimes for the addition and single-digit multiplication, this should not leak any information. It is just faster.

  do they have any applications for cryptanalysis of asymmetric cryptography algorithms?

I am not sure what you actually mean. Sure, they do have applications: Whenever there is a multiplication of big integers, Karatsuba is used already. But Karatsuba does not give you any other surprising advantage, as far as I know.

  What if we have very fast multiplier?

I don't know why the question i stated in such a hypothetical way, because that is actually how multiplication is realized. For integers, long multiplication is actually the rare case - that's how it is taught in school and mostly used for multiplication by hand.

  How can it help with extracting the secret key from encoded text?

It can't. Actually, I am not sure what you mean with this question. For any state-of-theart encryption scheme with proper parameters, it is practically impossible to extract the key from a ciphertext - if we assume lmitations in time and computation power like "If every atom on earth was a computer and we could use a Dyson sphere around our sun to produce energy until the sun burns out". It is a common misconception, that encryption can actually be broken in such a way.

But coming back to fast multiplication algorithms:  In some cases, other methods like Discrete Fourier transform-based multiplication is used, e.g. this can be used to speed up the Miller-Rabin primality test.


Is this pairing scheme for establishing trust between two devices with self-signed TLS certs secure from MITM? Assume two devices (A and B) with self-signed TLS certificates (this part can't change). We want these devices to trust each other.

One way to do this is to simply copy A's cert over to B's allowed cert list and vice versa, but this is a little cumbersome usability-wise.

Instead, what about this scheme:

Device A generates a key K that it remembers for a short period of time
The user copies K and enters it in, along with device A's hostname, on device B
Device B makes a TLS connection to device A and includes its client cert
Device B sends message m1 = HMAC(K, "request" + its client cert + observed server cert)
Device A checks that m1 looks like what it expects, if not, it closes the connection
Device A responds with m2 = HMAC(K, "response" + observed client cert + its server cert) and adds device B's cert to its trusted list
Device B checks that m2 looks correct, and if so, adds device A's cert to its trusted list.

Is this secure, and if so, how short can K be?

This is fine.  There is one corner case I would note which is that the message from 4 can be replayed in 6.  So the authenticated messages should include an indication of whether they are for step 4 or 6.  As for how short K can be: as long as necessary to get the guarantee you want from HMAC.


Generating 1024 bits of entropy from a seed I need to generate 1024 pseudo-random bits from a 100 bytes string seed (only valid lowercase chars)

One thing I'm pretty sure would be secure enough would be to repeat this 100 bytes string 20 times and encrypt it (using itself as the key with AES for instance) and then return the first 1024 bits

Does that seems fine?
Is there a more "standard" way to d that (some simple/secure key expansion algorithm)?

You should use a well-vetted implementation of a well-researched key derivation function that can output at least 1024 bits.

HKDF-SHA-256 is the standard and secure  choice these days, although constructions based on SHA-3 and Blake2 are also in use.

If the characters you’re hashing are created by a human, use a specialized and intentionally slow password-based key derivation function like scrypt or Argon2 instead.


How to rigorously prove that $Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$ is CPA secure assuming $\Pi$ is? Assume $\Pi$ is a CPA secure scheme. Let $\Pi'$ be a derived scheme, such
that the encryption of a message $M$ is as follows:

$Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$, where

$LSB(k)$ is the least significant bit of the randomly chosen key.

Can someone help me to finish my proof that the $\Pi'$ scheme is also CPA secure?

My proof:

Assume the contrary, $\Pi'$ is not CPA secure. Then the adversary can find two messages $M_0$ and $M_1$, such that whenever a challenger returns him $C'_b = Enc_{\Pi'(k)}(M_b)$, he can guess correctly the randomly chosen bit $b$ with the probability higher than $\frac{1}{2} + 2\epsilon_{fixed}$.

Now the adversary wants to win a game for $\Pi$ against me. He sends me those two messages $M_0$ and $M_1$. He asks me to randomly pick a bit b and return $C_b = Enc_{\Pi(k)}(M_b)$. The adversary then guesses the LSB(k):

With probability $\frac{1}{2}$ he will have guessed the LSB(k) correctly. Thus, he knows the value of $C'_b$ and can guess the bit $b$ with probability higher than $\frac{1}{2} + 2\epsilon_{fixed}$
With probability $\frac{1}{2}$ he will have guessed the LSB(k) incorrectly.
In this case, he will guess the bit b with probability 1/2. // Why?

Hence, the adversary can guess the bit b correctly with probability
$p > \frac{1}{2}(\frac{1}{2} + 2\epsilon_{fixed}) + \frac{1}{2}(\frac{1}{2}) = \frac{1}{2} + \epsilon_{fixed}$. This contradicts the assumption that $\Pi$ is CPA secure.

$\square$

The part I struggle to prove is why when the adversary has guessed the wrong $LSB(k)$ bit, he can still guess the correct $b$ with probablity $\frac{1}{2}$. For example, suppose the adversary runs an algorithm $\alpha$ to guess a bit $b$ when being challenged to win a game for $\Pi'$:

If we return him $C$ that equals $Enc_{\Pi'(k)}(M_b)$, then $\alpha$ guesses correct $b$ with probability 0.6
If we return him $C$ that differs from $Enc_{\Pi'(k)}(M_b)$ in the last bit, then $\alpha$ guesses correct $b$ with probability 0.

So now the adversary with the $\alpha$ algorithm would win the CPA game for $\Pi'$, because the game rules force us to send the correct ciphertext $C$. However, $\alpha$ used in the way described in the proof will not win the CPA game for $\Pi$ because
$\frac{1}{2} 0.6 + \frac{1}{2} 0 < \frac{1}{2}$

So what I want to ask is why we can always find a better algorithm than $\alpha$?

We want to prove that

$\Pi$ is CPA secure $\Rightarrow$ $\Pi'$ is CPA secure.

So, let's prove it using the equivalent contrapositive proposition:

$\Pi'$ isn't CPA secure $\Rightarrow$ $\Pi$ isn't CPA secure.

So, it means we have to suppose that there is an adversary $\mathcal{A'}$ that can win the CPA-game of $\Pi'$ with non negligible probability and then construct some adversary $\mathcal{A}$ to break the CPA security of $\Pi$, in other words,  $\mathcal{A}$ must win the CPA game of $\Pi$. (This is the point you seem to be missing, since you are not interacting with $\Pi$ at all).

So, we construct  $\mathcal{A}$ as follows:

$\mathcal{A}$ receives $m_0$ and $m_1$ from  $\mathcal{A'}$.
$\mathcal{A}$ sends both messages to the encryption oracle of $\Pi$.
$\mathcal{A}$ receives a ciphertext $c_b = Enc_{\Pi(k)}(M)$.
$\mathcal{A}$ chose a random bit $b_k$ and send $c_b||b_k$ to  $\mathcal{A'}$.
$\mathcal{A}$ receives a guess $b'$ from $\mathcal{A'}$.
$\mathcal{A}$ outputs $b'$.

Now, what is the chance that  $\mathcal{A}$ wins CPA game against $\Pi$? It is
$Pr[b' = b]$, that is equal to

(i) $Pr[b' = b | b_k = LSB(K)] \cdot Pr[b_k = LSB(K)]$

plus

(ii) $Pr[b' = b | b_k \not =LSB(K)] \cdot Pr[b_k \not = LSB(K)]$

But $Pr[b' = b | b_k = LSB(K)] \ge \frac{1}{2} + \alpha$ for some non-negligible function $\alpha$ (because $\mathcal{A'}$ can breaks $\Pi$). Therefore, (i) is greater than or equal to $(\frac{1}{2} + \alpha)\frac{1}{2}$.

And if $\mathcal{A}$ didn't guess the least significant bit of $K$ correctly, we don't know how $\mathcal{A'}$ would proceed, so, let's say that $Pr[b' = b | b_k \not =LSB(K)]$ is $ \frac{1}{2} + \beta$ some function $\beta$, then, we have that (ii) is equal to $( \frac{1}{2} + \beta ) \frac{1}{2}$.

Therefore,

(i) + (ii) $\ge  \frac{1}{4} + \frac{\alpha}{2} +  \frac{1}{4} + \frac{\beta}{2} = \frac{1}{2} + \frac{\alpha}{2} +  \frac{\beta}{2}$.

If $\beta$ is negligible, then $\alpha \ge \beta$ and then (i) + (ii) $\ge \frac{1}{2} + \frac{\alpha}{2} +  \frac{\alpha}{2} = \frac{1}{2} + \alpha$.

If  $\beta$ is non-negligible, then take $\gamma$ to be the minimun between  $\alpha$ and $\beta$. That way, we get (i) + (ii) $ \ge  \frac{1}{2} + \frac{\gamma}{2} +  \frac{\gamma}{2} = \frac{1}{2} + \gamma$.

In both cases, $\mathcal{A}$ can guess the bit $b$ output by the oracle to $\Pi$ with non-negligible probability, i.e., $\mathcal{A}$ breaks the CPA security of $\Pi$.


Periodic One Way Function Is there any notion of a periodic OWF?
I.e. an OWF $f$ that on every input $x$ in its domain it holds that $f(f(f\ldots f(x))\ldots )=x$ when $f$ applied many times, each time on the   previous output.

Also, if we take some One Way Permutation, it must be periodic of course. So is it guaranteed that its period is longer than any polynomial (in the security parameter)? (that is, if its period is of some polynomial length - is its security broken?)

Security is clearly broken if there is a polynomial-length period with non-negligible probability (where by this I mean if a random point falls in a cycle with a poly-length period with non-negligible probability). In order to find a preimage, just go forward until you get back to the starting point, keeping the previous value each time.


What is the difference between PKCS1 v1.5 and PKCS7? Is PKCS7 a superset of specifications in PKCS1 1.5? I have a requirement wherein we have to verify the PE binaries generated for an aarch64 platform.

These binaries are then signed using the opensource sbsign tool to generate a signed PE binary with PKCS7 signedData structure included in the SECURITY section of the binary. These binaries have to be verified by the bootloader (in our case uboot) before they are loaded.

I stumbled across a patch which made use of the ARM-software/u-boot to verify the signedData section. As can be seen, the functions in this file such as rsa_verify() and rsa_verify_with_keynode() refer to verifying an RSA PKCS1.5 signature.

My question is, is this the same as verifying the PKCS7 signedData structure? It would be great if someone could help me understand.

What is the difference between PKCS#1 v1.5 and PKCS#7?

PKCS#7 makes use of cryptographic primitives defined by PKCS#1 v1.5.

PKCS#7 is defined in RFC 2315. The modern PKCS#1 is v2.2 (also RFC 8017), and has a modern description of the schemes in PKCS#1 v1.5, including RSASSA-PKCS1-v1_5.

  Is verifying a PKCS#1 v1.5 signature the same as verifying the PKCS#7 signedData structure?

Verifying a PKCS#7 signedData structure involves verifying a RSA PKCS#1 v1.5 signature, but also a number of important steps before that, including parsing that data structure, and checks which depend on context. signedData has features which might not be needed by in a bootloader, like certificates with revocation lists.


Economically Rational as a security proof Is it possible to prove the security of a cryptocurrency payment protocol by saying that the actors will seek to maximize their profits. Would I need to set this up as a game and prove it that way or what can I do to get started?

The information I have is the state of the system and then I have just iterated each agents ability to change the system and just show that by following the protocol each agent maximizes their profit.

The tricky part is what if the agents do not follow the protocol? It is often the case that by deviating from the protocol, an agent can gain a higher payoff than following the protocol. if this happens, then the agent may not follow the protocol. One party deviating from the protocol may cause other parties to change their strategy. Will they reach a stable state?

Therefore, to prove security, you would need to specify the following:

All the parties (players);
All actions can be performed by the parties (strategies);
Is there any sequence or order of parties have to act, or they move simultaneously;
What information do the parties have in the process? Do they know everything or only some information?
The utility functions of each party -- taking into account not just money, but others types of payoffs.
All assumptions

Putting those together, you can formally specify a game. Having the game formally specified, you will have all possible outcomes induced by all possible combination of parties' strategies, and payoffs for each party associated with the outcome. You can then analyse the game to see whether there exist an equilibrium (or more than one), which is a "solution" of the game. An equilibrium consists of a set of strategies for each party (and maybe probabilities). An equilibrium basically says if all parties choose the strategies in the equilibrium, they will not want to change their strategies because their utilities won't be better.

In the simplest case, if you have one equilibrium and it entails your security goal, then you can say you have proved security in the presence of rational parties. But the situation can be much more complicated.


Why is appending the key to a mesage and then hashing that insecure if the hash isn't weakly collision resistant? Suppose I have H(M|K) and that H is not weakly collision resistant. If I have a message mac pair (M,MAC), how is it possible to find another message mac pair (M2,MAC2)? My thinking for this problem is that if the hash isn't weakly collision resistant, then I can find another message M2 such that H(M|K)=H(M2|K) and thus, I have a new pair (M2,MAC2). Is this a sufficient explanation for explaining why H(M|K) is insecure if the underlying hash function is weak?

It's a question about how actual hash functions work. So in the scheme where MAC=H(m||k) in practical terms that's equivalent to doing M=H(m) and then, with the resulting state of the hash function do H(k) starting with the state resulting of doing H(M), so you can see that's possible to find a collision, a m' such that H(m')=H(m), then H(m'|k)=H(m|k) with a cost n/2 bits. HMAC construction reduces substantially (according to wikipedia) the chances of finding such a collision, in fact a collision H(m')=H(m) is useless, so the weakness in this sense of the used hash function has no use.

Note: If $M_i$ are hash function's input blocks and $S_i$ are successive states most hash functions do just $S_i=F(S_{i-1},M_i)$, and the hash result is the last state, making length extension and collision attacks possible.

PD: Let me apologize if the answer is not clear enough. The answer is yes, HMAC can improve a collision weakly hash where H(m|k) does not.


Path ORAM asymptotics for arbitrary block sizes The Path-ORAM construction assumes that the data outsourced into the ORAM scheme is split into blocks of size $\Omega(\log^2{n})$. With respect to this assumption the authors state that their storage overhead is $20N$ and their bandwidth overhead is $\mathcal{O}(\log{N})$.

How would those those performance metrics be influenced if I do not make this assumption about the block size, e.g. I assume that the blocks are of constant size (and in particular independent of N). What would be the asymptotic/practical server-side storage overhead and what would be the bandwidth overhead in this case?

The smallest block size that is reasonable to consider is at least $\log N$, since the headers of blocks in server storage need to contain their virtual address and position (according to the position map).
The idea behind path ORAM (and most tree-based ORAMs) is to maintain the position map using a recursive ORAM. The "data units" in the position map are of size $\log N$ (a position in $[N]$), therefore the recursion will not work for a block size $O(\log N)$ since in such case you will not reduce the number of blocks in the recursion.
We now understand that for the scheme to actually work, we need a block size $k\log N$ for non constant $k$. For such a block size, the overhead will be $\log N + (\log^2 N)/k$ (I know this doesn't align with the original paper, but a better parameterization of the recursion with the same construction gives this overhead. See "Circuit ORAM" paper for more details).


Suppose $H(X) \rightarrow Y$ is collision resistant. Is $H$ also one-way? If we have $H(X) \rightarrow Y$
and it is collision resistant.
Can we say that $H$ is also one-way? And if that is true can you give me an example?

No. Consider $H:X \to Y$ where $X = Y$ and the function $H(x) = x$. The function is collision resistant, but not one-way.


Why is there a counter in CSPRNGs? This is probably one of those embarrassingly simple questions, but here goes.  Consider the following two constructs:

CSPRNG made out of a block cipher (AES) with a counter such as

CSPRNG made out of a secure hash function with a counter (Java SecureRandom's SHA1PRNG) such as

The common denominator is the provision of a counter.  What's the point of the counter as you could simply do state' = F(state) once you have state established?  So the state would be the seed alone, and it would be iteratively processed to produce the random stream. What does the counter bring to the party?

A counter has a practical advantage: it makes a random stream seekable instead of purely sequential. Which doesn't matter for a CSPRNG but does for a DRBG and parallelization.

But it also works around two possible issues with recursive calls to a hash function: the cycle length, and fixed points.

Hitting a fixed point would be particularly nasty; what should have been a random number generator would start generating the same value forever.

In practice, the risk is negligible unless your function is not a secure hash function, or has a really small block size. The cycle length is not an issue either, if only because storing all the observed values before biases become exploitable is not practical.

Still, using a counter is reassuring. Hitting a fixed point would have zero security implications. Neither would a point with a very short cycle length.


Understanding Hellman's TMTO I am trying to understand the basic TMTO by Diffie Hellman as described here. I am having trouble understanding this passage here:

  Hellman had the idea of storing the dictionary in the form of long
  chains. A randomly chosen key, with which a specific message is
  encrypted, stands at the beginning of such a chain. The result of the
  first pass is used as a key for encrypting the original message during
  the next pass. The result of this pass provides the key for the next
  one, and so on, until the chain has reached a predefined length. In
  order to save space, Hellman stored only the first and last values in
  the chain. The dictionary thus compressed is a two-column table sorted
  by end value.

What does the author mean by first and by last value? If I use a key a (from a set A of keys) on a certain cipher, it should give me a result b (from a set B of possible results). Now what exactly are the middle values in this process?

Also, do I get it right: in order to save memory the sets A and B are conjuncted? So when a 64-bit key a1 produces a 64-bit b1, in the next step we have b1=a2 (so in the image above, it should be 77CF=22CB)? But how does that work in ciphers where key and output length are not the same length? Also why does the author speak of a table, if the data structure here would obviously is a list? it would especially be no lookup-table, as the keys/values would be in a random order, so you could not look up a certain key/value by its bit-order (00001
00010
00011
...) and would have to go through the entire database to find the entry you are looking for.

This is a complex topic. Hence my suggestion:

There is a reasonable tutorial here. Forget the example table above and whatever you are reading and read the tutorial first. The example above is full of vague words and undefined terms. There is a lot going on in the TMTO and things have to be fully defined.

Even Hellman's paper while  very technical is more enlightening than what you have given above, but the tutorial is more gentle.

In the case keylength is not equal to blocklength, a projection map is used from 64 bits (say) to 56 bits (say) by taking the first 56 bits of the output, since the only goal of the update function along the trails is to give you a pseudorandom walk among possible key values.

Table vs list, these are valid programming and data management distinctions and the author was sloppy. While they have impact on the exact complexity, they have small impact on the overall big-oh complexity of the attack.


complete functionality for fair multiparty computation In this paper I found the statement "We reduce the fairness problem in MPC to the problem of fair decryption [...] Fair decryption was shown to be a complete functionality for fair MPC in [GIM+10]".

How is decryption considered to be complete functionality for fair multiparty computation? What do you mean by complete functionality?

The functionality that this paper refers to when speaking about "fair decryption" is probably the "fair reconstruction" functionality from [GIM+10].

In secure computation we say some cryptographic primitive is complete if we can use it to implement any ideal functionality (in some setting). One can think of complete primitives as the sufficient requirements for secure computation. For example, we know that one can securely compute any desired functionality if one has access to oblivious transfer as a building block.

Roughly speaking, [GIM+10] shows that fair reconstruction is complete as follows:
All parties first execute any unfair secure computation protocol that outputs (non-malleable) secret shares of the output.
The parties then run the fair reconstruction function, which returns the reconstructed secret.


Asymmetric Cryptography decryption I am new to cryptography, i know essential part of asymmetric cryptography but is it possible to decrypt 617 decimal digits (2,048 bits) with RSA ? How it can be factored?

There is no known classical algorithm that can factor a 2048-bit modulus in feasible time.

Shor's algorithm could do it in feasible time but this algorithm needs to be run on a large-scale quantum computer and as of now there are too many obstacles to create a large-scale quantum computer.


Quantum Secure Signing Algorithm with a 256 bit signature & key. Am I missing anything? Can I remove tradeoff? So I was looking at Lamport signatures and trying to figure out if there is a way to reduce the key size and signature. I stumbled across something that is tiny (125 times smaller signatures and 500 times smaller public key) and almost as secure but it has a catch.

So, I realized that Lamport Signatures get their security from requiring the user to pre-commit to 512 different values, you then show half your secret keys to sign. The security comes from the fact that an attacker only has odds of any randomly picked number being the correct signature of roughly 1/2^256

What if instead, you started with a random 512 bit number A, hashed A getting 512 bit B, then hashed it again to get 512 bit C. Now you use C as your public key. And when you want to sign a message, like Lamport signatures, if a bit is 0, then you pull a bit from A, if 1 then pull a bit from B. The difference being that with Lamport you need an entire hash not just a bit(little bit more secure.. but not worth the space, double the key in my system and you probably have more security).

Then catch is that you now need to reveal A, which can be used to calculate B and C. This proves that you did indeed use those hashes to sign. The problem is that you've just revealed your private key and anyone else can sign on your behalf. So the only way this works is if you use two phases: commit phase where you hand over the signature and message. Then a verifying phase where you send over your private key to verify that it was indeed you signing it.

In most cases, multiphases is fine. After all, Lamport is essentially multiphase.. send public key, send signature.

Using a long hash chain you could come up with a many-use private key where you just pop off the last hash (which is actually three hashes) to use it.

Am I missing anything? Any thoughts on how to remove the commit phase or construct something that gets similar security uses a similar idea?

Still not going to work for my cryptocurrency since I can't have multi-phase signatures but might help some people out there or help with brainstorming a shorter public key & signature scheme that would work.

In most cases, multiphases is fine. After all, Lamport is essentially multiphase.. send public key, send signature.

Not quite - with Lamport (or any other signature scheme), after seeing the public key and the signature, an attacker still cannot forge a signature; with your technique, he can.  Almost all uses of signatures rely on this property, and so your technique cannot be considered a general replacement.

If what you have meets the requirements of your problem space, that's fine.  Just realize that it really is a niche solution...

Actually, if you're happy with the limitations of your method, it can be simplified somewhat: to "sign" a message $M$, pick a random string $R$, and transmit $H(R, M)$ and $M$.  Then, in phase 2, transmit $R$.  This uses one fewer hash (and the hash can be of shorter length, as we're not giving away half the bits in the commit phase).


Key distribution and computation for homomorphic encryption How can a system where the party performing a computation also possess the private key and still not know the answer of computation be designed ? Also the other party who does not have the private key know the correct result ?

Involving a trusted third part seems a possible solution. But are there other ways to design such a system ?

Consider the following scenario: A has an input $x_1$, the public key and private key. B comes in with another input $x_2$. A sends the public key to B. B sends the encrypted value $enc(x_2)$ for A to perform a computation $C(enc(x_1), enc(x_2))$. A performs the computation and sends the result to B. A should not know the correct value of result. But here if A is performing the computation and also has the private key, then A can decipher the answer.

You are correct, if you do things the way you describe, A would be able to decrypt B's private data. So don't do it that way.

Instead, since B is to know the answer, let B encrypt his private input with his own public key. He sends that to A. A encrypts her private input with B's public key, then runs the computation. A then returns the encrypted answer to B. B decrypts it.

Since you added multiparty-computation, you may be interested in how this extends to more than two parties. Here is a relevant quote from Craig Gentry's PhD thesis

  Extending our application of fully homomorphic encryption from the two-party setting to the multiparty setting is not entirely trivial, since, in the two-party setting, Bob prevented Alice from seeing any intermediate values encrypted under Alice’s key simply by finishing the computation himself, and sending back the final encrypted value to Alice; in the multiparty setting, it is less clear how one prevents Alice from seeing intermediate value encrypted under her key.

A number of protocols using homomorphic encryption to enable secure multiparty computation have been proposed, the most practical of which is probably SPDZ.


Why is OCB-AES mode not becoming a standard for authenticated encryption? The OCB mode of authenticated encryption (used for example with AES) is the fastest way to provide authenticity and confidentiality without having to strive into questions like: Encrypt then MAC, MAC then encrypt, Encrypt and MAC.

So why it is not widely used and didn't become a standard?

Because OCB is patented.

And there are other good solutions for authenticated encryption that aren't patented.  This makes them more suitable, in most situations.  I can recommend, e.g., EAX, GCM, or CWC.  EAX and GCM have been used in some standards, and AES-GCM has been standardized.

For pointers where you can learn more, read Wikipedia.  And try using search on this site with the phrase "authenticated encryption".

Update: There are now free licenses available for OCB.  However, they have some unusual restrictions, which some implementors have expressed concerns over (e.g., one license only applies to open-source software; another allows only non-military uses).  For a detailed discussion, see the responses on this thread on the IRTF CFRG mailing list.


Mathematical Proof for Key independence in Differential Cryptanalysis How would you construct a proof that XOR difference of two cipher texts cancels the influence of the key?

I started out with a simple cipher defined as follows:

$C = \Phi( S(P\oplus K_{0}) \oplus K_{1})$

Where

$\Phi$ is a permutation box
$S$ is a substitution box
$K_{0}$,$K_{1}$ are the first and second round keys respectively
$P$ is the plaintext
$C$ is the cipher-text

In an effort to prove that the XOR difference is independent of the influence of the round keys, I start by constructing an expression for the XOR difference of two cipher-texts :

$C_{0} \oplus C_{1} =  \Phi( S(P_{0}\oplus K_{0}) \oplus K_{1}) \oplus  \Phi( S(P_{1}\oplus K_{0}) \oplus K_{1})$

Which I've simplified to the following algebraic form:

$\Phi^{-1}( C_{0} \oplus C_{1}) = S(P_{0}\oplus K_{0}) \oplus  S(P_{1}\oplus K_{0})$

I'm too paranoid about the non-linearity of the SBOXs to apply straight forward algebraic law to this form.

How do I get rid of the SBOXs and am I even going about this proof the correct way?

The difference between the pair of inputs going into the s-box (consisting of two plaintexts xored with the first round key) is the same as the difference in the plaintexts alone.  i.e. $(P_0 \oplus K_0) \oplus (P_1 \oplus K_0) = P_0 \oplus P_1$, because the round key $K_0$ cancels out.  Hence, the input difference is independent of the value of the first round key.  No matter what value you pick for $K_0$, the difference of the two inputs going directly into the s-box will be the same as the difference between the two plaintexts, with probability 1.

On the contrary, the output difference (difference between the outputs of the two s-boxes) is not independent of the round key.  Or to be more precise, if you know $P_0$, $P_1$, and $K_0$ then the output difference just after the s-boxes -- $S(P_0 \oplus K_0) \oplus S(P_1 \oplus K_0)$ -- is fully determined and will vary depending on the precise value of $K_0$.

If, however, you assume that the pair of plaintexts is chosen uniformly at random from all pairs that satisfy some particular difference $\Delta P$, then the probability that the output difference will equal some particular value $\Delta C$ is independent of the precise value of $K_0$.  This is because any given value for $K_0$ will simply exchange one pair of plaintexts that xor together to equal $\Delta P$ for another pair that xor together to equal $\Delta P$ (because of the equality in the first paragraph above).  As such, the input pair going into the s-box after the roundkey is applied is still a uniformly random pair that xors together to equal $\Delta P$.

So under the assumption that the input difference is fixed but the input pair that xors together to equal that fixed difference is selected uniformly at random**, the probability that the output equals $\Delta C$ is purely a function of the (unkeyed) s-box, as summarized in the difference distribution table for the s-box.  Note that this is different for key-dependent s-boxes.

** This assumption is equivalent to the assumption that the input pair is fixed but the roundkey is selected uniformly at random.


Difference between Tag and Signature Is there a technical difference between tag such as tag generated by authenticated encryption, and signature such as the signature generated by a functional signature scheme or homomorphic signature scheme.

The authentication tag is the output parameter, like in AES-GCM, which is generated by the symmetric key to authenticate the message.

$$(c,tag) = \operatorname{AES-GCM-Enc}(key,m,IV,AD)$$

Where $A$ is the Associated Data. The tag is verified by the same key, IV, and AD.

$$(\{T,F\},m?) = \operatorname{AES-GCM-Dec}(key,c,IV,tag,AD)$$ The tag verification must be performed before using the plaintext.

A signature, digital signature, is created by using the asymmetric encryption mechanisms using the private key. Such as DSA, ECDSA, EdDSA, or RSA signatures. The digital signature can only be created by the private key owner, and it can be verified by anyone who knows your public key. The secure hashing mechanism is an integral part of secure signatures not due to signing small messages.

$$\text{signature} = \operatorname{Sign}(k_{prv}, m)$$

$$ \{T,F\}\stackrel{?}{=} \operatorname{Verify}(\text{signature},k_{pub},m)$$

So the distinction is; the tag is generated by the symmetric key and the signature is generated by private-key.


What risks are involved when choosing a curve for an implementation of ECC? What risks are involved when specific curves are chosen for an ECC implementation?

How should I audit a system that uses ECC with regards to a specific curve?

Bonus: How can I (or a cryptographer) determine if a curve is backdoored?

Risks of choosing specific curves

Using your own crpytographic scheme (a.k.a. "rolling your own crypto") is extremly bad. Anyone can invent an encryption algorithm they themselves can't break. It's much harder to invent one that no one else can break. It's also bad practice to use a non-open-source API for cryptography because you might not know how exactly it's implemented.

But using specific curves doesn't necessarily imply that it's unsecure. Standardized ECC often uses specific curves that are presumed to be secure.

So in general it's good practice to use standardized ECC (i.e. curves from the safe-curve-project) and open-source implementations that have been vetted and are broadly in use.

Auditing a ECC system regarding specific curves

The first thing you should do is research. If you find a paper that raises concern about the security of a specific EC then you should probably find another one.

How to determine if a curve is backdoored

Like many other cryptographic schemes ECC uses random number generators, specifically CSPRNGs.

The problem is, that such CSPRNGs could potentially have a keltographic backdoor, if certain conditions are met. One example of this is a (former) CSPRNG, the Dual_EC_DRBG.

Many cryptographers (i.e. this PDF) have raised concern about this generator and through the Snowden leaks it is now presumed that the NSA had put a kleptographic backdoor in this generator. This video by Computerphile explains it quite well.

The vulnerability of ECC is not the discrete logarithm problem, this is (very likely) not solved. It's rather the implementation of the ECC scheme and especially the usage of certain CSRNGs. If there is a constant in the CSRNG it should be stated how and why this constant was calculated and chosen.


What is the difference between Scrypt and PBKDF2? After reading these two resources I am wondering am I getting all the differences between Scrypt and PBKDF2.

As far as I understood, the similarity is:

both are password-based key derivation functions.

The difference is:

Scrypt is more resource demanding.

Am I missing something?

Both PBKDF2 and scrypt are key derivation functions (KDFs) that implement key stretching by being deliberately slow to compute and, in particular, by having an adjustable parameter to control the slowness.

The difference is that scrypt is also designed to require a large (and adjustable) amount of memory to compute efficiently.  The purpose of this is to make cracking it harder to parallelize using devices like GPGPUs or custom ASIC / FPGA hardware.
Such devices may have hundreds or even thousands of parallel processing units, each capable of hashing a different password using traditional KDFs like PBKDF2, which don't require much memory.  However, it turns out that, at least using current technology, providing each of these parallel units with large amounts of memory space is a lot more difficult and expensive than making the units themselves.

Another difference between PBKDF2 and scrypt is that PBKDF2 is a generic construction for turning any cryptographic hash function (actually, a pseudorandom function, but the most common way to obtain a PRF for PBKDF2 is to build one out of a hash function using the HMAC construction) into a key-stretching KDF.  Thus, the actual KDF you use might be e.g. PDFKD2-HMAC-SHA256, meaning PBKDF2 built on HMAC built on the SHA-256 hash function.

Scrypt, on the other hand, is a specific key derivation function with "no user-replaceable parts inside".  While scrypt does make use of some standard functions and constructions (in fact, it internally uses PBKDF2-HMAC-SHA256 for the state expansion and compression stages), the scrypt specification doesn't make any allowances for, say, changing the hash function to something other than SHA-256.  It's a "take it or leave it" deal.

That said, it would, in principle, be possible to define a new KDF using the priciples described in the scrypt paper, but with different components.  In particular, the scrypt paper defines scrypt as an instance of a more general construction called MFcrypt, instantiated with HMAC-SHA256 and the memory-hard mixing function SMix (also defined in the paper).  It would be possible to use an MFcrypt instance with, say, SHA-3 instead of SHA-256, but that function would no longer be "scrypt" as defined in the paper.


Chance of finding the right key by exhaustively searching on half of the key space An exhaustive search of half the key space requires $2^{n-1}$ work and provides the right answer 75% of the time. If the attacker finds the key, he knows the answer. If he doesn't find the key, he still has a 50% chance of guessing right simply by guessing at random. Overall, his chances of getting the right answer are therefore $0.5 + 0.5*0.5 = 0.75$.).

In this quote from Cryptography Engineering book by Bruce Schneier, section 3.4, it has been said that there is 75% probability that a particular key can be found by dividing the key space into half, exhaustively searching from this and choosing a key randomly if not found. How the $0.5+0.5*0.5$ has been derived in this case? How is the chance of randomly guessing a key from the key space in 50%? Shouldn't it be $1/2^n$ in case where key size is $n$.

Schneier is talking about distinguishing a block cipher from an ideal cipher - or in other words, about formal definitions for security.  Think of a game, where the attacker is given a ciphertext encrypted either with a block cipher or with an ideal cipher (with equal probability), and has to guess which cipher encrypted the message.

Let's say this attacker tries 50% of the block cipher key-space, and if any key correctly decrypts the message then it guesses that the cipher that encrypted the message was the block cipher.  But if no key correctly decrypts the message then the attacker guesses that the ideal cipher was used.

There's a 50% chance that the cipher used was in fact the ideal cipher.  In that scenario, the attacker will always correctly guess that the ideal cipher was used - so it has a 50% chance of being correct along that branch of the probability tree.

There's also a 50% chance that the cipher was in fact the block cipher, and in that scenario there are two possible outcomes - either the key was among those that the attacker tried (in which case it will correctly guess that the block cipher was used), or the key was not among those that the attacker tried (in which case the attacker will incorrectly guess that the ideal cipher was used).  Since the attacker tries half the key-space, that means the attacker has a 50% chance of guessing correctly (given that the block cipher was used).  So the total contribution of this branch of the probability tree is 50% (odds that block cipher is used) * 50% (odds that key is among those tested) = 25%.

So the total probability of the attacker making a correct guess is 50% + (50%*50%) = 75%.


SPDZ for the 2-party case There exist protocols for 2-party computation e.g., GMW that use Boolean circuits. I could also use Paillier and arithmetic circuits for a 2 party computation. However after reading about SPDZ is my understanding I could use it to do 2-party computation. Is my understanding correct? Besides the fact that I would have to generate tons of triples, is there any other drawback of using SPDZ for 2-PC? If this is the case why is not widely use for the 2-party case? Should I favor a 3 party setting instead of a 2 party one when using SPDZ?

Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation protocols such as the various versions of the Yao protocol or the TinyOT protocol are limited to two parties. So it may sometimes be overemphasized that SPDZ goes beyond two parties.

There is no drawback to using SPDZ with just two parties compared to three parties. Certain aspects such as the required broadcast actually becomes simpler in the two party case. So you should never try to add additional parties beyond what you need, it will only make you application less efficient.

However, there are many trade-offs to consider when choosing a secure computation protocol. Therefore, there could be good reasons to pick an other protocol than SPDZ in a two party setting. For example, SPDZ is based on arithmetic operations. If your application is heavy on Boolean operations, other protocols such as TinyOT which is based on Boolean operations may perform better. Also, SPDZ has round complexity proportional to the depth of the circuit you are evaluating. Yao has constant round complexity for any circuit. So if you are in a high latency setting or evaluating a very deep circuit, Yao may perform better than SPDZ.


Dual_EC_DRBG and OpenSSL on a Mac Since there is not much info anywhere on the Internet related to this:

Does anyone know if OpenSSL's default CSPRNG is Dual_EC_DRBG or not?
Their wiki is not very clear…
Related to the first question, does anyone have any experience with OpenSSL on Mac changing the default CSPRNG?

Well, I think OpenSSL has documented this pretty well:

  If an alternative RAND_METHOD implementation is being used (either set
  directly or as provided by an ENGINE module), then it is entirely
  responsible for the generation and management of a cryptographically
  secure PRNG stream. The mechanisms described below relate solely to
  the software PRNG implementation built in to OpenSSL and used by
  default.

  These functions implement a cryptographically secure pseudo-random
  number generator (PRNG). It is used by other library functions for
  example to generate random keys, and applications can use it when they
  need randomness.

  ...

  The RAND_SSLeay() method implements a PRNG based on a cryptographic hash function.

  ...

  hash function; currently SHA-1

So that is certainly not Dual_EC_DRBG. You can switch RNG method by using RAND_set_rand_method but setting a different ENGINE should be preferred for newer applications.

Note that it would not hurt to check this in the source of the openssl implementation you are using. I don't believe it has changed yet, but openssl documentation is not known for its, eh, "up to dateness".


Where does the meaning of reduction to a hard problem lie? Given a protocol, if we can reduce breaking the protocol to a hard problem, such as DLP or CDH, we can say that this protocol is secure.
Theoretically speaking, reduction is a good method to prove the security of a protocol. As to key-exchange protocols, if the reduction method uses the adversary as a subroutine, the simulator will construct an algorithm. If the adversary can break the protocol under a certain model, then the simulator can solve a hard problem, say CDH.
However, in practice, can the simulator's algorithm be realised with a computer program? Moreover, does it work?

The idea of proofs by reduction is that it should be possible to turn a real adversary into an algorithm doing some "useful" computation. So yes and yes.

However, sometimes, reductions are weak, in the sense that even if the real adversary is feasible (can be run in reasonable time on reasonable computers), the resulting algorithm doesn't have to be feasible. The algorithm can be constructed as a computer program, but it doesn't really work. So that's yes and no.

Sometimes, we also have even weaker proofs, so-called existence proofs. They only prove that if an adversary exists, then an algorithm doing some "useful" computation exists. Which means that even if we are given an adversary, we don't really know how to construct the algorithm doing that "useful" computation. So that's no and no.

Modern cryptography recognizes all of these differences. Reductions that work are best. Weak reductions are considered solid evidence of security, but leaves something to be desired. The even weaker reductions are sometimes considered evidence of security, and sometimes leave a lot to be desired.


Does rsa-oaep provide or not plaintext integrity in addition to confidentiality? My own understanding (possibly wrong of course) of RSA-OAEP encryption scheme is that it  provides plaintext integrity (in addition to confidentiality) due to MGF function which for encryption operation, applies to maskeDB sequence which value directly depends of input M (plaintext) message, and is further checked during decryption operation.     However in previous post on that subject, the answer indicated that no public key encryption scheme can satisfy INT-PTXT (nor INT-CTXT) requirements

So is it possible to have confirmation if rsa-oaep insures integrity of input symmetric session key to be encrypted or if it is recommended with rsa-oaep to encrypt a symmetric session key appended with a hash or eventually crc value for insuring integrity ?

RSA-OAEP does not provide "plaintext integrity in addition to confidentiality".  By the definition of PKE, anyone with the public key can encrypt whatever plaintexts they choose.  In particular, encrypting "a symmetric session key appended with a hash or eventually crc value for insuring integrity" doesn't help.  To get integrity, there has to be something [the honest party knows which the adversary doesn't know] or [the honest party can do that the adversary can't do].


Using raw encrypted network data for randomness I've read that encrypted data should be, theoretically, indistinguishable from random data. Using this principle of encryption, could I combine encrypted network traffic streams to generate either a seed for a randomness algorithm or simply combine them for the random number itself?
For example: I could take data from a Tails or other Tor connected device and simply specify which incoming node to listen to and for how long, not only would the attacker have to know I used this system but they'd have to know the index and duration of the nodes I choose.
For context: I only need a few MB of extremely random data at very infrequent intervals. So time  and memory efficiency doesn't matter all that much.
To address a comment by DannyNiu: Obviously they now know this system exists but if it can run on any encrypted network then, as opposed to using a random number generator website, you do not know which computer is collecting network traffic for this purpose since any encrypted data could be used.

For Linux at least, the randomness that goes into /dev/urandom is already taken from the network. The difference between its scheme and yours is that it takes timing data instead of raw encrypted data. The reason for this is that timing data becomes harder to predict as you get farther away from the target, whereas raw traffic contents can be recorded trivially at any point in the path. This timing data comes from nanosecond timestamps of interrupts sent by the network interface device (NIC).
Taken from another answer I posted on another Stack Exchange site:

In modern hardware, an interrupt is a signal emitted by hardware to alert the CPU to a status change. It allows the CPU to avoid rapidly polling every hardware device for updates and instead trust that the device will asynchronously alert it when the time comes. When an interrupt occurs, an interrupt handler is called to process the signal. It turns out this handler is the perfect place to get randomness! When you measure the nanosecond-level timing of interrupts, you can quickly get a fair bit of randomness. This is because interrupts are triggered for all sorts of things, from packets arriving on the NIC to data being read from a hard drive. Some of these interrupt sources are highly non-deterministic, like a hard drive which relies on the physical motion of an actuator.

One caveat is interrupt coalescing, a feature supported by many modern NICs that batch interrupts to reduce per-packet overhead, rather than sending a separate interrupt for each received or transmitted packet. Depending on how it is implemented (count-based or timeout-based), it can potentially reduce the amount of entropy that can be gathered by the NIC. However, most NICs let you disable it.


Tranposition Ciphers I am studying classical ciphers and have the following doubts:

Is the row and columnar transposition cipher the same?

It is similar since the process of encryption and decryption is the same for both(my opinion).

How did the author get the ciphertext using row transposition cipher? (link: http://williamstallings.com/Extras/Security-Notes/lectures/classical.html)

Key(R): sorcery => 6 3 4 1 2 5 7
Plaintext: laser beams can be modulated to carry more intelligence than radio waves
Ciphertext: erasb lecam snabd umole atoed ctamo ryrre elntl iicee ntgha dnria oesav w

Your second Answer first.
[2] write down the key column wise as shown ,then fill the plain text row by row so you will get the matrix of (len(plaintext)/7 x 7), now for ciphertext, take first row and then start taking the value in ascending order of key,  see below, key and particular row
for ex for
row 1:- {1:e, 2:r, 3:a,4:s, 5:b,6:l,7:e}
row 2:- {1:c,2:a, 3:m,4:s,5:n, 6:a,7:b} and so on..
so your cipher text would be erasb lecam snab.....
-Key:    6   3   4   1   2   5   7
-PT:      l   a   s   e   r   b   e
-PT:     a   m   s   c   a   n   b
[1] In columnar transposition cipher you read column wise, for ex. in  above example, you can write entire characters of column 1 then 2 ...
so cipher text would be ecdtmecae rauooleds ammernena ....


Would a Rubik's cube be a trapdoor function? It's easy to scramble a Rubik's cube but it is hard to solve, unless you know the algorithms for solving it. This makes it a trapdoor function, correct?

It might be a viable example for explaining the concept of a trapdoor function to a layman without a computer science or math background. But from a CS standpoint this is only half-true.

For a low number of n where n is the number of rotate-operations performed on the cube, it is true that finding a solution for the cube is more computationally expensive than applying the rotations. But with very high values of n this might change. It was proven that any rubic's cube configuration can be solved with 20 moves or less, and finding that 20 move sequence might in fact be faster than applying the "correct" sequence.


Recommended Books for Cryptography : Theory and Implementation It is a great idea if experts in Cryptography from mathematicians to security engineers introduce books and textbooks which they think is helpful or instructive for all people interested in the field.I didn't find such topic in previous posts.

I think a good format for answering would be like this:

I.
Theory, Analysis, Algorithms, Complexity,...
II.
Design, Implementation, Code Writing( in C/C++, Java,...),...
III.
History, Development, Future possibilities,...

Thanks in advance to all contributors for sharing your knowledge

Theory and practice: Cryptography Engineering by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno

Design and some implementation tips are in Cryptography Engineering too. Code writing is highly dependant on the library you're using, so you should read its documentation first.

Development is covered, again, by Schneier's book. As for future possibilities: you'd need to subscribe to cryptography journals.

The older books (Practical Cryptography and Applied Cryptography) are good too, but don't cover the newest algorithms (AES, SHA-2, elliptic cryptography).


Can you explain “weak keys” for DES? A weak key for DES is a key $K$ such that $DES_{k_1}(DES_{k_2}(x))=x$ for all $x$.

I don't get why are the 4 keys $k_1||k_2$: $1^{112}$, $0^{112}$, $0^{56}||1^{56}$, $1^{56}||0^{56}$ considered as weak. (Also didn't find some detailed explanation in the web.)

Did you try Wikipedia?

DES consists of 16 rounds of the form:

$$L_{i+1} = R_{i}, \quad R_{i+1} = L_i \oplus F(R_i, K_i),$$

which are identical except for the round subkeys $K_i$.  (The last round is slightly different, in that the half-blocks $L$ and $R$ are not swapped as they are after all other rounds, but that makes no cryptanalytic difference.)

The subkeys $K_i$ are derived from the encryption key $K$ using the DES key schedule, which takes the form:

$$K_L \,\|\, K_R = P_1(K)$$
$$K_i = P_2(K_L \lll n_i, K_R \lll n_i)$$

where $K_L$ and $K_R$ are the left and right halves of the permuted key $P_1(K)$, the functions $P_1$ and $P_2$ are fixed maps that basically just shuffle the bits around, and $\lll n_i$ denotes bit rotation by the fixed number of positions $n_i$, where

$$(n_0, n_1, \dotsc, n_{15}) = (1, 2, 4, 6, 8, 10, 12, 14, 15, 17, 19, 21, 23, 25, 27, 28).$$

The important thing to note here is that, if $K_L$ and $K_R$ each consist of all zero or all one bits, then rotating them has no effect, and so all the subkeys $K_i$ will be equal, which in turn implies that all 16 rounds of DES encryption using these keys will be identical.  Since there are two choices (all ones or all zeros) for each of $K_L$ and $K_R$, this gives us a total of four weak keys.

In particular, because DES is a Feistel cipher, and therefore each DES round is its own inverse (except for the swapping of the half-blocks), the fact that all the rounds are identical also makes the full DES function self-inverse: that is, for weak keys, DES encryption is the same as decryption.

Ps. DES also has six pairs of "semi-weak keys", for which encryption with one of the keys in the pair is equivalent to decryption with the other (and vice versa).  Basically, these are the keys for which the bit patterns of $K_L$ and $K_R$ repeat with a period of 2, i.e. $$K_L, K_R \in \{000000{\dotsc}00,\, 010101{\dotsc}01,\, 101010{\dotsc}10,\, 111111{\dotsc}11\}$$ (excluding the four weak keys described above).  Because the bit patters have repeat with period 2, the round subkeys $K_i$ for these keys can only take two possible values, depending on whether the rotation constant $n_i$ is odd or even.

In particular, reversing the bits of each of $K_L$ and $K_R$ (or, equivalently, rotating them by one bit) for any of these semi-weak keys gives another "complementary" semi-weak key that generates the same two round subkeys, but switched around.  If you look at the DES rotation constants listed above, you'll notice that $n_i$ is odd if and only if $n_{16-i}$ is even, and thus this swapping of the round subkeys is equivalent to reversing the key schedule.  Since DES decryption is the same as encryption with the key schedule reversed, this means that encryption using a semi-weak key is equivalent to decryption using its complementary pair.

There are also 48 "possibly weak keys" for which the bit patterns of $K_L$ and $K_R$ have a period of 4, and which thus generate only four distinct round subkeys.  These keys don't have such obvious encryption/decryption symmetry properties as the weak and semi-weak keys, but they nonetheless produce a much simpler key schedule than usual, which might conceivably be exploited somehow.

Of course, in practice, all these types of weak keys are pretty much irrelevant: if your keys are chosen randomly (or by a good KDF), the chance of picking a weak (or semi-weak or possibly weak) key is negligibly small ($1/2^{50}$).  And if you did suspect that a system was, for some reason, more likely to use weak keys than one would expect by chance, a much more efficient way to exploit this knowledge would be to just test all these 64 keys and see if any of them indeed happened to be the correct one.  Not to mention that any (single) DES key is "weak" nowadays, simply because the 56-bit keyspace is too small to resist brute force attacks (although triple DES, which doubles the keyspace, does also have the same kind of weak keys as single DES).

Pps. Showing that there are no other similarly weak keys in DES would require a somewhat more detailed analysis. In particular, there's the quirk that the DES PC-2 function ($P_2$ above) ignores some of the bits of the rotated subkeys (specifically, it only selects 48 bits out of 56), so it's possible that $K_i = K_j$ even if $(K_L \lll n_i \,\|\, K_R \lll n_i) \ne (K_L \lll n_i \,\|\, K_R \lll n_i)$.

However, while I haven't actually worked out all the details, I do expect that, even if occasional subkey collisions are certainly possible, the self-inverse properties of weak and semi-weak keys should not occur for any other keys, since they require the whole subkey schedule to be (anti-)symmetric.


Properties of PRNG / Hashes? There are a lot of quite elaborate PRNG's out there (e.g. Mersenne Twister et.al.), and they have some important properties, especially when it comes to crypto applications.

So, I was wondering how hash functions like SHA1 or MD5 would perform in such a scenario / compare to actual PRNG's. For instance, one could use the a1 = hash(seed) to generate the first batch of random bits and then a2 = hash(seed + a1) for the next series and so forth.

Mersenne Twister (as an example) is a fast random number generator, and has good properties (long period, good distribution) for most applications of random numbers (like statistics, simulations, modelling).

For cryptographic applications, we need more: We need a cryptographically secure random number generator. Such a function (implemented by an algorithm) has the property that an attacker has no means of to distinguishing the output from a pure random bit sequence, if he does not know the seed.

Such CSPRNGs (cryptographically secure random number generators) can be build from several other cryptographic primitives:

cryptographic hash functions
block ciphers
stream ciphers

All these primitives effectively need the properties of a "normal" PRNG, thus they are usable as such.

On the other hand, the algorithms implementing such primitives are normally a lot slower than "normal" PRNG - thus don't use iterated SHA-1 when Mersenne Twister is enough for your needs.