What is the difference between substitution cipher and block cipher? I'm studying(and clearing my head) about block cipher. I started from Caesar Cipher which can be considered as a kind of substitution cipher (if my understanding is right).

And an ideal substitution cipher (in 26 alphabets) is the two functions $E(x,k)$ and $D(x,k)$ where $0 \leq k < 26!$. And given $k$, one of the bijection(substitution) functions is (uniformly)selected and used to substitute a letter.

What I thought here is that this is also a block cipher. (1 letter is 1 block)
I read https://en.wikipedia.org/wiki/Substitution_cipher and it says

  Although the number of possible keys is very large ($26! \approx 2^{88.4}$, or
  about 88 bits), this cipher is not very strong, and is easily broken.
  Provided the message is of reasonable length (see below), the
  cryptanalyst can deduce the probable meaning of the most common
  symbols by analyzing the frequency distribution of the
  ciphertext—frequency analysis.

I feel this description is talking about the problem of ECB mode in block cipher.

So my understanding so far is that substitution cipher can be considered as a block cipher. But I'm wondering if a block cipher is always substitution cipher.

What is the difference between them in general.

I feel this description is talking about the problem of ECB mode in block cipher.
So my understanding so far is that substitution cipher can be considered as a block cipher. But I'm wondering if a block cipher is always substitution cipher.

(1) let us compare a block cipher with ECB mode to a substitution cipher.
With ECB Mode and a given key, a block cipher can be seen as a substitution cipher which maps one block to another block. For example, AES, twofish, or serpent has a block size of 128 bits; you may say, "one 128-bit block is substituted to another 128-bit block".
(Note: this is just a simple comparison. If a block cipher has a "state", the same input blocks might get different output blocks. In this case, the block cipher might be compared to Vigenère cipher.)
While a Caesar Cipher maps one letter to another letter. That is from a 5-bit to a 5-bit, or at most a byte to a byte. (From this point, you could be right to say "substitution cipher can be considered as a block cipher"; but the block size is quite small.)
So, I might say a Caesar Cipher is a special block cipher which has a small block size; or, on the other hand, a 128-bit block cipher (with ECB mode) is a "monster Caesar Cipher with 2128 letters".
(2) a block cipher with certain mode (except ECB)
This is a fun part. From my point of view, if you want, you can actually create a Caesar Cipher with CBC, PCBC, OFB, CFB, CTR modes by replacing the IV or counter with a letter.

What is the difference between them in general.

(3) difference
They are quite different in practice.
But the main one is size: block size, key size, IV size, and counter size. (The last two is really the block size for different uses).
If a monster Caesar Cipher has 2128 letters and has CBC, PCBC, OFB, CFB, CTR modes, it might be as strong as a 128-bit block cipher.


Checking a key before actually using it I have a block of data crypted using twofish with a key of 128 bit.

The data must be accessed from a GUI, the user gives the key, the block is decoded and the real data is accessed.

Problem is that I need to be sure that the key is correct before trying to decode the block.

My current solution is to have a file (say chk.blk) that is the encryption of some data I can use to test the correcteness of the key.

Initially I had a file chk.blk being the encryption of a known data (say the text 12345678) then I thought that this could compromise the key. Is that true? Is there any weakness in twofish if the attacker has both the original and the encrypted data?

Fearing this could be the case, I now generate a random text with a given property (e.g. x...x..x where . is any character different from x). I take the key, decode chk.blk and verify the result has the desired property.  The idea is that now the attacker does not have a known text to use but a rather large group of them. Of course I can't be sure that the key is really correct, the user might have taken, by chance, a key that produces a decoded text which have exactly the desired property, but I think the probability is extremely low.  Do you think there any issue with this approach?

Any suggestion?

Usage scenario

I'm adding some more info here to clarify the intended usage.

Imagine you have a rather big set of documents (5Mb of data) that must be sent to a large number of recipients (say 10.000). Those documents have to be kept absolutely secret until a given date/time (say 21 Dec 2012 21:12).

Between now and then all the reciepients will be able to download the documents along with a decryption program on their PC. They will reach their designated destination and will wait there to receive the decoding key at the proper time.

Exact syncronization is not important but they all have to read the documents at (almost) the same time.

It is absolutely mandatory that none of them can read the documents before the given date.

They will be located in places where they might not be connected to the internet, that's why they have to download the docuemnts beforehand.

They will all, however, be able to receive a message with the key (e.g. via SMS, via phone, broadcasted by a TV channel or a radio number station, ...).

So, the idea is to distribute the documents encripted with 128 bits of security, which should be enough to protect the key for few months, and then distribute the key as a string (26 characters).

In order for a symmetric block cipher to be considered secure by modern standards, it has to be IND-CPA, that is indistinguishable from a random oracle under a chosen plain text attack. It also has to be IND-CCA and IND-CCA2, but IND-CPA is sufficient for it to also be secure under a known plain text attack.

Presuming TwoFish is still unbroken, it should consequently be safe to use the cipher text of a single known block as a key verifier. Or, to be more precise, storing that chk.blk file together with the encrypted file will not reveal significantly more information about the key.

However, there are other issues with your approach you might or might not already be aware of.

Firstly, do you really think it is feasible to get a user to enter a completely random 128 bit key using a GUI? Most application use pass phrases for such scenarios, and in such case your approach should be slightly different. For starters, where do you store the salt for the PBKDF? Will the key be used for encrypting more than one file? What information will the adversary be able to deduce just by looking at the cipher text of two files that are known to be encrypted using the same key?

Secondly, your approach is really only secure if the only threat is an adversary, without access to the key but with read only access to both the verifier and the actual cipher text, trying to guess the plain text contents corresponding to the cipher text. Your scheme is insufficient to prevent anything beyond that scenario.


Shannon entropy calculation: is $H(A|R·A) = H(A)$? Suppose I generate a random $m×m$ matrix $R$, where each of its elements belongs to $\mathbb Z_n$. I ensure that $R$ is invertible in $\mathbb Z_n^{m×m}$.

Now I take a non-random $m×m$ matrix $A$, where each of its elements belongs to $\mathbb Z_n$ and is not zero. I now multiply them both together to obtain $R·A$ and reduce $R·A$ modulo $n$.

My question is about its Shannon entropy: Is $H(A|R·A) = H(A)\ $?

Well, no, in general, it is not.  Here's a simple example that demonstrates it is not:

Suppose that $m=2$, $n \ge 3$ and the matrix $A$ can take one of the following two values:

$\pmatrix{1&2\cr1&1}$ with probability $1/2$, and $\pmatrix{1&2\cr1&2}$ with probability $1/2$

Note that the first matrix is nonsingular (invertible), while the second is singular.

In this case, $H(A) = 1$

On the other hand, if we are given the value $R \cdot A$, this matrix is nonsingular if $A$ is the first value, and singular if $A$ is the second value.  Hence, the value of $R \cdot A$ allows us to derive the value of $A$ with probability 1, and hence $H(A | R \cdot A) = 0$

If $A$ is constrained to be an invertible matrix, and $R$ can take on all invertible matrices with equal probability, then $H(A | R \cdot A) = H(A)$; this can be deduced from the fact that matrix multiplication is a group operation over invertible matrices.


How to Calculate GE of Sbox? How to count Gate Equivalent (GE) of Sbox used in block Cipher. For example how much area does the Sbox of Block Cipher Prince take? And How is it calculated?

This basically boils down to find a "good" implementation of the S-box and then compute the GE by weighting the operations used (e.g. XOR = 1GE), that is, as you already commented, synthesize the implementation.

Note that the resulting GE greatly depend on the optimization of your implementation, the technology library used etc.

Wikipedia lists some software for this:

https://en.wikipedia.org/wiki/Logic_synthesis#Commercial_tools_for_logic_synthesis
https://en.wikipedia.org/wiki/Logic_synthesis#Free_tools

I've never used a tool to design an ASIC, I have only some basic experience with FPGA development, so cannot tell you more about the different tools.


Key shortening for hmac sha256 For learning purpose, I'm trying to implement HMAC using SHA256.

In the pseudo code proposed in Wikipedia, the algorithm first focus on how to shorten or expand the key :

if (length(key) > blocksize) {
    key = hash(key) // keys longer than blocksize are shortened
}
if (length(key) < blocksize) {
    // keys shorter than blocksize are zero-padded (where ∥ is concatenation)
    key = key ∥ [0x00 * (blocksize - length(key))] // Where * is repetition.
}

Given I'm using SHA-256 that has a blocksize of 64 bytes and an output of 32 bytes :

if the key length is greater than 64 bytes, it will be shortened to 32 bytes
if the key length is less than 64 bytes, it will be expanded to 64 bytes

From what I read 32 bytes should provide enough security. But doesn't that seem odd that a 65 bytes key will provide less security than a 63 bytes key ?

From the HMAC-RFC 2104, section 3
(B = blocksize, L = hash output length):

  The key for HMAC can be of any length (keys longer than B bytes are
  first hashed using H).  However, less than L bytes is strongly
  discouraged as it would decrease the security strength of the
  function.  Keys longer than L bytes are acceptable but the extra
  length would not significantly increase the function strength. (A
  longer key may be advisable if the randomness of the key is considered
  weak.)

Tldr, unlike you, they don't consider a longer key to be more secure.


Using the encryption matrix from AES, how do you compute the decryption matrix? So I don't want the answer but somewhere to start with this problem, first I want to know if my logic and thinking is on the right path before I dive right into computing the decryption matrix so here is the question:

Recall the encryption matrix for AES is $E = \begin{bmatrix}1&x^2\\x^2&1\end{bmatrix}$ over the finite field $\mathbb{F}_{16}$ with irreducible polynomial $x^4 + x + 1$. Compute the decryption matrix $D = E^{-1}$

My thought is find the inverse of each individual polynomial in the matrix but I think that's way to simple to do but, calculating the inverse of each polynomial in the matrix we would just divide by the irreducible polynomial right?

Another thought would be using the same steps as the hill cipher?

please let me if I am on the right track or I'm not even close to the start of it all

First of all, this is not "AES", but something else.  Someone might claim that it's somewhat similar to AES, but it's still not AES.

However, to answer your question:

  please let me if I am on the right track or I'm not even close to the start of it all

Actually, you already got your answer:

  Compute the decryption matrix $D = E^{-1}$

That is, compute the matrix $D$ such that $D$ and $E$, multiplied together using standard matrix multiplication, gives:

$$\begin{bmatrix}d_{00}&d_{01}\\d_{10}&d_{11}\end{bmatrix}\begin{bmatrix}1&x^2 \\x^2&1\end{bmatrix}= \begin{bmatrix}1&0\\0&1\end{bmatrix}$$

This is a standard matrix inversion problem, and all the standard tools used to invert matrices over $\mathbb{R}$ work (and as a bonus, you don't have to worry about numeric stability).  Now, you do have to do your internal computations in $\mathbb{F}_{16}$, but that's pretty easy.


Encrypt with one cipher and decrypt with a different cipher? I recently installed an android app called Secret Space Encryptor and think I found a serious flaw in it.

Let me explain: This app provides a variety of different ciphers to use and I used Threefish 1024 to encrypt a test message with "Your Key" as the key.

I then saved the ciphertext to a text file using the export function in the app. Then I changed the text encryption program in the app to use Blowfish 448 and imported the TF-1024 encrypted message into the app once more.

I then entered the "Your Key" test key and to my total surprise the message successfully decrypted! I encrypted a message with one cipher and then decrypted that same message with a totally different cipher!

Now this should be totally impossible right? If so then is there a deadly flaw in this app?

I've checked out the source code (well, more or less, it's not that well designed, the main crypto class is 1600 lines) and as Richie guessed, the algorithm is stored together with the ciphertext.

Pretty gruesome stuff, but it does do EAX mode for text strings to my surprise. It probably only uses it for text strings originating from the password vault code though.

File encryption is performed in CBC mode. It does (ZIP) compress and stream files using CBC mode. It uses a static IV but this is offset by a random header that is included into the encryption.

This is a homegrown project with little documentation or comments in the code and a  slightly erratic class design.

Thanks go out to Tron to supply us the link to the format defition on the Paranoiaworks website.


Does anyone know why NISTs SHA3 256 output Hash for the 1600 bit file is different to other SHA3 256 output hashes? I have been trying to implement my own SHA3 256 function in python to try and learn and understand how it works. I have been comparing my hashes with an online sha3 tool found here https://emn178.github.io/online-tools/sha3_256.html and the test files on the NIST website found here https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values. I realised that the output hash found in the 1600 bit file found on the NIST file is different from the one on the online tool. I have even used a python sha3 library and the result of the hash is the same as the one on the online tool. Does anyone know why the NIST output hash is different? I know NIST has made some changes to SHA3 padding but I am still unsure.

NIST gave the 1600-bit input as a bit-string, with each byte in LSb first bit order. So 1 1 0 0 0 1 0 1 is A3, not C5 as one would expect.


Calculating 3DES Key Check Value (KCV) I am trying to verify a Triple DES Key Component generated by PC Crypto.
The key portion is:

E6F1081FEA4C402CC192B65DE367EC3E

and the KCV value that should be returned is:

212CF915

In theory, it should be calculated as: encryption of binary 0's with the key portion with 3DES.

I have been trying the following link, but the calculation doesn't work.
http://tripledes.online-domain-tools.com/

I used the following parametrization on the online tool.

Could anyone confirm that the calculation is performed as I mentioned?

Three problems here:

The online tool used expects a 24-byte (48 hex-character) key; thus you should enter E6F1081FEA4C402CC192B65DE367EC3EE6F1081FEA4C402C as the key, duplicating the first 8 bytes; this is the customary way to extend a two-block triple DES key of 16 bytes to a three-block triple DES key of 24 bytes.
You gave 16 bytes (32 hex chars) as input, which is twice as many bytes as required; this doesn't affect the computation of the KCV though.
The KCV value is supposed to be the first 3 bytes (6 hex chars) of the result, not 4 bytes (8 hex chars).

When this is fixed, the KCV 212cf9 is correctly obtained using the tool.

Note: it is a bad idea to use an online tool in order to check a real key, just like it is a bad idea to use an online RNG to generate a real key.


What are the differences between a digital signature, a MAC and a hash? A message may be accompanied with a digital signature, a MAC or a message hash, as a proof of some kind.

Which assurances does each primitive provide to the recipient?

What kind of keys are needed?

These types of cryptographic primitive can be distinguished by the security goals they fulfill (in the simple protocol of "appending to a message"):

Integrity: Can the recipient be confident that the message has not been accidentally modified?
Authentication: Can the recipient be confident that the message originates from the sender?
Non-repudiation: If the recipient passes the message and the proof to a third party, can the third party be confident that the message originated from the sender? (Please note that I am talking about non-repudiation in the cryptographic sense, not in the legal sense.)

Also important is this question:

Keys: Does the primitive require a shared secret key, or public-private keypairs?

I think the short answer is best explained with a table:

Cryptographic primitive | Hash |    MAC    | Digital
Security Goal           |      |           | signature
------------------------+------+-----------+-------------
Integrity               |  Yes |    Yes    |   Yes
Authentication          |  No  |    Yes    |   Yes
Non-repudiation         |  No  |    No     |   Yes
------------------------+------+-----------+-------------
Kind of keys            | none | symmetric | asymmetric
                        |      |    keys   |    keys

Please remember that authentication without confidence in the keys used is useless. For digital signatures, a recipient must be confident that the verification key actually belongs to the sender. For MACs, a recipient must be confident that the shared symmetric key has only been shared with the sender.

The longer answer:

A (unkeyed) hash of the message, if appended to the message itself, only protects against accidental changes to the message (or the hash itself), as an attacker who modifies the message can simply calculate a new hash and use it instead of the original one. So this only gives integrity.

If the hash is transmitted over a different, protected channel, it can also protect the message against modifications. This is sometimes be used with hashes of very big files (like ISO-images), where the hash itself is delivered over HTTPS, while the big file can be transmitted over an insecure channel.

A message authentication code (MAC) (sometimes also known as keyed hash) protects against message forgery by anyone who doesn't know the secret key (shared by sender and receiver).

This means that the receiver can forge any message – thus we have both integrity and authentication (as long as the receiver doesn't have a split personality), but not non-repudiation.

Also an attacker could replay earlier messages authenticated with the same key, so a protocol should take measures against this (e.g. by including message numbers or timestamps). (Also, in case of a two-sided conversation, make sure that either both sides have different keys, or by another way make sure that messages from one side can't sent back by an attacker to this side.)

MACs can be created from unkeyed hashes (e.g. with the HMAC construction), or created directly as MAC algorithms.

A (digital) signature is created with a private key, and verified with the corresponding public key of an asymmetric key-pair. Only the holder of the private key can create this signature, and normally anyone knowing the public key can verify it. Digital signatures don't prevent the replay attack mentioned previously.

There is the special case of designated verifier signature, which only ones with knowledge of another key can verify, but this is not normally meant when saying "signature".

So this provides all of integrity, authentication, and non-repudiation.

Most signature schemes actually are implemented with the help of a hash function. Also, they are usually slower than MACs, and as such used normally only when there is not yet a shared secret, or the non-repudiation property is important.


Public-key cryptosystems without poly-time quantum attacks It's well-known that Shor's algorithm can solve integer factorization, discrete logarithm and discrete log over elliptic curves in cubic time.  This implies that cryptosystems like RSA, ElGamal, and Elliptic Curve Diffie-Hellman (ECDH) are vulnerable to quantum computers.

Are there any existing public-key cryptosystem that are NOT known to have a polynomial-time quantum attack?

This question was inspired by this blog post.

McEliece

NTRU

Multivariate

If you mean "syntactically public key" instead of "implies the existence of secure key agreement",

then there is also hash-based signatures.


JWE between Android/iPhone and backend I'm working on a solution where JWE is needed between an Android app and a backend written in Node.JS, using node-jose. I've been struggling a lot since it seems there is no out of the box compatibility between Android - if you want to use the HW backed keystore - and any node JWE library when it comes to the RSA key, because:

Android supports these ciphers for the HW backed AndroidKeyStore provider. Note, RSA-OAEP-256 (MGF1 SHA-256) is NOT supported; for some reason Android only supports MGF with SHA-1 even for OAEP-256.
node-jose only seems to support OAEP schemes with the same MD for OAEP and the MGF:

RSA OAEP with SHA-1 and no explicit MGF1 (meaning MGF1 SHA-1)
RSA OAEP with SHA-256 and no explicit MGF1 (meaning MGF1 SHA-256)

Nimbus JOSE Java library doesn't support the Android KeyStore out of the box, but I've patched it to use RSA/ECB/OAEPWithSHA-256AndMGF1Padding(SHA-1)
Nimbus JOSE has deprecated RSA-OAEP (SHA-1) in favor of RSA-OAEP (SHA-256)

The incompatibility is surprising to me, you'd think there would be an off-the-shelf solution for implementing JWE between Node.JS and Android. But I'm wondering about RSA OAEP SHA-1. Nimbus JOSE deprecated it, is it discouraged to use it? Has it been proven vulnerable?

Also, in the future, I want to support the iPhone. I don't know much about iOS, but it seems Apple also has an HW protected key store ("Secure Enclave"). However, it only supports EC!

So if one wanted to build a solution where a mobile phone and a backend server uses JWE for encrypted communication, what's my best bet?
My idea is that the mobile app creates a key pair in its hardware-backed Keystore, gives the public key to the backend, and the backend can then create JWEs where the public key is used to encrypt the CEK. But considering Android only supports RSA with some flavors such as RSA OAEP with SHA-256 andMGF1+SHA1, and Apple only supports EC, I guess I'd have to support both RSA and EC on the backend, and if needed patch libraries such as node-jose and node-forge to fit my needs. But perhaps I'm going around this all wrong?

Ref: node-jose issue

node-jose only supports RSA OAEP with SHA-1 and no MGF1 or RSA OAEP with SHA-256 and no MGF1

That's extremely unlikely since OAEP does need to use a Mask Generation Function, and there is only one defined: MGF1. So maybe it doesn't specify it explicitly, but it really must support it to be called OAEP.

  But I'm wondering about RSA OAEP SHA-1. Nimbus JOSE deprecated it, is it discouraged to use it? Has it been proven vulnerable?

No. Best to compare MGF1 with an expanding key derivation function probably. For this kind of use SHA-1 is still secure, even though the relatively small output size doesn't help. It certainly doesn't depend on the collision resistance.

However, I've had plenty of entities asking to deprecate SHA-1 in its entirety. The problem is that it is a huge red flag for auditors, who then have to look if the use of the hash is secure. And, to be honest, many auditors wouldn't know how to qualify if it is secure or not, so they see it as an avoidable risk. Which, to be honest, it probably is.

  But perhaps I'm going around this all wrong?

I don't know, it seems that Apple supports RSA for encryption if I look at the description here.


In the Diffie Hellman Key exchange, why is a value of $a=\frac{p-1}{2}$ a bad choice? In Diffie Hellman key exchange, we have a large prime $p$ and non zero residue class $g \in F_p^x$ with a large order.  An $a$ and $b$ are chosen in secret, and those are used to compute $A \equiv g^a \mod p$ and $B \equiv g^b \mod p$.

Then the two communicating agree on value $g^{ab}$ via $A^b$ and $B^a$.

$a=p-1$ would be a bad choice (by Euler Fermat theorem). My question is why is the value of $a = \frac{p-1}{2}$ a bad choice?

In Diffie-Hellman besides $p$ being prime, if the factorization of $p-1$ comprises at least one big prime $k$ such that $p=2k+1$ (can be also $jk+1$, this is a safe prime). In the worst case if the factorization is composed of computable factors then we can compute $x$ using the direct product of cyclic groups (Pohlig-Hellman).

Normally, if $p$ is prime and $g$ a generator with order $p-1$ then $g^{\frac{(p-1)}{2}} \equiv p-1 \equiv -1 \pmod p$

If $g$ is a generator of the subgroup of prime order $k$, where $k$ is large enough then $g^{\frac{(p-1)}{2}} \equiv g^k \equiv 1 \pmod p$

Both congruences are deterministic as you can see.

Generally, two congruences are related by symmetry, since both have the same square root mod p:

$$g^a \equiv -(g^b) \pmod p \quad \iff b = x-d, \ d = \frac{p-1}{2}$$


Encryption with private key? we normally always encrypt by public key and decrypt with private key.

If i encrypt with private key, then its still secure as normal PKI ?
i mean known-plain-text will not take private key on the risk ? (for example when people know the plain text and signed message with private key, then private key is safe or will compromise?
When we encrypt with the public key then known-plain-text make public key compromise but private key is safe?

Well, first of all, this is not a generic 'public-key' question.  With RSA, it can make sense to talk about 'encrypting with the private key', for most other public key algorithms, there's isn't an obvious interpretation.  For example, with DSA, the public key operation (which is a signature verification) is 'plug the data from the signature, the hash of the data and the public key into a formula; the signature passes of both sides are the same value'.  There's no obvious way to use this type of operation to encrypt something.

Now, in your question, you ask whether encrypting with the RSA private key is secure.  Well, that depends on what you mean by secure; what precisely are you attempting preventing someone from doing?  In one sense, it is not secure at all; anyone who has the public key can decrypt the message.  Since it is generally true that anyone can get the public key, well, this means that this is not at all a secure encryption method.

On the other hand, you might not be assuming that this is a secure encryption method; this might be an attempt to simulate RSA signature generation.  Here, you have to be careful; RSA using padding methods to translate between the message being encrypted/signed into a value to give to the raw RSA function.  The security properties for an encryption padding method are different from the security properties for a signature padding method; in fact, there are real world secure encryption padding methods (for example, RSAES-PKCS1-v1_5 with e=3) that could be insecure if used as a signature padding method.

However, you may simply be asking "would the key be secure"?  In some sense, that is irrelevant; usually, the only reason an attacker wants the keys is that would allow him to perform some operation; if he can perform those operations without the keys (because, for example, of the vulnerabilities mentioned in the above two paragraphs), then he doesn't need the keys.  However, if you are still concerned about the keying data, well, it turns out that RSA is safe; performing RSA operations (even on attacker chosen values) doesn't leak the private key.


Is there any known malleability of scrypt outputs? The scenario is single-use passphrase-based non-interactive message authentication.

The obvious try to do this is to chose a random salt of the appropriate length and send:

concat(workfactor, salt, message,
       mac(scrypt(workfactor, salt, passphrase), message)).

That protocol is as secure as scrypt is a non-malleable key derivation function (with regards of changing of workfactor and salt).

Is there any publicly known malleability of scrypt?
Are there any better protocols for this scenario?

Non-malleability of Scrypt w.r.t. to salt (as well as passphrase) follows from the definition of Scrypt (which simply pass that salt to that input of PBKDF2); the definition of PBKDF2 (which uses the salt followed by a non-malleable encoding of an integer as a massage passed to HMAC_SHA256); the non-malleability of HMAC_SHA256 w.r.t. the message; and perhaps some reasonable assumptions also critical to Scrypt's soundness. Non-malleability w.r.t. to salt and passphrase should be a design goal of any good PBKDF.

Non-malleability of Scrypt w.r.t. workfactor is more difficult to argument, and hard (if possible) to prove, depending on how rigorous the argument needs to be, and how one maps the term workfactor to the three security parameters of Scrypt (number of iterations, amount of RAM used, and allowance for parallelization). In my opinion, no attack better than brute force is feasible: this is an issue of provable security only, and entering the workfactor(s) in the salt would restore that.

Beware that in some protocols, independently of any weakness in Scrypt (or whatever PBKDF is used), it could be necessary that a legitimate party holding the passphrase enforce a minimum workfactor, for fear of being abused into a fast passphrase-checking oracle.

I do not know any established PBKDF improving on Scrypt.


Why do we keep designing new static s boxes? As I understand s box properties, they primarily need high non linearity and low auto correlation.  But most importantly for this question, they're not secret.

There are many questions on this site asking for help in generating them.  And new ciphers always seem to have new s boxes.  Why?  There are proven numerical optimisation techniques such as tree search and hill climbing to optimise a function.  Could we not just devote an hour of a large computer cluster to generate optimum (say) 3, 4, 5, 6, 7 and 8 bit wide s boxes?  Universities have access to such resources.  They could then be published in a book rather like they used to publish random numbers.

Note: By static s box, I mean one of those that isn't related to a key like Blowfish's.

There are simply a long list of properties for S-boxes that are relevant, see for example these questions:

Desirable S-box properties
S-box design criteria and random sboxes

In addition people have been trying to design S-boxes that are fast to implement in hardware or in software or which can be masked efficiently. For example the Midori S-box is designed to be especially energy efficient.

The search space for S-boxes is actually quite big as well; for 4-bit S-boxes (pretty small) there are $16! \approx 2^{44}$ possibilities.

This might be a nice read: Cryptographic Analysis of All 4×4-Bit S-Boxes


How many passwords are possible in this scenario? A password string consists of one or more of the 26 characters A..Z and can be of any length from $1$ to $8$ characters. How many password are possible in this scenario?

As my calculation, it should be  $2^{26}\times8!$, is it correct?

for one 1 char passwords, one can only put $26$ different characters
for one 2 char passwords, one can only put  $26^2$ different characters
for one 3 char passwords, one can only put  $26^3$ different characters
...
for one 8 char passwords, one can only put $26^8$ different characters

In short, think each box can contain how many letters from the given alphabet and multiply the values in the boxes. Finally, sum them.
$$\sum_{i=1}^8 26^i = \frac{26^9-1}{26-1}-1$$
The name of the formula is Sum of Consecutive powers of a number;
$$\sum_{i=0}^n a^i = \dfrac{a^{n+1} -1}{a-1}$$
and $-1$ since $i=0$ is not a case here.

Update : a more general case;
Let assume that you want to build a web application and want to determine the security level of the passwords. Here a calculator;

Assume that the alphabet has $l$ letters,
$m$ numerals, and
$p$ non-alphanumeric.

If we set the passwords to require at least;

$n_m$ numerals
$n_p$ non-alphanumeric,with
passords's length to $$min \geq n_k+n_a \geq 6,\text{and}$$
$max > min$, then

What is the password space, $\mathcal{S}$?
$$ \mathcal{S} =  m^{n_m} + p^{n_p} + \sum_{i=1}^{max - ({n_m} + {n_p})} (l+m+p)^i$$
Under these assumptions, let

$l = 26$

$m = 10$

$p = 20$

$min = 6$

$max=20$

$n_m=2$

$n_p =1$, then we have;
$$ \mathcal{S}_{6:20} =  10^2 + 20 + \sum_{i=1}^{17} (56)^i = 533361663473057950558105648760 $$

$ \mathcal{S}_{6:20}$ has 99 digits in binary form.
if max is;

$6 \text{ then } S = 178928$
$7 \text{ then } S = 10013424$
$8 \text{ then } S = 10013424$
$9 \text{ then } S = 560745200$
$10\text{ then } S = 31401724656$ is 35-bit.

WolframAlpha calculator;
m^{n_m} + p^{n_p} + sum (l+m+p)^i, i=1 to (max - (n_m + n_p))


How can A pass a message to B, while preventing a third party from sniffing infos? $A$ has a message that he wants to send to $B$, without a third party being able to learn the contents of the original message.

$A$ encrypts the message and sends it to a server. The server decrypts the message somehow, and sends it to $B$. This way, no one would know what was the original sender, because the server will send it to the destination.

But if the server encrypts the message again, how will $B$ be able to decrypt the message? If $B$ knows how to decrypt the message, then any third side would also know.

What is the solution?

Server distribute respective private keys to A (PrivateKeyA) and B (PrivateKeyB) and stores their public keys (PublicKeyA and PublicKeyB) within it's database.
Now any of the user (eg A) generates a random session key (K) and encrypts this key with its own private key (PrivateKeyA). Since server has public key of A, it can decrypt the encrypted session key.
Now it encrypts the same session key (K) which it got from A with B's public key and sends it to B. Now since only B knows the corresponding private key, only B can decrypt the encrypted session key to deduce the key K.
Now A and B share a session key, which they can use to safely communicate with each other.

For exchanging session key the the algorithm  uses asymmetric cryptography and for communication it uses symmetric cryptography technique. The only thing to keep in mind is that either user must be capable of generating a good and strong random session key.


Non Linearity of huge Sbox Sboxes provide confusion in cipher. Non Linearity measures the strength of sbox layer. In order to measure non linearity of sbox, a table is computed to measure distances with its affine functions. If the dimensions of sbox are huge say eg 64 bits input to 64 bit output, how to determine it's non linearity as table construction is not computationally possible?

Table construction would require 148 Exabytes of RAM, so it would be hard to store all at once.  This also means that you can't have a predefined S box that you might have developed either to be a random permutation, or used some sort of hill climbing technique to be better than random.  You can however have a computed S box function. So it would not be a simple look up table, but rather the 64 bit output would be calculated piecemeal (byte by byte) based upon the 64 bit input.  As long as the function was bijective and not surjective, you'd have S box behaviour.

So instead of a large table, you'd have a mathematical function.  Without resorting to finite fields, the function could be a simple non cryptographic hash of the 64 bits /8 bytes.  One implementation would be a Pearson hash of the 8 bytes, with a unique 256 byte permutation table for each byte position.  That means you require 2048 bytes of RAM instead. Less than perfect non linearity could be compensated for with additional rounds, as is done in some current lightweight algoriths.

Note.  You'd need a similar function for the permutation layer of your cipher as you wouldn't be able to store that easily either.


Explanation of the EPC Gen2 randomness standard's first rule When we read PRNG requirements of the EPC standard, first rule (page 57 in this link) in the documentation;

  Probability of a single RN16: The probability that any RN16 drawn from
  the RNG has value RN16 = j, for any j, shall be bounded by 0.8/2^16 <
  P(RN16 = j) < 1.25/2^16.

Does that mean if the PRNG generates 2^16 16-bit numbers, each number should occur once? Basically it wants a perfect 16-bit entropy.

But if it is this way, even C#'s cryptographically secure PRNG cannot meet that requirement. So I'm wondering that I interpreted this requirement right.

All is revealed in the last paragraph of that section, repeated below:-

  A cryptographic suite defines RNG requirements and randomness criteria for cryptographic operations. These requirements and criteria may be different, and in particular may be more stringent, than those defined above for inventory and password operations.

Their three randomness tests are an attempt to create a protocol that works in the real world without too much computational effort.  By crude analogy, it's like a children's test for randomness.  You only have 65536 possible choices anyway (assuming the RNG can reach them all), so there's little point in relying on huge computational effort to generate cryptographic strength Tag codes.  An attacker will just brute force them when appropriate tools are developed.

  Basically it wants a perfect 16-bit entropy.

Actually no. On this forum, entropy is defined as unpredictability within a certain system's defined scope.  There's a EPCglobal test that stipulates that sequential values are only 0.025% certain.  That's pretty poor to protect your bank account or nuclear arsenal.  For perfect entropy, the next value should only be predictable with a 0.0015% certainly, irrespective of prior RN16s.   The first rule is just a lax, perhaps pragmatic interpretation. It allows a ~22% bias in the numbers.
 And yes, that means you can have consecutive identical RN16's.  Prolonged consecutive RN16s might be an issue for the specific protocol implementation (I don't know).

  C#'s cryptographically secure PRNG cannot meet that requirement

Unfamiliar with C#, but if it's like a proper *nix language, then the cryptographic generator should be pretty good.  My interpretation of these rules is that they are much less stringent than those required for cryptographic purposes.  Thus C# might very well fail them in the strict technical sense.  It's just that C# is too good for them.  True randomness (opposite of bad randomness) is a slippery beast.  (It might be useful to flesh out your question illustrating how C# fails the tests).

You don't have these three rules in cryptographic RNDs.  Just that each byte is very exactly 1/256ths certain in the long run.


What is the hard problem for this algebraic encryption construct? I would like to know what cryptographic hard problem this reduces to.

Select two large prime numbers $p$ and $q$, and let $N=pq$.  Select a random positive integer $r$.  Compute the encryption of plaintext $M$, ($M<p$) as $$
E_I(M)\ =\ (M\ +\ r\times p)\mod N$$

This is the inner encryption of the Algebra Homomorphic Encryption Scheme:  Xiang, Guangli, Benzhi Yu, and Ping Zhu. "A algorithm of fully homomorphic encryption." Fuzzy Systems and Knowledge Discovery (FSKD), 2012 9th International Conference on. IEEE, 2012.

Update: @poncho points out an easy GCD recovery attack against the inner encryption as stated.  In fairness, the inner encryption was never to stand alone in Xiang's paper.  I believe we can fix this by two changes:

Replace $N$ with $q$, and assume $q>p$ and $q$ is large enough to contain the message and factors of $p$, and
Require $r$ such that $r\times p>q$

Giving: $$E_I(M)\ =\ (M\ +\ r\times p)\mod q$$

Regardless, I'm interested in what the hard problem might be on such a thing.

I am relatively new to this.  I looked at a few hard problems; none of the residuosity or discrete logarithmic problems seem to apply, but I'm hesitant to say that it's integer factorization or RSA in case there is some problem with a stronger assumption that fits.  I want to get a good characterization of the construct so that I may describe it accurately.

Xiang et al. claims that the overall method is derived from ElGamal, and so I believe they feel the reduction is that of ElGamal (Discrete Logarithms), despite having introduced the inner encryption construct.

Thanks for your help!

I want to get a good characterization of the construct so that I may describe it accurately.

I would characterize it as "insecure".

If someone has a ciphertext, and manages to guess the plaintext it corresponds to, then they can compute:

$$\text{gcd}(E_I(M) - M, N)$$

and they'll give then the factor $p$.


Difficulty of finding collisions for two different CRHF Suppose that $\mathcal{H}$ is a family of collision resistant hash functions. Given $h$, which was chosen uniformly at random from $\mathcal{H}$, it is infeasible for a polynomial-time adversary to find collisions for $h$.

Now suppose that $h_1$ and $h_2$ are chosen uniformly at random from $\mathcal{H}$. Is it still infeasible for an adversary to find two elements $x_1$ and $x_2$ such that $$h_1(x_1)=h_2(x_2)?$$

Why?

Thanks!

To expand my comment into an answer. The answer to the question is: No, in general this not true. We will formally show the following:

  If a family of collision resistant hash functions $\mathcal{H}$
   exists, then there exists a family of collision resistant hash
   functions $\mathcal{H}'$ such that for any $h'_i,h'_j \in
 \mathcal{H}'$ it is trivial to find $x_i,x_j$ such that
   $h'_i(x_i)=h'_j(x_j)$.

As mentioned in my comment, what we will do is construct $\mathcal{H}'$ in such a way that $h'_i(i)=0^n$ (where $n$ is the output length of functions in $\mathcal{H}$).
However, we need to be careful in how we do that. A naïve construction of $\mathcal{H}'$ could define for each $h_i \in \mathcal{H}$ a function
$$h_i'(x) := \begin{cases} 0^n & \text{if } x=i\\h_i(x)&\text{otherwise} \end{cases} $$
However, this new family would not necessarily be collision resistant. If for example $\mathcal{H}$ was a family of functions where each function already mapped $0^n$ to $0^n$ we would have introduced a new easily found collision.

So we need to be careful to ensure that any collision in our new function corresponds to a collision in the original function. To do that we define $\mathcal{H}'$ as follows. For each index $i$ we define
$$h'_i(x) := h_i(x)\oplus h_i(i).$$

It is actually easy to see that collision resistance is preserved under this modification.

Let $\mathcal{A}$ be an arbitrary PPT adversary against the collision resistance of $\mathcal{H}'$. We observe that for any $x_1,x_2$ that $\mathcal{A}$ outputs in response to input $i$, it holds that
\begin{align}
&h'_i(x_1) = h'_i(x_2)\\
\iff& h_i(x_1)\oplus h_i(i) = h_i(x_2)\oplus h_i(i)\\
\iff& h_i(x_1) = h_i(x_2)
\end{align}

Therefore it holds that
$$\Pr_i[(x_1,x_2)\gets\mathcal{A}(i):h'_i(x_1) = h'_i(x_2)] = \Pr_i[(x_1,x_2)\gets\mathcal{A}(i):h_i(x_1) = h_i(x_2)]$$
the latter of which is known to be negligible by our premise that $\mathcal{H}$ is collision resistant.

However, it is also easy to see that for any $i,j$ it is trivial to find $x_i,x_j$ such that $h'_i(x_i)=h'_j(x_j)$. An attacker given indices $i,j$ would simply output $i,j$ and since by definition of $\mathcal{H}'$ it holds that

$$h'_i(i) = h_i(i) \oplus h_i(i) = 0^n$$
and
$$h'_j(j) = h_j(j) \oplus h_j(j) = 0^n$$
$\mathcal{A}$ would be succesfull with probability $1$.


Questions about using PRF to construct PRG Let F be a secure pseudorandom function with 128-bit key and 256-bit block length. Which are the following functions G are secure pseudorandom generators? (Select all that apply.)
A.  $G(x)=F_x(0...0)$, where $x$ is a $128$-bit input.
B. $G(x)=F_x(0...0)|| F_x(0...0)$, where $x$ is a $128$-bit input.
C. $G(x)=F_x(0...0)||F_x(1...1)$, where $x$ is a $128$-bit input.
D. $G(x)=F_{0...0}(x)|| F_{1...1}(x)$, where $x$ is a $256$-bit input.
The answer our teacher gave is $A,D$. But I don't understand. And Why C is wrong?

We don't directly answer homework questions, but will give hints.
An attacker is assumed to have control over all non-secret inputs. The key is secret, the block is not. This answer has a good definition of a PRG: in simple terms a PRG is a function that takes a fixed-length secret input seed bitstring, and outputs a longer bitstring which cannot be distinguished from a random bitstring with non-negligible probability.

A. $G(x)=F_{x}(0...0)$, where x is a 128-bit input key.

Does the attacker control any of the inputs? Can the attacker distinguish the output from that of a random function with non-negligible probability (ie, are there any observable patterns in the output)? Is the output longer than the input?
The only input variable is a secret key. No extra patterns get added to the output. How long is the output?

B. $G(x)=F_{x}(0...0)||F_{x}(0...0)$, where x is a 128-bit input key.

Same questions.
The only input variable is a secret key. The output repeats some sequence twice. How long is the output?

C. $G(x)=F_{x}(0...0)||F_{x}(1...1)$, where x is a 128-bit input key.

Same questions.
The only input variable is a secret key. Does the output have any extra patterns? How long is the output?

D. $G(x)=F_{0...0}(x)||F_{1...1}(x)$, where x is a 256-bit input data block.

Same questions.
The only input variable is a public data block. Does the output have any extra patterns? How long is the output?
There's a missing option that continues the pattern: E. $G(x)=F_{0...0}(x)||F_{0...0}(x)$, where x is a public 256-bit data block.
If you can answer the A-D, E should be trivial.


Terminology for parties in authentication protocols Is there a common terminology to designate parties in authentication protocols?

For example, we typically use prover and verifier to designate parties with zero-knowledge proofs.

Yes, it seems so: User and Principal/Party

In Protocols For Authentication And Key Establishment, published this year and written by
Colin Boyd, Anish Mathuria, and Douglas Stebila, it says this in Section 1.2.2:

  In the following,
  we use the term user to mean an entity who will use the session key for subsequent
  communication. We also use the term principal or party to mean an entity who will
  engage in the protocol. For example, in a protocol which uses a key server (often
  called an authentication server) there are users who will obtain the session key while
  the server is a principal but not a user.

These terms occur throughout the the international standard ISO/IEC documentation. Just one example is ISO/IEC 11770-2 Server-Based Protocols, in the section about key establishment mechanisms.


How RSA is implemented by authentication protocols? I am a beginner in cryptography, i recently learned about RSA algorithm : In short, my understanding for this is :
Sender needs receiver's public key to encrypt the message to a cipher so that only receiver can decrypt the cipher text to original message and vice versa.

When i try to understand the implementation in network and authentication i find this little confusing in following ways:

Sender and receiver both generate their own pair of private-public key.
Sender encrypts the message with private key and sends his/her public key and the receiver decrypts by using sender's public key and vice versa.
Now how this is RSA or AES? Because the message should be encrypted by receiver's public key so that receiver can only decrypt it. But here sender's public key is sent and receiver could decrypt the message by that public key. HOW??
If this is true, then any one in the network who can get cipher and public key can decrypt the message, because the cipher is meant to be decrypted by the same public key. RIGHT??

For example :
I was going through JWT (Json Web Token) implementation, here :

Server app signs the token with server's private key but third party app can verify the token and retrieve data by the server's public key.

I know i am missing something here, but do not know what.

Sender encrypts the message with private key and sends his/her public key and the receiver decrypts by using sender's public key and vice versa.

No, you cannot encrypt (for confidentiality) using a private key; anybody with the public key can decrypt after all.

  Now how this is RSA or AES? Because the message should be encrypted by receiver's public key so that receiver can only decrypt it.

What you are looking for is signature generation, which is different from encryption. For RSA it uses a cryptographic hash and different padding mechanisms. The "only" thing that is similar is that it uses modular exponentiation. Both encryption and signature generation depends on the RSA problem for security, and the RSA primitive is nothing but modular exponentiation (after a rather complex key pair generation).

The unfortunate thing is that because encryption and signature generation is so similar, the authors of PKCS#1 called it "encryption of the hash value using the private key". They somewhat rectified that mistake in v2.0 of their specification, but then it was too late.

AES doesn't take any part in signature generation. It is mainly used for encryption, including hybrid crypto-systems where RSA and AES are often combined to encrypt larger messages. It is not used or designed for hashing.

  But here sender's public key is sent and receiver could decrypt the message by that public key.

Well, if you perform modular exponentiation with the public key then you get the value that was input to the modular exponentiation with the private key. This contains the hash value (in some form). This is the base principle behind RSA signature generation and verification - the padding is just there to provide additional protection against attacks.

There is another misunderstanding here: the public key cannot just be "send", it must be trusted by the party that is doing the verification. Otherwise you may get send the wrong key, and you would perform verification of a signature that could be generated by anybody.

Establishing trust in a public key is the reason behind public key infrastructures. The certificate store in your browser is part of a PKI called PKIX as it relies on X.509 encoded certificates and the technology surrounding it. PGP's "web-of-trust" is another, less hierarchical PKI.

  If this is true, then any one in the network who can get cipher and public key can decrypt the message, because the cipher is meant to be decrypted by the same public key.

Correct, but we don't care. Because keeping the message confidential is not the goal. It is about proving that you have access to the private key so you can sign some session specific data. It needs to be session specific, otherwise an adversary can use an old signature to authenticate (a so called replay attack).


Does Cramer-Shoup allow re-randomization? Is it possible to re-randomize a ciphertext with the Cramer-Shoup System? I have some Cramer-Shoup ciphertexts and i want to re-randomize them, so they look different and are unlinkable to there previous form, but still can be decrypted with the original secret-key. Is this possible?

And if it is, would it still be possible using the Camenisch-Shoup System, which calculates a Proof, so someone knows that the "real original value" is encrypted, without decrypting the ciphertext?
I hope this is written clear enough
Thank you.

@hakoja correctly points out that what you are asking for is not compatible with CCA security (the security property that Cramer-Shoup satisfies). More specifically, you seem to be looking for a rerandomizable, RCCA-secure encryption scheme. These two properties mean:

Rerandomizable: Given an encryption of an unknown $m$, there is a way to generate fresh samples from $\textsf{Enc}(k,m)$.
Replayable CCA (RCCA): The scheme is non-malleable except for the possibility of modifying a ciphertext $c$ into another ciphertext $c'$ where $\textsf{Dec}(k,c) = \textsf{Dec}(k,c')$. Basically, the scheme is malleable only in ways that preserve the plaintext; otherwise it is non-malleable.

Rerandomizable RCCA means that the randomization feature is the "only malleability" of the scheme. These are not too hard to achieve together, but they become non-trivial when you include another requirement:

Unlinkability: Given $c = \textsf{Enc}(k,m)$ for an unknown $m$, it is hard to tell whether some other $c'$ is an independent encryption of $m$ or a rerandomization of $c$. In order to make sense, this property should hold even in the presence of chosen-ciphertext attacks (i.e., against attackers that have access to the decryption function), which makes it difficult. It often means that the rerandomization procedure must refresh all the randomness in a ciphertext.

In the paper below, we were the first to construct a rerandomizable RCCA scheme:

  Prabhakaran & Rosulek: Rerandomizable RCCA Encryption, CRYPTO 2007

The scheme is about 5-6x more expensive than Cramer-Shoup, and it relies on DDH holding in some groups with related order. There is a later followup work that gives different constructions of rerandomizable RCCA from pairing-based groups:

  Chase, Kohlweis, Lysyanskaya, Meikeljohn: Malleable Proof Systems and Applications. Eurocrypt 2012.


Should Ed25519 signature verification check the order and canonicity of its inputs? Studying different implementations of Ed25519 I see that some of them check the order and canonicity of input public key and signature and some other not. Why this difference? Are these tests relevant in the sense that points specially chosen points to be non-canonical or have an small order reduce the strength of the algorithm against forgery or tampering?

Public key: Generally, no.  If a legitimate signer is trying to pull a fast one on you, they already have the power to sign messages that you will accept.  So why would they bother feeding you a point that is not generated by the standard base point, when they could just feed you bogus signed messages?

Signature: Generally, no.  The verification equation for a signature $(R, s)$ under public key $A$ on a message $m$, where $A$ is a curve point, $R$ is a curve point, $s$ is a scalar, and $m$ is a bit string, is $$[8 s] B = [8] R + [8 H(R, A, m)] A.$$  If $A$ is an 8-torsion point, then the legitimate signer is already pulling a fast one on you—$(\mathcal O, \ell)$ is a valid signature on any message $m$.  If two points $R$ and $R'$ differ by an 8-torsion point, i.e. if $[8](R - R') = \mathcal O$, then they will both make valid signatures—meaning if a forger could forge one they could forge the other.  But a forger who doesn't know one signature to begin with still can't find one in the first place.

I add the ‘generally’ qualifier because maybe you rely on some properties that signature schemes are not generally expected to provide, such as uniqueness of signatures—as noted, it is easy given a signature $(R, s)$ under $A$ on a message $m$ to find another signature $(R', s') \ne (R, s)$ under $A$ on $m$: pick $s' = s$ and $R' = R + Q$, where $Q$ is any 8-torsion point other than the identity $\mathcal O$.  The assumption of signature uniqueness caused Monero some trouble last year, but most applications do not rely on this.


how does AES GCM in SSH work? I was looking at RFC5647: AES Galois Counter Mode for the Secure Shell Transport Layer Protocol and had some questions about section 7.1 "IV and Counter Management". Here's that section:

7.  Processing Binary Packets in AES-GCM Secure Shell

7.1.  IV and Counter Management

   With AES-GCM, the 12-octet IV is broken into two fields: a 4-octet
   fixed field and an 8-octet invocation counter field.  The invocation
   field is treated as a 64-bit integer and is incremented after each
   invocation of AES-GCM to process a binary packet.

         uint32  fixed;                  // 4 octets
         uint64  invocation_counter;     // 8 octets

           Figure 3: Structure of an SSH AES-GCM Nonce

   AES-GCM produces a keystream in blocks of 16-octets that is used to
   encrypt the plaintext.  This keystream is produced by encrypting the
   following 16-octet data structure:

         uint32  fixed;                  // 4 octets
         uint64  invocation_counter;     // 8 octets
         uint32  block_counter;          // 4 octets

           Figure 4: Structure of an AES Input for SSH AES-GCM

   The block_counter is initially set to one (1) and incremented as each
   block of key is produced.

   The reader is reminded that SSH requires that the data to be
   encrypted MUST be padded out to a multiple of the block size
   (16-octets for AES-GCM).

So let's say you invoke AES GCM twice and that the invocation counter is 0 (for simplicity sake). The first invocation encrypts two blocks and the second invocation encrypts one. What would be the source material for the encrypted keystream the second invocation?

For the first invocation, first block, it'd be this:

     uint32  fixed;
     uint64  0;
     uint32  1;

For the first invocation, second block, it'd be this:

     uint32  fixed;
     uint64  0;
     uint32  2;

For the second invocation, first (only) block, does the block_counter advance, as well, or does it reset? Here's what it'd be in the case of the former:

     uint32  fixed;
     uint64  1;
     uint32  3;

Here's what it'd be in the case of the latter:

     uint32  fixed;
     uint64  1;
     uint32  0;

eg. is the block_counter reset or incremented when the invocation_counter incremented?

Also, unless I'm mistaken, this approach breaks with tradition for SSH encryption in that encrypt(S1) || encrypt(S2) == encrypt(S1 || S2) (where || is the concatenation operation). That's how pretty much how it works with every other symmetric cipher for SSH but not this one.

The CTR-IV either must be random or regularly incremented in a way that the IV never repeats again. If there is a repetition then the encryption will be insecure.

In rfc5647, it is the second way; regularly incremented.

invocation_counter is incremented per package. Section 7.1;

  The invocation field is treated as a 64-bit integer and is incremented after each invocation of AES-GCM to process a binary packet.

block_counter is incremented per AES encryption within the package. It must be initialized to 1 for per package, otherwise, an overflow will occur and therefore the IV's cannot be unique. Section 7.1;

  The block_counter is initially set to one (1) and incremented as each    block of key is produced.

The 4-octet block counter matches with the size of the package that is defined in section 5.2 as;

uint32    packet_length;  // 0 <= packet_length < 2^32

Thus, this counter can be incremented for all encrypted blocks within one package. For a new package the set to 1 (that is your latter case).

For the second part, this can happen if ECB mode is used and the data sizes are multiple of the block cipher. Even in this case, a padding scheme must be applied. that will prevent your equation.


Feistel cipher key generation and round function algorithms I'm getting confused of what is the actual structure of the key generation and the round function algorithms that Feistel cipher uses. I have been reading many resources about block cipher. All resources starts talking about Feistel cipher, but non of them explains how the key generation and the round function work. They all suddenly jump to explain The DES method. I know perfectly how DES works,and also know that  DES is a form of Feistel cipher with specific features which are:

64-bits Key
64-bits Plain text
16 Rounds

So, are the key generation and the round function of Feistel cipher same as DES cipher? if yes, are there another key generation and round function algorithms else the one of DES?. Sorry for the many questions, but I really confused. Thanks in advance.

In the best maths I can manage, Feistel ≠ DES but rather DES ∈ Feistel.  This is important as that's what's confusing you.  It's just that DES is extremely prominent in the literature so articles are drawn towards it.  The following is two  Feistel rounds (ostensibly just a single round as they have to be in LH and RH pairs):-

This is also important in that this is the super set.  And being so, there is no particular architecture for either the function or the key schedule that generates the round keys.  DES architecture is just what the designers thought up to create it.  Similarly, Blowfish ∈ Feistel, but you can come up with our own function and key schedule.  I'm just a country boy and not a cryptographer, but as I understand it the overall security of a Feistel network will be proportional to the security of the key schedule times the security of function.  Approximately, but you get the idea.  It is possible to use anything from a strong hash function to simple compression techniques for function  This will directly affect the security requirements for the key schedule.

It is interesting to note that whilst there are proven architectures for Feistel compression functions (and indeed native block ciphers like substitution and permutation), there are no equivalent standardised architectures for a key schedule.  You can have anything, ranging from Blowfish's computationally expensive method, through AES' to the dodgy striping technique of RC4.  The basic requirement of the key schedule (even more important than security) is that the key can be repetitively slotted into the main architecture at the correct bit width.  Otherwise, it won't even begin to work.

There are of course certain fundamental requirements for both, and these are too extensive to list here.  Now that you know the nature of these two fundamental components, you can do your own research.  Look at things like:-

Are there any specific requirements for the function FF in a Feistel cipher?

Questions about key schedules

Implementation detail of Feistel networks (featuring Blowfish)

So I'll end as I started, Feistel ≠ DES but rather DES ∈ Feistel.


RSA Proof - Is Z(n) closed under multiplication In RSA proof it can be proved that $\mathbb{Z}^*_n$ is closed under multiplication. Can it be also proved that $\mathbb{Z}_n$ is closed under multiplication? If yes, then how?

$Z_n=\{0,\ldots,n-1\}$ is not a multiplicative group (I assume that this is what you mean by closed under multiplication in this context, see below) because it contains the zero (this element is not invertible) and furthermore if $n$ is not prime, all elements that are not co-prime to $n$ also have no multiplicative inverse. $Z_n^*$ are the elements from $1$ to $n-1$ that are co-prime to $n$ and thus all invertible and thus this set forms a group under multiplication (modulo $n$).

To expand on the "closed under multiplication": The set $\{0,\ldots,n-1\}$ is indeed closed under multiplication modulo $n$ meaning that whenever you multiply two elements modulo $n$ the result will be in this set. However, this is not sufficient to form a multiplicative group (you require an identity, inverses and to show the associativity of the group law).


When to use Argon2i vs Argon2d vs Argon2id? I've read the manual, and multiple articles / StackExchange posts about this topic, but still can't decide which implementation of Argon2 is best for my use case.

I want to securely encrypt passwords in a database in an unshared environment.
After first pass of the docs (pun-intended) it sounded like Argon2i is recommended in this case, but I feel like it's more likely for someone to gain access to the database directly and try to execute a GPU/ASIC/FPGA based attack to decrypt the data than someone gaining access to the network and attempting a side-channel attack.

I would like to prevent side-channel attacks if possible too, so that sounds like Argon2id is the way to go, but my understanding is the i-portion of the implementation only does one pass. Does the one pass really offer much protection against side-channel attacks (I read 3+ or even 10+ passes are needed to really secure Argon2i) and is there a way to increase the number of passes for the i-portion before the d-portion kicks in?

If Argon2id is the implementation for my use-case, but I can't increase the number of passes for the i-portion, would it make sense to effectively create my own "Argon2id" by implementing the Argon2i algorithm first, and then running the output through the Argon2d algorithm after?

If you are unsure, then always choose Argon2id. Only choose Argon2d if you need maximum security at the expense of side-channel risk, and only choose Argon2i if side-channel attacks are the primary threat.

The number of passes just increases resistance to time-memory tradeoff attacks (TMTO). What you are probably remembering is that Argon2i is more vulnerable to TMTO attacks, and thus needs more passes to obtain the equivalent level of security. Argon2id uses the Argon2i pass to resist side-channel attacks, and the subsequent Argon2d passes to make up for TMTO resistance that the first pass lacks.

If an attacker performs a perfect side-channel attack and breaks the Argon2d portion, then they will still need to perform a very extensive TMTO attack to break the Argon2i passes. Compare this with pure Argon2d, where a successful side-channel attack completely negates its memory hardness. In other words, a side-channel attack against Argon2id reduces its security to one-pass Argon2i.

Note that some of the more severe TMTO attacks against Argon2i have actually been fixed.


NP complete problems related to permutations of binary vectors or block ciphers Recently, T.Gowers wrote a blog entry called "How not to prove that P is not equal to NP" about the Razborov/Rudich Natural Proofs paper. He has a construction where he talks about compositions of 3-bit scramblers along with a paper on the subject. Boaz Barak replied to that post with the following comment:

  Some other intuition that these scramblers might be hard to distinguish from random is that they seem somewhat related to the designs of block ciphers, and these are actually conjectured by cryptographers to be indistinguishable from random. (And cryptanalysts spend significant time trying to attack these conjectures.)

I'm wondering:

  Are there any NP complete problems related to permuting bit vectors or block cipher constructions?

In a strict sense, no.  NP is about worst-case hardness.  Cryptography requires average-case hardness.  $P \ne NP$ implies the existence of problems that are hard in the worst-case (the worst-case running time is super-polynomial) but says nothing about average-case hardness.

For block ciphers, we need average-case hardness.  Therefore, there are good reasons to expect that $P\ne NP$ won't be enough.

(There are other reasons to think that $P\ne NP$ is not enough -- see, e.g., Impagliazzo's many worlds of cryptography -- but I'm trying to keep it simple for you.)

In a loose sense, you might be able to find some loose relationship, e.g., where someone builds a block cipher whose security they claim is "based" upon the NP-completeness of some problem.  But that kind of claim is on very shaky ground.  It's very unlikely they will have proven a theorem that says "if $P\ne NP$, then my block cipher is secure".  Instead, they will have some handwavy argument about how the problem is "related", and it'll all be just a bit sketchy.

The blog post you mention actually describes a relationship that goes in the opposite way: if secure ciphers exist, then a large class of natural ways of trying to prove $P\ne NP$ are doomed to fail.  That's a pretty nifty result.


RC4 , Is it possible to find the key if we know the plaintext and ciphertext? Is it possible to find the key if we know the plaintext and ciphertext with RC4. How should I write the algorithm?

No, to the best of our knowledge, it is not possible, apart from a brute force search over all possible keys.  RC4 has known cryptographical weaknesses; however, none of them are of much help in recovering the key, given a plaintext/ciphertext pair.

There are backtracking approaches that might take circa $2^{700}$ effort independent of the key size; however that is impractically huge (and unless the key is huge, a brute force search is still simpler)

On the other hand, if you have two ciphertexts encrypted with the same RC4 key, and you know the plaintext for one of the ciphertexts, it's easy to recover the other plaintext.  All you need to do is compute the exclusive-or of the two ciphertexts, and the known plaintext -- the result will be the unknown plaintext.

This works because RC4 takes the key, and using that, generates a long string of bytes (the keystream).  RC4 then takes the keystream, and exclusive-or's that with the plaintext, generating the ciphertext.  That is, if $P_i$ is byte $i$ of the plaintext, and $C_i$ is byte $i$ of the ciphertext, and $RC4_i(key)$ is byte $i$ of the keystream generated by the key, then:

$$C_i = P_i \oplus RC4_i(key)$$

If we have a second plaintext $P'$ and ciphertext $C'$ that is encrypted with the same key, we then have:

$$C'_i = P'_i \oplus RC4_i(key)$$

Combining them, we have:

$$P_i = P'_i \oplus C_i \oplus C'_i$$

Now, we can recover the values of $RC4_i(key)$, however there's no known way to recover $key$ from that.  However, if all you want to know is the plaintext $P$, you don't need the key.

Of course, if $P$ (the unknown plaintext) is longer than $P'$ (the known plaintext), this trick will reveal only the first part of $P$.

In addition, even if you don't know the value of $P'$, a similar trick will allow you to compute be value of $P \oplus P'$ - depending on what the plaintext is, that is often sufficient to allow an attacker to deduce the original values of $P, P'$.  Hence, it is always a mistake to RC4 encrypt two different things with the exact same key.


Practical sources of entropy on an Android device? What Android API's can be used a practical sources of entropy ?

Given the requirement of sourcing entropy on the phone for purposes of seeding a PRNG, what are good options ?

Edit:

I have a hard external requirement to periodically supplement the entropy of the RNG, which in the case of SecureRandom, I will do by calling setSeed and passing in the new entropy.

The Android docs for setSeed state:  The given seed supplements, rather than replaces, the existing seed. Thus, repeated calls are guaranteed never to reduce randomness..

As a result, I'm pretty confident that this is the safe and correct way to supplement the entropy of the RNG, but I need guidance as to appropriate on-device sources of entropy.

I have a FIPS compliant HSM on the server side that will contribute, but I need a safe source of additional entropy on the mobile device side.

Recommended options include the lower-order bits of random chunks of memory and phone sensors, and I would appreciate comment in this regard.

Just use SecureRandom and let the OS take care of it.


Suitable Symmetric Algorithm for Encryption Please, I would like to encrypt word not more than 5 letters such as (GO, HI, APPLE, EYES) and my key length just (40 bits only), please I am looking for a suitable symmetric algorithm that it can be lightweight, fast as well as less processing required so it can suit my mechanism?

Please any suggestion and sorry for my weak English ):

Is there any particular reason to use a key length of just 40 bits? Because it is vulnerable to brute-force attacks. To have a reasonable strength, the minimum reasonable key length nowadays is 128 bit (source).

If you don't care about this stuff, you may use one of the following: DES-40, RC2, RC5, Blowfish. These ciphers support a key length of 40 bits, as you require. Anyway, any of these ciphers always has block size different from 5 bytes, which you are probably interested into. I'm not aware of any cipher with a block size of 5-byte/40-bit.
The alternative would be to use a stream cipher that supports a key length of 40 bits, such as RC4 (you can find many more here).


How many rounds of encryption is ideal? I am a newbie to the cryptography world. I am working on a custom algorithm that encrypts the data multiple times and results in a cipher text. It uses a different key in each round to encrypt it. I researched a lot but couldn't find any answer to this question. What do you think is the ideal number for the rounds of encryption when the keys are different in each iteration? Could you show me some math?

Alex

How many rounds cannot really be answered as it depends on the design of a (block) cipher. As many as required to withstand attacks found by crypt-analysis, plus quite few more in case the attacks are enhanced is the best we can do.
AES-128 has a mere 10 rounds, but those rounds are rather complex. Threefish has a less complex inner structure, but uses 72 rounds for the 256 bit version. There are attacks on Threefish that break 53 of 72 rounds. If the rounds could be compromised that easily for AES then it would be utterly broken. Fortunately the best known attack against AES-128 covers 8 rounds out of 10 - and because it is a key distinguishing attack it doesn't give all that much power to an attacker either.
So for your own cipher you'll have to try to find out how well it withstands all known attacks. This is very  hard thing to do and it is unlikely that you will succeed without help. This is one of the reasons why it is hard to design a cipher. Another is to avoid meet-in-the-middle attacks between the rounds of the cipher.


Is there an existing authorative definition of the cryptographic term 'pepper' I can attempt to define the term 'pepper' as:

  In cryptography, a pepper is a something that is added to another
  value (for example a password) prior to a the value being hashed using
  a cryptographic hash function. A pepper can be added to a password in
  addition to a salt value. A pepper performs a similar role to a salt,
  however whereas a salt is commonly stored alongside the value being
  hashed, for something to be defined as a pepper, it should meet one of
  the following criteria that define it a more carefully hidden 'secret'
  than the salt value:

  The pepper is held separately from the value to be hashed
  The pepper is randomly generated for each value to be hashed (within a limited
  set of values), and is never stored. When data is tested against a
  hashed value for a match, this is done by iterating through the set of
  values valid for the pepper, and each one in turn is added to the data
  to be tested (usually by suffixing it to the data), before the
  cryptographic hash function is run on the combined value.

Is there a resource that can verify this as an authorative meaning of the term or otherwise? The articles I'm seeing on Goole aren't very authorative on the meaning of the term and are mutually contradictory in cases, so I'm deriving the definition above based on what's seemingly common in the software development community's understanding of the term 'pepper'.

I have found one source that claims to have invented the word "pepper".
-- But this doesn't mean that they were the first or the only inventors. I guess it may have been invented and reinvented several times.
1999 Paper
Kedem, G., & Ishihara, Y. (1999, August 23-26). Brute Force Attack on UNIX
Passwords with SIMD Computer. Paper presented at the 8th USENIX Security
Symposium, Washington, DC.
They invent "pepper" on page 6 like this: (line breaks added for readability)

The main idea is to add random bits to the password encryption, similar to the “salt” bits that are currently used to protect passwords against dictionary attacks.
We call the new bits: “pepper” bits. Unlike the “salt” bits that are saved with the encrypted password, the pepper bits are used to encrypt the password, but are never saved.

But I think there are likely to be many different definitions of the term "pepper", simply because people know what "salt" is and like to extend analogies.
I don't think K&I's 1999 definition ever really caught on. To me at least, "pepper" is a cryptographic secret, that is stored but stored somewhere else than the salt.


Sophie Germain primes and safe primes I am trying to find a list or table of safe prime  numbers i.e. the ones that are based on the Sophie Germain primes i.e. $N = 2p + 1$ where $p$ is also prime.

All I found till now is this database.
However the problem with that database is that all Sophie Germain primes in this database have at least 1000 digits. So, is out there any database that has the Sophie Germain primes  including the one that are less then 1000 digits long?

I am looking for Sophie Germain primes that will allow me to calculate safe prime numbers that are 512, 768, 1024, 2048, 4096  bit long.

A Sophie Germain prime is a prime $p$ such that $2p+1$ is prime (that later prime is deemed a safe prime). For small examples, see A005384 in the OEIS.

A random integer $n$ has odds commensurate to $1/\log(n)^2$ to be a Sophie Germain prime. Therefore, there's in the order of $2^{495}$ Sophie Germain primes of 511 bits, way too much to enumerate them, much less store them in a database.

In order to find a Sophie Germain prime that will allow to calculate safe prime of $k=$512, 768, 1024, 2048, 4096 bits, one can simply repeatedly find a random prime $p$ of $k-1$ bits, until $2p+1$ is prime (or repeatedly find a random $k$-bit prime $p$, until $(p-1)/2$ is prime); the smallest of the two related primes exhibited is the Sophie Germain prime, the other is the safe prime.

A large speedup is possible by sieving with small primes, noticing that $p$ and $2p+1$ being large primes implies $p$ odd; $p\bmod3=2$; $p\bmod5\in\{1,3,4\}$; and more generally $p\bmod q\not\in\{0,(q-1)/2\}$ for any small odd prime $q$.

For cryptographic applications, one can use the Miller-Rabin primality test.


Why is it better to have the private key as the multiplicative inverse mod phi(n) in RSA? I'm studying the RSA algorithm and the theory says to select $d$ to be the multiplicative inverse of.

$$
e \mod \phi(n)
$$

If we take this approach I know that it is important that $e$ and  $\phi(n)$ are coprime.

Why is this "better" as opposed to say the following equation where $e$ is still selected as a coprime to $\phi(n)$:

$$
 d = \frac{\phi(n) + 1}{e}
$$

I would like to have a deep explanation. I do not have formal math training, so any links to help understand the answer is very much appreciated.

In the standarized RSA algorithm the private key $d$ is calculated computing the modular multiplicative inverse with the Extended Euclidean GCD that satisfies:

$1\equiv e \cdot d\pmod {\varphi(p \cdot q})$

Notice that modular multiplicative inverse can be expressed as:

$$d=\frac{\varphi(p\cdot q)\cdot k + 1}{e}$$

for some $k$ multiple of $\varphi$($p\cdot q$). We know that $e$ is 17 bits (65537) so $k$ will be small, thus computing $d$ with this method would be realizable. You have to know the factorization of the semiprime for computing $\varphi(p \cdot q)$.

Mathematically other ways for computing the private key exist, such as the Euler Criterion.

For calculating the modular multiplicative inverse we would have:

$d\equiv e^{\varphi(\varphi(p \cdot q))-1}\pmod {\varphi(p \cdot q})$

As you can see we would need to have the factorization of $\varphi(p\cdot q)$, so we cannot deal with big semiprime modulus. Concretely we need the factors of $(p-1)$ and $(q-1)$ in order to compute $\varphi(p-1) \cdot \varphi(q-1)$


Is AES-256 weaker than 192 and 128 bit versions? From a paper via Schneier on Security's Another AES Attack (emphasis mine):

In the case of AES-128, there is no known attack which is faster than the 2128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2176 and 2119 time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems.
In this paper we describe several attacks which can break with practical complexity variants of AES-256 whose number of rounds are comparable to that of AES-128.

Is the implication here that AES-192 is stronger than AES-256? If so, in simple terms, how is that possible?

The attack exploits the fact that the key schedule for 256-bit version is pretty lousy -- something we pointed out in our 2000 paper -- but doesn't extend to AES with a 128-bit key.

Again, in simple terms, what does that mean?
In practice, does this mean I should drop AES-256 in favor of its 128-bit counterpart, like Schneier recommends in the comments?

That being said, the key schedule for AES-256 is very poor. I would recommend that people use AES-128 and not AES-256.

AES is an algorithm which is split into several internal rounds, and each round needs a specific 128-bit subkey (and an extra subkey is needed at the end). In an ideal world, the 11/13/15 subkeys would be generated from a strong, cryptographically secure PRNG, itself seeded with "the" key.

However, this world is not ideal, and the subkeys are generated through a process called the key schedule, which is very fast but not a decent PRNG at all; it is meant to offer sufficient security in the very specific context of producing subkeys for the AES only. The key schedule of AES was already known to be somewhat weak in some ways, allowing some exploitable structure to leak from one subkey to another, and this means related-key attacks.

Related-key attacks are not a problem when the encryption algorithm is used for encryption, because they work only when the victim uses several distinct keys, such that the differences (bitwise XOR) between the keys are known to the attacker and follow a very definite pattern. This is not the kind of thing which often occurs in protocols where AES is used; correspondingly, resistance to related-key attacks was not a design criterion for the AES competition. Related-key attacks can be troublesome when we try to reuse the block cipher as a building block for something else, e.g. a hash function. In the formal land of academic cryptanalysis, related-key attacks still count as worthwhile results, despite their lack of applicability to most practical scenarios.

The key schedules for AES-128, AES-192 and AES-256 are necessarily distinct from each other, since they must work over master keys of distinct sizes and produce distinct numbers of subkeys. It turns out that the version of the key schedule for AES-128 seems quite stronger than the key schedule for AES-256 when considering resistance to related-key attacks. It is actually quite logical: to build a related-key attack, the cryptographer must have some fine control over the subkeys, preferably as independently from each other as possible. It seems natural that the longer the source master key, the more control over subkeys the cryptanalyst gets -- because the related-key attack model is a model where the attacker can somehow "choose" the keys (or at least the differences between the keys). In the extreme case of a 1408-bit master key which would simply be split into eleven 128-bit keys, the cryptanalyst would have all the independent control he could wish for. Therefore, an academic weakness relatively to related-key attacks should, generically, increase with the key size.

The apparent paradox of the decrease in academic security when the key size increases highlights the contrived nature of the related-key attack model.


PRF based on the GGM construction What's the differences between the concepts “pseudorandom generator” and “pseudorandom number generator”?

In fact, I want to implement a pseudorandom function based on GGM's construction at http://crypto.cs.uiuc.edu/wiki/index.php/GGM_PRF, but I need to get a doubling length PRG first. I cannot find any effective way to do this.

Can anybody help me or give me another way to implement a pseudorandom function?

A pseudorandom generator is far more specific.

A pseudorandom number generator can just be statistical and/or produce an

endless stream of output and/or take extra entropy as input while it's running.

This RFC gives a way to implement a pseudorandom function.

In fact, if you hadn't specified that you wanted a PRG to implement a PRF, then

I would've just suggested $\;\;\; x \: \mapsto \: \operatorname{HMAC}\hspace{.02 in}(x\hspace{.02 in},\hspace{-0.03 in}0) \: || \hspace{.02 in} \operatorname{HMAC}\hspace{.02 in}(x\hspace{.02 in},\hspace{-0.04 in}1) \;\;\;$ as the PRG.


Soundness of Trevisan’s Extractor Against Quantum Side Information I wonder how sound Trevisan's extractor can be against quantum side information. I checked many papers. And all of these papers were aiming to explain how sound Trevisan's Extractor is against quantum side information but they all have the same information; the papers include:

what is an extractor?

what is a strong extractor?

what is the trevisan extractor?

some entropy explanations(they are the same as for other extractor types)

and after that papers finish without explaining the reason for soundness against quantum side information
Can someone explain this to me briefly?
Best regards

In quantum key distribution communicators can bound the amount of information (quantum side channel entropy) that an eavesdropper can obtain about the transmitted key based on the fidelity of the transmissions. If an $n$-bit key has been transmitted and at most $n-m$ bits of information are available to an eavesdropper then a strong extractor (such as the Trevisan construction) can then used to produce an $m$-bit key about which the eavesdropper has essentially no information and which is therefore ideally suited as strong cryptographic key. This process is called privacy amplification by quantum key distribution practitioners.
UPDATE in response to query 7/3: Not all strong extractors can be proven resilient to quantum side-channel information. Also, an instance of an extractor must be chosen uniformly at random from a strong family. The advantage of the Trevisan extractor is that good extraction can be shown from a small family and so choosing an extractor from the family consumes less strong random information. In particular most families resilient to quantum information consume strong random seeds of length $O(n)$, but the Trevisan family consumes seeds of length $O((\log n)^3)$. The down side is that the computational overhead of the Trevisan family is markedly worse than its competitors.
It is possible that other extractors are resilient to quantum information, but we can prove this for the Trevisan construction. The ability to form this proof is largely because the construction is really $m$ independent 1-bit extractors. This means that significant information about the whole output can be used to deduce significant information about a single bit and so we only need to prove the resilience of an individual bit. This argument is very heuristic, a full technical argument is in appendix B of De et al.


Dead-Man's Switch Cryptography? I was looking at Time Capsule cryptography? and came up wth this idea.
Question:
Is there a way to store a secret such that the creator must update it or the secret will be decrypted and anyone can access it?
Example:
I use this algorithm to encrypt the message, $enc(M)$, now if I don't update, $update(enc(M))$, then $M$ will be publicly known with high probability after some given time $t$
One idea was to use the Time Capsule cryptography to encrypt a (URL, key) pair that points to my data, and the update function would be me moving the data to another URL.  I feel that this is kind of cheating though, since I could just as easily write a script to give public access to the computer if I don't log in (for example) for a fixed period of time.
So, for this problem let's say that we don't have access to a server and $enc(M)$ must be publicly known and contain the message $M$.  i.e. this should become a Time Capsule crypto algorithm if I never perform an update.
I have a feeling this may be impossible, if so could you give a high level proof of why?

The scheme you propose is not possible as far as I know. This is because $enc(M)$ has to be known for the dead-man's switch to operate (in a time capsule like way, as you described), but there is no way in taking away the time capsule from someone non-cooperative (Eve), to substitute it with $update(enc(M))$.

Another possible scheme can be thought of, if you have a group of trusted parties. One can then use a threshold scheme in order to hide the key $k$ to your encrypted message $enc_k(M)$.
Whenever you don't update those trusted parties, after $t$ time, they can connect to each other, and if they reach the threshold of the scheme, release the key $k$.
This protocol requires a couple of external trusted parties. Although they can be computers, both computer and human can get compromised before the dead-man's switch fires.


Is there a feasible way to reconstruct the key from the (Triple-)DES round key? Assume there is a closed source application which uses Triple-DES with a fixed/hardcoded key to decrypt large amounts of data. Someone managed to extract the round keys from a process memory dump and was able to verify (using a patched version of 3DES that takes round keys as input) that these keys are actually able to decrypt the data successfully.

Is there a known way to use these round keys to reconstruct the original secret key from it? (As it is DESede, two keys are derived using decryption mode and one key using encryption mode). Technically, it is not necessary to be able to do so (a patched 3DES implementation can decrypt the data fine), but it would make the code more readable to just use normal 3DES and plug the original secret keys in. (Plus it would be possible to encrypt instead of decrypt with them).

If there is no such way, is it a design decision that reversing the derivation of round keys to be hard, or is it just coincidence?

DES key schedule takes the 64-bit key and PC-1 (Permuted Choice 1) discards the parity check bits and applies a permutation to the remaining.

Then for the rest they key bits are divided into 28-bit halves and for the each round

They are rotated left one or two specified for each round. Then
48-bit bits are selected by PC-2 (Permuted Choice 2) which is another permutation that discards some bits.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
\text{Number of Round} & 1  & 2 & 3& 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ \hline
\text{Number of Left rotations} & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 \\ \hline
\end{array}

  Is there a known way to use these round keys to reconstruct the original secret key from it?

Giving a round key of DES, apply reverse PC-2. With this, you will get the 48-bit of the 56 bits key. You can either complete this by using brute-force for the remaining key bits or use another round key to fill the missing 8 key bits.

  Is there a feasible way to reconstruct the key from the (Triple-)DES round key?

For the Triple DES, you need round keys for each different DES key if the keys are independently generated.

Though the reversibility of a key schedule is not really required, for older systems non-reversible key schedule makes the decryption require more process time or more memory.


Why all multivariate schemes restrict themselves to polynomials of degree 2 If we note all multivariate schemes restrict themselves
to polynomials of degree 2.
I was wondering why they do it. After looking on the internet, I came to know that they do it for the efficiency.
My question is how working with degree 2 is more efficient?

In multivariate schemes, the secret key is a ``simple'' multivariate polynomial with some structure. The public key is obtained by wrapping the secret key in random linear maps. The resulting multivariate polynomial representation is very dense and unstructured to anyone without the secret key, meaning that any possible monomial would occur with high probability (depending on the field size). That means, storing $n$ such polynomials would require $O(n\binom{n}{d})\approx n^{d+1}$ coefficients, where $n$ is the number of variables / outputs and $d$ is the degree. The same value determines time complexity of encryption, as one has to go through all the coefficients in the public key to compute the ciphertext.
As you can see, degree 2 schemes already have cubic complexity in the number of variables.


Twisted curves in protocol I've come to understand that twisted curves, as for instance defined in the Brainpool specifications, are $F(p)$-isomorphic to their regular $F(p)$ equivalents. So brainpoolP256r1 is isomorphic to brainpoolP256t1.

In a protocol, does it make sense to specify support for twisted curves? Should it be possible to specify the twisted curve OID instead of the $F(p)$ equivalent? If so, could using the twisted curve representation of the curve have any performance benefits over the regular representation? Or is the twisted curve representation only used for the security analysis of the curve?

If so, could using the twisted curve representation of the curve have any performance benefits over the regular representation?

Yes, at least in some cases. To quote Twisted Edwards Curves (section 7):

  One can choose $a$ to be very small, making twisted Edwards curves essentially
  as fast as Edwards curves and thus bringing the speed of the Edwards addition
  law to a wider variety of elliptic curves.

  Even when an elliptic curve can be expressed in Edwards form, expressing
  the same curve in twisted Edwards form often saves time in arithmetic.

  Or is the twisted curve representation only used for the security analysis of the curve?

In addition to the above, twists can also be used to make ciphertexts indistinguishable from random data like in A Public-Key Encryption Scheme with Pseudo-Random Ciphertexts (pdf).


Forging Rabin signature What is the chances to forge a signature for the system implementing Rabin signature with total message recovery, if attacker posses the public key and have some message pairs? The last byte of message to be signed is freely changeable.
The attacker doesn't have access to signing oracle.

I'll assume a system as follows

$N=p\,q$ is the public product of two large secret primes, chosen about uniformly randomly and independently, thus distinct (with overwhelming odds). Such $N$ is believed hard to factor.
the signer chooses a meaningful message $m$ independently of $p$ and $q$, expressed as a non-negative integer verified to be less than $N/256$, and somewhat finds $k\in[0,255]$ and $c\in[0,N)$ so that $256m+k=c^2\bmod N$ (there are four such $c$ for $s\approx64$ values of $k$, and no $c$ for the others $k$, with high odds).
the verifier receiving an alleged $c$ computes $m=\lfloor(c^2\bmod N)/256\rfloor$, and trusts that message if it makes sense.

The chances to forge a signature depends tremendously on what the verifier considers "makes sense". For example, the adversary could set $c=37152$, yielding $c^2=1380271104=\mathtt{52454400_h}$, $m$ is $\mathtt{524544_h}$, which in ASCII is RED. Similarly, $c=33360$ yields BUY. We can't pull that trick for many english words, but that counts as forgery unless we better define "makes sense". And for large $N$, if "makes sense" means that the low-order byte of $c^2\bmod N$ is set to zero to create a terminating character, and the whole thing passed as first argument to puts for display and must be something precisely specified, it is still trivial to forge anything desired up to about half the size of $N$. That can be next to any 127-byte string for 2048-bit $N$ (the lowest recommended minimum these days).

Update: We learn that "The meaningful bytes of $m$ (are) coupled together by (a) checksum" of unspecified size. Forgery can be attempted by trying various $c$ until finding one such that $c^2\bmod N$ pass the checksum check. Expected number of trials is $2^s$ (for optimal checksum), where $s$ is the number of bits in the checksum. For up to 32-bit checksum, we are talking at most seconds of computer time. There's nothing to force us to have $c>\sqrt N$, thus we can make the attack without using $N$ or example messages. Incremental $c$ will do, thus with mild optimization the cost is dominated by the computation of the checksum, at least if there is no other constraint on $m$ beyond the checksum. Even with such extra constraint, it still is possible to choose many bytes of the forged message without much increase in search cost. The high-order ones are particularly malleable: we choose $c$ such that the high bytes of its square are as desired, which merely requires computing a square root.