NIST LWC finalists (AEAD) vs ChaCha20-Poly1305 NIST LWC finalists announced. My question is that how finalists are faster or slower than current golden lightweight AEAD standard -- ChaCha20-Poly1305.
Some benchmark among chacha20-poly1305 vs LWC finalists?

As for every benchmark, it all depends on the computing platform.
As mentionned in comment, you will find benchmarks at bench.cr.yp.to that include NIST LWC finalists and ChaCha-20. However, most of the architectures considered for those benchmarks are rather high-end computing platforms, and they do not necessarily reflect the landscape of constrained devices where lightweight cryptography takes all its sense.
If you are mostly interested in how the NIST LWC finalists compare with ChaCha20-Poly1305, you should take a look at the benchmark by Rhys Weatherley which focuses on embedded devices (8-bit AVR, ARM Cortex-M3 and ESP32 Arduino). As stated on the performance on 32-bit platforms webpage, all the benchmarking results are reported in comparison to ChaCha20-Poly1305:

The approach I take here is "ChaChaPoly Units". The library contains a
reasonably efficient 32-bit non-vectorized implementation of the
ChaChaPoly AEAD scheme from my Arduino cryptography library. This
makes it a known quanitity to compare with other algorithms side by
side.
If an algorithm is measured at 0.8 ChaChaPoly Units on a
specific embedded microprocessor at a specific clock speed, then that
means that it is slower than ChaChaPoly by a factor of 0.8 on that
microprocessor. If the algorithm is instead measured at 2 ChaChaPoly
Units, then it is twice as fast as ChaChaPoly on the same
microprocessor. The higher the number of units, the better the
algorithm.

As you can see, many of the NIST LWC finalists show better performance than ChaCha20-Poly on such platforms. Note that all implementations considered are running in constant-time to ensure a fair comparison.
Another point that matters for the NIST LWC final round is resistance against side-channel attacks. Because ChaCha20 is an ARX-based design, it is does not facilitate the integration of countermeasures against power side-channel attacks such as masking, as highlighted in previous works (e.g. in [1] and [2]). The benefits provided by the NIST LWC finalists over ChaCha20-Poly1305 will likely be of greater interest when considering power side-channels.


How close is AES to random oracle model? I'm wondering if there are any guarantees about AES's randomness in comparison to Random Oracle, but I couldn't find any papers nor publications about it.

Let's say I have a blackbox B which for any input returns either encryption or random data

B(input){
  if(hasBeenEncryptedBefore(input)){
     fail();
  }
  with prob. 0.5 returns: "truly random bits from ROM" OR "f(input)"
}

where:

f(input){
  IV := randomIV();
  key := getKey();
  return IV, AES_ENC(IV, key, input);
}

let's assume that getKey() returns the same key for each encyption and randomIV() returns truly random bits from ROM

Is the adversary interacting with B able to determine whether the result comes from ROM or AES?

Like all PRNGs (pseudo random number generators), there can be no guarantee of randomness, so therefore no statement to that effect can exist. However, reasonable randomness for a given application can often be demonstrated.

Following up on Daniel Lemire's work: I used 254 p-values (30 corrected) obtained from each of over 512 TestU01 BigCrush results on high and low 32-bits (forward, reversed and byte reversed) of the 64-bit output to perform a (work-in-progress) meta-analysis of AES in counter mode (seeded using SplitMix). I find no evidence that suggest any issues with AES, however BigCrush (thus my meta-analysis) has its limitations.

I believe others (perhaps Vigna/Blackman) have performed Hamming Weight Dependency analysis on it to over a petabyte, but cannot find documentation.

Wikipedia has an AES article with information on security, which is a related topic.


Is nonce-less Encrypt-then-HMAC as secure as poly1305 While reading https://crypto.stackexchange.com/a/88732/87450 I noticed that it suggests encrypt-then-HMAC as a defense for partition attacks. However as far as I know unlike poly1305, HMAC does not make use of nonces and in the poly1305 paper DJB says:

There are several reasons that Poly1305-AES uses nonces. First, comparable protocols without nonces have security bounds that look like $C(C+D)L/2^{106}$ rather than $DL/2^{106}$ -- here $C$ is the number of messages authenticated by  the sender, $D$ is the number of forgery attempts, and $L$ is the maximum message length -- and thus cannot be used with confidence for large $C$. Second, nonces allow the invocation of AES to be carried out in parallel with most of the other operations in Poly1305-AES, reducing latency in many contexts. Third, most protocols have nonces anyway, for a variety of reasons: nonces are required for secure encryption, for example, and nonces allow trivial rejection of replayed messages.

Doesn't that mean that HMAC is an inferior choice compared to poly1305 if we consider all threats except partition attacks?

Even though they have slightly different properties, both Poly1305 and HMAC take a key and a message, and return an authenticator. A nonce is not a parameter they have.
The nonce is a parameter of the encryption and decryption functions. For a given key, different nonces are likely to generate different ciphertexts. And in an encrypt-then-MAC construction, different ciphertexts are consequently likely to produce different authenticators.
So, using a HMAC doesn’t prevent usage of a nonce. The nonce is not used by the MAC function itself, especially in an encrypt-then-MAC construction.
It also means that a static (or reused) nonce can be catastrophic no matter what MAC is being used.


In AES-256-CFB, does using a pseudo-unique key circumvent the weakenesses of reusing keys? Disclaimer: I'm not very familiar with the subject. Apologies for how that reflects in the question.
Goal: Encrypt multiple messages using the same key
Hypothesis: If we use, as the actual encryption key, a reused secret key concatenated with a publicly known yet varying (and never repeated) part, would that prevent exploits based on key reuse?
For example,
INPUT
- secret_key
- plain_text

ALGORITHM
- pseudo_key = SHA(plain_text) + secret_key
- initialization_vector = SHA(plain_text)
- encrypted_message = SHA(plain_text) + Encrypt_AES-256-cfb(pseudo_key, plain_text)

DECRYPTION would naturally be:
plain_text: Decrypt_AES-256-cfb(SHA_part_of_encrypted_message + secret_key, remaining_of_encrypted_message)

Let's suppose a resourceful attacker knows the algorithm and has access to 100 used messages
Would he/she be able to crack them? (taking into account the procedure above, and specifically, that the secret_key is the only unknown)
If he/she would, could a different base encryption algorithm make this stronger? Or another method/procedure?
I assume that this doesn't make it any safer, otherwise a similar procedure could be incorporated in the encryption algorithms themselves.
Nonetheless, it is not clear to me how some attacks mentioned in the context of key-reuse could work given that the actual encryption key would be different.
Is there any mode of operation of any modern cipher - if needed in combination with a procedure like the above - that allows us to reuse the same "secret" key without introducing vulnerabilities?
EDIT
(in light of Paul Uszak comment about a leaky initialization vector)
If I understand correctly, the comment means that according to the procedure above identical plaintexts will have the same initialization vector and key (which is constant, "by pre-condition/setup") and therefore the same encrypted text, which in turn is a weakness (?).
Assuming this interpretation to be correct, I'd like it if we could consider the following adaptation to the procedure:
INPUT
- secret_key
- plain_text

ALGORITHM
- R = randomNumber (e.g. Rand(0000-FFFF))
- pseudo_key = SHA(plain_text + R) + secret_key
- initialization_vector = SHA(plain_text + R)
- encrypted_message = SHA(plain_text + R) + Encrypt_AES-256-cfb(pseudo_key, plain_text)

DECRYPTION:
- plain_text: Decrypt_AES-256-cfb(SHA_part_of_encrypted_message + secret_key, remaining_of_encrypted_message), with SHA_part as IV

Note that:

"R" could be used only in the initialization_vector (and not in the pseudo_key also). I used it in both to "simplify" the full message transmitted. Please let me know if either including it or not in the key part impacts strength/vulnerabilities in any way.
Perhaps "R" could be a "top-level part" of the initialization_vector (instead of part of the argument of the SHA). But I'm not sure whether the fact that the attacker knows how the SHA of the plain_text and the random number are combined to form an initialization_vector (the whole procedure is public) would help "cracking something", having access to multiple encrypted messages (with the same sacret_key, same plain_text, and where the random number would also be transmitted "publicly").

In any case, focusing on the actual procedure, and not in the notes above:
Would this random component make the procedure stronger?
Evaluating the procedure as a whole and going back to the initial question:
Does this procedure circumvent the weaknesses of reusing keys when the attacker has access to multiple messages encrypted using the same base key?
Thanks in advance.

Goal: Encrypt multiple messages using the same key

That's what an IV is for! You can mitigate all the dangers of key reuse by using a unique initialization vector. The reason they exist is so that you can encrypt multiple messages without needing to go through the expensive process of changing keys (whether by generating a new random, truly independent key or by expanding one key into a number of keys with an algorithm like HKDF).

  Hypothesis: If we use, as the actual encryption key, a reused secret key concatenated with a publicly known yet varying (and never repeated) part, would that prevent exploits based on key reuse?

Your entire scheme is excessively complex and I haven't analyzed it. What I can say though is that you usually can concatenate a secret key with a public counter or other unique identifier and still treat the key as secure. A vulnerability that allows an attacker to violate some security principle of the cipher when multiple keys are used that are all secret but which differ in specific known ways is called a related key attack. Only ciphers that are badly broken, such as RC4, are vulnerable when used this way.

There is a better, standard way to expand one key into multiple though, and that is HKDF. It is a hash-based algorithm which expands a single key into any number of unique keys that can be treated as independent. This is useful because you don't have to sacrifice any part of the key by turning it into a public value. You can start with a 256-bit secret and derive any number of 256-bit secrets.


AES: a question about dual ciphers and security I have recently learned of dual ciphers, in particular dual ciphers of AES. It seems there are many. Most of my information comes from:(1) Representations and Rijndael Descriptions.

In this paper the authors (which includes one of the designers of AES) discuss $256!$ equivalent ciphers of which $2^{62}$ are useful (4.1 and 4.2).

if dual ciphers are equivalent can we assume they are all just as secure?

Another paper (2) In How Many ways Can You Write Rijndael discusses different types of dual ciphers, such as Log Dual Ciphers and Square Dual Ciphers.

This paper refers to trivial dual ciphers, could anyone give a simple example using a very basic cipher? I could not understand the explanation in the paper.

In sec. 4 of paper (2) they mention changing the irreducible polynomial (there are 30 with each having 8 square dual ciphers, giving a total of 240 dual ciphers).

If we used a different irreducible polynomial for each round of AES to create a kind of multi-dual cipher (my own term), would that make it harder to cryptanalyse and therefore stronger against DCA and LCA? If so, could we use fewer rounds whilst retaining the same level of security?
And, further to 3. above, what if each round's irreducible polynomial  were chosen at random and were changed for each full encryption? Again, would this allow for fewer rounds whilst retaining the same level (or at least adequate) security?

I understand that a so-called multi-dual cipher may have huge implementation problems and may slow the cipher considerably, but I am thinking purely in terms of security, i.e. resistance to analyse.

Are dual ciphers just as secure?  Yes.

The definition is:

  Two ciphers $E$ and $E'$ are called dual ciphers if they are isomorphic, i.e., if there exist invertible transformations $f(\cdot)$, $g(\cdot)$, $h(\cdot)$ such that $$\forall P, K \quad f(E_K(P)) = E'_{g(K)}(h(P)).$$

Note that $f$, $g$, and $h$ are independent of the key and plaintext.  If you had a random algorithm $\mathcal A(F)$ that can distinguish $P \mapsto E_K(P)$ from $P \mapsto U$ for uniform random $K$ and $U$ with some probability $p$, then the algorithm $\mathcal A'(F) = \mathcal A(P \mapsto f^{-1}(F(P)))$ distinguishes $P \mapsto f(E_K(P))$ from $P \mapsto U$ for uniform random $K$ and $U$ with the same probability $p$ and negligible additional cost, to evaluate $f^{-1}$.
The ciphers $E = \operatorname{AES}$ and $E' = \operatorname{AES}$ are trivially self-dual with $f(C) = C$, $g(K) = K$, and $h(P) = P$ for all $C, K, P$.  Proof is left as an exercise for the reader.  (Hint: It's trivial.)
Using a different representation for $\operatorname{GF}(2^8)$ in each round wouldn't substantively change the cipher.  The algebraic structure would remain identical, but you would have a different S-box in each round.

This would probably only make the crypto more expensive for the legitimate users without imposing any real hurdles on attackers—in fact, it would likely make the attacker's job easier by making implementations more likely to be vulnerable to timing side channel attacks.
Now you need to define a pseudorandom generator of irreducible degree-8 polynomials over $\mathbb Z/2\mathbb Z$, and somehow make it independent of everything else in the cipher that uses the same key.  If you're lucky, that might make it harder to attack, at high cost to a cipher that's already painfully slow in software—and probably even make it significantly costlier in hardware.

However, your job, as an aspiring cryptographer, is not to flail around proposing tweaks that might turn out to add security if you're lucky.  Your job is to demonstrate that the changes thwart all existing techniques for cryptanalysis more thoroughly than the simpler approach taken by AES.

Consider starting with smaller, simpler tweaks to AES.  There's an entire book on the design and implementation of Rijndael by the authors, in addition to stacks of literature.  What small tweaks to the design space documented in it can you break or prove resistant to existing cryptanalysis techniques?

As poncho noted in a comment, the easiest way to make AES stronger is to add more rounds.  If your tweak expands the security margin, is its expansion of the security margin greater than that of just adding more rounds?  Is it cheaper than just adding more rounds?


Proof of membership and non-membership in Merkle tree (Hash-tree) If we just know the Merkle root and the data block and we want to know this block is a member of this merkle tree. We need to know all the blocks from the leaf to the root that are associated with data block and we ignore the rest.
But how and whats the point of this?.
If the system is doing so much work finding the blocks associated with this data block we have.It might as well directly do a simple search and find out whether the given data block exists in the first place.
This is becomes even confusing when we use a sorted merkle tree for proof of non-membership. Please explain me what's the concept and what's going on in these two proofs

If you don't use a merkle tree then checking membership is an O(n) operation, as opposed to O(log n) with a merkle tree. Instead of going through each item in the set, you walk up one branch of the merkle tree which has O(log n) depth.
Though, without sorting, proving non-membership still requires O(n) steps. Sorting makes it possible to prove non-membership by only looking at the leaf nodes that would be adjacent to the non-element.
I found this short summary here that's really useful.


ChaCha20: is this a potentially safe way of using nonce derived from private key if the key/nonce pair is never reused, for a given plaintext? Note: I realize in ChaCha20 the nonce should be random and unique each time follow certain constraints but am trying to determine whether there could be a safe way to use it just once if other constraints were in place as follows:

Could the nonce be entirely deterministic and derived from the key so long as the key is only used exclusively once for a distinct plaintext (akin to the one-time-pad). I realize this is risky if the key/nonce pair is re-used on a different plaintext, but wouldn't it be as safe as the one-time-pad if the pair is never reused on a different plaintext message?

Related questions: Does ChaCha20 counter actually increment through iterations?

What happens if a nonce is reused in ChaCha20-Poly1305?

Can I reuse a nonce to retransmit the same packet using ChaCha20-Poly1305?

In other words, if a user wanted to only retain a 256-bit key using ChaCha20 and not have to retain the random nonce, could the nonce, for example, be derived from the leading 12 bytes (i.e 96 bits) of the 32-byte (256-bit) key, provided that they are both never re-used to encrypt a different message than the original one?

[Update: Another further constraint to this scenario, the 'nonce' is NOT made public and the algorithm is running locally on the user's device, such as in a cold storage or internet-gapped environment, even though the resulting ciphertext may later be shared online]

Example secret key and deterministic nonce:

secret key: ba665a007182e68a40aa23c781ed8dcd23b0e3673c7067a9df9cdad13b1d4880

determinisitic nonce based on leading 24-hex of 64-hex key: ba665a007182e68a40aa23c7

plaintext: 68656c6c6f

resulting chacha20 ciphertext:702da4b13e682d4b840b19cde305583b415765f936

Are there any known attacks given the above constraints or can it be considered secure (provided again the key & nonce are never reused on a different plaintext)?

''' ChaCha20 code from https://github.com/ph4r05/py-chacha20poly1305 '''

import os

from chacha20poly1305 import ChaCha20Poly1305
input_hex=str(input('paste 64 hex priv key without 0x pad'))
input_bytes = bytes.fromhex(input_hex)

private_key = input_bytes #os.urandom(32) # equal to 256 bits or 32 bytes
print('private key bytes:',private_key)
cip = ChaCha20Poly1305(private_key)
format_plain=input('paste plaint text data to encrypt')
plain=bytes.fromhex(format_plain)
nonce = os.urandom(12) # Random nonce that is equal to 96 bits or 12 bytes
print("nonce:",bytes(nonce).hex())
ciphertext = cip.encrypt(nonce,plain)
print('ciphertext with random nonce:',bytes(ciphertext).hex())
plaintext = cip.decrypt(nonce, ciphertext)
print('plaintext:',bytearray(plaintext).hex())

### DETERMINISTIC NONCE BELOW DERIVED FROM PRIVATE KEY (Just for reference)

private_key1 = private_key
print('private key1:',bytes(private_key).hex())
cip1 = ChaCha20Poly1305(private_key)

nonce = private_key1[:12] # nonce derived from leading 12 bytes of priv key
print("determinisitic nonce:",bytes(nonce).hex())
ciphertext1 = cip1.encrypt(nonce, plain)
print('ciphertext1 with determ nonce:',bytes(ciphertext1).hex())
plaintext1 = cip1.decrypt(nonce, ciphertext1)
print('plaintext1:',bytearray(plaintext1).hex())

I realize in ChaCha20 the nonce should be random and unique each time…

Nope!

For the ChaCha stream cipher, it is not safe to choose the nonce at random.  At 64 bits long, the ChaCha nonce is too short to be chosen at random.  In general, you should use a sequential message number under any single key as the nonce.

For the XChaCha variant, like the XSalsa20 variant of Salsa20, it is safe to choose the nonce at random because the extended nonce is 192 bits long so the collision probability becomes nonnegligible only after an unimaginable $2^{96}$ messages.  But your question was about ChaCha without an extended nonce.

  Could the nonce be entirely deterministic and derived from the key so long as the key is only used exclusively once for a distinct plaintext (akin to the one-time-pad). I realize this is risky if the key/nonce pair is re-used on a different plaintext, but wouldn't it be as safe as the one-time-pad if the pair is never reused on a different plaintext message?

If the key is chosen independently and uniformly at random for each message, then you can safely use the fixed nonce zero.  Don't mess with hare-brained schemes like copying bits of the key around into other places.

  plaintext: 68656c6c6f

  resulting chacha20 ciphertext: 702da4b13e682d4b840b19cde305583b415765f936

Something is wrong with your use of ChaCha because your ciphertext length is not exactly the same as your plaintext length.  [Update: This is because the question is actually about the ChaCha/Poly1305 authenticated cipher of RFC 7539, not about the ChaCha stream cipher originally described by Dan Bernstein with a different nonce size.]

Also: Write down what your protocol is and how it fits into your application so that a reviewer can confirm you're following the rules of ChaCha.

Also: Don't just use ChaCha and leave it at that.  Use an authenticated cipher (or AEAD, authenticated encryption with associated data) like crypto_secretbox_xsalsa20poly1305.


Constructing secure key exchange protocol I have $\Pi=(Gen,Enc,Dec)$ and let it be semantically secure public-key encryption scheme. Security parameter is $n$, then the message space of plaintext is always $\lbrace 0, 1 \rbrace^n$.

By using $\Pi$ I want to construct key exchange protocol $\Theta$. There should be 2 rounds (i.e. one for Alice and one for Bob). It must be secure against eavesdroppers (and it'd should be possible to prove it :) ).

Of course the only assumption is security of $\Pi$. For example Diffie–Hellman key exchange protocol fits to this exercise (if we assume somethink), but I don't know how to generalize it.

P.S. The key Alice and Bob establish $\in \lbrace 0, 1 \rbrace^n$.

Well, the obvious way to do this is:

Before the protocol occurs, Alice runs the $Gen$ procedure to create a public and a private key
For her round, Alice sends her public key to Bob
For his round, Bob selects a random symmetric key $\in \{0,1\}^n$, encrypts it with Alice's public key, and sends that encryption to Alice.
Alice decrypts the message that Bob sent her with her private key.

Now, Alice and Bob share a random symmetric key (Bob knows it because he created it, Alice knows it because she decrypted it).  In addition, Eve has no information on the key; the only thing that could possibly give her information about it is the encrypted version in round 2; and because we assume $\Pi$ is semantically secure, that gives her no information.


How does a receiver treat X.509 self-certificate with unknown the Signature Algorithm ID? As I know X.509 self-certificate is a mechanism that the host generates public and private keys, the public key will insert to a certification and the private key will be used to sign the certification. The receiver will verify the certificate by using the public key with certification.

In case if the receiver does not have the algorithm that used to sign the certification, how the receiver can verify the certification?

Does X.509 has default algorithm to sign the certification?

In the latest X.509 RFC you can read:

  The signatureAlgorithm field contains the identifier for the
     cryptographic algorithm used by the CA to sign this certificate.
     [RFC3279], [RFC4055], and [RFC4491] list supported signature
     algorithms, but other signature algorithms MAY also be supported.

However from RFC 3279, section 2:

  Conforming CAs and applications MUST, at a minimum, support digital
     signatures and public keys for one of the specified algorithms.  When
     using any of the algorithms identified in this specification,
     conforming CAs and applications MUST support them as described.

But more importantly, when verifying a certificate chain, there is no need to perform the validation certificate when validating the certificate chain. This certificate needs to be trusted beforehand.

So if you receive the certificate by the appropriate "out-of-band" procedure, you could validate the certificate at that time. Afterwards you only need to validate the dynamic values such as the end date of the certificate and - possibly - the status of the certificate - if it has been revoked or not.

That means that for devices with limited capacity you can validate and verify the certificate beforehand, put it in the device using a trusted path to the device / storage and then "just" check the date in the field.

This can be read in section 6.1 of the X.509 RFC:

  When the trust anchor is provided in the form of a self-signed
     certificate, this self-signed certificate is not included as part of
     the prospective certification path.  Information about trust anchors
     is provided as inputs to the certification path validation algorithm
     (Section 6.1.1).

Great, so that solves the problem, right? Not really. The public key of the certificate is commonly also used to encrypt or to verify the signatures send in the application - the reason the certificate exists in the first place. So now you've got your trusted "chain" of one certificate you're stuck with a public key that you cannot use, because it is identical to the one performing the signature verification over the certificate itself.

It would of course be possible that the receiver can encrypt or perform key agreement using the public key while the signature verification algorithm isn't available.

This issue is specific to self signed certificates because the public key is generally only used for a single purpose, while it must at least sign and possibly perform another kind of operation as well.

Notes:

Protocols may put additional requirements on which algorithms are supported, e.g. although TLS doesn't explicitly require RSA signatures / encryption, many websites would not work without it.
"a certificate" has a different meaning than "a certification". The latter means having a product certified against e.g. FIPS or Common Criteria. So "certification" is normally used in the more analog, paper-y sense.
"just" is put within quotation marks because getting the time from a trusted time source may be very tricky on restricted devices.


counting points on elliptic curve Given an elliptic curve with equation $y^2=x^3+ax+b$, and i want to find the number of points $(a,b)\in E(\mathbb{F}_p)$ where the polynomial has repeated roots, how do i do it? I have an intuition it is $p$, but don't know how to rigorously show it.

Thanks

An elliptic curve whose polynomial has repeated roots is not in fact an elliptic curve, but a singular cubic curve, as it has a singular point where the group law breaks down. Still, we can remove those broken points and treat the remaining ones as a group. There are 3 possible cases:

$y^2 = x^3 \bmod p$. This curve has a triple root, and is isomorphic to the additive group of integers modulo $p$. Therefore the order here is $p$.
$y^2 = x^2(x + a) \bmod p$, square $a$. This curve has a double root, and is isomorphic to the multiplicative group of integers modulo $p$. Therefore the order here is $p-1$.
$y^2 = x^2(x + a) \bmod p$, nonsquare $a$. This curve has a double root, and is isomorphic to the group of integers in $\mathbb{F}_{p^2}$ of norm $1$. Therefore the order here is $p + 1$.

The full treatment of all these cases is given in several places, e.g. Husemöller or Washington or Silverman.

The simplest case is the first one, where you have $y^2 = x^3$. Here's the outline: show that you can represent a point unambiguously as $t = x/y$ ($t = 0$ for the point at infinity), since $x = 1/t^2$ and $y = 1/t^3$. Since there are as many $t$ as there are field elements, the group size is the same, $p$.

The other two cases follow the similar approach of bijectively encoding a point as a single $\mathbb{F}_p^*$ (or $\mathbb{F}_{p^2}^*$) element.


A Lightweight Matrix Suggestion for MixColumns State of AES We know that the matrix in the MixColumns state of AES is the circulant  MDS matrix $C=circ(2,3,1,1)$ which is defined over $GF(2^8)$ with the  irreducible polynomial $f=x^{8}+x^{4}+x^{3}+x+1$. Let we show the elements of $GF(2^8)$ with positive integer numbers. For example, when we assume that the elements $2$, $3$ and $4$, we mean $\alpha$, $\alpha+1$and $\alpha^2$ where $\alpha$ is a root of $f$.  Consider the following matrix over $GF(2^8)$
$$
A= \left(
 \begin {array}{cccc}
 2&1&1&1\\
1&1&3&2\\
1&3&4&1\\
1&2&1&3
\end {array}
 \right)
$$
All squarer sub-matrices of $A$ are non-singular or in the other words $A$ is an MDS(super-regular) matrix over  $GF(2^8)$.

My question: Is matrix $A$ is  suitable for software Implementation rather than $C$?

Edit:(Motivated by @Richie Frame comment)
The inverse of $A$, denoted with $A^{-1}$, looks like to semi-circulant matrix as shown
$$
A^{-1}=
 \left(
 \begin {array}{cccc}
 11&194&120&173\\
194&57&173&11\\
120&173&111&50\\
173&11&50&120
\end {array} \right)
$$
Although  $A^{-1}$ is consist of seven elements $(11, 50,57,111, 120, 173, 194)$, from two elements $11$ and $50$ we can obtain other elements as follows
$$
 \left\{
 \begin {array}{lcr}
11+50&=&57, \\
11+50^2 &=& 120, \\
11^2+50^5 &=& 173, \\
11^8+50^8 &=& 194 ,\\
173+194&=&111.
\end {array} \right.
$$

Edit:(Motivated by @e-sushi comment)
After Definition 5 of the second paper, we have

For an efficient implementation of the perfect diffusion layer, it is desirable to have maximum number of 1’s and minimum number of different entries in the MDS matrix.

Although based on the this  terminology $C$ has an efficient implementation rather than $A$, I want to see this one by terminology of XOR and xtime.

After Proposition 3 of the second paper, the authors proved that multiplication
by the matrix of AES  can be implemented using $15$ XORs, $4$ xtimes (or $4$ table lookups) and $3$ temporary variables.

Unfortunately I do not know how to obtain XOR and xtime when the matrix $A$ is applied in MixColumns state of AES.

In addition,
I used software Implementation expression in the question since the matrix of AES($C$) is a circulant matrix, but the matrix $A$ is not  circulant and in 31th paper of FSE 2018, it is claimed that

using a circulant matrix gives adequate flexibility to
do a trade-off between the area requirement and clock cycle, whereas most of the other matrix types are suitable for either one but not both circumstances.

I'm not sure to what paper you reference with "30th paper from FSE 2018" because in this list the 30. paper is not about implementing MDS matrices. As the 31. paper is, I assume you refer to this, entitled "Shorter Linear Straight-Line Programs for MDS matrices".

When you take the XOR count as a metric for efficiency, you can just compute this for your matrix and end up with an naive XOR count of 144, an optimized XOR count of 103 when using the SLP heuristics from the above paper. While the 144 XORs for the naive implementation are better than 152 XORs we would need for a naive implementation of the AES MC matrix, the later can also be optimized with SLPs and this will give you an implementation with only 97 XORs.
So, when only using the XOR count metric, it appears that your matrix is not more efficient than the AES matrix.

Of course it also depends a lot what application you have, if you only need to encrypt stuff (e.g. using AES in CTR mode), looking only at the "normal" matrices is fine, but when you also need decryption and thus the inverse matrices, these have to be implemented as well.


Generating a valid signature on El-Gamal without knowing the private key Suppose we are given $p$, the large prime, $g$ which is the primitive root for $p$, $b$ which is calculated as $b=g^x$ mod $p$ where $x$ is the private key and $0<x<p-1$.

Also suppose we know $y=g^r$ mod $p$ where $r$ is some random number and $0<r<p-1$ and is the discrete log of $y$. We also know $s=(M-xy)(r^{-1})$ mod $(p-1)$ where $M$ is a padded message.

But now, lets suppose that we do not know $x$  but rather we know $r$, the discrete log of $y$. Now we want to forge/generate a valid signature for the message, $M2.$ Given all this information, how can we do this?

I found an article about this which states it in section 3 but I did not understand the process which can be seen at: ftp://ftp.inf.ethz.ch/pub/crypto/publications/Bleich96.pdf. I was hoping if anyone knew the simpler step for it or to put it in a simpler way, that would be great.

Any input is much appreciated. Thanks a lot.

First, I think you have a typo in your question since in the original article $s = (M - x y)(r^{-1}) \mod p-1$, and not $s = (M - x^y)(r^{-1}) \mod p-1$.

Knowing that, then we can construct $s_2$ from $s, r, M$ and $M_2$:

$s_2 = s + (M_2 - M)r^{-1} = (M - x^y)r^{-1} + (M_2 - M)r^{-1} = (M - x^y + M_2 - M)r^{-1} = (M_2 - x y)r^{-1}$

A valid signature for $M_2$ is then $(y, s_2)$

It is easy to see that this signature is valid:

$y^{s_2} b^y = (g^r)^{(M_2 - x y)r^{-1}} (g^x)^y = g^{M_2 - x y} g^{x y} = g^{M_2}$


RSA: deduce the public key from message & signed message In RSA, is deducing the public key from the (message, signed message) pair possible? If so, how can it be done?

With only one (message, signature) pair $(M,S)$, it is not known how to recover the public key $(N,e)$. However, that can be done

with two distinct pairs $(M_0,S_0)$ and $(M_1,S_1)$,
and assuming a known deterministic RSA signature padding scheme with appendix, including textbook RSA, hash-then-textbook-RSA, RSASSA-PKCS1-V1_5 (which is believed safe), and a few others (but not standard RSASSA-PSS).

In a deterministic RSA signature padding schemes, the signature of message $M$ is computed by transforming it into a padded message representative $\widetilde M$, then computing the signature $S={\widetilde M}^d\bmod N$. The signature verification step verifying alleged $M'$ against $S$ computes $\widetilde{M'}$ and checks $S^e\bmod N=M'$. Computation of the padded message representative typically involves hashing. Textbook RSA has $\widetilde M=M$, while hash-then-textbook-RSA has $\widetilde M=H(M)$ for some hash function (the fist is unsafe, and the second is only safe for very wide hash).

The attack needs to guess $e$, but that's typically a small integer, often $e=F_i=2^{(2^i)}+1$ with $0\le i\le4$, or $e=37$, with $e=F_4=65537$ common in practice. We need to pad the two messages $M_i$ into their message representatives per the padding algorithm used by the signature scheme, giving $\widetilde{M_i}$ (for RSASSA-PKCS1-V1_5, we need the size of $N$ in octets, which is the same as that of the $S_i$ if expressed as fixed-size octet strings, or typically given by the highest $S_i$ otherwise).

We are now trying to solve a system of two equations with only unknown $N$: $S_i^e\bmod N=\widetilde{M_i}$. In each, if we got $e$ right, $N$ is a divisor of $(S_i^e-\widetilde{M_i})$.

$N$ can often be found by computing the Greatest Common Divisor of the two $(S_i^e-\widetilde{M_i})$. In most of the remaining cases, pulling out a few small factors from this GCD by trial division of small primes will reveal $N$. For random parameters, this almost always works. The only implementation difficulty stems from the size of $S_i^e$, especially for $e=F_4=65537$ (Java's BigInteger gets impractically slow; GMP shines). Much larger $e$ would make the attack difficult.

If we make a wrong guess of $e$, the method fails (typically yielding a much too small GCD), we can detect that and try another $e$.

Note: at least for textbook RSA, it is possible to intentionally pick messages making pulling out small factors difficult. In that case, Pollard's rho or ECM (as in GMP-ECM) could come to the rescue.

Note: I have included a small demo in Java as invisible text at the end of the source of the present answer.


What is necessary for generating an elliptic curve? Let's say I want to generate my own elliptic curve with an order whose bit length is $n$ (specifically 2048, 4096, and/or 8192)? How would I do this? What needs to be done? What software can do this? How long would it take for a given size?

Let's suppose that you want to generate a classic $n$-bit curve in a prime field, with the complete curve order being prime. The process goes about thus:

Get a prime $p$ of size $n$ bits. The curve will be defined in the field of integers modulo $p$. For all we know, you can use $p$ to have a "special form" that promotes more efficient computations (e.g. $p = 2^n - c$ for a very small value $c$). It is not proven that special-form $p$ do not weaken the curve, but no such weakness is known. Alternatively, if you worry about unknown attacks, select a random $p$.

You may want to make sure that $p = 3 \pmod 4$ so that square root computations modulo $p$ are easy.
Generate a random non-zero integer $b$ modulo $p$ and count the points on the curve of equation $Y^2 = X^3 - 3X + b$. If that number is not prime, start again with a new $b$, until a prime order is found.
The prime curve order is $q$. Compute the trace which is $t = p + 1 - q$. If $t = 0$, then you were very unlucky and you got an anomalous curve; go back to step 2. If $t = 1$, then you were very unlucky and you got a supersingular curve; go back to step 2.
The curve embedding degree is the smallest integer $k ≥ 1$ such that $q$ divides $p^k - 1$. If $k$ is very small then Weil or Tate Pairing can reduce discrete logarithm on the curve to discrete logarithm in the multiplicative group of invertible element in the finite field $\mathbb{F}(p^k)$. With a super-large curve size $n ≥ 2048$ this would not even be an issue, but if you want to be really sure, just check all values of $k$ from $1$ to $100$ (that's what ASNI X9.62 recommends). If the embedding degree is too small to your taste, go back to step 2.

And voilà! you have your own curve.

Steps 1, 3 and 4 above are simple enough to implement with any language that has some support for "big integers" (either natively or with some library). Step 2, on the other hand, is quite complex to do and will be substantially slow; it uses Schoof's algorithm. You'd better use an existing implementation.

There are various additional details that you may want to mind, such as taking care of having a twisted curve which is also of prime order. Read up on Brainpool curves for some guidance here. You may also want to forego classic Weierstraß curves for the more fashionable Edwards curves, which allow for implementations that are somewhat faster, and easier to do properly.

But really, you should first question the wisdom of generating your own curves (because this will basically kill off any interoperability), and also of using curves of such overblown size (which will hurt performance very badly for no practical security gain).


AES-128 Decryption in Objective-C just slightly off I have been asked to integrate a home-grown CRM system with a 3rd-party data service provider (DSP).  The DSP has encrypted the information they are providing.  I only have their decryption instructions, which are as follows (verbatim):

Encryption Type: AES128
Mode: CBC
Padding: PKCS5 (.net usesPKCS7)
Password: jayjay
Encryption reference:(link below)

decryption example as provided by the DSP

The DSP instructions also contain some sample data, namely:

Sample Encrypted data:

h6KlotyqYvipjQHICwJK25mqY+2GC6qc/qf5fCBoGYaxe2zQad/j6Dxo6H259PretcjkUcBsgMl+vFkYPXGwH vbZMqMPCIznBrdZeSWP+Hie7YdLRYp9V5/JKLTIZZlZAG7Vii8DepV5KXjbat4qGxNTVRAvDQ8tT9xZbzEbzY 7Sb9q/f9TE/yardrrgDntw9WywTDbU4Yfg3BEC0jIKFg==

Sample Expected Decrypted data:

123456^CustIDLookup^John^Doe^Placeholder Name^ATS^217 General Patton Ave.^Suite 208^Mandeville^LA^70471^United States^985-809-0600^postmaster@atsleads.com

So, my mission, should I choose to accept it, is to arrive at the decrypted example.  This is for use within a native iOS app, so I need to code the decryption in Objective-C.

So far, my results for the decrypted data NSString look like this:

__NSCFString *  @"(\0\x1d\r\x040D^CustIDLookup^First Name^Last Name^Title^Company^Address 1^Address 2^City^State^Zip^Country^Phone^Email"   0x00000001780ee700

i.e. I am getting this result string:

\0\x1d\r\x040D^CustIDLookup^First Name^Last Name^Title^Company^Address 1^Address 2^City^State^Zip^Country^Phone^Email

I have shown my code below.  I can get very close to the expected decryption, but I can't match it exactly - the first 5 chars are wrong.

Can anyone shed any light on this issue, and perhaps steer me in a direction that would allow my decryption code to decipher the data correctly?  I'm no expert on encryption, but it seems strange to me that I'm very close but am not yet enjoying my cigar.  In my reading so far I have seen comments stating that AES128 and PKCS5 don't make sense together, but I don't if this has any bearing on things.

I have coded an NSMutableData category (extension) as follows:

@implementation NSMutableData (AES)

- (NSMutableData*)DecryptAES: (NSString*)key
{
    int blockSize = 16; // Actually kCCKeySizeAES128, but hard-coded for experimentation
    char  keyPtr[blockSize];
    bzero( keyPtr, sizeof(keyPtr) );
    bool rc1 = [key getCString:keyPtr maxLength:sizeof(keyPtr) encoding:NSUTF8StringEncoding];
    if (rc1==NO){
        NSLog(@"getCString failed");
    }

    size_t numBytesEncrypted = 0;
    NSUInteger dataLength = [self length];
    size_t bufferSize = dataLength + blockSize;
    void *buffer_decrypt = malloc(bufferSize);
    NSMutableData *output_decrypt = [[NSMutableData alloc] init];
    char ivBytes[8] = {0,0,0,0,0,0,0,kCCModeCBC};
    //char ivBytes[8] = {0,0,0,0,0,0,0,0}; // same results with this line
    int ivLength = sizeof(ivBytes);
    NSData* initialisationVector = [[NSData alloc] initWithBytes:ivBytes length:ivLength];

    //CCCryptorStatus result = CCCrypt(operation, algo, optarg, key, keylength, iv, datain, datainlength, dataout, dataoutavailable, dataoutmoved)
    CCCryptorStatus result = CCCrypt(kCCDecrypt , kCCAlgorithmAES, kCCOptionPKCS7Padding , keyPtr, blockSize, initialisationVector.bytes, [self mutableBytes], [self length], buffer_decrypt, bufferSize, &numBytesEncrypted);

    if (result!=kCCSuccess){
        NSLog(@"CCCrypt did not work");
    }

    output_decrypt = [NSMutableData dataWithBytesNoCopy:buffer_decrypt length:numBytesEncrypted];

    if(result == kCCSuccess) {
        return output_decrypt;
    }
    return NULL;

}

@end

I am then calling this category as follows:

NSMutableData* originalStringAsData = [[NSMutableData alloc] initWithBase64EncodedString:self.originalString options:nil];

NSMutableData* decryptedData  = [originalStringAsData DecryptAES:@"jayjay"];

NSString* decryptedString1 = [[NSString alloc] initWithData:decryptedData encoding:NSUTF8StringEncoding];

Any help would be hugely appreciated.

When you get the first part of the decryption wrong, but the rest correct, it almost always means that you got the IV wrong.

However, with CBC mode, what usually happens is that you get the first 16 bytes wrong; instead, you got only 6 bytes wrong; that may indicate that you got the first 6 bytes of the IV wrong (and the other 10 bytes correct).

In addition, I notice that, in your code, you're handing an 8 byte IV to the API; this is odd, because CBC mode takes a 16 byte IV.

I don't know the API you're using (and I certainly don't know the assumptions that the DSP has used), and so I'm at a loss at helping you any further -- however, you were looking for suggestions as to where to look...


Post-quantum alternative to ElGamal? (public key verifiability) Are there any alternatives to ElGamal that would be resistant/annoying to quantum machines?

I would like to preserve public key derivability/verifiability -- ability to ensure existence of corresponding private keys for made-up public-keys.

I've looked up several other cryptosystems from NIST proposals of post-quantum cryptography, but by directly reading the papers it looks like they lack this property.

For instance NTRUencrypt is a lattice-based cryptosystem.
As it operates under a lattice field in theory public keys could be randomly generated without private ones.
But I'm not sure that there would be a way to ensure existence of private keys and possibility of decryption (although the private key space could be large enough and this assumption would somehow hold).

There is nothing quite meeting your requirements, especially if you require the ability to generate random valid public keys without knowing the corresponding private key. CSIDH (not a NIST candidate) comes closest, in that you can at least generate random private keys and easily publish the corresponding public keys verifiably.


How to decode Playfair when only a small part of key is available? How to decode Playfair when only a small part of key is available?
What is the plain text for this message?
Can someone explain how to recover the plain text for this message?
Is there a program that I can download and execute on my PC to test possible keys in bulk to solve the following problem?
The cypher used is Playfair.
The partial key as a word is: ?A?D????BCG??KLNQ???V???Z.
The partial key as a 5x5 table is:
? A ? D ?
? ? ? B C
G ? ? K L
N Q ? ? ?
V ? ? ? Z

Note that the symbol "?" indicates an unknown letter.
The plain text is supposed to be in English or Portuguese.
Only one of these following 3 texts is encoded by the Playfair cypher, but I don't know which.
TXT1
WL_SWVJDTA_GSFSSL_SKKGJAZVWVJ_GEMWHUG_FSFS_WSWTW_SSG_SHWGWID_F_WELAWKS-_SWFKWGFELN__OZSE.ESEV_SA,AFUEAW_DWID_WEYFGSEGSMK_VAWW_XUDSKMJV_J,AL,FI_LVF_MWSLN__GF__OZHFFL_FKK_GAWLSGFWX__WGJ_S_L_GWKJSE_MYHKGWSD_AKTF.WGLDFVASLL_FKWUA_FW_LMUGSKGAF_GAWH_LKLSGGGIGSL_GU_F_WLJMFXSFJ_WNNGUBF__YFWVWMS__F,SWJ_WA_K_GGLSFKWAVAA_SVFYJSGWJE_G_NLU_F_GLSWWLJJ,M_JAUEWWLMJLSSLXDGUVFSW_GSKEWAMFG_FAUSL_F_SSKVMLX__JKS_JNSNVVEYSDJHM_AGUEWSWWWLMFJ_AJLS__SGYFGWF_WES-_DWX

TXT2
SNPQUNBFMIENSKVNSXPQAZMEFONUGSNFRHOEKHBSQRQKRHUPXOUOTULAADZAMARNQEQUSCCORLPQLMTUDECUGXACQKCZKUSIDQOLVFRHEHUCULMIENSKVNKSQRTULAADUDQUHOKUDSERLGPAMACKOCTUQRUBPSZPQUSMQPULMIENSKVNPZPUQKAZAMKEXIMXNDAXACCNIUNEACMEFONUACUMPQUSSLUDQRTPUCAQKGDUIKTUCLGQEIPIZXKGKCDUHRQTMPMBDQSMQPGCAMRHPOXOTNRLOQABNLEPZPIEOFPUUKPISXSKMUDASKISWESKPSPQPTDQQCEHOKQOTUACAFPELMSKPSZAUPPESDPXACMECOROTVRLEHUCVNOUPQEAOQXIPQXBKGOCRHLDMQPSQKSXGSFMPEKMUCSMQCUPXDBPSXMEZPBWCDMPCAKSRETFACPOBDMPMBOHQTQBPOBCNTGSOUQOEDDNSMQPTPEPGKZPMCMAOEXMMLDUEHSIAOBUGSUDGKQOPYPQMLVNKSNXSXSMSPRNQEQUSCAFERSKREGKYDGSMEIZHEMDHRSKPSXHQKUCOEGSHKTPNTQBWDTPEROEOCLMAOBQUPMQSDCMGSHNQEQUSCRMMIQKCUDRSDMEIOCOMFHOHCPOGKYDGSUDIUSNPQUNBFMIENSKVNCAUORHRLNOPQTULAMEFOUCUDTUERGBMARSTCKSQOTPEHIPMHQKIXCAUORHRLSDMEQUMAUCUCBUMASGMUPQOKQUACMESVUPBUQMAUSLCABYMIDHPAHRBULMEHSNPQUNBFMIENUDMQMPMWCAEHXACHEOOVEGLMDQSMQTRHPOGKYD

TXT3
VBRCTB%RS1W2G_0CBKDAPQBG___GXGW,O_QCWEF2GQDGA9QG-NDRY__1U-BWCT__YRKKTYXCKBZAB_HJVG_BXY_YDUR_B39_0JS2QG-_AD__TGVKHBD__GCBDT__0KBJD_.BDYG_CD2R0Y1H_DYJGUKWJKKB,C_BHWOB_NCODXZKDG__ZB__S2_20BDECTYDDKCYY_HY5UDY_GKOT1W_CC2
_CKDPQ_0G%X9GDTKNJFJ_CC_V_TC_B_BâUKTGKXTBFAP5BK2G30T_,_-BDURGBB_DDH,N0YB_BYGBK8_A__0
SB-CD_S2J.T_CBUJU_W_UDJVBUKYDUTY€YTYCJXHC_AD0C_0K_
K2_EYGG_CCVWGBVB_K%VWCMDDG__CTOY1CNDSBYA30__WDBJC,QHYGYG_YKYN_BCKO™VUKC.X

Playfair key grids are often generated by filling in the letters of a key phrase, then completing the grid with the remaining unused letters of the alphabet.
It looks to me like the partial grid you provided has been created in this way. If so, you can fill in several more letters straight away (assuming there is no J):
? A ? D ?             ? A ? D ?
? ? ? B C             ? ? ? B C
G ? ? K L     -->     G H I K L
N Q ? ? ?             N Q ? ? ?
V ? ? ? Z             V W X Y Z

Furthermore, the three cells between Q and V are most likely to be RST, RSU, RTU, or STU. For each of those four possibilities, there are now only six cells remaining to be filled. With a computer, it wouldn't take long to test every possible combination (4×6! = 2880). You could probably even solve this with pen and paper by attempting a partial decryption with the parts of the key you already have, then working back from the plaintext to figure out the others.
I think it's safe to assume that TXT2 is the Playfair encrypted message. It has an even number of characters, no digits or punctuation, and no letter J. Also, when split into pairs, there is no pair in which the same character appears twice (something that cannot happen in Playfair encryption).


What does it mean that $BW_N$ is a permutation over the squares mod N? Let $BW_N$ be a function such that $BW_N:\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ and let if be defined as follow: $BW_N(x) = x^2 \pmod N$ where $N=pq$ and p and q are primes and $p=q=3 \pmod 4$. I am reading on a set of lecture notes that, "$BW_N$ is a permutation over the squares mod N". Does someone know what that means?

Does that mean its a trapdoor permutation? Or what might it mean?

I am not sure if this question would have been more appropriate on the mathematics stack exchange site, but it had to do with crypo so I though it might get a response here.

"$BW_N$ is a permutation over the squares $\mod N$". Does someone know what that means?

You define your map $BW_N:\mathbb{QR}_N\rightarrow \mathbb{QR}_N$. Note that $$\mathbb{QR}_N:=\{r\in Z_N: r\equiv y^2 \pmod{N}, y\in Z_N\}$$ and a permutation is a one-to-one mapping (bijection) from a set into the same set.

Basically, this map is a permutation if under $BW_N$ for every $x\in \mathbb{QR}_N$ there is a unique $y\in \mathbb{QR}_N$ (and clearly the same for its inverse $BW_N^{-1}$).

Now, since you have $N=pq$ being the product of two Blum integers $p$ and $q$, you have that for every of the four possible square roots of $r\in\mathbb{QR}_N$, which are of the form $(\pm\alpha,\pm\beta)$, exactly one of those is also a quardratic residue modulo $N$, i.e., an element of $\mathbb{QR}_N$ (this is not hard to prove).

Consequently, $BW_N$ gives a bijection from $\mathbb{QR}_N$ to $\mathbb{QR}_N$ and this is what is meant by "$BW_N$ is a permutation over the squares mod $N$".

  Does that mean its a trapdoor permutation? Or what might it mean?

The factorization of $N$, i.e., the knowledge of $p$ and $q$, is the trapdoor of this permutation and is required to efficiently compute the inverse.


Is a single md5 hash a good way to generate an AES key? This site says how to encrypt data using a password in go using AES-GCM.
It says the following:

When encrypting and decrypting data, it is important that you are using a 32 character, or 32 byte key. Being realistic, you’re probably going to want to use a passphrase and that passphrase will never be 32 characters in length.
To get around this, you can actually hash your passphrase using a hashing algorithm that produces 32 byte hashes. I found a list of hashing algorithms on Wikipedia that provide output lengths. We’re going to be using a simple MD5 hash. It is insecure, but it doesn’t really matter since we won’t be storing the output.

Is this true?
So fine, I don't mind using something a bit more secure than MD5, it's easy to replace MD5 with SHA-2.
But another thing hit me:

Why is something like bcypt/scrypt not required?
Is AES slow enough to prevent a brute-force attack?

Assuming that the password/phrase is in fact a password/phrase, and does not already contain sufficient complexity to prevent guessing (e.g. is not a cryptographically strong random string)...

  Is this true?

No. An attacker will simply guess at the password, and a fast hash function will help them to guess faster. An attacker can try a truly ridiculous number of md5 hashes per second, and will certainly break any password/passphrase that was not generated to be cryptographically strong.

  Why is something like bcypt/scrypt not required?

Slow hashing is required, and the information in the article is not good advice. Choosing MD5 because it offers the right digest size out of the box is not justifiable: Stronger 256-bit hash functions exist (e.g. SHA256), and a larger hash digest could easily be truncated down to 256 bits

A cryptographic hash function is not appropriate for use on passwords/passphrases.

  Is AES slow enough to prevent a brute-force attack?

No, and it is not the ciphers responsibility to be slow to prevent brute-force attacks on the key. Assuming that they key is strong enough to be called a key (e.g. a uniformly random bit string), then having a slow cipher is completely non-productive.

So the responsibility for being slow to prevent guessing attacks falls to a step before encryption takes place, namely, the key derivation step. Functions such as Bcrypt/Scrypt/Argon2 are explicitly designed for the purpose.

Alternatively

If the passphrase was generated randomly and designed to possess sufficient entropy, then using a slow key derivation process is not really necessary or beneficial. In such a case, using something like HKDF would probably be the most appropriate.

In any case

Selecting MD5 from a list because it seems fine is not a good sign...


Can you explain what is whitelisting in TLS False Start In TLS clinet false start mechanism, the standard says the following:

  The symmetric cipher defined by the cipher suite negotiated in this
  handshake has been whitelisted for use with False Start according to
  the Security Considerations in Section 5.1.
  Reference: rfc7918

Can you explain to me with more details about white listing the ciphers? Is it a list of allowed ciphers stored at the client side? How is this different from the client's ciphersuite list?

Is it a list of allowed ciphers stored at the client side?

This list is defined by the application or more likely the implementation. Basically what you do with "False Start" is that you run a normal TLS handshake and if all of the conditions you found are met, you also immediately start sending encrypted application data - before you have finished the authentication with the server, ie awaited his Finished and ChangeCipherSpec. Because you wait for the third message run before making your decision, this means the cipher suite has already been negotiated and thus you can apply your white-listing strategy.

  How is this different from the client's ciphersuite list?

Indeed, these two lists may be identitical but the RFC explicitely states that you want strong security with the picked cipher suite if you want to use "False Start". Now consider what this requirement means: You cannot possibly connect to servers which only support cipher suites you consider "potentially weak", the RFC mentions RSA key-transport as an example for that. So if you'd make these lists equal, yoo wouldn't be able to connect to those servers which is usually undesirable.

For your last question, consider this quote from the RFC:

  Instead, the security goal is to ensure that if anyone at all can
  decrypt the application data sent in a False Start, it must be the
  legitimate peer.

Basically you want to make sure that if you are under attack and you used "False Start", an attacker can't learn anything about the application data, which is why you want to be "extra-confident" in the cipher-suite.


How is an IV used in a Merkle-Damgard construction- Explicit example I am interested to know how an IV is used in this simple Merkle-Damgard construction. I am referring to this image from the associated Wikipedia page as I explain further.

For the purpose of explanation, lets assume the following:

-We have a simple function: f(takes in 8 bits)= outputs 4 bits, or any similar simple function.(ex. f(a,b)= (a x a + b x b + 11) mod 15, where a,b are 4-bits)

-We have a 2 block message: M=101011110.

-The initial IV = 1111 or a similar simple IV

To my understanding, the first 8-bit block is 'a=1010 b=1111' and it would go through the function f(). I am unsure of how the IV would fit in to the process at this point, and how the IV would take action for the second block and so on. Any help is appreciated, and perhaps it may be the case that generalized variables as opposed to my specific numbers would make this example easier to explain in an answer.

If the function takes two inputs of 4-bits each, then yes, 4 of the bits would come from the IV.The output of the function would be used as the IV (although it is no longer initial) of the next iteration of the function with the next 4-bits of the message.

Since the function outputs 4-bits, the final digest would also output as a 4-bit digest.


Is there a problem with this non-ECDSA message signing? Is there a problem with signing a message like this?

p = the Elliptic Curve prime
G = base point
a = Alice’s private key
A = aG = Alice’s public key
e = hash(message)
Jx = x coordinate of J

In my target 32-bit microcontroller I am using p-256 and SHA256.  Thus e will typically be in 1..p-1.

Alice computes:

e = hash(message)
E = eG
J = aE          using Alice’s private key

and sends Jx as signature

Recipient computes:

e = hash(message)
K = eA          using Alice’s public key
and validates Jx = Kx

The only problem I see is that e might be 0 or 1 or some value >= p.  (If it is I have the flexibility to pad the message such that e is in a good range.)

Is there a problem if hash(msg) is greater or equal to the EC prime?  Other than a few unusable values of e is there is a problem that makes this method less secure than ECDSA?

The problem with this method is that it is insecure.  Anyone with Alice's public key can sign any message they want, by computing:

$e = hash(message)$

$J = eA$

This $J_x$ will verify correctly according to your verification procedure.


Are there any digital signature algorithms in common use that result in 32-byte signatures? I don't consider myself to be an expert in this field, so forgive me if there is an obvious answer.  I am having a tough time finding an algorithm that can sign data and output a 32-byte signature, that is in common use.  Specifically, I'd like to find an algorithm that frequently available in many security APIs that are in common use, across multiple architectures.  In other words, any algorithm that could be considered ubiquitous.

Is there a reasonably "standard" signature algorithm that generates 32-byte digital signatures?  To be clear, I'm not asking for any Github projects, or library APIs but I would like to find an algorithm that is pretty standard and is accessible to a broad group of developers.

Is such an algorithm in use or are most, if not all, common signature algorithms in the 64+ byte range in size?

Yes! (restrictions apply). ISO/IEC 9796-2 (scheme 1, SHA-1 hash, option 1 also known as implicit hash identifier, alternative signature production function) is a fully standard signature scheme, based on RSA, widely used in the Smart Card industry for public key certificates and message authentication, that adds only 22 bytes of signature overhead (if the message to sign is at least 234 bytes, for 2048-bit RSA modulus), and is quite simple to implement.

The main caveat is that some of the message to sign is not directly intelligible in the signed message; rather, that 238-byte section at the beginning of the message is recovered as a byproduct of the signature verification process. This restriction is often tolerable: who cares for the public modulus section of an RSA public-key certificate before the signature of the certificate has been verified? Especially since that signature verification is faster and simpler than in most competing schemes with relatively short signatures, e.g. ECDSA.

Other caveat: ISO/IEC 9796-2 scheme 1 is not safe when the adversary can obtain the signature of many chosen messages (there is the risk that the adversary can compute the signature of some more messages). Scheme 3 is a functional replacement free of this defect, with a security argument, but is seldom used AFAIK.

For details on signature with message recovery, including references to the standard, practical description, and known attack against scheme 1, see this answer.

Update: If we stick to ISO/IEC 9796-2 scheme 1 with SHA-1, option 1, alternative signature production function, because that's an industry standard, we should know when it is vulnerable: that's

Due to the padding scheme, when the adversary can repeatedly chose part of a message, exactly predict the rest with sizable odds $\epsilon$, and obtain the signatures, and gain advantage of the slightly constrained message(s) for which a forged signature can be obtained. In current attacks the number of signatures to obtain grows as $K/\epsilon$, with $K$ in the hundred thousands.
Due to SHA-1's relatively poor collision resistance (in the order of $2^{61}$ hashes in the best of the non-retracted attacks currently listed on wikipedia), if the adversary can chose or predict enough of the beginning of a message to create a collision, and can obtain the signature of one message (and gain advantage of the other).

A good mitigation to both issues, if we can afford a 32-byte signature overhead, is that the signer provides 10 bytes worth of entropy unpredictable to an attacker somewhere within the first 64 bytes of the message to sign (e.g. add 10 random bytes at the beginning), before applying the signature. That location best strengthens SHA-1 by making the output of the first compression function unpredictable, and falls within the beginning of the recoverable part of the message where that's best for strengthening the padding scheme.

So at the end of the day, in order to sign a message $M=M_1\|M_2$, with $M_1$ of 224 bytes and $M_2$ an arbitrary non-empty bytestring, using an RSA private key $(N,d)$ with $N$ 2048-bit, the signer

draws a random $M_0$ of 10 bytes, then apply ISO/IEC 9796-2 scheme 1 with SHA-1, option 1, alternative signature production function on message $M'=M_0\|M_1\|M_2$ (these are the next steps);
computes $H=\operatorname{SHA-1}(M_0\|M_1\|M_2)$, which is a 20-byte string;
forms $X=\text{'6A'}\|M_0\|M_1\|H\|\text{'BC'}$, which is a 256-byte string representing (in big-endian convention) a 2047-bit integer also noted $X$;
computes the signature $S=X^d\bmod N$, which is an at-most-2048-bit integer which we represent as a 256-byte string (in big-endian convention);
preferably, apply the verification procedure below on $S\|M_2$, and perform the next step 6. only in case the verification outputs $M$ (or $M'$ depending on variant); this guards against some fault attacks;
transmit the signed message $S\|M_2$ (which is longer than $M$ by 32 bytes).

The verifier using a trusted RSA public key $(N,e)$ with $N$ 2048-bit

checks that the alleged signed message is at least 257 bytes, else rejects the signed message;
splits the signed message into $S\|M_2$ where $S$ is 256-byte;
checks that $S$ (considered an at most 2048-bit integer in big-endian convention) is less than $N$, else rejects the signed message;
computes $X=S^e\bmod N$ (which is an at-most 2048-bit integer) and expresses it as a 256-byte string also noted $X$;
checks that the first and last byte of that string are $\text{'6A'}$ and $\text{'BC'}$, else rejects the signed message;
reformats $X$ as $\text{'6A'}\|M_0\|M_1\|H\|\text{'BC'}$ where $M_0$ is 10-byte, $M_1$ is 224-byte, $H$ is 20-byte;
checks that $\operatorname{SHA-1}(M_0\|M_1\|M_2)$ equals $H$, else rejects the signed message;
output $M_1\|M_2$ as the authentic $M$ (variant: output $M_0\|M_1\|M_2$ as the authentic $M'$).

Note: I have restricted to $M_2$ non-empty in order to avoid a slight complication, where according to the standard the prefix byte should be $\text{'4A'}$ instead of $\text{'6A'}$, and verified as such, when $M_2$ is empty.

For something still with 32-byte overhead, academically sound, fully aligned to standards (if not practice), and dumping the deprecated SHA-1, we can use ISO/IEC 9796-2 scheme 2, with SHA-224, option 1, 2 bytes of salt, and alternative signature production function.


Discrete logarithm problem is easy in a cyclic group of order a power of two Let $G=\langle g\rangle$ be a cyclic group of order $2^{k}$ and let $h\in G$. I have read that it is easy to find $\log _{g} h$, but I haven't been able to figure out how. Do you know why this can be done in polynomial time? Do you know of a book where I can find this?

You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like $p = 257$.

Since $g$ is a generator of the Group, $h \equiv g^x$ for some unknown exponent $x$.  In other words, $\log_gh = x$, and for Groups of order $2^k$, this discrete log is easily computed like so:

Interpret $x$ as a $k$ bit number, i.e. $x = c_02^0 +c_12^1 + c_22^2 + c_32^3 ...+ c_{k}2^{k}$ where the coefficients $c_0, c_1, c_2...c_k \in \{0,1\}$.  You can find the value of $c_0$ by raising $g^x$ to the power $2^{k-1}$ modulo $p$.  If $c_0=0$ then all the other terms in $x$ are divisble by 2, thus $x=2y$, and so by Euler's totient theorem, $$(g^{2y})^{2^{k-1}}\equiv g^{y2^k} \equiv g^0 \equiv 1 \mod p$$
If however $c_0 = 1$, then raising $g^x$ to the power $2^{k-1}$ mod $p$ will return the result $p-1$.  So by looking at the result, you can see directly what the value of $c_0$ is.  Now that you have the value of $c_0$, subtract the term $c_02^0$ from $x$ (i.e. multiply $g^x$ by the modular multiplicative inverse of $g^{c_02^0}$).

Now you can find out what the value of $c_1$ is, by using the same approach:  raise $g^{x-c_02^0}$ to the power $2^{k-2}$.  If $c_1=0$, then all the remaining terms in $x-c_02^0$ are divisible by 4, and so $x-c_02^0 = 4y$ and $(g^{4y})^{2^{k-2}} \equiv g^{y2^k} \equiv 1 \mod p$.  If on the other hand $c_1=1$ then again the result will be $p-1$.  Subtract the term $c_12^1$ from $x-c_02^0$, and repeat the procedure for $c_2$.  Continue until you have discovered all the coefficients for $x$: you now know what $x$ is.


Is there an $n$-bit hash function such that $n$ is equal to the length of input and the collision resistance is close/equal to $2^{n/2}$? Let $B$ denote a non-empty bitstring of arbitrary length. Then let $n$ denote the length of $B$.

The question: does there exist a cryptographic hash function $H$ that outputs a hash $h$ of $B$ such that the length of $h$ is equal to $n$ and collision resistance of $H$ is either $2^{n/2}$ or negligibly less than $2^{n/2}$ (other standard cryptographic properties, such as pre-image resistance equal to $2^n$, are also implied)? If yes, what can be an example of such function?

I should also emphasize that $H$ is allowed to be significantly slower than standard hash functions, and the entire input is allowed to be stored in RAM.

EDIT
Of course, a function with this abstract property is not a standard “hash function” in the usual meaning. One example of similar function would be MD6 compression function (described in Chapter 2.5 and Chapter 9 of the document “The MD6 hash function: A proposal to NIST for SHA-3”), which was designed without any claimed limits on the security level. That is, the security depends on the length of the output, not on the length of the internal block size. It accepts the input of arbitrary length and outputs a truncated bitstring, assuming that the number of rounds increases when the length of the input increases. Yes, the output is truncated (and becomes smaller than the size of the input), but since the input size is variable, we can simply pad the input by any number of bits to obtain the output of any size. One problem is that this function requires an additional algorithm (described in Chapter 9.2 of the document) to detect what specific parameters will be optimal for the corresponding length of the input. This is different from Keccak family of fixed pseudo-random permutations, which is designed without any additional optimizing algorithms for different block sizes (1600, 800, 400, ...). Also, non-iterative cryptographic hash functions may be relevant.

I am not entirely sure I got your question right, so let me rephrase it: you want a function $H$, that takes as inputs strings of bits, and outputs other strings of bits, such that:

There is nothing secret in $H$; it is deterministic, easily computable, and uses no secret key.
If $m$ has length $k$ bits, then $H(m)$ also has length exactly $k$ bits.
It should be computationally hard to find two distinct inputs $m$ and $m'$ (with the same common length $k$ bits) such that $H(m) = H(m')$. The "hardness" here means that the effort to find a collision should be at least in $O(2^{k/2})$.

With these requirements, a very simple solution is to use the identity, i.e. $H(m) = m$ for all strings $m$. The identity can be computed very efficiently: it has cost zero. There are no collisions at all, so the hardness of finding a collision is infinite. However, I suppose that the identity is not appropriate in your use case; i.e. you actually want more than just "resistance to collisions".

So let's add some extra requirements. You want a publicly computable function $H$ that preserves length ($H(m)$ has the same length, in bits, as $m$, for all strings $m$), and that fulfill the three classical notions of security for hash functions:

Resistance to preimages: given output $t$, it should be computationally hard to find input $m$ such that $H(m) = t$.
Resistance to second preimages: given input $m$, it should be computationally hard to find input $m'$ such that $m\neq m'$ but $H(m) = H(m')$.
Resistance to collisions: given a bit length $k$, it should be computationally hard to find inputs $m$ and $m'$ of length $k$ bits, such that $m\neq m'$ but $H(m) = H(m')$.

Note that, in our case, we must use the bit length as parameter. In usual hash function, the input length is arbitrary but the output length is fixed an implicit in the definition of the hash function. For your function $H$, you must add the bit length $k$ as parameter to the security notions. For preimages and second preimages, this is easily obtained as the length of the challenge: when I give you $t$ and challenge you to find $m$ such that $H(m) = t$, then I also necessarily give you the bit length $k$, which is the length of $t$. But for the "collisions" challenge, I must specify the bit length $k$ explicitly, otherwise you could (smugly) solve the problem for a very short length, and show me that collision.

The variable-length property of $H$ makes the problem a bit harder to analyze. With a normal hash function with a fixed output size ($k$ bits), but accepting inputs of arbitrary sizes, it can be shown that the best resistances you can hope for are on the order of $2^k$ for preimages and second preimages, and $2^{k/2}$ for collisions. However, with a length-preserving function, you can get farther some of these limits; indeed, if you use the identity (i.e. $H(m) = m$), then resistance to preimages is nil (simply set $t = m$) but resistance to second preimages and collisions is infinite (there is simply no collision at all).

All of that being said, an easy solution is to use a key derivation function. One standard KDF is HKDF: it can take inputs of arbitrary size, and produce outputs of configurable size, so you can simply use HKDF with an output size equal to the input size. This has some caveats, though:

Maximum output size of HKDF is limited to 255 times the output size of the underlying hash function. If you build HKDF over SHA-256, then you will get an output of at most 8160 bytes (65280 bits).
You will heuristically get your collision resistance target ($2^{k/2}$) but, again, only up to some limit. If the internal hash function is SHA-256, then for $k \gt 256$, you might not get more than $2^{128}$ resistance to collisions. This does not matter in practice, since anything beyond about $2^{100}$ is equivalent to infinite for the foreseeable future.

Another candidate is SHAKE, one of the variants of SHA-3. SHA-3 is based on Keccak, a "sponge function" in which you first accumulate the input into an internal state, then produce output from that state; with "plain" SHA-3 you just get enough bits to reach the defined output size for the hash function, but with SHAKE you let it flow for as long as you want. If you define $H$ to be "SHAKE256, with an output size equal to the input size", then you should get a reasonable solution. Note that SHAKE output size is not practically limited; however, like with HKDF, there is an internal limit which will set a maximum to the collision resistance you can hope for, in a theoretical point of view.

(Having such a limit is mostly necessary for any function that works but first absorbing the data into an internal fixed-size state, then producing output deterministically from that state alone. This should not be a problem in practice, since you can put that limit far away into the land of "cannot do that in practice". If you want to talk theory with adversaries of truly unlimited power, then take care that there is no known proof that secure hash functions can actually exist at all.)


Could ANY cipher serve as the foundation for a public key cryptosystem? My reasoning goes like this:

In principle, any trapdoor function can serve as the foundation for
an asymmetric encryption scheme.
All ciphers are trapdoor functions, since it's easier to encrypt plaintext than it is to crack ciphertext.  Put another way, it's easier to use key and plaintext to produce ciphertext, than it is to go backwards and use ciphertext to produce key and plaintext.
Therefore, one could (at least in theory) devise a public key
cryptosystem derived from any cipher, whether it be Caesar or AES.

This has the interesting implication that one could devise an asymmetric encryption scheme based on an existing asymmetric scheme + key + plaintext combo, and then derive another from that one, etc. etc.

I found this interesting quote which seems to confirm my hunch:

  every problem X in NP has a naturally associated public-key cryptosystem (warning: it's a .PDF file)

Your reasoning is flawed. Producing a cipher text for a given key from plaintext without the key is no easier than the reverse for symmetric ciphers.
Without the key k, producing ciphertext $Enc_k(x)$ is every bit as hard as $Dec_k(x)$ for many ciphers it is the same operation entirely (e.g anything in CTR mode). And even for common block ciphers there is great similarity between encrypt and decrypt.

For a public key system I need some operation which can be done without the private key. AES etc. do not supply one. If you have the key both operations are easy, without the key they are darn near impossible.


Are there any tools for expressing the cipher operations as a system of equations? The first step In Algebraic-attack is expressing the cipher operations as a system of equations. Is there an automated tool to do this?

Theoretically, the equations could be derived from the representation of the cipher in a hardware description language like VHDL or Verilog; you implement the cipher as if you want to make a FPGA/ASIC which runs it, but you stop at the symbolic representation of the logic gates (the "netlist"). However, I am not aware of any existing conversion tool which will transform a netlist into a sequence of equations in the right format for whatever equation solver you want to use for performing the attack.


Does RSA operate over a Finite Field (Galois Field)? Is it correct to say that RSA operates over a Finite Field (Galois Field)? In this case GF(p)?
I do understant that the modulo in RSA is not itself a prime number, but all the operations (multiplication, inversion) occur as if it is a GF(p).

No, RSA encryption and signature is performed in (the multiplicative semigroup of) the factor ring $\mathbb Z/n\mathbb Z$ which is not a field since the non-zero elements $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) do not have multiplicative inverses. (However, one easily observes that all other non-zero elements are invertible, as their representants are coprime to $n=pq$).


In what sense are silicon PUFs unclonable? I see quite a few publications on Physically Unclonable Functions implemented using regular silicon IC techniques; for example A 0.19pJ/b PVT-variation-tolerant hybrid physically unclonable function circuit for 100% stable secure key generation in 22nm CMOS (10 authors at Intel), at 2014 IEEE International Solid-State Circuits Conference, with free preview there. The device is summarized as

  ..creating a golden key at first array power-up during tester-time operation and thereafter recreating this golden value from the inherently noisy raw PUF value during regular field operation. The golden key is used to compute an Error Correction Code signature, which is stored on-die as fuses. During regular operation, error correction circuits mix raw PUF bits with ECC fuse values to regenerate the golden key with 100% accuracy.

A reference for that principle is given as: FPGA Intrinsic PUFs and Their Use for IP Protection (4 authors at Philips), in proceedings of CHES 2007.

I wonder in what sense these things are unclonable.

In particular, I fail to understand why it would not be possible to replace the noisy PUF array and its sensors by ROM with content the (probed) raw PUF value, replace the ECC data/signature by ROM too, letting the error-correction circuitry do its thing; or replace the whole thing by a small ROM or wires defining the golden key.

The answer lies in "complexity", but I do not believe they are unclonable in the explicit sense, but I can think of ways to get data out depending on how they are made.  It is easy for me to see "ROM" type gates under a SEM, and what PUFs buy you is that the structure is uniform but then you do not know the electrical characteristics.

In a PUF array, you give it some electrical input and you get a seemingly random, but repeatable output due to [PVT] (Process Voltage Temperature) of the devices 1. You could actually consider this just a huge lookup table of complexity of bit-width and clock depth.  A 32-bit number gives you a 32-bit number out at some clock of X.  The input is generally easily to get to, but the output is buried in the layout.  The output could completely be probed, but you would get an answer for a single input.  (on the reverse engineering side, I could make things current mode so I could not probe them because probing them would cause errors).  Now assume that you have a PUF array that takes a single clock and has a 32-bit output due to a single 32-bit input, that means you'd need a single 32-bit value in your ROM to emulate the PUF.  Otherwise, you need an entry for each clock and input vector.  If you have 32-bits of possible input, for one clock, you'll need $2^{32}$ entries in your rom, and it gets huge from there.

So, (1) If you a voltage mode circuit on the output, (2) have a single entry to map, and (3) have a semiconductor lab, there's no reason you could not get a single output and replace it with the ROM.


Building Key Streams from PRNGs I am reading an intro book about cryptography and the author tries to explain why using pseudo random number generators is vulnerable.

Given PRNG equation;

\begin{align}
S_0 &= \text{seed}\\
S_{i+1} &\equiv A\cdot S_i + B \mod m, i = 0,1,\ldots
\end{align}

where we choose $m$ to be 100 bits long and $S_i,A,B \in \{0,1,\ldots,m−1\}.$ Since this is a stream cipher, we can encrypt

$$y_i \equiv x_i + s_i \mod 2$$

Further in the text:

  But Oscar can easily launch an attack. Assume he knows the first 300
  bits of plaintext (this is only 300/8=37.5 byte), e.g., file header
  information, or he guesses part of the plaintext. Since he certainly
  knows the ciphertext, he can now compute the first 300 bits of key
  stream as: (Equation 1) $s_i \equiv y_i + x_i \mod m, \; i=1,2,\ldots,300$

There are several things about the paragraph above that I don't understand.

Firstly, by what mechanism could Oscar gain the first 300 bits of plaintext? It makes little sense for Alice (the person who tries to securely communicate with Bob) to send encrypted and plain text together.
Is there a situation this happens?
How exactly could Oscar predict the word and location of cyphertext?

Secondly, I don't understand how Equation 1 was derived?

I appreciate any help.

Firstly, by what mechanism could Oscar gain the first 300 bits of plaintext? It makes little sense for Alice (the person who tries to securely communicate with Bob) to send encrypted and plain text together.

This is called a Known-Plaintext Attack (KPA). In some real-world examples, this attack makes sense. Also, we want our cipher to resist to KPA, we don't rely on attackers not being able to find known-plaintexts.
Why would Alice send the plaintext together with ciphertext? If so, what is the aim of encryption?

Is there a situation this happens?

This is taken from Mark Burnett's answer

Example: We saw this with the old pkzip encryption method. In this case if you had any of the unencrypted files in the archive, you could use that to obtain the key to break the rest.

Also, in some militaries, the message must be started with
FROM: Name_of_the_Sender
TO: Name_of_the_Receiver

If you are intercepting the encrypted messages, this means that you know at least the first line plus 3 more characters from the plaintext.

How exactly could Oscar predict the word and location of cyphertext?

If you know the context, you can guess about the plaintext. Then you need to solve the equations for position $i$ to get the key. Once a candidate key is found, decrypt the rest of the ciphertext to see that is is not a false positive key. If false-positive, try next guess, if not wonderful.
Cryptanalysis is not an easy job but once successful gives lots of pleasure.


Problems understanding the applications of pseudo random number generators I am trying to explore different methods used to generate pseudo-random numbers for my project in maths and I would be very grateful for some help or references to valuable sources as it is very hard to explore this field without background information.

Although the mechanism used to create PRNs are quite clear for me, I have problems understanding how they are really applied. I was wondering which algorithms I can use to generate a 4-digit code. When you generate such codes, do you always convert the generated numbers to bits? What tests do you use to check if the sequence of those 4-digit numbers is actually random?

Thanks a lot for help!

In most cases your runtime uses a DRBG rather than a PRNG. A DRBG is a Deterministic Random Bit Generator, so it delivers bits to the user rather than random numbers in a specific range. Generally it is possible to request bytes and then use - for instance - the lowest 4 bits. If the 8 bits of a byte are random then the lower 4 bits must be random as well after all. In most programming languages you can get to the lower 4 bits (4 bits is called a nibble) by MASKing: nibble = byte & 0x0F.

If you have a PRNG that delivers numbers in a range $0$ (inclusive) to $n$ (exclusive) then you can request a number in the range $0$ to $16$ because $2^4=16$. The number requested will have the lowest order bits set to the random values.

Generally the conversion to nibbles should be covered by existing tests. However, if you still want to perform a test then you could try and generate about 500 billion nibbles (yes, you are reading that correctly) and use that to create a 250 GB file. That file can then be used to test against the Dieharder testing framework. Testing for randomness requires a lot of samples if you want to be cryptographically secure.

Beware that most DRBG's are actually (re-)seeeded using an operating system. You must make sure that the DRBGs/PRNGs actually delivers the type of pseudo-random stream you're after.


What's the entropy of the output for Tiger Encryption? I'm tasked to apply tiger encryption to my string(key). Does anyone have any idea how to find the entropy of the hex output by tiger encryption?

Tiger is a 192-bit cryptographic message digest (hash function).

A design goal of an ideal hash function is to distribute the input entropy evenly over the message digest.

If an input string of 40 bytes with 28 bytes (224 bits) of entropy is hashed by Tiger, the resultant 192-bit string will have at most 192 bits, since the output cannot have more entropy than its size.

If the input string has 28 bits of entropy, the resultant 192-bit string will have at most 28 bits, since the output cannot have more entropy than the input.

A hash function is not encryption.


Difference between Tweak and nonce What are diffrences between tweak and nonce?

I only know that nonce is used only once but tweak can be used for more than one time.but still by this diffrence I can't diffrentiate tweak and nonce

They are somewhat similar. A nonce is a more general concept which might occur in modes of operations or protocols whereas a tweak almost always refers to a tweakable blockcipher.

A nonce is a number that must be used only once. Of course there are now nonce-misuse resistant constructions which decrease the impact of accidental nonce reuse but in general you lose security if you reuse a nonce.
A tweak on the other hand can quite naturally be reused. One of the original uses for a tweak was for disk encryption where the tweak would depend on the position on disk. This will make the same plaintext encrypted with the same key give different ciphertexts.

In a way a tweakable blockcipher allows using more simple modes of operation without nonces. You don't have to chain blocks in complicated modes anymore to make sure that blocks cannot be compared or replaced you simply use "ECB mode" with a different tweak for each position.

So they somehow accomplish the same goal but nonces do so on the mode-of-operation level and tweaks directly on the blockcipher level.


Z*p Generator (Cyclic Group) in java I am trying to implement ElGamal in java without using the in-built libraries. The problem occurs when I am trying to find the generators of the number(in this case 11). Everything works perfectly except that it is returns 10 as a valid generator of 11(which it is not, right?)

public void generateKey()
{
    SecureRandom r = new SecureRandom();
    BigInteger i ;
    //i = new BigInteger(2048, certainty, r);
    i = new BigInteger("11");
    ArrayList<BigInteger> numbers = new ArrayList();
    boolean safePrime = isSafePrime(i);

    numbers = zGenerator(i, safePrime, 10);

    System.out.println(numbers);
}

public boolean isSafePrime(BigInteger i)
{
    return i.subtract(BigInteger.ONE).divide(new BigInteger("2")).isProbablePrime(90);
}

public ArrayList<BigInteger> zGenerator(BigInteger i, boolean safePrime, int count)
{
    Set<BigInteger> numbers = new TreeSet<BigInteger>();

    if(safePrime)
    {
        BigInteger num = new BigInteger("2");
        BigInteger exp = i.subtract(BigInteger.ONE).divide(new BigInteger("2"));
        do
        {
            if(num.modPow(exp, i).compareTo(BigInteger.ONE) > 0)
                numbers.add(num);
            else
                numbers.add(num.negate().mod(i));
            num = num.add(BigInteger.ONE);
        }while((--count > 0) && (num.compareTo(i) < 0));
    }

    return (new ArrayList<BigInteger>(numbers));
}

Output: [2, 6, 7, 8, 10]

I even tried using $g^q=p-1 \bmod p$

Well, if $g$ is a generator of $\bmod\  p$ for prime $p$; that is, if all values in the range $[1, p-1]$ are possible values for $g^i \bmod p$, then we have $g^a \neq 1 \bmod p$ for any $a = (p-1)/r$ where $r$ is a prime factor of $p-1$.

You select $p$ to be a "safe prime", that is $p-1 = 2 \times q$ where $q$ is also a prime.  This implies that, in this case, there are only two values of $a$ that are of interest:

$a = q$ (with $r = 2$), this implies the condition that $g^q \ne 1 \bmod p$
$a = 2$ (with $r = q$), this implies the condition that $g^2 \ne 1 \bmod p$

Both conditions must be true, however your code tests only the first condition; it doesn't test the second.  Now, it turns out that the only possible values of $g$ that do not meet this second condition is $g=1$ (which doesn't pass the first either), and $g=p-1$, or in your case, $g=10$.

Because you're not testing this second condition, you're seeing $g=10$ as looking like a generator when it is not.

Now, $p-1$ is the only value which is excluded by this second condition, in practice it's probably easy just to test values in the range $[2, p-2]$, and not bother explicitly testing this second condition.


Verifiable delay functions vs Proof of Sequential Work I've read recent papers about verifiable delay functions (Boneh et al 2018) and proof of sequential works (Cohen et al. 2018). I understand that the core difference between the definitions is that a VDF output is required to be unique (while in PoSW constructions - many commitments can prove knowledge of the same x w.h.p.).

But... why does it matter? Namely, what are the applications that use VDF, and that rely heavily on this uniqueness property such that replacing the VDF with the PoSW won't suffice?

For example, the Randomness Beacon - one of the basic motivations for VDF, can use PoSW as well, no?

A typical thing which you cannot do with a proof of sequential work is achieving time-lock encryption. In time lock encryption, you want the user to be able to retrieve the hidden message only after some time (i.e., you want to "send a message to the future", as its inventors initially put it). With a VDF, you can use the unique secret to mask the secret message $m$ which you want to send to the future; with a proof of sequential work, there is no clear way of masking a message such that retrieving it requires solving the puzzle (except in an interactive way, where another party checks the proof of sequential work and send $m$ if the check passes).

See also the discussion page 23 of this paper: proofs of sequential work fail to replace timed commitments in protocols that seek to achieve fairness. I believe that VDFs, on the other hand, can be used here, since they do not suffer from the limitation that prevents proofs of sequential work to be usable here - namely, that one can lie to the verifier about what was the solution to the puzzle we solved, even though one must still invest a given amount of sequential work to solve the puzzle in the first place. With VDFs, you cannot lie this way.


Why can't one implement bcrypt in Cuda? I had heard that although it's easy to implement message digest functions like MD5, SHA-1, SHA-256 etc. in CUDA (or any other GPU platform), it is impossible to implement bcrypt there.

bcrypt is different from these hash functions, in that Blowfish is a block cipher, and in order to produce a one way hash a "feed back" is used.

I am not too familiar with the GPU platforms. Does anyone know if bcrypt can be ported to a GPU and if not, why?

It is not impossible, only harder. This is because of RAM. In a GPU, you have a number of cores which can do 32-bit operations. They will run at one operation per cycle and per core, as long as they operate on their respective registers. RAM access, however, is more troublesome. Each group of cores has access to a small amount of shared RAM, and all cores can read and write the GPU main RAM, but there are access restrictions: not all cores can read from or write to RAM simultaneously (constraints are stricter for main RAM).

Now bcrypt is a variant of the Blowfish key scheduling, which is defined over a table (a few kilobytes) which is constantly accessed and modified throughout the algorithm. Due to the size of the table, each core will have to store it in the GPU main RAM, and they will compete for usage of the memory bus. So bcrypt will run -- but not with full parallelism. At any time, most cores will be stalled, waiting for the memory bus to become free. This comes from the type of elementary operation bcrypt consists in, not from the fact that bcrypt is derived from the key schedule of a block cipher.

For SHA-1 or SHA-256, computation entirely consists in 32-bit operations on a handful of registers, so a password cracker will run without doing any memory access at all, and full parallelism is easily achieved (I did it on my GeForce 9800 GTX+, and I got about 98% of the theoretical maximum speed with a straightforward unrolled SHA-1 implementation).

For details on the programming model in CUDA, have a look at the CUDA C Programming Guide. Also, the author of bcrypt now proposes scrypt (edit: actually that's not the same person; the author of scrypt is Colin Percival, while bcrypt has been designed by Niels Provos and David Mazières), which is even heavier on the memory accesses, exactly so that implementation is hard on GPU and FPGA.


Searchable encryption vs Homomorphic encryption For a search algorithm, what are the differences between using searchable encryption (SE) and using homomorphic encryption (HE) ? What are the advantages or disadvantages of using one of the above over the other if the requirement is a method for "searching"?

Does this only depend on the particular scheme/algorithm chosen in each of these types of systems ?

Searchable encryption is a form of encryption where you can search for ciphertexts whose decryption satisfying some condition without decrypting those ciphertexts and looking at the decryption. The end result is typically a collection of ciphertexts.

Sometimes a secret key is needed to create a "search token" for a given query.

Searchable encryption for limited types of search is often quite efficient, but it tends to leak information.

Fully homomorphic encryption (FHE) is a form of encryption where you can do (a limited form of) computations on the decryptions of ciphertexts without decrypting those ciphertexts and looking at the decryption. The end result is an encryption of the result of those computations.

You can use FHE to do searchable encryption in various ways. This typically results in a very flexible form of searchable encryption that does not leak much information, but also quite inefficient (since FHE is currently rather slow).


Small signature for packets using asymetric encryption? The smallest signature sizes that I can find are for elliptic curve public key systems where the signature is 4 times the security level (2 x the key size). In my case I can change the key every day, after which it is OK if the key is revealed.

So my questions are:

is there a more efficient signature than 2 x key size?
what would be the minimal acceptable key size for implementations over the next 10 years or so. Looking at a table of key size vs. operations to crack I get a 108 bit ECC key requires 1.8 x 10^8 MIPS, but I'm not sure how to interpret MIPS these days when graphics processors are so powerful. Is 1.8 x 10^8 MIPS a lot of compute power?

A Signature-Scheme known for it's short signatures is the Boneh-Lynn-Shacham (BLS) Signature Scheme, that uses not only Elliptic Curves but Bilinear Pairings over the curve.
The paper can be found here and lists signature sizes provided. For example the paper states that you can

  … get a signature of length 154 bits with security comparable to 320-bit DSA or 320-bit ECDSA …


Does the public key and private key for WhatsApp only remain within a WhatsApp account The world of cryptography is starting to really intrigue me admittedly. I initially hated it because it looked too hard Mathematically but now it looks cool :)

Got a good question for the experts and nerds on this forum. I got like a feeling that WhatsApp works by making use of public keys and private keys encryption. That would mean that Sender A would send a message to Sender B using Sender Bs public key. My question is, where would the private key of this recipient be stored, like within their account?

Also, how would the whole key thing work in a WhatsApp group as there are multiple users involved?

Like I said, I am just interested and want to hear from the experts here

I got like a feeling that WhatsApp works by making use of public keys and private keys encryption.

That's correct, WhatsApp uses Curve25519.

  My question is, where would the private key of this recipient be stored, like within their account?

The keys are generated client-side, so they should be stored on your phone.

  Also, how would the whole key thing work in a WhatsApp group as there are multiple users involved?

According to their paper:

Traditional unencrypted messenger apps typically employ “server-side fan-out” for group messages. A client wishing to send a message to a group of users transmits a single message, which is then distributed N times to the N different group members by the server.

This is in contrast to “client-side fan-out,” where a client would transmit a single message N times to the N different group members itself.

The exact procedure

The first time a WhatsApp group member sends a message to a group:

The sender generates a random 32-byte Chain Key.
The sender generates a random Curve25519 Signature Key key pair.
The sender combines the 32-byte Chain Key and the public key from the Signature Key into a Sender Key message.
The sender individually encrypts the Sender Key to each  member of the group, using the pairwise messaging protocol explained previously.

For all subsequent messages to the group:

The sender derives a Message Key from the Chain Key, and updates the Chain Key.
The sender encrypts the message using AES256 in CbC mode.
The sender signs the ciphertext using the Signature Key.
The sender transmits the single ciphertext message to the server, which does server-side fan-out to all group participants.

The “hash ratchet” of the message sender’s Chain Key provides forward secrecy . Whenever a group member leaves, all group participants clear their Sender Key and start over.

Important here is point number 4:

  The sender individually encrypts the Sender Key to each member of the group, [...].

If you need even more details then you can click here to download their whitepaper.