texts: ECDSA: What is the purpose of adding a hash of the used certificate to the signed data?

texts:
I recently started looking into security mechanisms used for Car2Car communication according to DSRC/WAVE and ETSI.

What I found so far is that each packet is signed using ECDSA mechanism.
Also each packet either contains the certificate that is used for signing or some hash value identifying that certificate.
This certificate contains the public key that can be used to verify the signature.

What puzzles me is the way the signature is created.
I am aware that not the whole message is used for signing, but only a hash value.
But the way this hash is created, looks a bit strange to me:

Hash ( Hash ( Data ) || Hash ( SignerInfo ) )

where Data is the message or part of the message to be signed and SignerInfo refers to the certificate in use (or to an empty string in some cases).

Why is this second part required?

Hashing the message as well as hashing the certificate does not include any secret credential as both are transmitted within the message.

Given the public key from the certificate I can validate that the related private key was used for signing.

While the length of the 2 hash values isn't very large, it still means that I have to run a second round of hashing which is probably not done "just for fun".

Which benefit do we gain from this extra step?


texts: How to encrypt plain-text message using Diffie-Hellman algorithm

texts: Let's say bob says Hi and Alice says Hello, With the knowledge of n and g, how can we encrypt those message using Diffie-hellman or any ECDH


texts: What are some of the best prime factorization algorithms and their effecitvity

texts:
I was wondering aren't the most used prime factorization algorithms a symbolic mile behind the security of the RSA cryptosystem?
The way it looks to me is that every time an algorithm is able to crack RSA or in specific to find the two prime factors, you can just simply change the size of the prime factors.
Is it really that simple?
Anyways thank you all for your time and effort!


texts: Verify hash of plaintext through ciphertext

texts:
Suppose that Alice runs a paid archival service.

Bob wants to download a well-known plaintext M with hash H(M) from Alice by sending her the hash.
Alice does not want to send M to Bob without Bob paying and Bob does not want to pay unless Alice sends him the real thing.
Thus, Alice encrypts M with some temporary key K into: E(M, K) and sends that to Bob alongs with H(K).
Bob checks that E(M, K) is indeed M encrypted with K, knowing only {E(M, K), H(K), H(M)}.

Is step 3 possible under some crypto system?


texts: How long would it take all of the supercomputers or cloud computing on Earth to bruteforce a significantly long password?

texts:
I was arguing with a colleague who thinks that SHA256 (password + 64 character static salt) is "insecure." My argument is that nothing in cryptography is "secure," it's all a sliding scale, and the amount of time it would take to bruteforce such a combination would be so long (I'm thinking over 30 years) that for all intents and purposes it is "secure." His argument is that because SHA256 hashes are so quick to generate, you can crack something like this using all of the computers on Earth quite easily, and as such, it's "insecure."
I agree that using something like Bcrypt is "more secure," but I wouldn't consider the above "insecure" because of the difficulty in cracking such a thing.  If we factor in Moore's law, which argument is correct? And how about if we change that 64-character salt to a
128-character salt?
I feel like this is an argument about semantics, but it annoys me that someone can have such a black-and-white perspective that "this is insecure (SHA256 pass + insanely long salt), but this is secure (Bcrypt)". I understand that something like Bcrypt is obviously preferred and "more secure," and I could see the argument that the other approach is "less secure," but to say one is "secure" and the other is "insecure" is to me a fallacy.


texts: Security issues of a MAC-then-Encrypt-then-MAC approach?

texts:
Encrypt-then-MAC does provide ciphertext integrity, but no plaintext integrity. With MAC-then-Encrypt it’s the other way around: Plaintext integrity but no ciphertext integrity.

What comes to mind is that it could make sense to use both to fix that “partially missing integrity” issue:

$$\tt …\ MAC_2(ENCRYPT(plaintext,MAC_1(plaintext)))$$

Trying to research if this would introduce more problems instead of solving them, I wasn’t able to find any useful papers that provide a security analysis of this approach. Also, I wasn’t able to find any papers discussing related schemes.

Ignoring potential speed impacts and focusing strictly on the security aspects… is there any obvious reason I’m not seeing why such a scheme should not be considered in the first place? Or do related references/papers exist and I was simply too inapt to find them? (If, what should I be looking for?)

EDIT:
As some confusion was expressed in the comment area – please note that the above LaTeX merely represents a readable hint at what I’m talking about. It is not meant to describe a whole formula (which I assumed be clear due to the prepended “$…$” and the fact that there is no $key$ in the above LaTeX either). The reason to prefer posting a hint instead of a complete formula was simple: the complete formula renders/formats much less readable and could have confused some people – which I wanted to prevent. Obviously, “what is less confusing to some, is more confusing to others”. That’s something I honestly hadn’t anticipated…  my bad. Here’s the whole thing:
$$CypherText = IV || Encrypt(PlainText || MAC_1(PlainText, MacKey_1), IV, CipherKey) || \\
MAC_2(IV || Encrypt(PlainText || MAC_1(PlainText, MacKey_1), IV, CipherKey), MacKey_2)$$
Don’t even ask how this would look if I wouldn’t be using a <sub> tag… yet, it may help understand why I opted-in to posting a hint.


texts: Is it feasable to combine ECB and CTR block modes of operation?

texts:
Both ECB and CTR block modes have advantages over other block modes. They both support parallel encryption and decryption and random reads/writes. Yet both have major disadvantages: (I'm assuming AES block sizes)

ECB produces repeating patterns for the same 16 bytes of cleartext
ECB can be shuffled in 16 byte blocks, which results in the cleartext to become shuffled the same way
CTR xors the clear text to an encrypted nonce+counter. If nonce and key are reused, you can create an XOR key for encrypting/decrypting any AES-CTR encrypted file/message which uses the same key and nonce (This is mainly useful when you can encrypt data, but not read the key/nonce back from the HW AES)

Combining ECB and CTR (By first encrypting the data with ECB,then the ciphertext with CTR) will still allow parallel encryption/decryption and random reads/writes. Yet if you shuffle the blocks, the blocks that changed locations are completely broken. Plus you can't just create an xor key using the same key/nonce, as the data is then still encrypted with a different key. This will also double the key size.

My question is: Does this block mode exist? What are the main problems with an block mode like this?

EDIT:
The keys for both encryptions are different, which makes it unlikely that both the ECB and the counter encryption produces the same ciphertext.


texts: How can a XOR encryption be cracked systematically?

texts:
It's given that a string, encoded in hex format, is obtained by XOR encryption of a plain text and a key. The key is unknown (not even the length). What are the steps that I should follow to get the plain text? Since I am new to this, I am unaware of the tools to be used.

Example:  Crack the following hex encoded string, obtained by XOR cipher:
000000003f2537257777312725266c24207062777027307574706672217a67747374642577263077777a3725762067747173377326716371272165722122677522746327743e

PS: I know that by applying XOR on the cipher text with the key will give me back the plain text. How should I proceed, if I don't know the key?


texts: Are there any hash functions that use integers of arbitrary bit size (e.g., int63)?

texts: More precisely, I am looking for hash functions where the internal state can be decomposed as a vector of integers of size 63. That is, machine integers where one of the bits is fixed and unusable.


texts: Why does Merkle's Puzzle requires Eve quadratic complexity of effort to break the system?

texts:
The way Applied cryptography 2ED explains the puzzle is as follows (I paraphrase it):

Bob generates 2^20 messages of the form x,y where x is a puzzle number and y is the secret key. Both x and y are different for each of the one million message. Encrypt each message using symmetric cipher with a different 20-bit key. Send all messages to Alice.
Alice picks one at random and brute force it. She should be able to recover x and y.
Alice encrypts her message to Bob by using y she just recovered (using symmetric cipher). Her message will contain x, the puzzle number.
Bob looks up the secret key for puzzle x and decrypts the message.

According to the book and many Internet sources, Eve would have to do theta(n^2) work to brute force the communication.

The book doesn't seem to say much about how x is included in Alice's response to Bob. It must be not be encrypted right? Because Bob has to do a O(1) look up. That is, Alice would have to send x+E(private message, y) to Bob.

Then why can't Eve just wait for Alice's response to Bob and compute that puzzle?

This is the brute force algorithm I think would satisfy 2^n if x is encrypted in Alice's response as well.

for y in 2^20:
   for x in 2^20:
       c = symmetric_enc(y, x)
       if c == c_from_alice:
           return yes, c, x, y
return no, none, none, none

But if x is encrypted in Alice response, then Bob have to brute force like Eve too, no?


texts: Short integer solution lattice problem with q=2

texts: For large values of $q$, we know that there are worst-case lattice problems which reduce to the average-case short integer solution (SIS) problem. Does this means that for $q=2$, the SIS problem is NOT hard-on-average?


texts: Last Sbox of a block cipher for Linear Cryptanalysis

texts:
I figured I should try to learn about linear cryptanalysis with a super simple cipher with only one Sbox. The problem is that with that approach the last subkey bits seem to be involved in the linear approximation.

It looks like I need at least 2 Sboxes, keeping the last one to bring randomness in case of a bad guess on the bits of the last subkey. So obviously, the last one should also not appear in the linear approximation.

Is that understanding of Linear Cryptanalysis correct?


texts: Do I need to keep a 64-bit version number secret?

texts:
Assume the following structure:

version | iv | ciphertext | HMAC(version | iv | ciphertext | ..., key)

The version starts out to be a "random" 64-bit number. It identifies the key used to encrypt the ciphertext for the purpose of key rotation (version is not, nor does it contain any part of the key). For every message encrypted by the same key, version is the same. The rest of the text, starting with a random iv, is always different.

Is there any reason I need to protect version? If an attacker knows the version the most they can do is identify a group of ciphertext that was encrypted with the same key.

The ciphertext itself has validity period of it's own. The data should be updated around the same time as the key is rotated. The rational behind version is to allow the ciphertext to be updated gradually as-needed.

Would obscuring the version in some way add any benefit, even small? Something like this:

$Version_n \oplus Hash(iv)_n$

I know this adds no real security benefit. If version doesn't need to be protected, the most I'm going for is to make it appear random.


texts: Would a pictographic, phoneme-based, hand cipher be difficult to crack with computer crypt-analysis?

texts:
What I'm talking about is a hand cipher which uses phonemes instead of individual characters and pictograms instead of the usual shuffling/substitution methods (e.g Caesar, Solitare, Vignere).

The pictograms would be composite images made from smaller images that represent each phoneme in the word. These images are are drawn by hand.

Would this deter computers at all in breaking the cipher? (I'm thinking it would be difficult to input the images for analysis given our current image recognition utilities).


texts: Post quantum security of the BLAKE family

texts: Is there any proof that BLAKE (including 2 and 3) is post-quantum secure? We know that as Merkle–Damgård (with proper padding) preserves collapse sha2 is post-quantum secure. I know that the sponge-based winner of the sha3 competition does not have such a proof. Since BLAKE uses neither of these constructions has there been any research as to whether it's construction is post-quantum secure?


texts: Choosing the Bernoulli distribution for LPN encryption scheme

texts:
The symmetric-key encryption scheme from [1] is based on the LPN (learning parity with noise) problem. The definition of the problem is, informally, that the adversary cannot recover $\mathbf{s}$ from $\mathbf{A} \cdot \mathbf{s} \oplus \mathbf{e}$ given $\mathbf{A}$, where $\mathbf{A}, \mathbf{s}$ and $\mathbf{e}$ are some random (public) matrix, the secret and the noise vector, respectively. The noise $\mathbf{e}$ is sampled from a Bernoulli distribution with parameter $\eta$.

My understanding is that typically $0 < \eta < 1/2$. But the lower $\eta$ is, the easier it is to break LPN (when $\eta$ is 0 LPN can be solved using Gaussian elimination). Suppose I need a security level of, for example, 80 bits, how do I select the value of $\eta$ if other parameters are fixed? I understand [1] provides some concrete parameters, but it's unclear to me how to calculate the security level from a concrete value of $\eta$.

[1] https://link.springer.com/chapter/10.1007/978-3-540-70583-3_55


texts:
I am trying to figure out AES in two rounds with 128 keys. If I have a known plaintext and the ciphertext that comes from this procedure. I get another plaintext which is similar to the previous with the difference of only one byte. I don't know the keys. Everything is  128 bits. How much will be the final ciphertext be affected?

I am taking this step by step for the two plaintexts (with one-byte difference) and I see that:

XORing with the first key: Only the different byte will change.
Byte substitution: Comparing the result of the 2 cases everything will stay the same except form the different byte.
Shift byte: The two outcomes will change the same way and the different byte will still be one just in a different place.

(is that correct so far?)

Then comes the mixcolumn... Here I am confused as to how much the result will be affected if I compare the two cases.

Any help with that?


texts: Zero-knowledge proof for committing a choice?

texts:
Let's say there are 100 choices (which are publicly known), each represented as a different string, and today you have to choose one of them. You need not reveal what that choice is right now, though. One thing you could do is take your choice, append a bunch of entropy at the end, and publish your signature of the resulting string. Later, to prove that you made a valid choice, you can publish the string, proving that you had decided on that choice by the time you published the signature.

However, this still requires you to ultimately reveal your choice in order for others to verify that you did indeed select one of the 100 choices and didn't try to pass off some garbage string. Is there a zero-knowledge protocol, such that you can let others verify that you indeed chose one of the 100 choices without leaking any information? That is, we want the advantage of an adversary trying to guess your choice to be still only 1/100. If not possible, anything under 1 (which would result from directly revealing your choice) would nonetheless be an improvement.


texts:
In this lecture the lecturer notes that the projection of the vector $b_2$ onto the vector $b_1$ will always result in a vector that lies between $-b_1/2$ and $b_1/2$. Why is this statement true?

I recognize I could be mis-reading these lecture notes. More generally my question is: What is the significance of the value $1/2$ within the first property of a LLL-reduced basis?


texts:
I have this curve in $E(\mathbb{F}_{131})$: $$Y^2 = X^3 + X + 2$$

I want calculate the sum $P + Q$ considering that $$P= (5,1) \quad Q = (60, 49)$$

For calculating the result I use these formulas:

$$\begin{align}
x_r &= \left(\frac{y_2-y_1}{x_2-x_1}\right)^2 - x_1 - x_2\\
y_r &= -y_1 + \frac{y_2-y_1}{x_2-x_1}(x_1 - x_r)
\end{align}$$

I need to obtain as result of $P + Q = (127 , 14)$ but something that I do is wrong. Can someone show me how I can calculate this sum?


texts: Signal Key Stretching Regarding Their Blog Post

texts:
I just read this blog post (Signal - Technology Preview for secure value recovery) by Signal and something is not quite clear to me. In section "Stretching beyond a KDF" they generate a stretched_key on the client side using stretched_key = Argon2(passphrase=user_passphrase, output_length=32). Argon2 needs a salt and other parameters (iterations, parallelism, etc.) as far as I know.

Now my question is: How do they store this salt (and Argon2 parameters)? Since a user could delete the app and later want to login again, it has to be stored on the server or the salt and parameters need to be the same for all users. If it is indeed stored on the server, how do they protect it? Or is it sufficient for "key stretching" purposes to use the same salt and parameters for all users?

Hope somebody can help me out here.
Cheers!


texts: How is key length of feistel cipher calculated?

texts:
In Feitsel Algorithim

If our block size is n, then our key length would be n x 2^n .

But this does not make sense for me.
For example: Let's assume that we have 4 bit block size. If our block size is 4, how can the key length be 64 bit?


texts: How to encrypt huge amount of data using AES-CTR

texts: As far as I know, AES-CTR depends on nonce. If I will use same key and nonce for encrypting 1 block of data and another - it will be unsecure. So, how can I encrypt a huge block of data (about 1GB) using AES-CTR?


texts: Understanding the impact of partitioning oracle attacks on stream ciphers

texts:
Yesterday I came across some conversation discussing partitioning oracle attacks, against authenticated stream ciphers like ChaCha20 and Salsa20 with poly1305 for MAC.
As I understand it (though the paper is a little dense), the exploit requires:

an interactive client/server where messages are encrypted under keys derived from passwords.
the encryption is "non-committing".
The server responds indicating if decryption was a success.

Though this discussion raised a number of concerns for me:

These multiple key things seem crazy, I always understood symmetric ciphers like ChaCha20-256 required searching a $2^{256}$ bit keyspace for a single correct key. I read that you can actually calculate using linear equations approx 200,000 valid keys for decryption. Is this really true, if so we shouldn't consider the bit-strength $2^{256}$ even for ECDH agreed on keys should we?

In an example local application where one uses say, libsodium's secret box (Xsalsa20+Poly1305) and Argon2 to derive a password and encrypt some file, if this file is stored on a system with no other API or info, is this vulnerable to this attack? (e.g. by calling libsodium and watching if the MAC primitive is successfully verified) or are "offline/stored" files like this safe? i.e. like a padding oracle attack, does this whole thing require that the server knows the correct key, and as such can give away information?

Is this only an issue with password-based keys? Doesn't this attack also mean one can reduce the keyspace for ECDHE agreed keys to $2^{256}/200k$ when destined for use with ChaCha/Salsa?


texts: In the RSA encryption system, are there not multiple messages m that give the same cipher text c?

texts:
For example:

p = 5, q = 11, n = 55

$\phi$(55) = 40

e = 3, $\phi$(55) and 3 are relatively prime

m = 3, then: $3^3 mod(55) = 27$

m = 113, then: $113^3 mod(55) = 27$

I heard that e and $\phi$(n) have to be relatively prime in order for the encryption to give unique solutions, but it seems that even if they are, multiple values for m gives the same encrypted c value. Is this not a problem? Or am I missing something or doing something wrong? I am asking if it is a problem that multiple values of m give the same cipher text c.


texts: LibTomCrypt Documentation on LRW Mode/Tweakable Block Cipher - Apparent Contradiction?

texts:
In the LRW mode discussion on page 34/161 of the LibTomCrypt manual, available here for example
https://opensource.apple.com/source/CommonCrypto/CommonCrypto-55010/Source/libtomcrypt/doc/libTomCryptDoc.pdf
there is the following comment:
"The tweak value is NOT a nonce or IV value it must be random and secret"
Nonetheless, in the original LRW article
https://people.csail.mit.edu/rivest/pubs/LRW02.pdf
this observation is made:
"We wish to carefully distinguish between the function of the key, which is to provide uncertainty to the adversary, and the role of the tweak, which is to provide variability.The tweak is not intended to provide additional uncertainty to an adversary. Keeping the tweak secret need not provide any greater cryptographic strength."
They also say:
"For this operator, we call the new (second) input a “tweak” rather than a “nonce”or “initialization vector,” but the intent is similar. "
And in the proposed TBC mode, the tweak plays an analogous role to the IV in CBC mode.
Would anyone be able to clarify the meaning of the author in the LibTomCrypt document? I am not expecting this to be an error, but nonetheless I cannot explain this seeming contradiction...


texts: How many bits of hash are realistically needed for key verification?

texts:
Say I'm connecting to a web server secured with TLS but with a self-signed certificate. Accordingly, I call the owners of the server and ask them what SHA1 fingerprint they have.

They start reading out the hex digits to me and I follow along, but before reaching the end, I just say "That's fine thanks, no need to read the rest." as I click the OK button.

How far along is the point where its reasonable to stop checking and still remain practically secure?


texts:
Let's assume a digital signature scheme such that there's a probability of 0.2 for two random messages to have the same signature.

How can I exploit this sheme?

I'm having difficulties in finding an exploit since the messages has to be random.


texts: Show that the equal difference property exits for a modified DES encryption system

texts:
My cryptology professor gave us this problem on a past homework assignment and I only managed to get one of the 3 parts correct. Needless to say, I want to know how to do the other two parts as well. The question is as follows:

  Consider the following DES-like encryption system that operates on 16-bit strings.
  The system takes the input and divides it into two 8-bit string $L_0$ and $R_0$.
  One round of encryption starts with $L_{i-1}$ and $R_{i-1}$
  and the output is $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus S(R_{i-1})\oplus K$,
  where $K$ is the key.

  The function S rotates the bits of $R_{i-1}$ to the right.
  More precisely, if $R_{i-1}=b_0\|b_1\|b_2\|b_3\|b_4\|b_5\|b_6\|b_7$
  then $S(R_{i-1})=b_7\|b_0\|b_1\|b_2\|b_3\|b_4\|b_5\|b_6$.

The two parts that I was not able to get are:

  1) Explain briefly why if $A$ and $B$ are bit strings, then $S(A\oplus B)=S(A)\oplus S(B)$

  2) If $M$ is the plaintext, let $E_K(M)$ denote the process of encrypting $M$ using one round of the above process. Show that $E_K$ has the equal difference property, namely that if $A\oplus B = C\oplus D$, then $E_K(A)\oplus E_K(B)=E_K(C)\oplus E_K(D)$.

Anyway, if someone could provide a complete explanation (answer included) on how to the 2 above questions, I would greatly appreciate it! Thanks in advance!


texts:
My question is related to PBKDF2. I am unsure how to validate user entered password with already existing hashes and salts.

I have heard of the so called "length-constant" comparison which basically ensures that every byte is being compared rather than a simple string comparison. And this is part where I am confused about. When deriving a key using for example "Hello" as password and "Hello2" as salt the output of PBKDF2 will always be the same. So why is there a slow equals (length-constant) comparison method?

What is the correct way of validating passwords in PBKDF2?


texts:
We have a POS (Ingenico) that uses DES3-CBC encryption using a derived key.
It sends encrypted data, and 10 bytes size Key Serial Number (KSN). I tried to use CKM_DES3_CBC_ENCRYPT_DATA to derive the key, and decrypted the data using DES3-CBC mech. However, I get some gibberish data something like this:

\ufffd\u001dl\ufffdP\ufffdl\ufffd\ufffd\ufffd+\ufffd\ufffd[\ufffd\ufffdl\u0017\ufffd\ufffd\ufffd\u001f?E\ufffd[*\ufffdmd\u0014\u0009ay\ufffd\ufffd3\ufffd\ufffd

I am not sure if I am using correct mechanism to derive the key, or even using the correct mechanism to decrypt the data.

Can someone please help me understand what could have been wrong? Some info says I need to pad the KSN.

Edit: I asked a similar question on Github/PKCS


texts: Entropy of a random message chosen by an adversary from a subdomain

texts:
Assume we have a set of random bit strings: $S=\{s_1,...,s_n\}$, where each of them is of length $\lambda$ ($s_i\leftarrow\{0,1\}^{\lambda}$).

We give the set $S$ to an adversary who picks one of the set elements at will and outputs it. Let's $s'\in S$ be the adversary's choice.

Question: What is the entropy of $s'$?


texts: What measures can I do to prevent decryption of encrypted data?

texts:
This is entirely hypothetical, I'm working on securing some data and I want to make sure we do this properly.

If I have a list of information which is encrypted (say, using a 256 bit encryption key) and by chance somebody gets their hand on the list.

In this case, they do not know what the encryption key/method is or any of that. The only thing they know is that X value is equal to "some string".

Using this, I assume they can reverse engineer and find out what the rest of the information is.

What can I do to prevent (or greatly diminish the risk of) them being able to reverse engineer the encrypted data. If I use a longer key, would that make a difference?


texts: PRF and pairwise independent hash function

texts:
I'm confused with the concepts of pairwise independent hash function and pseudorandom function. They seem identical to me.

A family of hash functions $H=\{ h:U \to [m] \}$ is $k$-independent if for any $k$ distinct keys $(x_1, \dots, x_k) \in U^k$ and any $k$ hash codes (not necessarily distinct) $(y_1, \dots, y_k) \in [m]^k$, we have:

\begin{equation}\Pr_{h \in H} \left[ h(x_1)=y_1 \land \cdots \land h(x_k)=y_k \right] = m^{-k}\end{equation}

This definition is equivalent to the following two conditions:

for any fixed $x\in U$, as $h$ is drawn randomly from $H$, $h(x)$ is uniformly distributed in [m].
for any fixed, distinct keys $x_1, \dots, x_k \in U$, as $h$ is drawn randomly from $H$, $h(x_1), \dots, h(x_k)$ are independent random variables.

These properties are exactly the properties of a PRF, aren't they? So what is the difference between these two definitions?


texts:
It is my understanding that a KDF adds entropy, whereas a hash loses information.

I've read that KDF should be used to store passwords. I don't understand why we don't use a KDF and then a hash, so that – if the database of password is leaked – it would also be impossible to figure out the plain passwords.

So storing passwords in a database would be like this:

Use KDF to increase entropy (especially good if users are using short passwords),
Use a hash to lose information,
Store the hash.

Shouldn't this be the advised way to store passwords?


texts: Parallel MAC vs doubled rounds for SipHash, KMAC and others

texts:
SipHash 4-8 is documented by the authors as being about half the speed of SipHash 2-4 and is obviously the more conservative option.

I was wondering from a security perspective how this would compare with performing SipHash 2-4 with two different keys and XOR-ing the outputs? Albeit one would need 2 128-bit keys (as opposed to 1 128 bit key for 4-8), but one could then perform the individual hashes in parallel.

My intuition would be that even if there were an attack that breaks SipHash 2-4, the doubled key length would require that the attack reduce the security by at least half in order for this parallel construction to be less secure than SipHash 4-8.

Would this generalize as well to other MACs that use "rounds" of some form (e.g. KMAC could be represented in this way, HMAC not really)?


texts: Invalid challenge-ciphertext in IND-CPA and IND-CCA games

texts:
Consider the IND-CPA game between a challenger $C$ and an adversary $A$ for  a given public-key encryption scheme $PKE$:

$C$ generates a key pair $(pk,sk)$ based on some security parameter $n$, and publishes $pk$ to $A$. $C$ retains $sk$.
$A$ may perform a polynomially bounded number of encryptions or other operations.
Eventually, $A$ submits two distinct chosen plaintexts $m_0,m_1$ to the challenger $C$.
$C$ selects a bit $b \in \{0, 1\}$ uniformly at random, and sends the challenge-ciphertext $c=E(pk,m_b)$ (the encryption of $m_b$ using the public-key $pk$) back to $A$.
$A$ is free to perform any number of additional computations or encryptions. Finally, it outputs a guess $b'$ for the value of $b$.

The advantage of $A$ is $Pr(b=b')-1/2$.

The IND-CCA2 game is the same except that, in phases 2 and 5, $A$ has access to a decryption oracle, with the condition that $A$ can not ask for the decryption of the challenge-ciphertext.

My question is: Suppose that there is an adversary $A$ that has a non-negligible advantage in one of these games. Suppose that, in phase 4, the challenger $C$ sends an invalid ciphertext to $A$ (i.e., $C$ sends a ciphertext that is not the encryption of $m_0,m_1$ or any other message $m$). In this situation, what does $A$ answer? Does $A$ knows that the challenge ciphertext is invalid?

Thanks in advance!


texts:
I want to give an introductory talk on Diffie-Helman key exchange. Along the way, I will mention that there exist groups, like $(\mathbb Z/p\mathbb Z)^\times$ for which it is believed that the discrete logarithm problem (DLP) is hard. Trying to anticipate a question from the audience, suppose someone asks:

  Are there groups for which the DLP is surely known to be hard?

What is a good way to answer such a question, and in the case of no asnwer, how do I convince the audience that the Diffie-Helman key exchange is still worth the hustle?
I understand this is not good question to ask here, so I bring my honest apologies.


texts: What if using a block cipher as compression function in Merkle–Damgård?

texts:
The Merkle–Damgård construction builds a hash by iterating a compression function $F$, with $S_{j+1}=F(B_j,S_j)$ where $B_j$ is one of $n$ padded message blocks, $S_0$ is the IV, and $S_n$ is the hash.

Customarily, $F$ is built from a block cipher $E$ with block width the hash width and key size the message block size, as $F(B,S)=E(B,S)\boxplus S$, where $B$ is at the key input of the block cipher, and $\boxplus$ is some simple group operation (typically addition with carry suppressed across words, or perhaps just XOR).

What security property would suffer if we used $F(B,S)=E(B,S)$, e.g. in SHA-256?

I see only two obvious negative consequences:

For unknown message fragment $A$ of length multiple of the block size, with knowledge of $B$, $C$, and $H(A\|B)$, it would be trivial to compute $H(A\|C)$; sort of a length extension property on steroids, but nothing that breaks collision-resistance, first or second preimage resistance, or indistinguishably from a random oracle for one not knowing some arbitrary constant;
the IV would no longer be suitable as the only arbitrary constant unknown to the adversary in that random oracle model; but we could use a constant part of the definition of $E$ towards that, and there are plenty of such constants in the typical $E$.

On the positive side, the output of the hash of a long random message multiple of the block size would have practically as much entropy as the hash width, when there is less with the standard construction (like, 0.8272... bit less).


texts: Ed25519 choice of private key implementation

texts:
This answer to another question describes the different values chosen as private key and public key by various Ed25516 implementations. What are the advantages / disadvantages of each?

(Table cropped from diagram in the linked answer, originally taken from "How do Ed5519 keys work?" by Brian Warner.)


texts: How to prove that the Permutation cipher is not CPA secure?

texts:
Encryption scheme is called a permutation cipher if every plaintext string with letters
$a_1,\ldots, a_n$ is encrypted as $a_{\pi(1)}, \ldots, a_{\pi(n)}$ for some (not necessarily uniform) permutation $\pi$.

To break this cipher, one has to distinguish two messages based on their encryptions. I'm trying to solve this by playing a game.

Two players A and U.

A: send a plaintext message to U (in this example A sends followashore)

U: Encrypt this message and send the cipher text to A

Input size of $\pi$: m = 6
$\pi$: $\begin{array}2 &1 &2 &3 &4 &5 &6 \\ &3 &5 &1 &6 &4 &2\end{array}$
Ciphertext: LEFOOLHEARSO

A: Changes this ciphertext by appending text $p$ of length $l$, which is a multiple of the length of the original plaintext. Let's say A sends LEFOOLHEARSOLEFOOLHEARSO (concatenated the ciphertext with itself)

U: Encrypt this message using the previous permutation?

I'm not sure where to go from here.


texts: The example of Wikipedia on steganography doesn't work

texts:
I was reading some stuff on steganography.

There is an example on the wikipedia page :

However, I tried many software to get the hidden image, but no one worked. Is there anything wrong about that?

I tried OpenStego (Windows), SecretLayer (Windows) and VSL (Linux).


texts: What is the correct value for "certainty" in RSA key pair generation?

texts:
I'm creating an RSA key pair in Bouncy Castle and need to specify an int value for certainty.  This Stack Overflow answer says it is a relative test for how prime the values are.

There is another answer that says this value should be adjusted relative to the key length.

Question

What are the correct values for certainty relative to key length (how did you determine this?)
What does it mean to say "certainty of x bits" of a number?  (If it's possible to sub-divide a number and certify bits, which bits are being certified?)


texts:
In the Wikipedia article on Diffie-Hellman, the algorithm calls for a large prime modulus, $p$, and a generator, $g$, which is a primitive root of $p$.

As far as my knowledge of number theory goes, to find a primitive root of a prime number, you first need to determine the prime factors of $\phi(p)$, or $p-1$.

Obviously, 2 divides $\phi(p)$, but after that you are left with the problem of factoring a number that is the same bit size as the original $p$.

I was under the impression that the security of the system was dependent upon the difficulty of finding the prime factors of a big number in the first place.

What am I missing?


texts:
Our goal is find a faster discrete Gaussian sampling to solve $"SVP"$ problem in lattice:

A lattice is discrete subgroup of $R^n$ such that define as below:

let $\{b_1,\cdots ,b_n\}$ be a basis in $R^n$. Then $L:=\{a_1b_1+\cdots+a_nb_n | a_i \in Z\}$ is a lattice.

Shortest vector problem in $L$ is:

$SVP(L)$ = shortest non-zero $y\in L$.

This is a $NP-hard$ problem to solve. The best algorithm to improve approximation of this problem mentioned by "Discrete Gaussian Sampling". In this method, the TIME and SPACE computed $2^{n+ o(n)}$. What is the faster  discrete Gaussian sampling?


texts: Iterations of pollards kangaroo attack on elliptic curves

texts:
I want to understand the Pollard kangaroo attack on elliptic curves. I found this Pollard's kangaroo attack on Elliptic Curve Groups Q/A pretty helpful, but not complete. The posts provides a pretty good algorithm for the attack:
def pollardKangaroo(P, Q, a, b, N):
    # Tame Kangaroo Iterations:
    xTame, yTame = 0, b * P
    for i in range(0,N):
        xTame += Hash(yTame)
        yTame += Hash(yTame) * P
    # yTame == (b + xTame) * P should be true
    # Wild Kangaroo Iterations:
    xWild, yWild = 0, Q
    wildLimit = b - a + xTame
    while xWild < wildLimit:
        xWild += Hash(yWild)
        yWild += Hash(yWild) * P
        if yWild == yTame: return b + xTame - xWild
    # No result was found:
    return None

I did the algorithm on paper and it worked. $P$ and $Q$ are the points in the ECDLP: $Q = n\cdot P$. $a$ and $b$ give the interval, in which the attack searches for $n$. So the algorithm can only succeed if $n \in [a,b]$. Now I got two problems: The hash-function and the parameter $N$ are not explained/defined.
My questions:

Is the hash-function just a semi-random generator and can be pretty simple (e.g. H(point) = x + y + 1)?
How exactly is $N$ defined? What value should $N$ be? How does the value of $N$ affect the algorithm?


texts:
I am working on RSA CRT and there is a point that I don't understand :

So we have $n=pq$ and $c = m^e \bmod n$ an encrypted message.

To decrypt $c$ with RSA CRT, we have to compute :

$d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$

Why do we have to do a reduction $\bmod (p-1)$ and not $\bmod p$ ? (Same for $(q-1)$ and $q$)
Plus, next computations are made $\bmod p$ and $\bmod q$, right ?
($m_p = c^{d_p} \bmod p$ and $m_q = c^{d_q} \bmod q$)

To reduce modulo $p$ instead of $(p-1)$ to compute $d_p$ could allow attacks for example ?

Thank you in advance :)


texts: Compare two protocols of keyed hash functions

texts:
Authentication protocol using a keyed hash function: Alice and Bob share a secret key for a keyed hash function. The protocol is: Alice $\Rightarrow$ $m||h_{k}(m)$ $\Rightarrow$ Bob.
There are the following two methods: $h_{k}=E_{k}\circ h$ and $h_{k}=h\circ E_{k}$.
What are the advantages and disadvantages of the two protocols?
($E_{k}$ is a well designed one-key cipher and $h$ is a well-designed hash function. $\circ$ is function composition).
I was reading another question. And in our lecture notes, only the first one was mentioned, and the lecture notes says that if both components are well-designed, the first method should be secure. I have the following questions:

Why would the first method be secure?
What about the second method? The second was not mentioned in lecture notes, is it because it cannot be secure even if both components are secure?

Thanks!!


texts: Block cipher fixed points (plaintext equal to ciphertext)

texts:
A block cipher is a bijective map from the set of possible plaintexts to the set of ciphertexts, which are the same size and might as well be considered the same thing: $\theta: S\to S$. In this there must exist a fixed point m $\in S$ such that $\theta(m) = m$ (alternatively you could consider encryption to be a binary operator acting on the set $S$ then you could write encryption under key $k$ as $m \odot k = m$, with $m,k \in S$. Unfortunately this cannot form a group since there is no unit $e$ that makes $e \odot k = e$ for all $k \in S$).

It is clear that when the block size is equal to the key size a single fixed point will exist when you hold the plaintext message constant and permute the key. The key allows you to select one of all the possible possible unique mappings, of which one must surely be a fixed point (am I right about my use of the word unique here?).

What I don't understand is how a key that is longer than a block size provides any extra security. From what I understand this would suggest the existence of many fixed points, or equivalently many different keys that will decrypt a ciphertext.

Note: I would also be interested to see articles that apply algebra to the study of block ciphers. Specifically constructing groups to aid analysis that also consider the fact that a block cipher is a composition of several round functions.


texts: RSA keys are multiplicative inverse in mod phi(n), but also in mod n?

texts:
I understand that the RSA keys $pk$ and $sk$ are choosen such that one is the multiplicative inverse of the other, in $\mod \phi(n)$

But for the encryption and decryption to work, in other words, that

${m^{pk}}^{sk} \mod n = m$

holds, $pk$ and $sk$ must also be multiplicative inverse to each other in $\mod n$, right?


texts: How can I force slow decryption in the browser?

texts:
I have a string that I will encrypt on the server. I then want to send the encrypted string along with a decryption method for it to be decrypted in the browser.
I want the decryption to take some time for the end user. Let's say ~10 minutes.
Let me be clear:

I want the decryption to happen.
It must happen on the browser (I understand that some might cheat but let's assume I don't care much about these cases even if they happen).
It must take some time (~10 minutes).

I understand that decryption time depends on many parameters. You can assume that at least the string of data to be encrypted can be as small or as big as we need it to be in order to achieve the above 3 things. And we can assume the processing power of an average computer/browser.
Is this possible and how?
I am a JavaScript developer so a JS solution would be preferable. Some pseudocode/steps would also help.
I know nothing about cryptography so I would appreciate it if you could please refrain from using too much jargon I will probably not understand.


texts: Algorithm for symmetric encryption (diffusion without confusion)?

texts:
I'm looking for a symmetric encryption algorithm with specific characteristic. Having a key $k$ a message $m$ returns a ciphertext $c$, where $E_{k}[m] \rightarrow c$

It should be hard to perform a KPA. I believe the diffusion concept makes it hard to perform such an attack?
Yet I require that $k + x \rightarrow e$, $E_{e}[m] \rightarrow (c + x)$ where $+$ can be the sum operator in a finite field. I believe this will require to avoid the confusion concept?

Edit: From $E_{e}[m]$ I should be able to recover $c = E_{e}[m] - x$, or some other possible operation that can revert x.

Is there any algorithm with those characteristics? I do believe that a hash function can work for my use-case.


texts:
Is anyone aware of an algorithm/method that allows me to validate just a few letters (or other characters) from a password. For example, the application asks for the 2nd, 3rd, 6th and 9th letters from the password. Which letters are requested is determined randomly.

I really, really don't want to store passwords in plain text. This technique is used by at least one UK bank.

I this a good idea? Can anyone offer any help? I'm a fairly competent programmer.

1st Edit

When a password is required, the user is prompted to provide a random selection of the characters in their correct positions. This selection might be, say, the 2nd, 3rd, 6th and 9th characters, or might be some other selection, chosen at random. The only feedback that the user gets is "pass" or "fail". He cannot use this to probe each character in the password at his leisure.


texts:
So I have the m = p x q, p = 7 and q = 11

m = 77

S (which is the seed) = 4

Xi = 4^2 mod 77

from here I didn't know to continue the algorithm. Any help?


texts: I have to solve Hill's cipher. I have only cipher text: CGQIYN and key: CFDG. I don't know how to decrypt it, because in all videos I've watched they knew the Matrix key from the beginning. I don't want you to solve it, but I am really hopeless and I absolutely don't know how to do it. If you can provide me some procedure, I will be grateful. Thank you.


texts:
I have been following the medium post of Vitalik, where he shows step by step how to convert program --> Circuit --> R1CS --> QAP.
I am aware of the Pinocchio protocol, where they utilize the Groth13 QAP to generate proofs. I am also aware of Groth16, which improves QAP generation.
However, besides Vitalik's post, I haven't seen anyone in those papers talk anything regarding the R1CS constraints. Is this process somehow get done inside the QAP generation?
What am I missing?


texts: How hard is it to link a hardened BIP32 child public key to it's parent public key?

texts:
The BIP32 spec says this in the security section:
Note however that the following properties does not exist:
 * Given a parent extended public key (Kpar,cpar) and a child public key (Ki), it is hard to find i.

The spec doesn't say that this line is valid only for keys that are not hardened.
Is this true even if the child is hardened?


texts:
First of all, I just implemented AES because I wanted to understand how it works and as a challenge to see if I could do it and I won't use to encrypt anything important, ever.

The (German) Wikipedia article of AES linked to a flash animation which demonstrated precisely how AES-128 in ECB mode worked. I implemented AES exactly as shown in that animation and I am able to reproduce the same encrypted byte array they get in the result.

In that example the hex string: 328831e0435a3137f6309807a88da234 encrypted with the key 2b28ab097eaef7cf15d2154f16a6883c results in the encrypted hexadecimal string 3902dc1925dc116a8409850b1dfb9732 and I get the same result.

Encrypting given test vectors however does not work with my algorithm and neither does encrypting the examples given in the animation with an AES encryption tool (which encrypted the test vectors correctly) work. Is there anything wrong with that flash animation or am I missing something obvious?


texts:
I'm currently trying to write a server emulator for a multiplayer game. I've found what I believe to be the RSA keys. I've found that by editing them I can get the real login server to reject them saying they are corrupt, IE. not encrypted properly. So from that I can confirm they are the correct keys. However, I can't figure out how to generate my own because they are a little weird.

The modulus is 511 bits long and the exponent is 128.
Does this mean they are a 512-bit RSA key? When I generate my own, my public keys exponent is much smaller at only 17 bits long. How can I create my own key pair that is this strange size?

Sorry if this is a bad question, I am new to this.


texts: Does it matter whether the KDF salt is integrity protected?

texts:
I am writing a simple application, mainly as a fun challenge, but also to hopefully someday use as my password manager.

I'm using pynacl's SecretBox, which provides an extremely simple API to encrypt and MAC (presumably encrypt-then-mac, although the docs are a bit sparse on these details) data. In my application, the user is prompted for a password, which is then run through pynacl's KDF module to generate the key for the SecretBox.

Obviously, it's important to supply the KDF with a randomized salt, and if I want the file to be usable, I have to store that salt. At the moment, I am storing the salt in the first 32 (set by the pynacl constant SCRYPT_SALTBYTES); to read the file the application reads the first 32, stores that in a variable as the salt, and then reads the rest and passes that on to the SecretBox.

As a result, my salt has no integrity protection at all. The downside of the simplicity of the SecretBox API (literally a constructor, and encrypt and decrypt methods) is that there's no obvious way to sneak this extra bit of data into the MAC, and I'd rather avoid implementing my own encrypt-then-MAC scheme if possible as I'm not a crypto expert (A big part of why I chose this API is because of how idiot-resistant it appears).

Are there any concerns with allowing an attacker to modify the password salt in this context?


texts: Authenticated encryption using libsodium's crypto_box_curve25519xsalsa20poly1305

texts:
It seems that crypto_box_easy, generates a random nonce and appends it to the cipher text in libsodium.
I understand using the same nonce with the same key can be catastrophic with  salsa20poly1305, as such is it bad practice to re-use the same public/private (static) curve25519 keys when using crypto_box_easy?
Is it safe enough to assume that libsodium will ensure a random nonce is always used, or should curve25519 keypairs be regenerated on each use?


texts: Is there a cryptography algorithm that will remain safe if P=NP?

texts:
From what I heard, many encryption algorithms are based on the assumption that some problems are computationally hard, i.e, NP-complete. In the unlikely event that someone proves that P=NP, these codes will break.

Is there a practical encryption algorithm that will remain safe even if P=NP?
I.e, an algorithm that depends on problems that are more difficult than just NP-complete?

My guess is that the answer is no: to be practical, a code must be verified in polynomial time, i.e, the problem must be in NP. Is this correct?


texts: Universal hash functions with homomorphic XOR property

texts:
Let $H = \{h_r : U \rightarrow [m]\}$. What are the currently known most efficient algorithms such that $H$

is a universal family and
fulfils the homomorphic XOR operation property $\forall h \in H \forall x,y \in U: h(x \oplus y) = h(x) \oplus h(y)$?


texts: Hash functions with variable and fixed length inputs

texts:
I was told that a hash function (mostly looking at the SHA-* family) should have input strings of variant length provided first, and those of fixed length after (ie salt), in order to avoid some kind of collision attacks.

I haven't seen this explained anywhere, so I was wondering whether this holds and how so.

What I'm describing seems to be related to the length extension attack (also see Understanding the length extension attack) (thanks to Dan Anderson for bringing this up)


texts: Hash multiset to point on elliptic curve where $A = 0$

texts:
I want to hash a multiset to a point on the elliptic curve $y^2 = x^3 + 3$ over a finite field of some 254-bit prime order, where $P = 3 \pmod 4$. Moreover, I want this hash to be incremental, in that the hash of the union of the multisets should be the same as the elliptic curve group sum of the hashes of each multiset.

The basic strategy for achieving this is to hash elements of a multiset using some hash function into the elliptic curve group, and then compose the multiset hash using group operations.

There is an elliptic curve multiset hash in the literature, but it relies on a deterministic Shallue-Woestijne encoding of field elements into EC group elements. In general, there are a number of deterministic encodings of field elements for elliptic curves which are "safe" assuming the hash function used for the elements of the multiset is a random oracle, but they all either apply to curves over fields with characteristic $2$ or $3$, or require the curve equation $y^2 = x^3 + ax + b$ to have $a \neq 0$ (I was looking at this paper).

I'm also can't just take a generator $g$ in the EC and produce $\operatorname{hash}(elem) \cdot g$ as the hash of {elem}, as a generalized birthday problem may be employed to find collisions between multisets (assume the inputs to the hash are public).

My question is how safe against multiset collisions is hashing {elem} by just setting $x = \operatorname{hash}(elem)$, and incrementing $x$ until $x^3 + 3$ is a square? SW encoding was used in the paper for ECMH mentioned earlier, but if timing/determinism isn't an issue, can this simpler approach be used instead? This approach is called MapToGroup in this paper.

I also found a multiset hash similar to what is described in the post here, with $b = 7$ and some $256$-bit prime field.


texts: Signing an exchanged symmetric key that is asymmetrically encrypted

texts:
Consider the following implementation:

  Bob wants to communicate long-term with his team over an unsecured channel. Bob and all members of the team generate individual public/private keypairs (ex. RSA) and store/share their public keys on an untrusted key server.

  Bob, being the first member of the team, also generates a long-term random symmetric key for the team that he and all team members will use to encrypt their communications. Bob encrypts the team's symmetric key with his public key and also the public key of all current members of the team and stores them on the same untrusted key server.

  When new members are added to the team, Bob (or any existing member of the team that can add new members) takes his own encrypted version of the team's symmetric key from the key server, decrypts it with his private key, then copies and re-encrypts it with the new member's public key, storing it back on the key server for the new member to use for future communications with the team.

The problem with this implementation is that the symmetric key can be forged by Eve, a bad actor with access to modify the key server. Since public keys are all available, Eve could take Bob's (or any and all members of the team) public key and encrypt a new symmetric key on the key server. Past communications would then fail to decrypt, however, if gone unnoticed by the team any future communications could be read by Eve. If the forgery occurred when the symmetric key was first stored, no member of the team would ever know that Eve has been reading their communications.

I think that we need some sort of signature on the symmetric key exchange, however, where would the key material for this signature come from? How could we produce a signature in a way that each member of the team could privately verify that their version of the team's symmetric key is authentic? Maybe some other way?

Update #1

One solution could be for Bob to compute a hash of the symmetric key whenever he first generates it, then sign the hash with his private key and store it on the key server. Whenever members retrieve their copy of the symmetric key from the key server, they could also obtain Bob's public key, verify the hash's signature and recompute the hash to verify the symmetric key.

However, the problem I see with this solution is that it seems Eve could still forge a new symmetric key, sign it with her private key, and replace Bob's public key with hers on the key server. This would allow her to impersonate Bob's signature while other team members verify and use the forged symmetric key.


texts: Is BLS signature scheme strongly unforgeable?

texts:
I would like to know if BLS signature scheme is strongly unforgeable under adaptive chosen message attack. If it is not, is it possible to modify the BLS scheme in order to reach this property ?

Thank you in advance.


texts:
I have this question in which I m struggling. I have read in many sites about encrypt-then-mac etc.

If the confidentiality for transmission is needed, discuss the feature for the order of encryption and encode by error correcting code (ECC), i.e., 1) encryption-then-encode, 2) encode-then-encryption.


texts: Avoiding doubled letters in encrypted text

texts:
I have an encrypted string based on an "alphabet" of 29 runes and access to successfully decrypted (runes->English) plaintext. Testing for a Vigenere cipher, I tried a Friedman attack (aka Kappa test, Index of coincidence test) to try and find a probable key length and obtained the following results for the index of coincidence (IoC):

IoC of decrypted plaintext: 0.0616742 (c.f. 0.065 for plain english)
IoC of encrypted text: 0.0332257
IoC of random choice: 1/29=0.0344828 (c.f. 1/26 for plain english)

(Mostly adapting the procedure outlined in method 3 of https://www.it.uu.se/edu/course/homepage/security/vt08/labs/lab1.pdf)

As you can see, the encrypted text has a lower IoC than random choice which I suspect is due to an engineered bias against doubled runes in the encrypted text.

Is this indicative that a Vigenere cipher was not used? Is such a bias characteristic of any other classical ciphers?

(Note: the IoC above were obtained from a string of ~250 encrypted runes and ~850 decrypted runes from a separate plaintext)


texts: Is there an algorithm for factoring N, which is just as simple as this one, but faster?

texts:
I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA (paywall-free).

It basically works like this:

You reverse the digits in $N$, let's call this value $Ň$
You pick an integer, $k$ (normally 1, but can be other values)
A variable, $Δ$, can be any integer value between the square root of $N$ and the square root of $Ň$

You then calculate four values, if any return a value other than 1, then you have one of your prime factors:

$\gcd[N, (k × Ň) + Δ]$
$\gcd[N, (k × Ň) - Δ]$
$\gcd[N, (Δ × Ň) + k]$
$\gcd[N, (Δ × Ň) - k]$

Using this algorithm and the GMP library, it would factor 18014417929109603 in 3 seconds.

I was wondering if there were any other algorithms which were faster than this, but just as easy to implement? I know the GNFS is the fastest, but it is also incredibly hard to implement.


texts: Could this Method be Used to Create a highly Compressed Alternative to Merkle Proofs?

texts:
See equation below as I see an easier alternative, as I'm having trouble explaining it. Is there a hash function where many hashes can be combined together in a way where any single hash can be combined with a hash of the rest of the hashes to generate the hash of all hashes?

Seems to me like a hash that fits this property might exist.. and be an excellent way to seriously compress Merkle proofs very significantly.

Example:
Let's say you want to hash 4 blocks of data together

A  B  C D

And in my below equations:
() = hash
+ = some function that combines together the hashes append, xor, and, etc.

Is there a hash where this property is true:
(A + B + C + D) = (A) + (B + C + D) = (A) + (B) + (C + D) = (A + B) + (C) + (D) = (A + B + C) + (D)

Alternatively would be ideal, but I see this being harder to do:
(A + B + C) = (A) + (B + C) = (B) + (A + C) = (C) + (A + B)

This would mean that instead of providing proof at every level of a tree, you could instead submit 2 hashes as well as the root hash to prove that an item is included.

Imagine that this was used as an alternative to a Merkle tree for 128 items. Instead of submitting 7 hashes to prove you own one, now you only have to submit 3. This would lead to a compression of roughly 60%

In fact, any Merkle proof for more than 8 items would still only require 3 hashes to prove it's correctness. Use it for something like Zero-Knowledge Proofs with millions of items and seems to me like theoretically, you could compress the data structure by 90% or more.

Which leads to my final question:
Do you know of a hashing function that could work like this and have this property? I don't understand hashing well enough.


texts: Derive $x$ when given $g,g^x$ and $g^{(1/x)}$?

texts:
If an adversary has access to the generator g of a group G and is given access to $g^{x}$ and $g^{(1/x)}$, will it make it any easier to derive the value of $x$ compared to when he had access to only $g$ and $g^{x}$?

EDIT: My question is different from “Can we reduce Diffie-Hellman problem to “Discrete-log inversion” problem?” as in this case the adversary has the values and does not need an oracle to derive it


texts: Can you tell me how to create a cipher please? just a little simple one

texts: I don't how to make a cipher text at all, can you help me?


texts: Exchanging Keyspace and Message space in PRF

texts:
Suppose there is a secure PRF $F: K \times X \to Y$. Then is $F': X \times K \to Y$, defined by $F'(x,k):=F(k,x)$, a secure PRF?

In my opinion it should be because exchanging the keyspace with the message space shouldn't effect the security. As we were choosing a random key from the key space, similarly we can choose a key from message space randomly and can use to compute $F'$. However, I am not sure about my intuition.


texts: Standard basis representation of elements in binary field

texts:
In Remark B.1 from this paper it says:

  We assume canonical representation for binary fields $\mathbb{F}$, given by an irreducible polynomial and a primitive element $g \in \mathbb{F}$ for it (i.e., $g$ generates $\mathbb{F}^*$). We use the standard basis {${1, g, g^2, ..., g^{n-1}}$} to represent $\mathbb{F}_{2^n}$ over $\mathbb{F}_2$.

I think I understand the first sentence, but the second sentence confuses me. Shouldn't there be $2^{n}-1$ elements generated by $g$? If so, the elements would be {${1, g, g^2, ..., g^{2^n-1}}$} - right? Am I missing something?


texts: How long must be the key of a stream cipher?

texts:
I am watching Lecture 3 (Stream cipher, random numbers and one time pad) by Christof Paar and perhaps its something that will be explained in another lecture but:
When he explains how XOR works, in the example he gives, plaintext X3.X2.X1 is encrypted with key S3.S2.S1 and becomes ciphertext Y3.Y2.Y1.
So if the plaintext is N-bits long...the key has to also be N-bits long?
If the answer is no and it can be an arbitrary number...wouldn't that be a block cipher?
If the answer is yes, does the sending and receiver end have to agree on the quantity of bits to be transmitted beforehand?
If this is random (ie. unknown beforehand), how can they know what key to use to encrypt and unencrypt if it has to be as long as the plaintext?


texts: Calculating minimum number of messages hashed a 50% probability of a collision (Birthday Paradox)

texts:
I encountered this while solving a crypto puzzle. This is the puzzle.
You have a hash which gives a 11-bit output. How many minimum messages do we have to hash to have a 50% probability of getting a collision.
Normally we see kind of problem being solved by using an approximation $2^{n/2}$ or $\sqrt {2^n}$
So for a 11-bit hash, the number of messages to hash to have 50% chance of a collision would be
$\sqrt {2^{11}} = 45.255 \approx 46$ messages
However, the solution for this puzzle uses
$log_{\frac {2^{11} - 1} {2^{11}}}{(0.5)} = log_{\frac{2047}{2048}}{(0.5)} = 1419.22 \approx 1420$ messages
So you have to hash approximately 1420 messages to get a 50% probability of having a collision.
The solution doesn't explain how they arrive at this. So which is the correct solution?


texts: How to decrypt Rabin message when p=q and you have the roots from Tonelli-Shanks


texts: Diffie Hellman unsafe prime vulnerability

texts:
I have done some research about how the DH key exchange is unsafe if an unsafe prime p is used (that is, $p-1$ has a lot of small factors). Many answers here on StackExchange claim that for any factor $r$ where $g^{\frac{p-1}{r}}\neq1$, if given $g$ and $g^x \bmod p$, one can determine the value of $x \bmod r$ in $O(\sqrt{r})$ time (See this and this answer).

The latter of the two answers even includes an outline of a way to do this. However, this requires $A^{\frac{p-1}{r}}$ with $A$ being the public key to be calculated. For a large $A$ and $p$ (say 4096 bits for both) and a small $r$ (8 bits or less), for me this does not seem to be computationally possible. Therefore, I was wondering how one would write a solution to this problem which is possible to execute with finite time and memory.


texts: Best way, how to convert 32-byte Keccak hashes to positive numbers up to maximum?

texts:
I have 32-byte Keccak hashes and I have some maximum number, for example 500, how to uniformly convert those hashes to pseudo-random positive numbers up to that maximum?
I mean I have for example 100 quite random hashes and I want to distribute them so the result would be something like 80 numbers hit once, 19 twice and 1 hit three times (I guess something like that), somehow uniform distribution.
The maximum can be over 32-bits, so I need to use 64-bit integers.

Some approaches come to my mind:
a) always take first 8 bytes, convert them to 64-bit integer and use modulo 500 on them,
b) sum 1st 8 bytes, 2nd 8 bytes, 3rd 8 bytes and 4th 8 bytes to 64-bit integer and use modulo 500,
c) something better?

I know that modulo is not the best for uniform distribution, because it slightly prefers numbers at the beginning of the range, but I think I google how to overcome that by myself and I think it's not even a big deal.

The other thing I am not sure about is whether all the bits in Keccak hashes are quite uniformly distributed, but I guess they should be. I hope that some bit doesn't favor 0s or 1s so some numbers don't get an advantage during my conversion.


texts: Combining multiple hash functions for HKDF

texts:
I'm trying to apply the hash function combination method described in https://eprint.iacr.org/2013/210.pdf to a HKDF PRNG construction. Thing is it needs 4 uniformly random parameters/keys chosen by the signer during the combination step, but that's what I was already using the PRNG for so it feels like I'm running into some chicken-egg problem.

What would be the recommended way to generate these keys? Is it at all possible to strengthen PRNGs with this trick?


texts: Is it possible to verify and relay an encryption key with a trusted but transparent third party?

texts:
I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?):

Bob has an encryption key. Alice has the encrypted data and wants to buy the key from Bob.
Bob sends the key to the smart contract (SC).
Alice sends some ether (and perhaps the encrypted data or some function on it) to the SC.
The SC verifies that the key decrypts the data properly. If it doesn't, it halts.
The SC sends Bob the ether, and Alice the key.

The main issues I'm finding when I'm trying to think of a solution are:

How does the third party verify a decryption is correct?
Is it possible for the third party to verify this decryption without revealing it, since it is transparent? I know of zero knowledge proofs, but am not sure of how they could apply here.

Thank you!


texts:
I am wondering whether $e = 2$ can be used in unpadded RSA...
It seems like it is not possible to use it: the value of e needs to be coprime with $tot(n)$. $tot(n) = (p - 1)(q - 1)$ where $p$ and $q$ are prime numbers.

The way I see it, there are two scenarios.

1) Neither $p$ nor $q$ are equal to $2$. This means they are odd. The product of $(p - 1)(q - 1)$ would be even i.e. not coprime with $2$.

2) Let's say $p = 2$ and $q$ is any prime greater than $2$. This would give $tot(n) = 1(q - 1)$ and since we know that $q$ is odd, the result will be even anyway.

Is there something I am overlooking here or is my reasoning correct?


texts:
I am using a vendor library that signs a text producing a PKCS#7 message. I'm not sure of the content of this message.

Does a pkcs#7 message have to contain the signed message, the certificate, the payload? Does it have to start with ----BEGIN PKCS7---- and end with ----END PKCS7----?


texts: How can AES + cycle walking be used as an FPE?

texts:
I'm a bit confused after reading several articles that seem to provide conflicting information.  Basically I was wondering if AES by itself can be used as an FPE? And if so is this something computationally prohibitive, or something reasonable to do.  Furthermore how can we use AES by itself + cycle walking?

According to this paper it says one of the methods for FPE is

  5.2 Cycle walking Method "The  cycle  walking  works  by  encrypting  the  plaintext  by repeatedly   applying   AES   or   3DES   until the
  cipher   text becomes in acceptable range. The duration for ciphering
  is not deterministic. "

If this is the case, what is the general construct for this (I.e. how to set up your AES encryptor, key, IV, mode etc)

In that paper they also have a table that summarizes the speed of this method compared to others.

But in another article it is stated that it would be prohibitively expensive to use cyclewalking alone since it would take many iterations to get a value in the desired range.

  "So, why can't we just use cycle-walking? Because it only works well
  if the block size is approximately right—if the size of the valid set
  is a lot smaller than the block size of the cipher, then you have to
  do a lot of iterations in order to get an in-range result. So, you
  can't use a 64-bit block cipher in order to encrypt an SSN because you
  end up having to do a prohibitive number if iterations; you need to
  use L-R to construct a block cipher of approximately the right size
  and then use cycle-walking to shave off the last few values."

I'm not sure if the result 1500 milliseconds in the comparison table above is considered prohibitive or not for such an encryption scheme.


texts: More rounds after AES related key attack?

texts:
In his blog Schneier discusses that there is a new related key attack on 10 rounds of AES-256 "Another attack can break a 10 round version of AES-256 in 245 time, but it uses a stronger type of related subkey attack".

My question is how many more rounds would they have to use to keep this security margin on AES (other then adding a hash to AES 256 key schedule)? And would NIST actually change the standard again to something more secure such as Serpent?

Consider the number of rounds broken out of the total rounds for the security margin.


texts: Why can we ignore $y$ when using the extended Euclidean algorithm to calculate an RSA decryption exponent?

texts:
I have a follow-up question about the extended Euclidean algorithm, as applied to RSA key generation, described in this answer.

Let us say we have $p=5$, $q=11$ and $e=17$, so that $N=55$ and $φ(N)=40$.

We can verify that $\gcd(e, φ(N)) = 1$, so $e$ is a valid encryption exponent.

Now the answer says we should use the extended Euclidean algorithm to find $x$ and $y$ such that $e \cdot x + φ(N) \cdot y = 1$, so that $e \cdot x \equiv 1 \pmod{φ(N)}$, and then let the decryption exponent be $d = x$.

By applying the extended Euclidean algorithm, we find that $x = -7$.

My first question is, how come $17 \cdot (-7) \equiv 1 \pmod{φ(N)}$?

Also, in the answer I linked to above, it says:

  "The value of $y$ does not actually matter, since it will get eliminated modulo $φ(n)$ regardless of its value. The EED will give you that value, but you can safely discard it."

I'm not sure what this is supposed to mean.  Could someone please explain it more clearly?


texts:
The german site "SAS und Chiffrierdienst der DDR"
http://scz.bplaced.net
has some interesting content under point 11.3 in the category "manuelle Verfahren" I found ciphers named from A to D. But I think none of these are secure besides security trough obscurity or am I wrong?


texts:
I read this article and I think the approach outlined there is very interesting for one of our use case.

We use ChaCha20 Poly1305 (via Sodium crypto_aead_chacha20poly1305_encrypt_detached) to encrypt the data, which is typically 8 kb in size. We use this because this way the mac + nonce can fit in the available space we have in the page header, using XChaCha20 (and random nonce) is not possible because of the amount of space they would take.

The data is pages in database, and each page may be modified multiple times over the lifetime of the database.

I'm trying to figure out what the best way to handle nonce / key management in this case.

Currently we generate a random nonce per page and then increment the nonce every time the page is modified. To avoid the case where a random nonce / increment is reused, we also derive a new key for each page (via crypto_kdf_derive_from_key, where the subkeyid is actually the page number).

This seems fine, but it require us to do quite a bit of work every single time.

Note that we use

The article above seems to indicate that using the hash of the data that we encrypt as the nonce will help avoid the problem with nonce reuse, since if that happens, it will be identical data & nonce, so you can't XOR them together to find anything meaningful (but can find if they are repeating).

If this is a valid option, that would give us the option of having a single key for all the pages, and a nonce based on the hash of the data and avoid the need to carefully manage the nonces.

Assuming this is the case, can we use any hashing algorithm (we already do checksum with XXHash64, or do we need a cryptographic hash to use)?


texts: How to Derive a Child RSA Key Pair from an Existing RSA Key Pair?

texts:
I want to understand how, using standard tools like openssl (or similar), to derive a child RSA key pair from an existing RSA key pair.  Additionally I would like the derived key to contain a reference to it's parent such that the relationship could be verified using the same tools used to create it.
From my research so far it seems like the methodology is to sign an arbitrary value with the parent key and use the result as the derived child key.  However, the output of openssl dgst -sign master.pem is not an RSA key but ciphertext.  If I'm on the right track, how then do I transform the ciphertext into a private key or key pair (I understand the public key can be generated from the private key).
If that is not the correct way, what should I do instead?
This question seems to be hinting at what I want but does not provide enough detail (at least for my understanding).


texts:
I'm playing around with the idea of a blockchain where both the proof-of-work and verification steps are NP-hard.  It seems the NP-hard verification step can be resolved if you allow for multiple parallel blockchains with different sets of blocks in the head of each version.  This of course creates another problem of trying to reconcile multiple blockchains in a secure manner.

The go-to proof-of-work method of reconciliation seems to be "take whichever chain has the most work in it," but is there anything out there already which allows for the reconciliation of the blocks without a loss of proof or transactional data?


texts: How is Pre Master Secret related to Client.random or Server.random if DH KEX is RSA

texts:
For TLS 1.2 cipher Suite AES256-GCM-SHA384, RSA is KEX(key exchagne algorithm). As per standards of RSA Diffie Hellman KEX, after 'ServerHello' message client gets server certificate and it generates a 48 byte random number which is 'pre master secret' and sends it to server. This ensures both have setup pre master secret.

Are client.random and server.random anyway related(mathemetically) to pre master secret?

As per my understanding (after researching on web), server.random prevents handshake replay attack in ECDH. How is RSAKEX preventing handshake replay attack?

Are they only significant after master secret generation and succeeding steps, but not in preventing handshake replay attack?


texts: What does perfect mean within perfect forward secrecy and why do some cryptographers disagree with the term?

texts:
In this blog post, Matthew Green says

Forward secrecy (usually misnamed “perfect forward secrecy”)...

The Wikipedia article on forward secrecy (which the same sentence links to in the blog) says

forward secrecy (FS), also known as perfect forward secrecy (PFS)...

which implies that they are the same thing and nullifies Matthew Green's statement.
Apparently Professor Green's statement is simply a personal disagreement with the term perfect
I'd be interested in knowing how forward secrecy is/isn't 'perfect',(why cryptographers disagree with perfect) and why was the term was originally attached to forward secrecy?


texts: Is it a good practice to use plain text for derivation of Keys?

texts:
I have a question regarding the derivation of keys in crypto.
Is it a good practice to use the plain text (in form of hashes) for derivation of keys ? these keys will be used for encryption of the same plain text later on.

What are possible drawbacks of the same if any ?

Thank You in advance.

Edit 1: For example

I have a plain text say X

The hash, H = Random Text + X;

Key, K1 = Initial Key XOR H;

Cipher C = Enc (K1, X)

So it is a good practice to use the plain text as shown in above manner for key generation and encryption ?
what are the drawbacks of the same.

Edit 2
The other party will receive

Cipher C along with C1 = Enc(K0, Hash)

So that in order to decipher, apply Dec(K0, C1) = Hash

K1 = Hash XOR K0

and then PT = Dec(K1, C)

Thank You.


texts: Does encrypting different versions of the same file or folder with the same key make it easier for hackers to attempt the decoding?

texts: Assuming the hacker has access to the ciphers of each of the versions, will it help him/her to decipher the original file(s) by doing some sort of comparison of the ciphers?


texts:
In the BLAKE2 paper, the authors define

  Maximal depth (1 byte): an integer in [1, 255] (set to 255 if unlimited, and to 1 only in sequential mode)
  Node depth (1 byte): an integer in [0, 255] (set to 0 for the leaves, or in sequential mode)

Node depth is incremented as you approach the root node of the tree.

I was considering using BLAKE2b in tree mode with a fanout of 1 (e.g., a "unary" tree) for an iterated hashing scheme. The spec above says to set maximal depth to 255 for "unlimited" depth, but the node depth is only one byte so can only uniquely denote nodes in trees smaller than this depth.

First, is there a reasonable way to achieve arbitrarily-deep trees (e.g., on the order of 2^48 nodes deep) with BLAKE2b? And second, is this way preferable to some other approach?

Edit: One idea that comes to mind is to swap the interpretation of the node offset and node depth fields for the purpose of this scheme, since node offset would otherwise go unused (all trees in this scheme have an offset of 0), and it's a 64-bit value.


texts: Generation of a cyclic group of prime order

texts:
I am trying to implement a cyclic group generator in Java, but I am running into some issues. In many cryptosystems, the following phrase is expressed during the key generation stage.

  Let G be cyclic group of prime order q and with a generator g

I have done some research on this and have been able to implement a cyclic group generator with a modulus p and a generator g. However, I am currently stuck on how to make sure that the generated group's order is a prime q.

This is what I have:

public class CyclicGroup {
    private static final int EQUAL = 0;
    private static final BigInteger TWO = new BigInteger("2");

    private BigInteger p, g;

    public CyclicGroup(int bitLength) {
        init(bitLength);
    }

    private void init(int bitLength) {
        BigInteger q = BigInteger.ZERO;

        while (true) {
            q = CryptoUtil.getPrime(bitLength);
            p = (q.multiply(TWO)).add(BigInteger.ONE); // p = 2q+1

            if (!p.isProbablePrime(40)) {
                continue;
            }

            while (true) {
                g = CryptoUtil.rand(TWO, p.subtract(BigInteger.ONE));

                BigInteger exp = (p.subtract(BigInteger.ONE)).divide(q);

                if (g.modPow(exp, p).compareTo(BigInteger.ONE) != EQUAL) {
                    break;
                }
            }

            break;
        }
    }

    public BigInteger getRandomElement() {
        return g.modPow(CryptoUtil.rand(BigInteger.ONE, p), p);
    }

    public ArrayList<BigInteger> getElements() {
        // This method is horribly ineffective for large groups and should not be used

        ArrayList<BigInteger> elements = new ArrayList<BigInteger>();

        BigInteger index = BigInteger.ONE;
        BigInteger element = BigInteger.ZERO;

        while (element.compareTo(BigInteger.ONE) != EQUAL) {
            element = g.modPow(index, p);
            elements.add(element);

            index = index.add(BigInteger.ONE); // index++
        }

        return elements;
    }

    public BigInteger getModulus() {
        return p;
    }

    public BigInteger getGenerator() {
        return g;
    }
}

The above class generates a cyclic group with modulus p and a generator g. The following code will produce the subsequent sample output. Note that the tiny bitlength of 4 is to avoid huge numbers in the sample output.

public class App {
    public static void main(String[] args) throws IOException {
        CyclicGroup cg = new CyclicGroup(4);

        System.out.println("Modulus (p): " + cg.getModulus());
        System.out.println("Generator (g): " + cg.getGenerator());
        System.out.println(cg.getElements());
        System.out.println("Random element in group: " + cg.getRandomElement());
    }
}

  Modulus (p): 23

  Generator (g): 9

  [9, 12, 16, 6, 8, 3, 4, 13, 2, 18, 1]

  Random element in group: 9

To sum up, how can I make sure that the generated cyclic group's order is prime? In the above sample output I got lucky that its order is 11. It would also be nice to be able to make the determination without computing all the group's elements and then to count them.

I appriciate any help you are able to give me on this. For your information, my background in group theory is limited at best. Thanks in advance.


texts: Can DNA computing to solve elliptic curve algorithms using this method

texts:
The authors of this paper: Fast Parallel Molecular Algorithms for DNA-Based Computation: Solving the Elliptic Curve Discrete Logarithm Problem over $GF(2^n)$ proposed a novel algorithm based on DNA computing which they claim (in theory, at least) can solve elliptic curve algorithms in polynomial time.

An excerpt from the article:

  "We have constructed the algorithm above for parallel computing the point of the sum of two points. Then, we can solve the elliptic curve discrete logarithm problem as follows: consider point P and Q are given, and l is what we want to get which matches Q = lP. First, we amplify P into two tubes and add P in one tube. Check if 2P equals to Q; if not, note down the value of 2P and pour two tubes together. Then, amplify the tube into two tubes and add 2P in one tube. Check if any point equals to Q; if not, note down the value of 4P and pour two tubes together, or we get the value of l. Then, amplify the tube into two tubes and add 4P in one tube,…, while this loop executes n times, the value from 1 to 2n for l will have been checked, and the elliptic curve cryptosystem has been broken by the solved elliptic curve discrete logarithm problem."

I'm just starting to learn cryptography as a hobby, so I'm not too familiar with it yet. Can someone explain their strategy to me in simpler terms? Is their strategy practical in real life? The authors claim they can solve elliptic curve algorithms "in polynomial time" but I'm not so sure......


texts: SHA-1:Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output?

texts: Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output? What is the probability that a 160-bit SHA-1 hash output contains at least 128 1's?


texts: Efficient way of knowing large factors of $\phi(n)$ given small prime factors and $n$

texts:
Knowing large prime factor$(r > n^{1/4})$ of $\phi(n)$ can easily factorize n and hence learn $\phi(n)$.

If we have knowledge on all small prime factors $(2< r_i  << n^{1/4})$ of $\phi(n)$ then, is there any efficient way to factorize $n$ and  $\phi(n)$?

Note: $n$ is an RSA number


texts: AES cache-timing attacks and nonce-based operation modes

texts:
As I understand it, AES cache-timing attacks exploit the execution time variations due to cache hits/misses, especially the ones depending on the SBox look-up tables which are key-related.

To mount such an attack, does an attacker need to have knowledge of the algorithm input? If so, are such attacks still relevant against operation modes such as CCM or GCM where the input nonce has a specific format and might be not transmitted (at least a part of it)?

In the paper of Daniel J. Bernstein one can read:

  By considering table lookups in (e.g.) the last AES round, develop an
  attack that works with highly structured AES inputs (as in, e.g.,
  counter mode) rather than random-looking AES inputs (as in, e.g.,
  CBC).

Have related works been published yet?


texts:
Let $k$ by a randomly generated $n$ bit string, and $m$ a $n$ bit message.  Then putting $c = m \oplus k$ is the one-time pad and is perfectly secure.  Now assume the transmitter and receiver wanted to share more messages: then they could publicly choose a random $n$ bit string $b$, and then by putting $k' = b \oplus k$ they have obtained a new random key, which they can again use to encrypt a new message $m'$ with perfect secrecy.

I am wondering why such a cipher is not used?  The only reason I can think of is that if the attacker obtains a single plaintext message, they can decrypt all past and future messages which is clearly not good, and thus the reason it is not used.  Are there any other reasons I am missing?

Further, couldn't this be used to create a random bit generator?  That is, the seed is a random $n$ bit string, and the publicly known generator will XOR $k$ random but publicly known $n$ bit strings with the seed $k$, to generate a random sequence of length $kn$.  Naturally, the reason I am assuming this is not a good random number generator is that, again, if the attacker learns the internal state they can obtain all past and future bits.  Are there any other reasons this is not good?


texts: How secure is $\operatorname{AES256}_{\operatorname{ECB}}(\operatorname{ChaCha20}(\text{plaintext}))$?

texts: Suppose I encrypt a bytestream using ChaCha20, and then encrypt the resulting ciphertext using AES in ECB mode.  How secure is the combination?


texts: Why Diffusion and Confusion prevent statistical analysis?

texts: I've studied the concepts of Diffusion and Confusion of cryptographic algorithms, however, I don't understand why they help in preventing a statistical analysis. Are you able to explain to me?


texts:
This secret sharing scheme takes place in the polynomial ring over a finite field $F_p[x]$, $p$ being a large prime, in the following simplified way:

The dealer chooses a private polynomial $f(x)$.
Every participant $P_i, i \in N$, has a public polynomial $m_i(x)$, with $deg(m_i(x)) \leq deg(f(x))$.
The dealer computes the private secret share of $P_i$ as $s_i(x) = f(x) \mod m_i(x)$ and sends it to $P_i$.

I need a way for $P_i$ to verify that the private secret share $s_i(x)$ was well calculated.

Suppose there is a polynomial commitment scheme that allows you to commit to a certain polynomial $p(x)$ as $p(\beta)G$.

$\beta$ is a value unknown to everyone (as well as $p(\beta)$), including the dealer, and $G$ is a point generator of an Elliptic Curve over $F_p$.

This polynomial commitment scheme also allows to produce a proof evaluation of a certain committed polynomial, i.e., you can prove that a certain point (a, b) belongs to the committed polynomial.

With this, my idea to verify the private secret share $s_i(x)$ is the following:

Since $f(x) = m_i(x)k_i(x) + s_i(x)$, the dealer commits to $f(x)$ and $k_i(x)$ as $f(\beta)G$ and $k_i(\beta)G$, respectively, and sends them to $P_i$.
$P_i$ asks for an evaluation of a random $z$.
The dealer sends $f(z)$ and $k_i(z)$ to $P_i$, along with the proofs that they belong to the committed polynomials.
$P_i$ verifies that $f(z) = k_i(z)m_i(z) + s_i(z)$.

My thinking was that two polynomials $p(x)$ and $p'(x)$, with degrees $n$ and $m$, can have at most $max(n, m)$ intersections, so if the dealer commits to polynomials $f'(x)$ and/or $k'(x)$ instead of $f(x)$ and/or $k(x)$, the probability that the equation holds for those committed polynomials, is negligible.

I don't know how to prove or disprove this, so I would appreciate if anyone can help me.


texts: Where can I find source code for ideal world simulation?

texts:
In many crypto papers I see they use a Real World / Ideal World Paradigm.  However, I have never see the source code of such Simulators that try to simulate the adversary.  Could somebody point me to source code that simulates an adversary in the ideal world? How does this code look like  ?

An example of a paper that uses this paradigm is on pg. 1244 of this paper.


texts: What does "congruent to 448, modulo 512" mean for padding in MD5 hash function?

texts:
What does "congruent to 448, modulo 512" mean within the MD5 hash specifications?

From the specification:

  The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. That is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long. Padding is always performed, even if the length of the message is already congruent to 448, modulo 512.


texts: Why won't a BFT protocol using simple signing/voting work?

texts:
PBFT and most consensus algorithms are more complicated than a simple voting scheme. By simple voting I mean the following: we require all nodes to sign their local copy of the state and send this signed message to all other nodes. Each node then collects messages from all other nodes, and accepts the state if more than t < n nodes agree on the same state.

There are many ways to achieve the scheme above (e.g., each node individually signs, or using threshold signatures), which seems much simpler than other protocols such as PBFT (which among other things, requires designating a leader).

Therefore, I'm left to assume that voting can't directly produce a secure BFT protocol, but my question is - why is this the case? Where does consensus by voting break?


texts: Given ciphertexts C1, C2 of different messages P1 and P2; how can we prove that both C1 and C2 were encrypted using public keys of the same pair?

texts:
I vaguely recall reading about a scheme that accomplished this but am not able to figure out which one it was. For the sake of brevity I'm gonna omit any nonces.
Let's say we have an asymmetric keypair: (Kpub, Kpriv)
An observer is provided:
C1 = E(Kpub, P1)
P1 is known. It can verified that by performing E(Kpub, P1) the result is indeed C1.
The observer is then provided:
C2 = E(Kpub, P2)
P2 is not known to the observer, but they are provided a proof that they can use to verify that C1 and C2 are indeed ciphertexts that can be decrypted by the same private key (or in other words; were obtained by encrypting using the same public key).
I think ElGamal and NIZK were part of the proof but I'm not sure. Any ideas?


texts: Is the MD5 algorithm only useful for bytes, rather than bits?

texts:
The MD5 algorithm is designed to accept a message of any length and produce a 512-bit message digest. Because of the way it pads the original message, by adding a 1-bit then a number of 0-bits, the length of the message can be any number of bits. It is not limited to an integer number of bytes. But it can also be written to work only in bytes, so the padding stage would involve adding a 0x80 byte then a number of 0x00 bytes. The end result is the same, as long as the input data is an integer number of bytes.
However, my understanding is that data is almost always stored in bytes. This is especially the case for character strings, where each character is represented by at least 1 byte. For this use case, I believe a byte-oriented approach would work fine. But if I wanted to write an MD5 implementation that also accepts files, does the bit/byte distinction become important? Would I need to write the algorithm to deal specifically with bits, or would a byte-oriented implementation work just as well for strings (e.g. from STDIN) and files?
In other words, is data always stored as whole bytes? And if so, what applications are there in which one would need to write an MD5 algorithm that uses individual bits, rather than whole bytes?


texts:
I am current learning the internal working of several Symmetric key Cryptographic algorithms, and came across DES and AES.

  DES takes in input a 64 bit key and AES-128 takes in input a 128 bit key

My question is, since the user provides these algorithms inputs of variable size (or bits), then how is it able to upscale/downscale it to lower bits in order to feed it to the algorithm. Does it uses KDF (key Derivation function)? If yes, then is the KDF capable of decreasing the size of bits too?

By decreasing I mean, If the User Inputs a key = APPLE PIES, and gives it as an input to DES. Then how is DES able to convert this (80 bit) key into a 64 bit one?


texts: In RSA, how to make sure that $p-1$ and $q-1$ are still hard to factorize?

texts:
See this question. The comment by Brett Hale stated:

  On the other hand, ensuring $(p - 1)$ has a large prime factor requires very little extra effort.

What's actually the 'little extra effort'?


texts: Does there exist a deterministic, invertible function $\{0,1\}^n \rightarrow \{0,1\}^n$ that is not a bijection?

texts:
One of the requirements for a function to be a PRP is

  For any $K \in \{0,1\}^s$, $F$ is a bijection from $\{0,1\}^n \rightarrow \{0,1\}^n$.

Taken from Wikipedia

Does this have to be explicitly said? Is it even possible for this not to be true for a deterministic, invertible function where the input and output domains are the same?


texts: Is DL difficult under the group of Unimodular matrices?

texts:
Is discrete logarithm assumed to be computationally hard in a non-abelian group as the  subgroup of the general linear group under matrix multiplication formed by the unimodular matrices? The two assumed unimodular matrices have the form $$A=\begin{bmatrix}
    X       & 1  \\
    1       & 0
\end{bmatrix},B=\begin{bmatrix}
    X       & X+1  \\
    1       & 1
\end{bmatrix}$$, for a irreducible polynomial P_n of degree $n$.
Elements belong to a quotient field $\mathbb{F}_{2^n}=\mathbb{F}_2[X]/P_n$


texts: Implement Twofish cipher with 16-bit blocksize?

texts:
I've seen implementation of Rijndael cipher with 16-bit blocksize. And I have also tried to implement 16-bit Rijndael cipher by myself with only a little sneak peeking at the example of the implementation.

I think this was a very good way to learn how Rijndael or AES cipher works, by simplify the cipher and reducing the block size to small numbers that is possible to calculate with your brain.

I would love to learn how twofish works, and I was hoping to use same method as with Rijndael cipher. But I was not able to find anyone who had already implemented a 16-bits Twofish cipher, so I started to wonder if this was possible. After looking at the flowchart of the Twofish cipher:

K0 to K7 should be possible to reduce to 2-bit size, same with the S-boxes, MDS and PHT. But what about the rotary bitshifting and K2r+8? And are there other problems with reducing blocksize of Twofish cipher? Or the first question I should have asked, is it possible?

This is only for learning purpose, I know very well that 16-bits cipher is «unsecure» and highly probability for collision.


texts: How to stop an attacker from repeating the same ciphertext?

texts:
I have this situation where a PC is connected, via RS-232, to a certain hardware module that controls industial machinery.

The hardware is supposed to receive commands to turn on or off these machines, and the same command may need to be sent multiple times in a span of a single minute. Now, I am very new to cryptography, so I will be programming this hardware with an already pre-existing library that supports AES-128, AES-192 and AES-256 in ECB and CBC modes.

The problem I'm facing is that a potential attacker can very easily gain access to the transmission line and just probe it for the message being sent, and then use this information to send commands that can compromise the industrial machinery.

Let's say that the PC encripts a message like "MACHINE1 ON" using AES-256 with a secret key that the hardware module knows. Since the command is always the same, using AES in ECB mode will result in the same ciphertext, meaning that the attacker can just repeat the same ciphertext in order to turn the machine on.

Now, CBC encryption makes use of an IV to randomize the ciphertext, but the problem is, how will both the PC and hardware module know the IV? If the PC generates a truly random IV and encrypts the command with it, there's no way the hardware module will be able to decrypt the message without it.

So it thought that maybe the PC should transmit the IV to the hardware, using ECB mode, and then transmit the command encrypted with that IV, but we're back to square one, because an attacker can just repeat both ciphertexts and the hardware will just accept it (is this considered a replay attack?).

I've read a little about MAC and how it allows to verify if the sender has not changed, but how does it apply to this scenario? Would it even help? If not, what techniques could one use in a situation such as this?

Keep in mind that there is very little variety in the messages that will be send to the hardware module. The hardware module is also capable of generating truly random numbers, and it replies to the commands with a simple "OK" or "Invalid command" messages. These should also be encrypted to ensure an attacker gets as little information as possible.

EDIT:

I also read that sometimes, the IV is sent at the beggining of the encrypted text, so that the receiving end knows that the first N bytes correspond to the IV and can decrypt the message. Isn't this also vulnerable to the same replay attack?

Wouldn't it be better to implement some kind of "handshaking", where the hardware is the one to generate the IV and send it to the PC, the PC modifies the IV in a deterministic way, and then sends the messages using that modified IV? The process would then repeat each time the PC needs to send a command, and as long as the hardware doesn't generate the same IV twice, everything would be safe, right?

I'm sorry if this question is all over the place, I'm very confused about criptography and I'm being asked to implement something that I have almost no clue as to how it works. Any help would be much appreciated.