texts: In Paillier homomorphic encryption, do we need to take modulo after multiplication of 2 ciphertexts?

texts:
The multiplication of 2 ciphertexts generated using Paillier encryption will result in encryption of sum of corresponding plaintexts. I need to do a linear combination operation of N integers in Paillier encrypted domain. Then after multiplying every 2 ciphertexts, do I have to take mod with respect to n^2.
OR
Is it enough to take mod after multiplying all the N ciphertexts?

Will both give the same result or not?


texts:
So I'm trying to understand how the key exchange with Curve25519 works. I read the original Paper from Bernstein "Curve25519: new Diffie-Hellman speed records", but I still got some questions. First of all, this is graphic, how the key exchange should work:

So Alice and Bob create their own secret key by randomly choosing a number $$n\in 2^{254} + 8 \cdot \{ 0, 1, \ldots , 2^{251} - 1\}.$$ In other ECC standards, this $n$ is multiplied with a Public Point $P$, but here I don't have a public Point $P$. So that's where I don't understand the concept.

The Public string is not a point, it is a number $q \in \{0,1,\ldots,255\}^{32}$ and i don't understand, why it is only a number and not a Point.

So in other Standards, the public key of Bob and Alice is produced by multiplying the secret key with the public Point. That produces new Points, which are the public keys.

Here there is a public function also included I have no idea, what it does. That means, I can't figure out, how the shared secret key is produced.

In addition, I would like to know what the functional call of $\operatorname{Curve25519}(a,9)$ means, so what do the parameters do with my curve?

Can someone explain this to me? Is it possible to give me a simple example of how it works?


texts: Is a random length-extension worth the effort?

texts:
I'm conceiving an application that uses cryptographic tools and concepts for securing data. I know that's difficult and risky, therefore I prefer to ask around before implementing anything.

When using generic length-extension for hash functions, such as SHA256d where, if I'm correct, "d" stands for the number of times the hash gets re-hashed, I wondered if using a random value for "d" (within certain limits) could do anything to improve security.

The application would be a tad slower when finding out the correct value of "d" for a particular hash, but wouldn't it be justified by the annoyance caused to the attacker ?

This would be in case where the attacker has the source code (which isn't so far fetched if he already has access to the data) and could easily find out the value of "d".


texts: How can I send a secure public message using ECC?

texts: I want to know how to send a secure message protected with elliptic curve private and public keys.


texts:
Why is SRP considered to be resistant to MITM attack? Documentation says

  A man-in-the-middle attack, which requires an attacker to fool both
  sides of a legitimate conversation, cannot be carried out by an
  attacker who does not know Carol's password. An attacker who does not
  know x cannot fool Steve into thinking he is talking to Carol, so at
  least one half of the deception fails. If the attacker doesn't know v
  either, he is in worse shape, because he also can't fool Carol into
  believing that she is communicating with Steve.

But let's assume Carol, Steve and MITM have salt, generator and safe prime. And imagine the Carol trying to log in, but MITM stands between Carol and Steve.

1) Carol sends A, but MITM takes it and sends to Steve.

2) Steve responds to MITM with B. MITM sends it back to Carol.

3) Both Carol and Steve create a common key(K).

4) Carol sends Steve h(K,s1), where h is a one way hash function and s1 is some salt that was given to Carol by Steve. MITM takes it and sends it to Steve.

5) Steve checks it and say "Hello Carol, nice to meet you".

So MITM can log to the server by sending requests back and forth.


texts:
I would like to know what is the security of an encrypt-and-MAC with different keys for each transaction

For example: the one-time-pad with $k_1$ and the HMAC with $k_2$

$$C = M \oplus k_1\\
MAC = HMAC(k_2,M)$$

The ciphertext is $C||MAC$. The two keys $k_1$ and $k_2$ change for each transaction (for each $M$).


texts: What happens to the entropy of a password when you hash it?

texts: For example, if the entropy of a password is 30 bits, what is the entropy of the password when you hash it with MD5?


texts: Elliptic ElGamal Public Key Cryptosystem doubt

texts:
I need an example of Elliptic ElGamal Public Key Cryptosystem. I have been trying with some values but I don't get the right solution.

I have $p=13$, the elliptic curve $E:y^2=x^3+11x+7$ and a point $P=(6,\sqrt{3}) \in E(\mathbb{F}_{13})$.

The message is $M=(0.5,12.625)\in E(\mathbb{F}_{13})$.

Alice, chooses the value $nA=5$, calculates Q$_A=n_A \cdot P=(2.5,11.125)$ and sends $Q_A$.

Bob chooses the integer $k=2$ randomly and calculates $C_1$ and $C_2$:
$$C_1=k⋅P=(12,\sqrt{23})$$
$$C_2=M+k⋅Q_A=(5.5,8.875)$$

Bob sends $(C_1,C_2)$ to Alice.

Alice calculates M: $$M=C_2−n_A⋅C_1=(−2.5,−8.4455)$$ and the solution should be $ M=(0.5,12.625)$ ... Does someone know what is wrong? I think that my problem is calculating in $\mathbb{F}_{13}$, but I'm not sure.

Thank you :)


texts:
EDIT: The instructor clarified that part (a) was wrong. He declined to indicate why. I can share more details of the prompt if need be.

I apologize again if this question is too low-level; it comes from a practice midterm in a course I'm taking. I was told by an instructor that my proposed solution was wrong, but not why. The notation is Katz's.

For the problem, $F:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ is a block cipher (or pseudorandom permutation). The scheme works as follows: to encrypt $M = m_1 || \cdots || m_l$, where each $m_i \in \{0,1\}^n$, we select a key $k$, choose a uniform $\mathrm{ctr}$, and output $$\mathrm{ctr}||F_k(\mathrm{ctr} + 1 + m_1)||\cdots||F_k(\mathrm{ctr} + l + m_l).$$
The question(s) were a) how do we decrypt, and b) how can the scheme be shown EAV-insecure?

My answers were:

a) $F_k$ is 1-1, so invertible; for each $i$th block we compute $m_i = F_k^{-1}(c_i) - \mathrm{ctr} - i$, and return $m_1||\cdots||m_l$.

b) Pick $m_l' = m_{l-1}' + 1 = \cdots = m_1' + l - 1$, and (towards an EAV attack) let $m_0 = m_1'||\cdots||m_l'$; choose $m_1$ at random. Let $\mathcal{A}$ output $b' = 0$ if $c_1 = \cdots = c_l$ and $b' = 1$ otherwise. Then $\Pr[\mathrm{PrivK^{\mathrm{eav}}}_{\mathcal{A}}(n) = 1] = \frac{1}{2} \Pr[\mathcal{A}$ outputs $0|b = 0] + \frac{1}{2}\Pr[\mathcal{A} $ outputs $1|b = 1] = \frac{1}{2} \Pr[\mathcal{A}$ outputs $0|b = 0] + \frac{1}{2}(1 - \Pr[\mathcal{A} $ outputs $0|b = 1]) = \frac{1}{2}\cdot1 + $ $\frac{1}{2}\cdot(1 - \left(\frac{1}{2^n}\right)^{l-1}).$  This is plainly greater than 1/2 + $\epsilon(n)$ for negligible $\epsilon$, so we see that the scheme is not EAV-secure against $\mathcal{A}$.


texts:
This is not homework, but a question from an exam.

Let $G(x)$ be a PRG with expansion parameter $\ell(n)$.

$$G'(x) = G(x) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ where $\ell(|x|) = |G(x)|$

My intuition is that it is a PRG, first, $n$ bits are just XOR between $x$ which is random, with $G(x)$ which is a PRG, and the rest of the bits are untouched.

I tried to formally prove this to no avail, so I tried a simpler exercise:

$$G'(x) = G(x) \oplus (x_1 \mathbin\| 0^{\ell(|x|)-1})$$ where $x_1$ is the first bit of $x$.

If I can show this is a PRG, it will be easy with induction on the number of bits we take from x to show the original $G'$ is a PRG.


texts:
Modern hash functions are considered to be efficient to calculate by boolean circuits (i.e their implementation are using bits- operations).

I'm looking for a cryptographic hash function, that can be efficient calculate by arithmetic circuits (i.e they use OR and AND gates (or $+$ and $\cdot$ gates) and work over $\operatorname{GF}(q)$.

After bit of search, I found MASH-1 and MASH-2 constructions, but they seem to include the $\text{xor}$ function that I'm trying to eliminate.


texts:
I can't really understand MixColumns in Advanced Encryption Standard, can anyone help me how to do this?

I found some topic in the internet about MixColumns, but I still have a lot of question to ask.

ex.

$$
\begin{bmatrix}
\mathtt{d4} \\
\mathtt{bf} \\
\mathtt{5d} \\
\mathtt{30} \\
\end{bmatrix}
\cdot
\begin{bmatrix}
\mathtt{02} & \mathtt{03} & \mathtt{01} & \mathtt{01} \\
\mathtt{01} & \mathtt{02} & \mathtt{03} & \mathtt{01} \\
\mathtt{01} & \mathtt{01} & \mathtt{02} & \mathtt{03} \\
\mathtt{03} & \mathtt{01} & \mathtt{01} & \mathtt{02} \\
\end{bmatrix}
=
\begin{bmatrix}
\mathtt{04} \\
\mathtt{66} \\
\mathtt{81} \\
\mathtt{e5} \\
\end{bmatrix}
$$

Here, the first element is calculated as

$$(\mathtt{d4} \cdot \mathtt{02}) + (\mathtt{bf} \cdot \mathtt{03}) + (\mathtt{5d} \cdot \mathtt{01}) + (\mathtt{30} \cdot \mathtt{01}) = \mathtt{04}$$

First we will try to solve $\mathtt{d4} \cdot \mathtt{02}$.

We will convert $\mathtt{d4}$ to it's binary form, where $\mathtt{d4}_{16} = \mathtt{1101\,0100}_2$.

$$\begin{aligned}
\mathtt{d4} \cdot \mathtt{02}
&= \mathtt{1101\,0100} \ll 1 & \text{(}{\ll}\text{ is left shift, 1 is the number of bits to shift)} \\
&= \mathtt{1010\,1000} \oplus \mathtt{0001\,1011} & \text{(XOR because the leftmost bit is 1 before shift)}\\
&= \mathtt{1011\,0011} & \text{(answer)}
\end{aligned}$$

Calculation:

$$\begin{aligned}
 & \mathtt{1010\,1000} \\
 & \mathtt{0001\,1011}\ \oplus \\
=& \mathtt{1011\,0011}
\end{aligned}$$

The binary value of $\mathtt{d4}$ will be XORed with $\mathtt{0001\,1011}$ after shifting if the left most bit of the binary value of $\mathtt{d4}$ is equal to 1 (before shift).

My question is, what if the left most bit of the binary value is equal to 0, what do I XOR it with then? ex. $\mathtt{01}_{16} = \mathtt{0000\,0001}_2$ ..?


texts: Is entropy being lost when the hash of a secret has a specific format?

texts:
Bitcoin's mini private key format works by brute forcing random data to produce a secret so that when appending ? and then hashing with sha256 it will produce a hash that starts with 0x00. This way the user knows the secret is well formed and can proceed to hash it without appending ? to produce their private key.

This technique could be extended to include useful data in the hash "header", up to 2 bytes could be brute forced in a second or two.

However it seems that this scheme is reducing entropy of the secret i.e. if the attacker knows that a key is not valid by using a cheap sha256 hash, she will skip the expensive private to public key calculations. When the hash header is 1 byte around 99.6% of the random candidate keys were rejected, for 2 bytes it was 99.9983282%.

So does this scheme reduces the entropy of initial secret? If so how much?


texts: Is there a way to make a black-box function side-channel attack resistant?

texts: If I have no knowledge of the inner workings of a function, (i.e. a black box function) is there a way to make it side-channel attack resistant? (For reference, I'm working with a JavaScript encryption library)


texts: How to determine the exponent when using RSA

texts:
Can someone please explain to me how, when using RSA, to determine the exponent to be used in encryption and decryption? I have attempted a worked example on using RSA (shown below) but I can't ever get the decryption algorithm to work.

Worked example:

$p  = 29$

$q  = 37$

$n  = 29*37
 = 1073$

$\phi  = (29-1)(37-1)
     = 1008$

$e = 3$

$d  = (2(1008))+1)/3
 = 672.3333333$

$m  = 121512$ (taking the positions in the alphabet for 'L', 'O' and 'L')

Encrypt:  $ c = 121512^3 \mod 1073 = 878$

Decrypt: $ 878^{672.3333333} \mod 1073 = 352.91536313837299042255202310536$


texts: Help understanding how to decrypt cipher

texts:
I am trying to create a padding oracle attack to decrypt a cipher that is encrypted with cbc and PKCS#7 padding.
My first step is just to try and decrypt the second block.
I have read a lot about it, and have started to code the first step of the attack, where I edit last byte in the first block and send it to the oracle.
But there is a point of the attack/decryption method I'm a bit confused about regarding the xor of the bytes.
The part I don't understand completely is the math on how manipulating the last byte in the first block result in the last byte in the decrypted byte to turns out to be 0x01, 0x02 etc.
I haven't figured out how the math for that works, for what I have researched it should just be to xor OriginalByte xor TestByte xor 1.
Should that be equal to 0x01?
Here I have a string "TestBlockForStackBBBBBBBBBBBa31", it is 31 bytes. That means that it has to get padded with 1 to make it equal to 32 bytes so it fits inside 16 byte blocks.
The string byte is as following (without encryption):

54657374426C6F636B466F72537461636B4242424242424242424242613331

Then we decrypt the string with the key and IV below using cbc and PKCS#7.
byte[] Key = new byte[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9, 9, 9, 9, 9, 9};
       //we don't need key the key under the attach, only under encryption.
byte[] IV  = new byte[]{2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2 };

We then get this result:

Ciphertext:  ;fŒ˜ÆOgÄ:VûÎ{Ž+6iXK¿îMŠžÌš

Cipher bytes: 3B668C98C64F67C43A56FBCE7B8E150E9D2B1F3669584BBFEE4D8A0E189ECC9A

Under the padding oracle attack I edit the last byte in the first block

(3B668C98C64F67C43A56FBCE7B8E15 0E <--).

I know that when I edit the last byte in the first block to 0D the decryption result will have a 0x01 at the end.
The first block is then going to look like this:

3B668C98C64F67C43A56FBCE7B8E150D

And what I then send to the oracle in this case DecryptStringFromBytes (code can be found in RijndaelManaged.CreateDecryptor Method) is the following
first the edited chiper 3B668C98C64F67C43A56FBCE7B8E150D9D2B1F3669584BBFEE4D8A0E189ECC9A, then the key that is only 0 (Key = new byte[16]), then the same iv as above.
It then returns that the padding is valid. I did go into the function BCryptDecrypt (used inside the decryption call) and set a breakpoint to confirm this, and it is indeed 0x01.
The output bytes from the call BCryptDecrypt is then like this:

 [0]  0x95    byte        [1] 0x28    byte        [2] 0xE5    byte        [3] 0x18    byte
 [4]  0x90    byte        [5] 0x8E    byte        [6] 0x31    byte        [7] 0xFF    byte
 [8]  0xF0    byte        [9] 0x28    byte       [10] 0x86    byte       [11] 0x7B    byte
[12]  0x9D    byte       [13] 0x63    byte       [14] 0x2F    byte       [15] 0x01    byte

The decrypted file result that returns from the decrypter to the user looks like this:

Text :  ?????xi?G?w?T}!y?(???1??(?{?c/ Bytes :
3F3F3F3F3F78693F473F773F547D21793F283F183F3F313F3F283F7B3F632F (Thay
have removed the 0x01 and the bytes is a bit different, maybe something
with how I formatted it or it does something more before returning the
bytes?)

So my questions are:

How does the info I did send turn out to be 0x01 at the end?
What do I need to xor to the result to get the plaintext/byte?


texts: Given enough RSA ciphertext, is it possible to determine which key was used?

texts:
Given enough RSA ciphertext, is it possible to determine which public key was used to generate the ciphertext?

Presume an unknown public key that was used to generate RSA ciphertext, and we have quite a lot of ciphertext. Would it be possible to determine which key was used to generate the ciphertext?

It seems to me that any ciphertext would be in the range $[0, N)$ where N is the modulus. So if you have enough ciphertext you should be able to estimate a value for N. Now I don't think that this would be enough to establish N even when given enough ciphertext. But I wonder if you could find out which key was used from a set of public keys with some certainty.

Could there be enough information to establish which key is used? Is there a formula that would allow me to calculate the certainty for each key out of a set? Would that formula only consider basic probability over the range or is there anything in the RSA scheme to be more precise?

Only padded RSA with PKCS#1 v1.5 padding or OAEP padding may be considered, not raw/textbook RSA.


texts:
Attacks on a MAC that do not require the discovery of the key are possible.
Consider the following MAC algorithm. Let $M=(X_1\mathbin\|\dots\mathbin\|X_m)$ be a message that is treated as a concatenation of 64-bit blocks $X_i$. Then define:
$\Delta(M) = X_1 \oplus\dots\oplus X_m$
and
$C_k(M) = E_k[\Delta(M)]$
where $\oplus$ is the exclusive-OR operation and encryption algorithm is DES
in ECB mode. Thus the key length is 56 and the MAC length is 64 bits.

How would an attacker breach the system without knowing the encryption
key?


texts: Why is pseudorandom OTP (P-OTP) IND-CPA insecure

texts:
My lecture notes state that P-OTP is IND-COA but not IND-CPA insecure. I understand IND-COA secure, assuming PRG is secure, as that is the whole point of a OTP, but why is it IND-CPA insecure? Surely, if the PRG is assumed to be secure, then the resulting ciphertext would be random, so whatever plaintext you feed into the oracle will reveal no information.

I ask this because PRF+OTP is IND-CPA secure and cannot figure out the difference.

$Enc_k(m)=m\oplus PRG(k)$

$Dec_k(c)=c\oplus PRG(k)$

and the IND-CPA adversary game:

Pick two messages $m_0$ and $m_1$ arbitrarily.
Send them to the challenger who chooses $b\in\{0,1\}$ uniformly at random and returns you $c_1=Enc_k(m_1)$.
Output your guess for $b$ named $b'$. You "win" iff $b=b'$.

Edit: screenshots of the relevant slides


texts:
I would like to get a USB token to secure my keys. My use case is protection of 3 GnuPG keys that I will be using 10 times per day at least. I plan to create a new key ring from scratch. Because ECC seems more future-oriented than RSA, this is what I chose to use. I'm wondering which USB token to choose as well as which curve.

On the GnuPG FAQ, it is said that many people think curves recommended by the NIST or defined by Brainpool have a doubtful origin; therefore, they recommend the non-standardized Bernstein’s Curve 25519. On the NitroKey forum, one poster says that

He is not aware of any profound criticism of Brainpool curves, and
Bernstein’s Curve 25519 is hard to protect against side-channel attacks when implemented in embedded devices.

As a result, I'm a bit lost as to which key/curve to choose.


texts: Is it necessary, that the public key is a prime number in the RSA algorithm?

texts:
I read some  books talk about RSA cryptography but I did not understand something when choosing a public key $e$ Sometimes the condition is

$1<e<$$\phi(n)$

Where $\phi(n) = p-1 * q-1$

also sometimes is

$e \in [{1,2,...,\phi(n)-1}]$

also sometimes is

$e$ should be prime number

Examble

Choose $p = 3\ and\ q = 11  $

Compute $n = p * q = 3 * 11 = 33 $
Compute $\phi(n) = (p - 1) * (q - 1) = 2 * 10 = 20$
Choose $e$ .here can choose e = 7 where 7 is prime number or I can choose $e=9$ where 9 is relatively prime to 20.

My question

Are both states right when choose 7 and 9. or not right .If no why???


texts: Linear feedback shift register combination, secure?

texts:
I am currently working on a project which consist in the encryption of image using the GPU of a raspberry.

I would like to use LFSR to generate a stream cypher in each Core of the GPU.
In the wikipedia article they recommend to use combination of several LFSR, we could use 2 LFSR, one could tell if we use the current output bit from the other one shrinking generator

It says: "Despite this simplicity, there are currently no known attacks better than exhaustive search when the feedback polynomials are secret"

Do you think it's a good choice ?

Working with image makes me working with large field of data, Kb files.
I saw that if we select a good polynomial we can have a large period, so in theory if i have a 32 bits LFSR register and i use a polynomial from this page
polynomial

Could I generate 2^32 pseudo random bits (not  bytes) ?

Last question, is it okay to use the same polynomial and changes the seed (initial state of the register) for later use or should i change the polynomial each time i want fresh data ?


texts: Security exists or not in Modification in schnorr signature

texts:
In Schnorr's digital signature protocol (https://en.wikipedia.org/wiki/Schnorr_signature), the signature is $(s,e)$ where $s=k-xe$.
Assumption:
 $k$ and $x$ are assumed to be secret value of user.
So, ($k,x$) value is never changed except $e$.
$s_{i}=k_{i}-x_{i}e$ for $i$ users
Unlike Schnorr's signature, $e$ is also kept secret so that only valid users, who knows respective k and x values, can reveal it.
Even though different $k,x$ values, $e$ is selected uniformly randomly from $ Z_{q}$ and assumed to be same for all valid users.

Does the modification secure to securely deliver different values of $e$ for every time ?


texts: In the SIKE known answer tests, why is there only one secret key?

texts:
I'm looking at the SIKE known answer tests and am realizing that I'm confused on all the different terms in a Diffie-Hellman key exchange.

From the Wikipedia page, I would think there would be a public key and 2 secret keys, then a shared secret. However, the KAT provides a public key, a secret key, a shared secret, and a ciphertext. What exactly is the ciphertext, and where is the secret key?


texts: A fair peer-based coin-flipping protocol?

texts:
I found this question on the game programming site and was intrigued.  I came up with an answer off the top of my head but I'm no cryptanalyst so it is probably not water-tight.
This is how my idea goes:

each of the two peers generates a random number.

each peer creates a salted hash of its number and sends it to the other peer.

once both peers confirm reception of each other's hashes, each then sends the other its actual random number.

each peer verifies that the hash sent by the other is actually a hash of the random number.

the result of the coin flip is the XOR of the least significant bit of each number, i.e.
(a & 1) ^ (b & 1)

So would it work? If not, how could it be made secure? Is there some conventional method for solving problems like this one?
The rules are, there are two untrusted parties with no intermediary.  Assume the channel of communication is secure.  Neither party must be able to unfairly win or lose.


texts: Are attributes of an access structure visible or guessable in a CP-ABE ciphertext?

texts:
Suppose that Alice has attributes A, B and C. I have a ciphertext with this policy: A AND C.

Can an adversary guess the attributes and then decrypt the ciphertext? What is the probability of guessing attributes in a ciphertext policy attribute based encryption?


texts:
It sort of looks like to me that there is a kind of risk mitigation in the architecture of block cyphers vs the xor cypher.

In XOR, the risk is entirely in the random number generator. The XOR operator by itself is perfect, it provides perfect forward secrecy, so if used with perfect random numbers, so the risk is entirely shifted into the RNG.

In a block cypher, like AES the risk or the majority of the risk is inside the cypher, and only a small risk is inside the key. Obviously if the key is somewhat decent, I believe they hash the key, so frequency analysis is off the table, again implying that the hash algorithm is decent as well, shifting most of the private key's risk into the hash algorithm's security.

So basically there is little risk in a block cypher that comes from the private key, if the private key is decent. Now if the PRNG is weak, then it can be brute forced, or if the PRNG generator generates deterministic numbers, then it can be guessed, but that is more like an Information Security problem than a Cyptographic problem.

Therefore the majority of the risk, since the attack surface is much larger, is in the block cypher itself.

It would technically be easier to find a vulnerability in a block cypher than to break a 256-bit key even if it has like only 150 bits of entropy in it.

And if we are involving theoretical quantum computers, well then again, that is a risk of the block cypher, since it's not secure enough against the capacity of a theoretical quantum computer, whereas a perfect XOR would be.

Conclusion

So it kind of looks to me that the way a block cypher works is that it assumes that it's hard to generate TRN, so it shifts the burden away from the randomness into the complexity of the block cypher.

Meanwhile a XOR or any other OTP type of encryption relies purely on a good RNG, while the algorithm itself is perfect.

Question

Is this this a good way to interpret their role?


texts: How to prove that a perfectly secure cryptographic protocol is not possible in a given scenario?

texts:
This question was inspired from the discussion related to this question on security StackExchange.
Now I was wondering given a scenario, is there a general approach to prove that a cryptographic protocol is possible/not possible for a the constraints provided? All I could think of was, trial and error. Develop a protocol, see if you can break it and if not, then you have your answer.


texts: A simple block cipher based on the SHA-256 hash function

texts:
I've come up with this little routine for doing encryption using the SHA-2 (in this case SHA-256) hash function. As such it is a block cipher with a 256 bit (32 byte) block size and an arbitrary key length. It's easy to see that you could replace the hash function and get an entirely new type of algorithm.

I want to know if there are any problems, especially flaws, in this construction, and whether algorithms of this type have been studied.

Initialization with key:

$$ S_0 = H(k) $$

Encryption for plaintext blocks $P_1, \dots P_n$:

$$ S_i = H(S_{i-1})$$
  $$ C_i = P_i \oplus S_i $$

Decryption for ciphertext blocks $C_1 \dots C_n$:

$$ S_i = H(S_{i-1})$$
  $$ P_i = C_i \oplus S_i $$

Here is some sample C source code using SSL:

#include <openssl/sha.h>

struct sha_crypt_state {
    unsigned char digest[SHA256_DIGEST_LENGTH];
};

void sha_crypt_set_key( sha_crypt_state *state, unsigned char *key, int key_length )
{
    SHA256( key, key_length, state->digest );
}

void sha_crypt( sha_crypt_state *state, unsigned char *block )
{
    sha_crypt_state temp;
    SHA256( state->digest, sizeof(state->digest), temp.digest );
    memcpy( state->digest, temp.digest, sizeof(temp.digest) );

    for ( int i = 0; i < sizeof(state->digest); ++i ) {
        block[i] ^= state->digest[i];
    }
}

void sha_crypt_test()
{
    const char *key = "secret";

    // prepare a test block
    char block[SHA256_DIGEST_LENGTH];
    memset( block, 0, sizeof(block) );
    strcpy( block, "Hello, testing encryption!" );

    // test encrypt
    sha_crypt_state state;
    set_key( &state, (unsigned char *)key, strlen(key) );
    sha_crypt( &state, (unsigned char *)block );

    // test decrypt
    set_key( &state, (unsigned char *)key, strlen(key) );
    sha_crypt( &state, (unsigned char *)block );
}


texts: I am trying to encrypt the word Hello using RSA. When encrypting Hello’s integer representation, is each letter encrypted separately, or is the whole thing encrypted? Furthermore, am I correct in assuming that Hello is to be represented in binary form for RSA encryption?


texts: Can we proxy-re-encrypt using homomorphic encryption schemes?

texts:
Homomorphic encryption schemes are PKE schemes with an additional special method Evaluate.

The Evaluate method takes input any function (as boolean circuit) and encrypted inputs of the function and evaluates the circuit. The results of such function are still encrypted under the public key $PK$.

Now, if the user needs to re-encrypt the data with a new public key $PK^1$, the user should decrypt the data with older private key $SK$ first, and then encrypt again with new $PK^1$.

Or how can I efficiently proxy-re-encrypt using FHE schemes without decrypting the data?

Note that if the user runs the re-encrypt circuit as input to the Evaluate method with $PK^1$ as parameter, the result would still  be encryption of (encryption of original data with new $PK_1$) with the older $PK$.


texts: Digital signature for an expiring password

texts:
I would like to create a publicly available tool that is used to generate a password that gives a limited time access to a resource.

My idea is to digitally sign the current date with a private key entered by the user, generating a message that is sent to the resource that verifies it with the public key. If valid, the access is granted if the date matches the current date.
The only secret element is the private key.

My constraints are:

as the private key has to be memorized and typed, it should remain short (10 characters)
the generated message should be as short as possible, to be manually typed

What is the best security level that can be reached with these constraints?
What algorithm can be used?


texts: What is the connection between "replay attack" to CCA security?

texts:
Often in analyzing systems, the emulation of Replay Attack becomes important. Are systems that protected against CCA attacks also immune against replay attack, or it is a different criterion?
Thanks


texts: Gram-Schmidt coefficients in LLL algorithm

texts:
To my understanding the LLL lattice reduction algorithm starts with a set of integer vectors $\{b_1, \dots, b_2\}$, which span a lattice, and tries to generate a new basis of shorter vectors of the same lattice.
It first defines the Gram-Schmidt orthogonal basis $\{b_1^\ast, \dots, b_2^\ast\}$ (which is in general not integer) and proceeds to find new vectors according to
$$
b_i \leftarrow b_i - \lfloor \mu_{i,j} \rceil b_j \,
$$
where the Gram-Schmidt coefficients  $\mu_{i,j}$ are given by
$$
\mu_{i,j} = \frac{(b_i, b^\ast_j)}{(b^\ast_j, b^\ast_j)} \,.
$$
This process is repeated iteratively (including some resorting of the $b_i$) until certain criteria are met.
However, naively I could also imagine to use
$$
\tilde \mu_{i,j} = \frac{(b_i, b_j)}{(b_j, b_j)}
$$
instead of $\mu_{i,j}$ in the above replacement rule.
In particular, if one tries to minimize the norm of $b_i + \lambda b_j$ analytically by taking the derivative of
$$
\|b_i + \lambda b_j\|^2 = \|b_i\|^2 + 2 \lambda (b_i, b_j) + \lambda^2 \|b_j\|^2
$$
with respect to $\lambda$ and setting the resulting expression to zero, the optimal $\lambda$ is exactly given by $- \tilde \mu_{i,j}$ (and not $- \mu_{i,j}$).
So I would imagine that the shortest possible vector on the lattice is obtained by rounding this value to the closest integer.
Therefore, my question is: Why does LLL use the coefficients $\mu_{i,j}$ and not $\tilde \mu_{i,j}$? For just two input vectors they are literally the same, but do they guarantee a shorter runtime or better results (despite my naive argument) in the higher dimensional case?


texts: Is there a bulletproof way to know a file has been successfully decrypted?

texts:
I am wondering whether there is a bulletproof way to know if one is successful in decrypting a file.

As an example, say I encrypt a text file and protect it with a 3 letter password. I use brute force to decrypt it, but two different passwords lead to a file that contains English intelligible text. Is there a way for me to know which one is the original one? In other words, is there an infallible way to know I've entered the password correctly?


texts:
A gradual fair exchange (layman term) is a form of fair exchange protocol where Alice will transfer 1 bit to Bob then Bob will transfer 1 bit to Alice. The flaw with this protocol is that the party which starts first may lose out as after Alice transfer her final bit to Bob , Bob may choose not to transfer his final bit to Alice.

An optimistic fair exchange is like a normal fair exchange except that in the event of a dispute , there is sufficient evidence to show who misbehave during the protocol. An arbitrator is present to settle the dispute.

I would like to know if there's an fair exchange system which combines both optimistic and gradual fair exchange protocols such that I get the best of both worlds? How would it work if its exists?
Is it possible to make gradual fair exchange protocol any fairer, if yes how is it done?
I would also appreciate if someone can explain to me how is "evidence" gathered during the optimistic fair exchange protocol?


texts:
Depending on the framework you are using, there are various padding modes that can be used with AES encryption. For example, with .NET we can choose PKCS7, ISO10126, ANSIX923, Zeros or None.

I understand that the encryptor and decryptor need to use the same mode to be interoperable.

What considerations are there when choosing a padding mode? With the exception of 'None', does it even matter which you choose? Can some be considered more secure than others?


texts: What is the difference between a bijective random oracle and a random permutation?

texts:
Assume

$S$ be a finite set
$O$ be a random oracle from $S$ to $S$, such that $O$ is bijective
$f$ be a random permutation of $S$

Is there any difference between $O$ and $f$?

Does it makes any difference if $S$ is not finite?


texts: Difference between plain AES CTR and "CCM-style" CTR

texts:
I am trying to adapt the following function from SJCL, which does "AES-CCM" style CTR encryption, to do "pure CTR" encryption. I am playing around with SIV and would rather use this well-reviewed implementation rather than build my own CTR cipher from scratch. However, I'm having trouble understanding exactly what the CCM part does, and how I would go about modifying this routine to "strip out" the CCM functionality (the part that deals with the tag and the L parameter). My question is: what exactly is (are) the difference between the two CTR "styles", and how does that translate in the snippet below? Any help is appreciated.

_ctrMode: function(prf, data, iv, tag, tlen, L) {
  var enc, i, w=sjcl.bitArray, xor = w._xor4, ctr, b, l = data.length, bl=w.bitLength(data);

  // start the ctr
  ctr = w.concat([w.partial(8,L-1)],iv).concat([0,0,0]).slice(0,4);

  // en/decrypt the tag
  tag = w.bitSlice(xor(tag,prf.encrypt(ctr)), 0, tlen);

  // en/decrypt the data
  if (!l) { return {tag:tag, data:[]}; }

  for (i=0; i<l; i+=4) {
    ctr[3]++;
    enc = prf.encrypt(ctr);
    data[i]   ^= enc[0];
    data[i+1] ^= enc[1];
    data[i+2] ^= enc[2];
    data[i+3] ^= enc[3];
  }
  return { tag:tag, data:w.clamp(data,bl) };
}


texts: How to break fully homomorphic encryption over integer algorithm with known cipher of same integer?

texts:
If I do encryption and decryption like this:

Encryption: $\text{E}(m) = (r \times p_1+m) \bmod N$

Decryption: $\text{D}(\text{E}(m)) = ((r \times p_1 + m) \bmod N) \bmod p_1 = m$

where,

$r$ = random number

$p_1$ = random large prime

$m$ = plain text (int)

$N$ = product of two large primes $p1 \times p2$

So, my question is if $\text{E}_1(m)$ and $\text{E}_2(m)$, two different ciphers for the same integer are known, what could be done to break the algorithm?

This question is for my assignment but I do not have a clue where to start. A little clue will be appreciated.

Thanks.


texts: Secondary hash function utility, regarding data destruction?

texts:
Given that hash functions are inherently irreversible, would they not then be useful in applications where it's desired to overwrite sensitive data? (i.e. Darik’s Boot and Nuke)

Specifically, why should hash functions not be used for data clearing?


texts:
This question is related to the question I asked here. I'm looking for encryption scheme with the following properties:

Given $m$ is a 256-bit value, $pub_a$ and $pub_b$ are public keys, and $priv_a$ is a private key for $pub_a$:

$E'(E(m, pub_a), pub_b) = E'(E(m, pub_b), pub_a)$, where $E'$ is a re-encryption function
$E(m + x, pub_a) = E(m, pub_a) ⊕ E(x, pub_a)$, where $⊕$ could be either $+$ or $*$
$D(E(m, pub_a), priv_a) = m$

It seems like non-randomized "exponential" version of EC El Gamal (as described here) satisfies conditions 1 and 2, but 3 would be difficult to do for large values of $m$. There are potential ways to get around this, but I'm wondering if there is another encryption scheme that could be used instead. (note: using non-randomized version should not compromise security because messages would be randomly padded prior to encryption).

Specifically, I came across this paper which in section 3.2 describes something that might work for my purposes. Unfortunately, my ability to read scientific literature is not advanced enough for me to fully understand the proposed scheme.

Explanation of how a modified EC El Gamal satisfies conditions 1:

Assuming $G$ is a generator point, $m$ is a padded message, $x_a$ and $x_b$ are private keys, and $X_a$ and $X_b$ are corresponding public keys, we can do:

$k_a = H(X_a)$, $k_b = H(X_b)$, where $H$ is some hash function
Encrypting $m$ with $X_a$ we get: $C_a = (k_aG, mG + k_aX_a)$
Encrypting $m$ with $X_b$ we get: $C_b = (k_bG, mG + k_bX_b)$

We can then define re-encryption as follows:

$C_{ab} = (k_aG + k_bG, mG + k_aX_a + k_bX_b)$
$C_{ba} = (k_bG + k_aG, mG + k_bX_b + k_aX_a)$

So, we have $C_{ab} = C_{ba}$


texts: Cryptography Headers in Cryptographic Libraries

texts:
I have a question regarding the headings in cryptography. In python, in the pycryptodome module, I am doing symmetric encryption, which asks for a header that goes as follows:

Cipher = Crypto.Chiper.AES.new(key)
Cipher.update(HEADER)

My question is, how do I configure the header correctly? I've seen examples of just putting a str, like , and never explaining beyond what they are for, because I should use them, how I should use them, etc. If I need to know how to use them correctly, because I should use them, I understand that they are associated data that are linked or related to the content to be encrypted.


texts: Compression in key generation of DES algorithm

texts:
Does anyone have a pseudo-code or an algorithm or even a diagram of the compression (pc2) of the DES algorithm?

I can't find a relation between the bits that are dropped, even when I do it manually it does not generate the right result. I mean put as the first bit of the output (subkey $K_i$) the 14th bit of $C$, the 2nd of the output is the 17th of $C$.. the 25th bit of the output is the 41th of $D$.

Is the above correct or did I misunderstand?


texts: Relevance of Input and Ouput size of PRF on CTR mode

texts:
I'm working on exercise 3.25 on Katz' book (2nd ed):

  Let $F$ be a pseudorandom function such that for $k \in \{0, 1\}^n$ the function $F_k$ maps $\ell_{\text{in}}(n)$-bit inputs to $\ell_{\text{out}}(n)$-bit outputs.

  (a) Consider implementing CTR-mode encryption using $F$. For which
  functions $\ell_{\text{in}}$, $\ell_{\text{out}}$ is the resulting encryption scheme CPA-secure?

  (b) Consider implementing CTR-mode encryption using $F$, but only
  for fixed-length messages of length $\ell(n)$ (which is an integer multiple of $\ell_{\text{out}}(n)$). For which $\ell_{\text{in}}$, $\ell_{\text{out}}$ does the scheme have indistinguishable encryptions in the presence of an eavesdropper?

My answer is that it really does not matter: any combination of $\ell_{\text{in}}$, $\ell_{\text{out}}$ and $\ell$ will yield the mentioned security. Why do I think this? well, the proof that CTR mode is CPA-secure is presented in the book as theorem 3.32 and I'm pretty sure it only requires $F$ to be a PRF, with no restriction on the input and output sizes (even though it is presented with length-preserving PRF's), this should answer (a).

For part (b) I think something similar: the proof is not dependent on the message length (as long as it is polynomial in $n$, of course), so fixing a particular $\ell$ should not lead a vulnerability on CPA-security (let alone EAV-security).

Where am I failing? Intuition says this is not the case! for instance, if $\ell_{\text{in}}(n) = 1$ (for all $n$), then the counter can only be increased once and from there it will cycle
$${\tt ctr}, {\tt ctr}+1, {\tt ctr}, {\tt ctr}+1,\ldots,$$
which should lead to an attack, doesn't it? The proof should take out these cases somehow, but I just can't see it, it seems to work without even in this case.


texts: Example of CHI Square test on Caesar Cipher?

texts:
I am trying to get my head round the chi square test, when used with the Caesar cipher.
I started off using this formula,

$$ X = \sum_{i = 1}^k \frac{f_i · f'_i}{n · n'} $$

Where $k$ is the number of distinct letters in the alphabet, $f$ is the number of times the $i$-th letter appears in the first string and $f'$ is the number of times the $i$-th letter appears in the second string. And $n$ and $n'$ are the total number of characters in the first and second strings.

However when I run this, the highest value is not always the correct result. I was expecting values to be around 0.0650, however my correct answer is coming out around 0.0700. Is this the right way of calculating the Chi value?

The formula on Wikipedia is a completely different formula, and the values should be near to 0 for the correct answer? Which has confused me.


texts: Chi-Squared Step of Vigenere Cipher Decryption

texts:
So, I have been assigned an assignment where I had to solve a Vigenere cipher.

Following along with this webpage I managed to get all the way to the chi-squared step. But, that is the problem. Upon trying to code this, I found my results to be unfavorable. In fact, all of my results for the chi-squared probability test for each string were exactly the same. So, obviously I did it wrong.

I tried to use the formula on this page to calculate this for each character, and for each string, I added them all together. Doing this leads to them all being the same total number for each string, which makes sense. But, if that is the case, how exactly do I use it to solve the cipher?

What I did:

Found the key length with I.O.C. (say it's 7)
Create a string of all the 7th characters and the 1st
Write a method to calculate chi squared value
Calculate this for each character in each string from A-Z
For each string, add up the probability of all the letters(PROBLEM)

What exactly am I supposed to do here? All of my "chi-squared" results are the same.

P.S. I found the keyword using a codebreaking website to clarify that my other information was right, but I would really like how do solve this last step.


texts: Why 64 bits output hash function is insecure

texts: I know this is a insecure design to 64 bits output size hash function. Is there any report or literature illustrate this condition. I want to do some relevant reading about it.


texts:
How to determine the inverse multiplicative matrix of the following two irreducible polynomials GF(2^8)
x^8 + x^5 + x^3 + x^2 + 1 and x^8 + x^5 + x^4 + x^3 + x^2 + x +1


texts: How much stronger is RC4 if it is keyed with an RSA private key?

texts: My idea is to generate a RSA 2048 bit key and use RC4 with the private RSA key to encrypt a stream of data. RC4 is weak because RC4 keys are small, 256-bit. But when we use RC4 with private RSA 2048 key, how much stronger will it be?


texts: Public key encryption and big files with NaCL

texts:
I am trying to encrypt big files using NaCL (actually PyNaCL) - see http://nacl.cr.yp.to/box.html

After reading some docs, I came up with this prototype :

Bob wants to send a big file to Sarah. They both have a public/private key pair.

set "position" to 0
for each 256ko file chunk

generate a random nonce
append to the chunk 10 bytes containing position zfilled with zeroes
encrypt the chunk using crypto_box (using Bob private key and Sarah public key)
increment position

When Sarah gets the encrypted chunks:

set "position" to 0
for each encrypted chunk

decrypt the chunk using crypto_box (using Bob pub key and Sarah priv key)
extract the position and assert it's equal to "position"
increment position

prototype code here : https://github.com/tarekziade/fxakeys/blob/master/fxakeys/crypto.py#L119

What do you think ?


texts: SPAKE2 - Pairwise keys with multiple participants

texts:
With magic wormhole, I've discovered SPAKE(2) and I was wondering if it is possible to derive pairwise shared keys between multiple participants still using one password only. More precisely, amongst N participants, each node can broadcast the same handshake value to every other nodes.
Reminder for node A and B:

A) x random, X = g^x, sends X* = X * N^pwd

B) y random, Y = g^y, sends Y* = Y * M^pwd (N & M are public and can be the same)

If everyone broadcast the same handshake (X*, Y*, Z*...), and make pair-wise shared key with every other participants (i.e. combining X* and Y*, X* and Z*, etc), is it still secure ? The paper does not say about x being unique, although I might have overlooked.

Thanks


texts: Given a 128-trit state space, is a 3-symbol block cellular automaton secure against preimage attacks?

texts:
The following implementation, here for illustration:

void hash(int* bits, int bitsLen, int* out, int outLen){
  const int tt[9] = {1,2,0,0,0,1,1,2,2};
  int st[128], i, k, j, x, y, a, b;     // state st holds 128 trits
  for (i=0; i<128; ++i)                 // initial state setup
    st[i] = i%3;                        //
  for (k=0; k < bitsLen + outLen; ++k){ // for each input and output bit
    for (j=0; j<32; ++j){               // 32 times for each input and output bit
      if (k < bitsLen)                  // if processing an input bit..
        st[0] = bits[k];                // enter that input bit in state
      for (i=j%2; i<128; i+=2){         // for each pair of trits in state
        x = (i+0)%128;                  // index of first trit
        y = (i+1)%128;                  // index of second trit
        a = st[x];                      // get these current trits values
        b = st[y];                      //
        st[x] = tt[a*3+b];              // update these trits per table tt
        st[y] = tt[b*3+a];              //
      };                                //
    };                                  //
    if (k >= bitsLen)                   // building an output bit
      out[k-bitsLen] = (st[0] + st[1] + st[2] + st[3]) % 2;
  };
}

uses a 3-symbol block cellular automata, with transition rules encoded as the 3x3 table defined by tt and using a 128-trit (about 202 bits) state space, to materialize an one-way function. It employs k interactions, where each interaction advances the automata by 32 steps, inserting one of the input bits on the first cell of the automata at each step. Under those conditions, is this function secure against preimage attacks? Here is a test run.

Note: code commented and trimmed for clarity, without changing the output. See previous link or this for the original.


texts: Number of generators of an elliptic curve

texts:
Consider the elliptic curve E:$y^2 = x^3 + 3x + 11\,\, mod\,\, 19$. Two questions:

Let the cardinality of the set of points on the elliptic curve( including
$O$ ) be $|E|  = 25$. How many points are generators and why?
Find an element of this group that has order $5$. The group operation is addition of points.

Answer of (1): First, when the author says points, I assume he is being sloppy and really means group. The number of generators for a cyclic group with $n$ elements in it,
are the number of integers from $[1,n-1]$ that are relatively prime to $n$.
Therefore, in this case, the answer is $19$. Is my answer right?

Regarding question (2): I am thinking about guessing at the answer and doing a brute force approach (maybe doing the brute force approach in software) but it seems to me that there should be a shorter way to do it. Could you comment on my idea?

I think I just found a trick for solving the second question. Let $a$ be a generator of the group. Then I claim that $a^5$ is an element of order $5$. Is my claim correct?


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

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

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

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


texts: How to achieve identity authentication without revealing credentials

texts:
I am looking at a scenario where I would like to claim to an authority (call it A) that I am indeed me without revealing my identity documents. I am guessing some zero knowledge protocol has to be used. We can assume a trusted authority where I will show my identity documents for authentication. But I do not want A to know these details. I also do not want A to be able to collude  with the trusted authority and gain information about my identity. What are the possible schemes/areas I should be looking at?
From some reading I see that there is a Brands scheme and pairing based crypto schemes. One is interactive and the other noninteractive. Are there any other differences? Are there other schemes?


texts: Are there attacks on AES with 16-bit keys?

texts:
Are there known attacks on AES that uses a 16-bit key?
Assuming the data can be 95MB size, and that I can request the same data over and over.

For example, can someone explain to me how this code vulnerable? I know my around C, but can’t seems to find anything here. Usual CRIME attack won’t work.

#include <string.h>
#define MAX_SIZE 100000000
#define MAX_NAME_LENGTH 1000

unsigned char shared_key[16]={0x01,0x23,0x45,0x67,0x89,
0xab,0xcd,0xef,0x01,0x23,0x45,0x67,0x89,0xab,0xcd,0xef};

char directory_location[50]="../../server_directory/";
char *file_to_string (char *output_string,
FILE *input_file, int *length);

FILE *compress(char *input);

FILE *encrypt(unsigned char *key, FILE *input);

void application_send (FILE *output);

int get_file (char *name, unsigned int name_length)
{

FILE *input, *compressed_file, *encrypted_file;

int file_length;

char uncompressed[MAX_SIZE];

char file_string[MAX_SIZE];

char filename [MAX_NAME_LENGTH];

if (name_length >= MAX_NAME_LENGTH-50)

return -1;

strcpy(filename,directory_location);

strcat(filename,name);

input = fopen(filename,"r");

if (input == NULL)

return -1;

file_to_string (file_string, input, &file_length);

memcpy(uncompressed,name,name_length);

memcpy(uncompressed+name_length,file_string,file_length);

compressed_file = fopen("compressed","w");

if (compressed_file == NULL)

return -1;

encrypted_file = fopen("encrypted","w");

if (encrypted_file == NULL)

return -1;

compressed_file = compress (uncompressed);

encrypted_file = encrypt (shared_key, compressed_file);

application_send (encrypted_file);

return 0;
}


texts: ECC - Point Addition/Point Multiplication

texts:
So I have a very beginner-esque knowledge of ECDSA and I'm trying to write something in python to take a private key and output the public key (Basically from what I understand just trying to do the point multiplication k number of times on the basepoint) to get a better understanding.

My two main resources are the wikipedia page
and this tutorial.

While trying to program point addition, I couldn't work out how to calculate the lambda on wikipedia under point addition (Which as I understand as the "slope"). What happens if you get numbers that don't divide nicely into each other in the fraction?

One example I found in the certicom tutorial (my second resource) is with the curve $(a = 0, b = 6$ over $\mathbb F_{23})$ doing a point doubling on $P=(7,2)$. It gives $\lambda = 147/4  \mod 23$, which it then simplifies to $\lambda = (9 * 6) \mod 23$ . What happens to turn $147 / 4$ into $9 * 6$?


texts: What is the standard way to generate a unique non-reproducible ID?

texts:
Say that a manufacturer wants to label her products in such a way that a third party could verify that the manufacturer is the one that labeled the product, meaning it's not a counterfeit.

The manufacturer could have a serial number to each product, and have it signed with some signature scheme. However, this introduces some redundancy, as a verifier would have to use both the manufacture's public key and the serial number.

  Is there a different, more efficiently method create such labels?

Two cases are of special interest:

The label should be publicly verifiable.
The label should only be verifiable by an entity that share some secret information with the manufacturer (so perhaps encryption schemes are relevant).


texts: PBKDF security if all but one keys are exposed

texts:
I'm trying to understand the security of KDF but stuck with PBKDF case (case 3). Suppose, we have the following settings:

$KDF(SK,salt_1) \rightarrow k_1$

$KDF(SK,salt_2) \rightarrow k_2$

The adversary $A$ knows $salt_1$, $salt_2$, $k_2$ (and maybe even more derived keys $k_j$ for salts $salt_j$). His goal is to get $k_1$. Let even help him by makeing all salts closely related and haveing the same substring. Can $A$ learn $k_1$ from  $salt_1$, $salt_2$, $k_2$?

In the best (and almost unrealistic) case $SK$ is random and uniformly distributed in key space $K$. In this case, we can use some PRF $F$ to derivate a key $k \leftarrow KDF(SK,salt,l):=F(SK,salt||0)||F(SK,salt||1)||...||F(SK,salt||l)$
In such case $A$ can't learn $k_1$, otherwise $F$ is not secure PRF.
Slightly worse case: $SK$ is uniform in some subset of $K$. We need Extract-then-Expand KDF - so we use HKDF. At first we extract $k_{short} \leftarrow HMAC(salt, SK)$ and then expand $k_{short}$ to $k$ by using HMAC as PRF with key $k_{short}$. Again, $A$ can do nothing as long as underlying compression function in a hash is PRF and $SK$ has enough entropy.
Worst case: $SK$ is a password. Suppose it's PBKDF1 and $k \leftarrow PBKDF1(pwd,salt,c) = H^{(c)}(pwd||salt)$

On the one hand, $A$ still should learn nothing about $k_1$ if the hash is secure. On the other, I've got a feeling that he knows enough data to come up with something better than bruteforce. Am I wrong?


texts: Which is faster, PRF based on AES-CTR and PRF based on BLAKE{2,3}?

texts:
Recently Blake3 has been announced, which can be used as PRF.
I'm wondering which PRF is faster, namely PRF based on Blake3 or the one based on AES-CTR?


texts:
I have that $N = 798$, $p=2$, and $q=399$. I choose $e$ such that $\gcd(e,(p-1)(q-1))=1$ where $e=7$. I, then, choose $m = 123$. Thus, $c=123^{7}\bmod798=669$, which is my ciphertext. After, I try $d=7^{-1}\bmod398=57$. I, then, get the wrong result that $m'=669^{57}\bmod798=729$ which is not my original message $m$.

Why is this? I can't seem to understand why RSA would break. Does RSA break if either $p$ or $q$ is 2 and the other is a composite?


texts: Is this a PRF? Fk(x) = G(k⊕x) where G is a PRG

texts:
This is not homework, but a random thought.

Let $G(x)$ be a PRG.
We define the following function:
$$F_k(x) = G(k\oplus x)$$

My intuition is that it shouldn't be a PRF but I couldn't come with an example yet.

I tried to build a reduction from identifying G to identifying F but I'm not certain how you can simulate an oracle call when all you have is some string.


texts: Is there a big dataset containing RSA public $(n,e)$ and private keys $d$ and primes $p,q$ where $n = p.q$ ?


texts: How are the lower levels calculated using upper levels in an optimized Merkel Hash Tree?

texts:
I was reading about the TIK protocol for thwarting wormhole attacks on adhoc networks.
It uses a Merkel Hash Tree to store keys. But since the number of keys can be large, the tree is optimized by only storing the upper levels.

As far as I understand, the $a$ node is the result of the hash of its two children. But what I do not understand is that hashing is irreversible. If it is theoretically not feasible for an adversary to construct the child nodes if the parent node is known, how does storing the upper layers help at all?

What am I missing here?


texts: Plaintext DH keys in the message header in the Double Ratchet Algorithm

texts:
I've been reading details about the Double Ratchet algorithm, and I wanted some clarification regarding the aspect of the DH public keys going out in the plain in the header of every message. Quoting from the specifications of the Double Ratchet:

  Every message from either party begins with a header which contains
  the sender's current ratchet public key. When a new ratchet public key
  is received from the remote party, a DH ratchet step is performed
  which replaces the local party's current ratchet key pair with a new
  key pair

Doesn't that effectively allow an adversary to trace back the message to you and effectively prevent deniability? For example, lets say some messages get delayed from A to B, and meanwhile B is advertising the same public key over and over again, won't you be able to somehow know that it is B communicating with A. Probably, another way to put the same question is, is there a way for some adversary to know who B is, given that they can see their public key in the header (in that interval of time when B has not received a new DH public key from A)? Or alternatively, at least link that communication to a distinct user.

Thanks!


texts:
"All 8x8 s-boxes created using Galois Field inversion plus an Affine Transform have the same non-linearity, as the Affine Transform does not change the linear or differential properties" is what this answer claims.

Is there a proof of this statement?

I am unable to see how this is true. I tried to calculate the Walsh and autocorrelation spectrum but was unable to see how they are equal.


texts: Can we develop a working asymmetric crypto message protocol without an asymmetric encryption algorithm?

texts:
Our crypto libraries have:

DSA (4096, 512)
DH (4096)
AES (256)
SHA (512)

Let us say these are implemented directly in hardware so that trying to pull the pieces out is not possible, and the CPU isn't really fast enough to implement crypto itself.

Can we develop a protocol that permits us to exchange public keys, and at some later date send messages by courier or some means that does not assume live communication. That is, DH won't work directly because message round-trip time is intolerably long.

This question is far more interesting on a theoretical basis than any practical means by which I might have gotten here.


texts: Example of a Hash function which is second pre-image resistant but not collision resistant

texts:
We know that a collision resistant hash function is also second pre-image resistant. But the converse is not necessarily true.
I am looking for the example of a hash function which is second pre-image resistant but not collision resistant. Please help.


texts:
According to the birthday paradox we need approximately $O(|T|^{1/2})$ samples from the tag-space to find a collision for a hash function $h:K\times M \to T$. But how many samples are needed to find a three-way collision, i.e. $h(a) = h(b) = h(c)$ for three messages $a,b,c \in M$ hashed with the same key $k\in K$ ?

I thought that it would be $O(|T|^{1/2})$ to find $h(a) = h(b)$ and another $O(|T|^{1/2})$ to find a third, but when thinking about it, that feels wrong. How can I calculate this?


texts: Can poly1305 be used as an error-correction code?

texts: Given a message $m$ of size $n$, a key $k$, and a message authentication code $mac = poly1305(m, k)$ what is the minimum amount of bitflips on the message that can be corrected (or at least detected) by someone who knows the corrupt message, the mac code, and the key?


texts: What does this advantage statement signify?

texts:
In many Attribute Based Encryption papers I see this line...

The advantage of an adversary A in this game is defined as Pr[b' = b] − 1/2.

Can someone explain what it means to me?

I assume it means that the chances of the guess being correct is equal to 1/2. Is this assumption accurate?


texts: Why would anyone use an elliptic curve with a cofactor > 1?

texts:
In cryptography, an elliptic curve is a group based on a finite field $GF(p^k)$; this group has $n$ elements on it, and we work on a prime-sized subgroup of size $q$.  We denote the value $h = n/q$ as the cofactor of the curve.

My question is: why would we ever want to consider using a curve which has a cofactor $h>1$?  Or, in other words, why would we consider using an elliptic curve that had a composite number of points?  After all, the discrete log problem can be solved in $O(\sqrt{n / h})$ time; if we were to select a curve with $h>1$, we are deliberately making this problem easier.

Now, if $h$ is small, we're not making it much easier; if (for example) $p^k \ge 2^{256}$ and $h \le 4$, this would still appear to be an intractible problem.  On the other hand, I don't know if we want to make the attacker's job any easier than necessary, unless we gain some other benefit from it (perhaps making some other attack harder, or gaining some computational efficiency).

So, is there any benefit for using a curve with a cofactor > 1?


texts: Correlation among Psuedo Random Sequences generated from seeds which are correlated

texts:
I want to see and mathematically verify how PN sequence generated by LFSR or maximum length codes would correlate (auto-correlation and cross correlation) for seeds of varying correlation.

Say I want to generate 512 bits of PN sequence on two sides (A and B). To hide the possible output from eavesdropper I choose some seeds (which can be generated by both A and B simultaneously). The issue is the seeds(sequence of 512 bits) generated at various instants of time are correlated with previous time instants.

I want to:

  See how correlation in input seed affects correlation in output

Is there any paper or reference literature survey for same?

EDIT

My research efforts...

As of now I am studying properties of PN sequence generators. In my research I have a source which generates correlated sequences of various degrees. I want to analyse what happens to PN sequence generated using those seeds.


texts: Generate random in secure message transfer

texts:
I’m doing a school assignment about secure communications between a Server and a Client.
Basically, messages are exchanged between the clients and the server and these communications must implement confidentiality, authentication, integrity and non-repudiation.

Imagine I have to send a message from the client to the server. This is what I’ve idealized:

Client and Server both generate their public/private keys;
Their public keys are shared between them;
Client, generates a session key using 'AES';
Client encrypts the message using the session key and sends this to the server;
Client encrypts the session key with the Server public key and send this to the server;
Client creates a hash of the message and encrypts this hash with the client's private key and sends this to the server;
Server uses is private key to get the session key;
Server uses session key to decrypt the message;
Server decrypts the hash with the client's public key;
Server creates hash of message and compares with the above hash.

I’m thinking of creating a new session key every time the Client sends a message to the Server.

Is this the way it should be done?
In the generation of the keys I have to use a random number. How do i do this?

My thoughts for #2 are:

KeyGenerator keygen = KeyGenerator.getInstance("AES");
keygen.init(128,new SecureRandom());

Or this:

KeyGenerator keygen = KeyGenerator.getInstance("AES");
keygen.init(128,  System.nanoTime());

Or should I use other way? I'm asking this because I don't know the best way to generate the seed.


texts: How hard is to find the operators of an addition knowing the sum of them?

texts: I want to learn whether or no there is a cryptographic primitive,scheme assumption that is based on the following hard problem if it is hard . By hard we mean that we have a polynomial adversary: The attacker obtains a number  $\sigma$ . In order to reverse engineer that or to go one step further for the cryptanalysis she needs to break that number in a set of numbers $m_{1}, m_{2}, m_{3}, \ldots, m_{n} : \sum_{i=1}^{n}m_{i}=\sigma$ . How hard is that problem?


texts: Would it be safe to store GCM nonce in the encrypted output?

texts:
I'm looking to use AES-256 GCM to encrypt and authenticate a file containing sensitive information. I am a bit loss on where to store the nonce that is required for GCM.

Would it be adequate/safe to store the nonce unencrypted at the beginning the the encrypted file?


texts: Idea for user/pass hashing to prevent rainbow tables, would it work?

texts:
I'm very new to cryptography (and security in general, for that matter), but I had an idea that I'm sure is very flawed, but is worth asking. If a computer user, online account, etc, needs to verify a username and password, wouldn't this work well?

Upon signup, ask for username and password as usual
Hash username (charliebucket)
Hash username, colon, password (charliebucket:NgWB9pLx), using username hash as salt for user:pass hash.
Upon login, hash username and user:pass
Check if user:pass hash is the same, using hash of username as salt
If user:pass hash succeeds, log in.

In my theory, this would prevent rainbow tables two-fold. If you require 8-character and up usernames and passwords, the pre-hash string will be at least 17 characters, making it unlikely that it would be on a rainbow table. But even if it were, it would take 3+ quadrillion years on a desktop PC, I'd assume it would take a good thousand on a million-dollar cluster.

As I said, I'm fairly new, and don't fully understand anything related to cryptography or hashing (besides "password go in, hash come out"), but I thought there might be a circumstance where this could be used.


texts: Is there a possibility to create a public key block cipher?

texts: Why there is no public key-based block cipher? It is known that the block ciphers are symmetric-key encryption. However, what is the motivation to not design a public key encryption that encrypts blocks of bits?


texts:
I have a question regarding what parameters should be used when generating HMAC-SHA1-128. I have fairly limited knowledge in this field.

HMAC parameters:

H = Hash = SHA1

K = Key size = 128 bits (16 bytes)

B = Data block byte length = 64 bytes

L = Output size of SHA-1 Hash = 160 bits (20 bytes)

Ipad = inner padding = 0x36 repeated B times

Opad = outer padding = 0x5C repeated B times

Charset = UTF-8

Does this make sense? Anything else I should consider? I want to make it similar to the following RSA example:

Format = x.509

Charset = UTF-8

Encoding = Base-64

Endianness = Little Endian

Key size = 2048 bits

Is encoding, endianness or anything else other than the things I mentioned under HMAC parameters relevant and should be paid specific attention to?

Thank you!

Edit since last comment:

Regarding the data;

I would like to take data from 4 different columns in a database table and create a HMAC based on those - one HMAC for each row in the database table.

The data are the following:

Date(YYYY-MM-DD), Time (hh:mm:ss), String(xxxxx), Number (1000.00).

The data shall be separated by semicolon - so the full string will for example be: 2000-01-31;23:59:59;"hello";1000.00


texts: Why are processes requiring (almost) as much work as brute force considered an "attack" on a hash function?

texts:
In the literature on attacks against hash functions, I frequently come across algorithms requiring $2^n$ work described as being preimage or collision "attacks" on a hash function with only marginally more than $n$ bits of output$^1$.

Have I grievously misunderstood the terminology here?

If the result of the attack is an $n$-bit value then brute force takes $2^n$ tries; how can anything only slightly better than this be considered a meaningful enough "attack" to be worthy of publishing?

It seems to be making article titles nearly useless; a well peer-reviewed article titled "an attack against AES" in a reputable publication could be anything from irrelevant to cataclysmically internet-shattering in its consequences.

Here's an example from the Wikipedia page for Salsa20:

  In 2007, Tsunoo et al. announced a cryptanalysis of Salsa20 which breaks 8 out of 20 rounds to recover the 256-bit secret key in $2^{255}$

or key-recovery "attacks" against a symmetric cipher having only marginally more than $n$ bits of secret key, although I've been reading mostly hash function papers lately.


texts: Is calculating a hash code for a large file in parallel less secure than doing it sequentially?

texts:
I would like to improve the performance of hashing large files, say for example in the tens of gigabytes in size.

Normally, you sequentially hash the bytes of the files using a hash function (say, for example SHA-256, although I will most likely use Skein, so hashing will be slower when compared to the time it takes to read the file from a [fast] SSD). Let's call this Method 1.

The idea is to hash multiple 1 MB blocks of the file in parallel on 8 CPUs and then hash the concatenated hashes into a single final hash. Let's call this Method 2, show below:

I would like to know if this idea is sound and how much "security" is lost (in terms of collisions being more probable) vs doing a single hash over the span of the entire file.

For example:

Let's use the SHA-256 variant of SHA-2 and set the file size to 2^35=34,359,738,368 bytes. Therefore, using a simple single pass (Method 1), I would get a 256-bit hash for the entire file.

Compare this with:

Using the parallel hashing (i.e., Method 2), I would break the file into 32,768 blocks of 1 MB, hash those blocks using SHA-256 into 32,768 hashes of 256 bits (32 bytes), concatenate the hashes and do a final hash of the resultant concatenated 1,048,576 byte data set to get my final 256-bit hash for the entire file.

Is Method 2 any less secure than Method 1, in terms of collisions being more possible and/or probable? Perhaps I should rephrase this question as: Does Method 2 make it easier for an attacker to create a file that hashes to the same hash value as the original file, except of course for the trivial fact that a brute force attack would be cheaper since the hash can be calculated in parallel on N cpus?

Update: I have just discovered that my construction in Method 2 is very similar to the notion of a hash list. However the Wikipedia article referenced by the link in the preceding sentence does not go into detail about a hash list's superiority or inferiority with regard to the chance of collisions as compared to Method 1, a plain old hashing of the file, when only the top hash of the hash list is used.


texts:
In normal ElGamal encryption, the encrypted message is a pair (gb, gabM) - that is, the actual "encryption" is simply multiplication by the shared secret gab.
A common pattern with public-key encryption is to encrypt a symmetric key using PK, and then encode the actual message with the symmetric key.

It seems to me that you could simply use the shared secret gab as your symmetric key instead - so your pair would be (gb, AES(M, gab)).  (This looks extremely similar to agreeing on an AES key via Diffie-Hellman.)  This would take up less space, putting it on even footing with RSA + AES for a given key-/group-size.

So: has anybody heard of a scheme like this?  If so, does it have a name, and is it actually used?  As for why I'm interested:

Possible advantage: semantic security without DDH?

In normal ElGamal, we lose semantic security if we don't have DDH (given ga, gb and c, we can test whether c = gab).  AFAIU, this is because the message is encoded as E = gabM mod p, so you can divide by your suspected message (c = gabM/Mguess), and test whether it matches gab.

It seems to me that if we use gab to provide an AES key instead, then recovering a candidate c is equivalent to recovering an AES key from a plaintext/ciphertext pair.  I understand that AES is not susceptible to known-plaintext attacks, so does this mean we have semantic security even without DDH?

Possible advantage: easier generation of private keys?

With RSA, it takes a reasonable chunk of computational effort to generate a new public/private key pair (because you have to find a probably prime).  With ElGamal, it seems much easier, which means you could rotate your short-term keys much more often, without draining a low-power device.

The more often you rotate your short-term keys, the "better" your forward secrecy is.  (After all, if you rotated your keys so often that each one was only ever used once, then you're basically doing Diffie-Hellman, just re-ordered a bit.)


texts: Are large polynomials secure for order preserving "hashing"? (newbie question)

texts:
I've been searching for some time now for an answer to this simple question: if I have a large polynomial that is secret, and I use it to transform a set of integers so as to obtain a new set that preserves the order for each transformation, can the polynomial be deduced by an attacker only from the output?

Notes to take into consideration:

The polynomial is carefully chosen to assure the outputs maintain order
I'm working only with positive integers
An attacker would only be able to see the generated outputs, never the inputs nor the polynomial (of course)
The attacker could have access to large sets of generated outputs

One example of a valid polynomial could be: $$f(x) = 31x^{15}-27x^{14}+13x^{12}-10x^{9}+5x^{7} $$

Can the attacker deduce the polynomial from the output only, even if I make the polynomial much harder? Are polynomials even a possible solution for order-preserving "hashing"?

I assumed an attacker would be able to find out the secret polynomial through some fancy math tricks and algorithms, so I added the following three difficulties:

I'm "pre-transforming" the input before inserting it into the polynomial by adding a large integer $\beta$ to it, so as to skew the input away from small positive integers - this $\beta$ value is unique per polynomial
I'm "post-transforming" the generated outputs by dividing them with a common divisor as large as possible but that still maintains order - I'm doing this to take some information out of the generated outputs (the remainder) of the divisions. The common divisor is calculated the following way: $$commonDivisor = 10^{numDigits(f(1)-f(0))-1}$$
where $numDigits(x)$ outputs the number of digits in the provided number.
I'm also adding a random deviation value $\alpha$ to every output, that is small enough to not make it larger than the next output: $$out_{n-1}+\alpha_{n-1} < out_{n} + \alpha_{n}$$

All these operations together would produce something like the following:

$$f(x+\beta) = \frac{pol(x)+\alpha_x}{10^{numDigits(f(1)-f(0))-1}}$$

Continuing the previous question, would these changes make any real difference to the challenge of finding the polynomial, or are there ways to crack this?

A  not too technical answer would be very much appreciated due to my lack of experience in this field.


texts:
Let $(Mac, Vrfy)$ be a safe defined $MAC$ over $(K,M,T)$ where $ M = \{0,1\}^n$ and $T = \{0,1\}^{128}$.
Is the following $MAC$ safe? Show your proof.

$Mac'(k,m) = Mac(k, m)$

$Vrfy'(k,m,t) = \{Vrfy(k,m, t), $ if $m≠1^n;1, $ otherwise$\}$

My proof is as follows:
I take an example message $m = 01$ and query an oracle for the $T$ corresponding tag. And then I take another message $m' = 11$ and immediately see that $Vrfy'(k,11,T) = 1$ with the previous $T$ obtained tag, therefore I obtained true with a message that I did not query an oracle for it's tag, therefore it is not safe.

Is my proof correct and complete or am I completely missing the point?

Thank you for the help.


texts: LFSR for small numbers with large periods

texts:
I want to generate a few random numbers using an LFSR. However, the LFSR output depends on the number of taps, so for a large period I use large (relative) number of bits. This causes the numbers to be as large as the period. For example, I would like to use a 16-bit LFSR to generate random 5-bit numbers. What is the proper way to reduce the number of bits but still ensure that single numbers don't repeat and that the sequences don't become shorter?

[Edit:]

For degree 5, I am using the polynomial x^5+x^3+1 and the following code:

lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0x0014u);

For n = 16, I am using the polynomial  x^16 + x^14 + x^13 + x^11 + 1

lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xB400u);

Are any of these a problem?


texts:
I have this equation, $E_{K_{as}}(E_{K_{bs}}(K_{ab}))$ which means $K_{ab}$ is encrypted by $K_{bs}$ then whole packet is encrypted by $K_{as}$.

I think the key structure is $K_{as}$ is the master key, $K_{bs}$ is under $K_{as}$ and $K_{ab}$ is the session key.

My question is: if I have two long term keys and one session key, can I make both long term keys to be the master key? Or only one out of two of them can be the master key?


texts: Is RSA-OAEP secure when the exponent is equal to 3?


texts: Would the public key of Digital Signature be replaced?

texts:
According to my understanding, Digital Signature is a technology to use private key/public key to sign/verify data in order to ensure data authentication, integrity and non-repudiation. Sender signs the data with private key and send the signature with the original data to receiver, and receiver verify the signature to confirm the sender is trustworthy.

But I wonder how the receiver confirm whether the public key on his hand hasn't been changed?

I mean if it is possible that the public key has been intercepted and replaced with a fraudulent public key while transferring to the receiver, and finally receive a fraudulent message with a signature signed by a fraudulent private key? If there is a safe way to send a public key to receiver, why don't just send the message in the same way?

I tried to google for the answer but no luck, if you think this question is too simple you can just throw me the url or something, I am willing to study by myself.

Thanks in advance.


texts: Is it feasible to break Diffie-Hellman key exchange when the implementation uses a poor-quality PRNG?

texts:
I've come across an implementation of DH in Java that uses the Random class to generate the secret integer value $a$, as shown in in Wikipedia's description of the algorithm. As such, the seed of the RNG is only 32 bits and the output may be predictable.

By observing DH exchanges only, would it be possible to predict or compute the shared secret?


texts: Rsa accumulator's storage complexity is known as O(1). However, how can i calculate size of accumulator value in byte?


texts: Retrieve cryptographic key knowing cyphertext and plaintext

texts:
I was curious about cryptography so I started to learn about symmetric encryption.

From what I understand a symmetric encryption works as follow:

PlainText -> (Encrypt)K -> Cipher text -> (Decrypt)K -> PlainText

I was wondering if it is possible to retrieve the cryptographic key by knowing the plain text, the cipher text and the encryption algorithm used.


texts: Why does the following SIS-based decision language not make sense?

texts:
I'm currently reading about important lattices problems and noticed that while CVP, SVP, and LWE have decisional versions, SIS does not.  I read in the question Relation between decisional SIS and leftover hash lemma in lattices that deciding between the distributions (A, u) when $A \in Z_{q}^{n \times m}$ and $u = Ax$ for some short x, versus the case that "u" is random is unfeasible because these distributions are statistically close.

However, what keeps us from looking on this language (which seems closely related to SIS to me), and ask how hard is it to decide it?

$$L_{m,n,\beta, q} = \{(A, u) \in Z_{q}^{n \times m}\times Z_{q}^{n}\,|\, \exists x \in Z_{q}^{m}: Ax = u \wedge ||x|| \leq \beta    \}$$

This language seems well defined to me and in the case of $\beta \leq q$ it feels non-trivial too (looking on the first norm to keep the combinatorics simple - at most $(\frac{\beta}{q})^{m}$ of u's are in the language for each A...)


texts: Difference between cryptanalysis and brute force attacks

texts:
I wonder about the difference between brute force and cryptanalysis attack?
as my professor asked us about the difference,
but i searched and found that the brute force is one type of cryptanalysis attacks is that true or there's a difference between them ?
Thanks in advance.


texts: Is there short period in AES 128 key schedule?

texts:
I am wondering if for some particular keys the AES 128 key schedule lead to a periodic pattern for the round keys.
The key schedule is only 10 rounds, but I am also wondering in the general case where we expand the key much more, as it happens if one use the last round key of an operation as the key for the next operation (definitely not a standard use of AES, but of some interest on small devices with on-the-fly key schedule).


texts:
The article Elliptic Curve Digital Signature Algorithm in Bitcoin's wiki  talks about signatures having probabilities (as in Signatures are either 73, 72, or 71 bytes long, with probabilities approximately 25%, 50%, and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.).

What does “probability” mean in this context?


texts: Is AES-CBC mode not secure against chosen cipher-text attacks even if the IV is not predictable?

texts:
I've seen questions where people have asked if AES-CBC mode is vulnerable to chosen cipher-text attacks if the IV is predictable.

But is it guaranteed to be secure against chosen cipher text attacks if the IV is not predictable?


texts:
Follow up on this question: How efficient are the generic attacks regarding near-collision-resistance?

  Let $H:\{0,1\}^∗→\{0,1\}^n$ be a cryptographically secure hash function. Let $k\in \mathbb{N}$ be $0 \leq k \leq n$. Without further details, how much effort is needed to find two strings $x_1,x_2$ such that $\Delta(H(x_1),H(x_2))\leq k$ holds? $\Delta(\cdot,\cdot)$ denote the hamming distance.

The accepted answer mentioned that it requires $\displaystyle \sqrt \frac{1}{p}$ hashes where $p=\displaystyle \frac{\sum_{i=0}^{k}{n\choose i}}{2^n}$ to have probability of $1/2$ to obtain one near collision pair. Why is that?

I tried to work out the math using birthday paradox. I get the minimum number of hashes one has to compute is something like:

$$\frac{2^{n/2}}{\sqrt{\sum_{i=0}^k{n\choose i}\cdot 2^i}}$$

Where did I go wrong ?


texts: What does the strict avalanche criterion mean?

texts:
I can build black box ciphers with the following properties:

Satisfies SAC, but is trivially weak (a keystream from an LFSR seeded with the key).
Does not satisfy SAC, but built from secure primitives (Base64 encode the output of AES).

From 1 you can see that SAC is not sufficient for security. From 2 you can see that SAC is not necessary for security.

Since neither $SAC \implies Security$ and $Security \implies SAC$, what conclusions can you make based on SAC?


texts: Is xgcd faster than Fermat for calculating $d$ in RSA?

texts:
I want to calculate $d$ from $e$ when generating RSA keys.

What is faster?

Calculating $\operatorname{xgcd}(e,p)$ and $\operatorname{xgcd}(e,q)$ and CRT.
Or calculating $e^{p-2}\bmod p$ and $e^{q-2}\bmod q$ and CRT.

I'm having a hard time understanding how to calculate the complexity here.


texts: Can I use the secret part of a asymmetric encryption keypair as a symmetric encryption key?

texts:
Background

I'm working on a framework for crypto-based authentication and authorization that is largely inspired by the way Keybase's Teams product works.

Keybase uses the same process to generate per-user keys and per-team keys. Quoting their docs:

  A user generates a 32-byte random seed s.
  She computes e = HMAC(s, "Keybase-Derived-Team-NaCl-EdDSA-1") and uses this value as the secret key for an EdDSA signing key. She then computes the public half, yielding keypair (E, e).
  She computes d = HMAC(s, "Keybase-Derived-Team-NaCl-DH-1") and uses this value as a secret key for a Curve25519 DH encryption key. She then computes the public half, yielding keypair (D,d).
  Computes c = HMAC-SHA256(s, "Derived-User-NaCl-SecretBox-1") and uses this value as a symmetric secret key.

In brief:

Make a random seed, and use it to generate
A signature keypair
An asymmetric encryption keypair
A symmetric key

Question

I was thinking that to simplify things, I could skip step 4 and reuse the asymmetric encryption secret key d as the symmetric key, instead of deriving an additional key c. In practice, if you know one, you'll know the other. All else being equal, I'd prefer to have fewer moving parts.

Is there a reason not to do this?

(To be clear, my system doesn't need to interoperate with Keybase - I'm just
using their process as a model.)


texts: Space complexity of quantum collision search?

texts: Is there a known way to reduce the space complexity of quantum collision search (PDF) beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below what is achieved by the classical Pollard's rho method?


texts: How to exctract ECDH parameters from an OpenSSL-generated $G$?

texts:
I'm using ECDH for generating ECDH public parameters (p,a,b,G,n), I try to get this values using openssl ecparam -in cert.pem -text -noout

For Generator $G=(x,y)$ I get :

Generator (uncompressed):
  04:aa:87:ca:22:be:8b:05:37:8e:b1:c7:1e:f3:20:
  ad:74:6e:1d:3b:62:8b:a7:9b:98:59:f7:41:e0:82:
  54:2a:38:55:02:f2:5d:bf:55:29:6c:3a:54:5e:38:
  72:76:0a:b7:36:17:de:4a:96:26:2c:6f:5d:9e:98:
  bf:92:92:dc:29:f8:f4:1d:bd:28:9a:14:7c:e9:da:
  31:13:b5:f0:b8:c0:0a:60:b1:ce:1d:7e:81:9d:7a:
  43:1d:7c:90:ea:0e:5f

My question is, how to extract $x$ (the x-coordinate of the generator $G$) and $y$ (the y-coordinate of the generator $G$) values from this answer.
by the way: when displaying ECDH parameters I get a seed value. Can someone please explain what this value is useful for?


texts: Do Cryptographic Hashing Algorithms operate only on Integers?

texts:
Do all the Cryptographic hashing algorithms operate only on integers (32 bit or 64 bit)? Is there any operation performed on Floating Point Numbers as well?

The reason I ask this is because I read here that there are no floating point calculations performed in hashing algorithms and hence FLOPS do not matter:

http://www.golubev.com/about_cpu_and_gpu_2_en.htm


texts: Since XMSS only requires a 2nd preimage resistant hash function, is using Blake2 in XMSS possible? It is not in standard, but Blake2 seems to be faster than SHA256


texts: What is the easiest cipher to use in designing double ciphers?

texts:
I want to make a double cipher consisting of two encryption method Enc1 and Enc2, and two corresponding decryption mechanisms Dec1 and Dec2. I want it so that:
(1) we can encrypt any message M1 to a ciphertext C1 using Enc1  and a key K1, and it can decrypt the ciphertext C1 with Dec1, using the same key to recover M1.
(2) There exist key K2, where Dec2(C1,K2) = M2 and Enc2(M2,K2) = C1, and M2 makes sense(intelligible).
In conclusion, I want to make a cipher designed for a scenario in which if someone were forced to decrypt the ciphertext, they could do so with a different key K2 to produce a message that makes sense but is not the original message.
What is the best cipher to use to accomplish this?


texts: DES Encryption Algorithm all 64 bits for key instead of 56 bits

texts:
Would a DES algorithm that uses all 64 bits for the key instead of just the 56 bits be more secure? I have been thinking about it but those 8 bits used for parity are very useful and but including them in the key could potentially make it more easily cracked.

From Wikipedia, it stated that the 56 bit key was cracked in 4 days due to hardware. Now if we include the 8 parity bits to make it a 64 bit key, would that make the key crackable after 1024 days? My math: 2^8 * 4 = 1024 days. Assume we use the same hardware.

If we included the 8 parity bits, would it have made the security of DES substantially stronger?


texts:
In the Digital Signature Algorithm, is there a reason why the larger prime parameter should be an $N$-bit prime where $N$ is a multiple of 64 ?
Is this strictly necessary for proper working of the algorithm?


texts: RSA function over $Z_t^{*}$ where $t$ is prime

texts:
RSA function is defined over $Z_N^{*}$ where $N=pq$ with $p,q$ primes. A public key is a pair $(N,e)$ and a private key is $(N,d)$ where $d=e^{-1} \mod \phi(N)$.

Assume that RSA function is defined over $Z_t^{*}$ where $t$ is prime (instead of $t$ being composite). Show how one can compute $d$ from a public key $(t,e)$.

Could you check my solution? It looks a really easy assignment... if $t$ is prime, then $\phi(t)=t-1$, so $d$ can be calculate from formula: $d = e^{-1} \mod \phi(t)=e^{-1} \mod (t-1)$? And that's it?:)


texts: What are the possible security issues when exporting a plaintext database to a file like this?

texts: Say I have plaintext database with key-value pairs of usernames and passwords. Then I iterate through the database, encrypt the passwords, and write the username and encrypted password pairs to file with a specific format: I would be storing the salt, IV, and an encrypted hash checksum (for authentication to file) in the headers. The rest of the file would be the username-encrypted password pairs. There are indicators that specify how many bytes the username and passwords are. What would be some of the security issues with this file format?


texts:
Most successive squaring time lock puzzles I've seen appear to be broken by Shor's algorithm. Is there another practical and efficient time lock protocol that is not broken by Shor's algorithm? If not, what will I need to make one?
time lock requirements
What I mean as a time lock puzzle is something that balances being cheap to crack, but requires a lot of time to crack. This is achievable by requiring that a solver computes a long, non-parallelizable function. However, it has to be very cheap (less than a minute of modern CPU time) to make. In order to encrypt something with the puzzle, the creator probably needs to know the outcome of the puzzle when creating it. If there is a way to encrypt something with out knowing the solution (via asymmetric encryption) that will also be acceptable.
known research
I have read that as of 2014 there were no (at least practical) alternatives to successive squaring. A lot has happened since then. One more recent creation, verifiable delay functions(VDF), are very similar to time lock puzzles but has a different purpose. It may be worth looking in to to see if VDFs can be converted to time locks.


texts: Is ciphertext stealing important in relation to Blowfish?

texts:
I am writing a simple messenger (as a proof of concept  not for production), and I came across Blowfish as being as being an interesting alternative to AES.

As it is not meant to be an actual product, I am not entirely concerned with something like E2E encryption, nor do I want to deal with certificates, so my goal is to use just a mid-speed block cipher for encryption.

During my development, I noticed that there were options for ciphertext stealing. How big is the security benefit from using it, and what are the costs?


texts:
Typically, Private Set Intersection (PSI) protocols let you learn the subset of items on each party's dataset that are in the intersection. The problem in this case is a relaxation of these kind of constructions. I would like to learn only the number of elements on the intersection.

I could achieve this by using proxy re-encryption on a 2-party setting, however it is non-trivial (at least to me) to do the same on an n-party setting without disclosing the intersection of any parties subset.

I wonder if this problem has a specific name and whether it has been studied before (some literature you can point me to). Any idea on how to achieve this is also welcome.


texts: Which Fully Homomorphic Encryption schemes are fastest?

texts: I want to know which one Fully homomorphic encryption schemes are the best in terms of time to encrypt & decrypt or compare between them ?(Preferred valid link)


texts: Key sizes for discrete logarithm based methods

texts:
I have a question regarding the key generation process of methods that are based on the discrete logarithm problem.
This site gives some good insights, but I don't fully grasp it I think: http://www.keylength.com/

For example I know that till lately one should have used 1024 bit group modulus and a 160 bit long secret key and that picking the secret key size is always roughly double the security level (hence here 80 bit security) one wants to achieve.

My question is: How does the groups modulus size relate to the security level? Does the group generator always have to be the same size as the group modulus?


texts: How do I construct variable length input (VIL) in a block cipher mode?

texts:
I've just been skimming NIST's "Five Confidentiality Modes". I understand those block cipher modes are used to securely encrypt input longer that the block cipher length. However, the common block cipher modes all assume my input length is evenly divisible by my block cipher length.

What is a recommended way to deal with my non-block-cipher-length-divisible input to safely encrypt it? Are implementors prepadding it using data length? Or are there other common block cipher mode standards that deal with this?


texts:
I'm studying a protocol whose security is based on the following assumption: given $g_1, g_2, A, B \in \mathbb{F}_p ^*$ with $g_1, g_2, A \neq 1$ and $g_1 \neq g_2$ , it is difficult to find exponents $r_1,r_2, d$ s.t. the following equation holds:
$$
g_1^{r_1}g_2^{r_2} \equiv A^dB \ \ (\mbox{mod} \ p)
$$
The paper I'm reading states "this is a type of discrete logarithm problem, hence it is assumed hard to solve". I'm not sure why this last sentence is true: initially I thought I could show this problem was harder than the DLP by saying "if I could solve this problem for given $g_1, g_2, A, B$, in particular I could solve it for $g_2 = A = 1$, so I could solve $g_1^{r_1}=B$, which is a DLP". But my argument is fallacious as $g_2$ and $A$ are different from $1$ by hypothesis. I would really like to have some proof like the one I was trying to show, so that I can bring this problem back to the DLP hardness assumpion, and don't assume anything more.
If someone know about similar-discrete-log-problem or see any way to show this problem is harder than the DLP, please help me! Thank you in advance


texts: What is the difference between computational complexity and time complexity?

texts:
Computational complexity seems to be used quite a lot in cryptographic papers.

The time complexity I am referring to is the one from Computational Complexity Theory.

Are these two the same things?


texts: Oblivious Decryption: Decrypting with a private key, without knowing the message

texts:
I’m trying to devise a protocol, complimentary to a private-set-intersection, involving three parties, namely Alice, Bob and Charlie.

Alice has a public and a private key. And receives website logs from Charlie.

Charlie runs a website, and he sends his website logs to Alice, encrypting the user-ids using Alice’s public key. Let’s say they are using RSA with padding for each log entry, this way the same user-id always looks random when encrypted.

Bob is managing a small part of Charlie’s website. Charlie has agreed to forward a related portion of the logs to Bob. But it’s directly sampled from the same logs Alice got, so they carry the user-ids encrypted with Alice’s public key.

Naturally, Bob doesn’t have Alice’s private key, and wants to learn the user-ids that visited his section. He can ask Alice to decrypt the user-ids he has, however he doesn’t want to give Alice the information about the users he’s interested in.

Is it possible to devise a protocol where Alice decrypts the messages encrypted by her public key, without really knowing what the message was. Hence the name Oblivious Decryption...

So, I have thought of the commutative property of RSA. If Bob had a private and public key both secret to himself, before sending the message to Alice he might have encrypted and  then decrypt what Alice has decrypted, getting access to the user-id himself only. However for Bob to be able to create such a key-pair he needs to know the prime factors of the modulus.

Is there a way, this can be achieved. And If not can we prove that this is not possible?


texts: Solid summary of what encryption remains strong after recent events

texts:
Following the recent government hacking (and subsequent news and fallout), I'm wondering what crypto-systems remain strong (and why) and what crypto-systems were exploited too heavily to be reliable. I'm wondering what will remain strong for the foreseeable future and why these systems were not affected (while the others presumably were).

I tried to find the information on the following and many other pages, but they were not very helpful in this case…

http://en.wikipedia.org/wiki/NSA_encryption_systems
http://en.wikipedia.org/wiki/NSA_cryptography

Perhaps someone can help me understand this.


texts: Does Linear Cramer-Shoup have pseudo-random ciphertexts?

texts:
"Linear Cramer-Shoup" is defined on pages 4 and 5 of $\:$ eprint.iacr.org/2007/074.pdf .

Are the ciphertexts in Linear Cramer-Shoup computationally indistinguishable from uniform
under a chosen-ciphertext attack? $\:$ (We can assume without loss of generality either that

$M$ is the identity element or that $M$ is a a random element unknown to the adversary.)

This is not homework, and is relevant to a Zero Knowledge

Proof of Knowledge protocol I'm thinking about.