texts: Looking For Additively Homomorphic Encryption

texts:
I have a construction that requires as primitive an Additively Homomorphic Encryption scheme that does not rely on hidden group order, meaning I can't use Paillier.

I now have two different instantiations of that primitive:

Additive ElGamal, with its issue of small message space.
Regev scheme based on LWE, which have bad parameters once you try to do homomorphic additions with a modulus bigger than 2.

My question is the following:

Do you know of some Encryption scheme which is not based on hidden group order and is additively homomorph for a bigger message space?


texts:
When reading ''Algebraic Cryptanalysis'' by Gregory V. Bard, Springer Editions, I got confused by this sentence:

  Suppose there were three naïve Cryptography students, who choose to use 3-DES iterated roughly one million times, because they are told that this will slow down a brute force attacker by a factor of one million.

I just wanted to make sure I understood this sentence fully. Does this mean that, for a given message m, we just compute 3DES(3DES(...(3DES(m))...)) one million times? (Assuming we keep the same keys)


texts: Should I calculate SHA-256 hash of a raw bytes of a token or it's hex encoding?

texts:
I have a system where I should generate a secret token for a user. The presence of a token is sufficient to grant access to some user-related data.
I am generating a 4096 bit token from a cryptographically secure random number generator. Internally I'm handling the token as a string, encoded to hex. Token is hashed using SHA-256 and this is stored in the database, hex string representing the token is sent to the user and never stored.
When the user presents the hex string of the token, I calculate its SHA-256 hash and look it up.

Question is: am I sacrificing something by calculating SHA-256 of the hexadecimal encoded string vs calculating the hash of the raw byte payload? I'm writing this in Go, so I'm really calculating the SHA-256 hash of []byte(str) which converts the string to byte array.
I have this feeling I'm comparing apples to oranges to melons perhaps.
Should I perhaps get the hex encoded string from the user, convert it to byte array, hash that using SHA-256 and then use that?
Question 1-a: Do things change if it's base64url instead of hex?


texts: Why are garbled circuits selectively secure?

texts: In Adaptively Secure Garbled Circuits from One-Way Functions, the authors wrote that the adversary may be able to influence the choice of the input $x$ after seeing the garbled circuit, so we need a stronger notion called adaptive security. Why may the adversary be able to influence the choice of the input after seeing the garbled circuit?


texts: Why does SRP-6a use k = H(N, g) instead of the k = 3 in SRP-6?

texts:
I've been reading up on the Secure Remote Pasword protocol (SRP). There are a couple different versions of the protocol (the original published version being designated SRP-3, with two subsequent enhancements 6 and 6a).

There was a very limited attack on version 3, where the attacker could submit two password guesses per falsified attempt against the server instead of just one. This was because in step 2 where the client submits ($g^x + g^b$) to the server, they could in fact set $b$ to be a second password guess, and since the server doesn't have the password, it can't tell that $b$ isn't randomly chosen (like it's supposed to be). The attack and remedy are detailed in the paper for SRP-6.

The remedy described in SRP-6 is that the client send $k·g^x + g^b$ instead, where $k = 3$. However, there is also a version SRP-6a (which is the version detailed on the page above), which sets $k = H(N, g)$. Since both $N$ and $g$ are publicly known values ($N$ is a large safe prime, and $g$ is it's generator), and the $(g,N)$ group is used for all transactions in a given SRP system (independent of password, user or session), $k$ is still a constant value.

So the question is, what's the justification/benefit of picking this alternate value $H(N,g)$ for $k$? This value of $k$ is used in the TLS/SRP implementation, but I haven't found any explanation for why.


texts: Affine cipher: calculate the key from a known plaintext/ciphertext pair

texts: Suppose I have a ciphertext that I know is encrypted using an affine cipher in $\mathbb{Z}_{26}$. The plaintext begins with es and the corresponding ciphertext is FX. How can I calculate the key?


texts:
What does it mean that a protocol realizes "strong mutual authentication"? And What does it mean that a protocol realizes "weak mutual authentication"? Can you define them formally ?

I have found a definition for "strong mutual authentication" (not formal):

  Strong mutual authentication requires not only matching conversation records: all principals’ records of the content and the order of all messages must coincide, but also matching views of the intent: all principals’ views of the purported sources and the intended destinations of all messages should also coincide.


texts: How does the Efficient Fully Homomorphic Encryption from (Standard) LWE work?

texts:
I am interesting to learn the low level implementation of Efficient Fully Homomorphic Encryption from (Standard) LWE and I am wondering if anyone can answer the following questions:

Does the BV scheme work on binary numbers (0,1) or not?
Does the BV scheme encrypt and decrypt each bit separately?
Is there any difference between the original paper of BV andthe updated version in terms of encryption and decryption processes?


texts: Difficulty understanding 'random square root' in enhancement to fiat-shamir

texts:
This was published in 1986 and I'm trying to reproduce it in an assignment. It's a small variation on fiat-shamir, by the original author, which does away with a public key (and supposedly drastically improves performance) by doing:

  Our improvement comes about from choosing the ${v_{i}}'s$ to be the first $k$ prime numbers
  $(v_1=2,v_2=3,v_3=5)$, etc. The ${s_{i}}'s$ will then be set to be a random square root of the corresponding $v_i \bmod n$

In the paper, ${v_{i}}'s$ are the public key, ${s_{i}}'s$ are the private key.

But I'm a bit lost with the wording. It says to set the ${s_{i}}'s$ to the random square root of the corresponding $v_i \bmod n$.

So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11*19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$?

Obviously this isn't correct, so I'm sure I'm missing an assumption somewhere. Any help would be really appreciated.

Nb. For reference, there's a paper which isn't behind a paywall which looks at this enhancement. There's also a patent for the scheme here.

edit: After poncho's post, I plugged his two example values into the algorithm and the scheme doesn't seem to work.

p=11
q=19
n=p*q # 209

r = 123 # random
e= 1.234 # random challenge

v = 5 # public key
s = 29 # secret key
y = (r)*(s**e) % n

rhs = (y**2)*(v**e) % n
x = r**2 % n
assert x == rhs


texts: Has the ECDH protocol been designed just for key exchange or is it widely used for key exchange?

texts:
As far as my understanding of the ECDH goes, after systems are encrypted using ECDH protocol, any data that comes out of the first system will be encrypted and can only be decrypted at the receiving end. Literature says that ECDH is used for the purpose of key exchange(when data is encrypted using symmetric encryption methods like AES) but can I not communicate application data via ECDH (regardless of whether or not I'm further encrypting the data at application layer using something like AES-CTR or DES) ?
PS: I'm trying to establish encrypted communication between 2 BLE devices.


texts: In the Linux Kernel 4.8+, does the CSPRNG update the entropy pool?

texts:
My understanding of how /dev/urandom works is that the kernel collects true randomness from a variety of sources, and mixes them together to remove statistical bias. It does this at regular intervals to refresh the entropy pool.

The CSPRNG then takes a subset of these bits to generate random bits for consumption.

My question: in the course of dipping into the entropy pool, does the CSPRNG also update the entropy pool or is that done only by the OS?


texts: If an attacker has a chosen-plaintext and encrypted data, can they determine the encryption type?

texts:
This question differs from How to determine what type of encoding/encryption has been used?, which asked about a ciphertext-only attack. This question is asking about a chosen-plaintext attack.

Let's say an attacker was trying to perform a chosen-plaintext attack on an encrypted password server. This attacker is an internal employee with their own registered account. They can:

Specify an arbitrary plaintext password for their account.
View encrypted ciphertext passwords saved to the server.

This attacker doesn't know what encryption method is being used, whether passwords are salted, or what key is being used. However, they notice that the encrypted passwords are always the same number of characters (64).

Using their chosen plaintext and encrypted passwords, could an attacker determine what type of encryption was used?


texts: calculating a group element in a discrete log problem

texts:
An encryption scheme is based on the DLP: $c = a^x mod ~b$, where $x$ is hard to find. How hard is it to find $a$, given all the other values, $c$, $x$ and $b$?

Would this make the problem easy to solve?

$c^{1/x} = (a^x)^{1/x} mod ~b$

An example would be great to better understand.


texts: Revoke a GPG key using previously generated revoke certificate after renewd (change expiration date)

texts:
I have few sub-questions

Do secret keys get expired, or just the public key gets expired?
Do I have to back up the master sec key each time I renew it?

For an example:

Let's say I generate gpg keypair and ssb for signing, encrypting, and a revoked certificate. And I backup the master sec key, revoked certificate and place them somewhere safe, and remove master sec from the key-ring.

Then the pub and sub keys get expire so, I get a copy of master sec key from the safe place and re-import it to the key-ring for the sake of key renewing process. After that, can I just safely remove and delete that copy of master sec key from the key-ring? If so, is master sec key that I saved at the first place aware of these new renewed pub and sec keys, shouldn't I re-backup the sec key after using it for renewing process? and replace to the old sec key that I saved in the safe place?

What would happen If I generate a new ssb key for authentication after that renewal process? Is my master sec key that I saved in the safe place at the first aware of the newly generated ssb key? If so, how is my revoked certificate affect to these new keys? (new ssb keys, and renewed pub keys)
Do I have to re-generate revoke certificates each time after I renew the secret key, or can I just use the previously generated revoke certificate after renewing the key?

For an example:

First I generate a seckey and a revoked certificate, then I generate ssb key.

Then sec and ssb both get expire and I renew it for a next 6 months, then I lose my master sec key, so Is my revoke certificate still valid? can I revoke the key by importing the revoked certificate?


texts: What are the requirements of a key schedule?

texts:
In the first block cipher I designed I used a CSPRNG to generate the round keys.  The purpose was to at least have a chance of creating a (hopefully!) secure cipher on the first try (but please don't use it in production).

One criticism I got was that the key schedule was too expensive.  This made me wonder: what are the actual requirements of a key schedule?  Clearly a CSPRNG is overkill.  I want to know what the actual requirements are.  What is required of a key schedule?

I know:

Every bit of the key should ideally effect each round key.
As always, speed and simplicity are desirable.


texts: Is it necessary to use Fermat's Little Theorem to prove the 'correctness' of the RSA Encryption method?

texts:
Given a 'message' $M$, a proof of the 'correctness' of RSA encryption means to show that $(M^e)^d \equiv M \pmod{n}$, where $n=pq$ is a product of primes, and $ed \equiv 1 \pmod{\phi(n)}$, where $\phi$ is Euler's totient function, so that $\phi(n)=(p-1)(q-1)$.
Most sources attribute the correctness of RSA encryption to Euler's theorem (a generalisation of Fermat's little theorem), however the end of the intro of the Wikipedia page claims this is erroneous, since it doesn't apply in the case when $\gcd(M,n) \neq 1$, and that actually it is sufficient and necessary to use the "uniqueness provision of the Chinese Remainder Theorem". However, in every proof I can find on the web and on this site, Fermat's little theorem is used as well as CRT.
So, my question is, is it necessary to use FLT? And is it necessary to use CRT?
If so, is there a proof of this, i.e. that FLT / CRT $\Leftarrow (M^e)^d \equiv M \pmod{n}$ ?


texts:
The LoRaWAN protocol has a specific way of encrypting data (page 20, chapter 4.3.3.1), and I'm trying to do it in C#.

First, a sequence A with blocks with a size of 16 bytes each A1..An is created. Then they are encrypted to get a sequence S of blocks Si:

Si = aes128_encrypt(K, Ai) for i = 1..n
S = S1 | S2 | .. | Sn

And finally the payload is encrypted:

(pld | pad16) xor S
truncation of the first len(payload) bytes

So far I managed to generate the blocks, but I'm new to cryptography and have no idea on how to proceed, can anyone help?

Here is the encryption script in python.

And this is the C# code I have so far:

public string encrypt(string payload, string dev_eui, string dev_addr, int counter_up)
{
  try
  {
    byte[] devaddr = StringToByteArray(dev_addr);
    byte[] aBlock = {
      0x01,
      0x00,
      0x00,
      0x00,
      0x00,
      0,
      devaddr[3],
      devaddr[2],
      devaddr[1],
      devaddr[0],
      (byte)(counter_up & 0xff),
      (byte)((counter_up >> 8) & 0xff),
      (byte)((counter_up >> 16) & 0xff),
      (byte)((counter_up >> 24) & 0xff),
      0x00,
      0x00 };

     \\...


texts: Why should I use X.509 Authentication over PKC based Authentication?

texts:
So I have two examples and I don't understand why one would be chosen over the other.

Example 1.
A sends EPUb[r1] to B (asks B to prove knowledge of PRb)
B replies with r1, EPUa[r2] (asks A to prove knowledge of PRa)
A replies with r2 to prove it

Example 2.
A sends r1 to B (asks B to prove knowledge of PRb)
B replies with r2, EPRb[h(r1)], CertB (provides B with signature and certificate and own challenge)
A replies with EPRa[h(r2)], CertA

Why would example 2 be better than example 1? Are there any security loopholes I'm not seeing in example 1 than example 2 fixes?

I'm studying for my cryptography exam tomorrow and been stumped by this example. Fast responses would greatly appreciated.

From what I can pick up on these two examples. Example 2, you provide each other with your public keys and you know the origin is trustworthy after you verify the certificates. When communicating you can then use each others public keys for encryption or you could establish a symmetric key which eliminates the man in the middle attack possibility.

In Example 1 all I can think of is that without the certificate they can't be sure the other entity is who they claim to be but then again to know each others public keys there must be some form of trust between them. Is example 2 better just because you can be MORE sure that the other entity is who they claim to be?


texts: Which attacker model is weaker? IND-CPA or OW-CCA?

texts:
I know that IND-CPA is a security goal, which is defined as the inability of an attacker to distinguish two ciphertext of some arbitrary chosen plaintexts.
Unfortunately i havent found a good definition of OW-CCA, but i assume it has something to do with an Oracle and Chosen Ciphertexts. So in my understanding OW-CCA is defined as the inability of an attacker to find out the key by chosing an arbitrary number of Ciphertexts and letting the Oracle decrypt these.
In IND-CPA the Attacker has the ability encrypt chosen plaintexts, which basically anyone can do. In OW-CCA, the Attacker can reverse the ciphertexts to plaintexts and is dependant on the oracle
Since the attacker has less power in IND-CPA the security goal is more easily achieved, which makes the attacker model weaker.
Is that correct?


texts: Is that simple additive homomorphic scheme secure?

texts:
I am doing a little cryptography research and stuck with question.

Suppose $\bar m$ is a vector of 64-bit numbers. And i want to have an additive homomorphic encryption over them. I choose large (2048 bit) prime $n$, large not prime $s$ and vector $\bar r$ of large random numbers, with size of vector equal to vector $\bar m$. Finaly, encryption function $Enc$ looks like that:
$$Enc(m_i) = (r_i,m_i+r_i\cdot s\mod n)$$
where $Enc$ yields an ordered pair of numbers.
So the number $n$ with encrypted vector $c=Enc(m)$ goes to the opponent, but $s$ keeps secret.

Sum of an encrypted values is just sum of pairs (all operations are modulo $n$):
$$Sum(c_i,c_j) = (c_i.first+c_j.first,c_i.second+c_j.second)$$
$$or$$
$$(a,b)+(c,d)=(a+c,b+d)$$
where $c_i.first$ is the first element of pair $c_i$ and $c_i.second$ is the second.

Decryption looks like that:
$$Dec(c_i) = c_i.second - c_i.first\cdot s$$

Intuitively, i think, that this scheme is vulnerable, but i can't see why. I will be glad to have a hint to understanding this problem.

Many thanks in advance to your great community!
(sorry for any grammar mistakes, English is not my native language)


texts: Perfect Forward Secrecy with Pre-shared Key

texts:
I've recently been looking at how to do perfect forward secrecy on a unidirectional connection (server can only push messages to client, client cannot respond).

What I've come up with is the idea of using a random shared key as a starting place and using this as a symmetric cipher key for the first pushed message. Once this message is pushed, the key is hashed, the result of this hash is the key for the second message. This continues to function as a sort of hash tree, ie:

$$
\begin{aligned}
   K_0 &= R &&
\\ K_1 &= H(K_0) &&= H(R)
\\ K_2 &= H(K_1)&&= H(H(R))
\\ \vdots &\qquad\vdots && \qquad\vdots
\\ K_n &= H(K_{n-1}) &&= H^n(R)
\end{aligned}
$$

If this is implemented correctly and the previous key is always destroyed fully (perhaps kept only in RAM) then I believe this could offer perfect forward secrecy assuming client and server can exchange the initial random value securely (the idea is that these be exchanged via QR code or similar mechanism).

The only disadvantage that I'm aware of to this approach compared to interactive Diffie-Hellman would be that if a server or client was compromised in this system, using the information within could allow a passive attack instead of an interactive (MITM) attack.

I doubt this is a new or unique idea at all, but just looking for some people to bounce this idea off before I attempt an implementation. I'm wondering if anyone has any thoughts on additional things to look out for that I may have missed or if I am catastrophically wrong and this won't work at all.


texts:
I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” which states:

  With an ACR hash function $F$ the key $K$ is announced and the adversary wins if she manages to any collision $M,M'$ for $f = F_K$. The points $M$ and $M'$ may depend arbitrarily on $K$.

Could you give me an example of messages $M$ and $M'$, so that they depend arbitrarily on $K$?

My other questions related to the same paper:
Dependence on Keyed Hash Function • No Birthday Attack to TCR • Weaker Notion of Target Collision Resistance


texts: How to encrypt a symmetric key with a shared secret?

texts:
I am reading this article (pdf) on the Diffie–Hellman key exchange. It states the following:

  At this point, the Diffie-Hellman operation could be considered complete. The shared secret is, after all, a cryptographic key that could encrypt traffic. But completion at this point is very rare, because the shared secret is an asymmetric key by its mathematical nature, and all asymmetric key systems are inherently slow.

  ...

  In most real applications of the DH protocol (SSL, TLS, SSH, and IPSec in particular), the shared secret encrypts a symmetric key for one of the symmetric algorithms, then transmits it securely, and the distant end decrypts it with the shared secret.

I'm trying to understand the point in an authentication scheme where two parties have exchanged keys with Diffie-Hellman, and now have the "shared secret".

How is the shared secret asymmetric if the "shared secret" is used to both encrypt and decrypt?
How exactly do i encrypt an AES key with the "shared secret" key?
Is it not possible to directly create a symmetric AES key with the DH key exchange?


texts: Does “SHAttered” only work for PDF files?

texts:
It appears that SHA-1 is broken in practice.  The website detailing this attack shows an infographic of how two PDF files can have the same SHA-1 hash value.  Also Google's.  I've also read Mathew's answer regarding the implications of this, and his explanation example focuses on PDFs.

What is it with PDFs?  Does the attack only work on them exclusively?  A PDF is just a sequence of bytes arranged in some order specified ages ago by Adobe Inc.  I would have thought then that any two arbitrary file types could be attacked and hashed to the same value, not just PDFs.


texts:
I want to create 2 Bilinear Pairing $e_1$,$e_2$ such that
$$e_1:G_0 \times G_0 \rightarrow G_1$$
$$e_2:G_1 \times G_1 \rightarrow G_T$$

and use this to encrypt a message $M$ in the form  $$M e_2(e_1(g,g),e_1(g,g))^{xy}$$ To decrypt the message, first one has to retrieve $e_1(g,g)^{x}$ and $e_1(g,g)^{y}$ using linear secret sharing scheme. Then, can calculate $$e_2(e_1(g,g)^{x}, e_1(g,g)^{y})=e_2(e_1(g,g), e_1(g,g))^{xy}$$ Ultimately one can retrieve $$M=\frac{M e_2(e_1(g,g),e_1(g,g))^{xy}}{e_2(e_1(g,g), e_1(g,g))^{xy}}$$
My question is whether it is possible to user this to create a cryptographic scheme? And also is it practical to implement using any existing crypto library? One idea is if it were possible to define $e_1$ as $e_1:G_0 \times G_0 \rightarrow G_0$, then we could define $e_2$ as $e_2:G_0 \times G_0 \rightarrow G_0$. And that serves our purpose. Since I am new in Pairing based cryptography, I do not know whether the solution is practical. It would be great if I get any help or lead from any of you guys. Thanks in advance.


texts: Public Key Fingerprint: Preimage Resistance

texts:
In my system, “resources” are granted operational certificates signed by a particular CA.
Each resource has a unique public/private key pair that it generates once. The operational cert granted by the CA signs the public key of the resource embedded as a field, along with the public key of the CA. In addition, there is a 64bit “Resource ID” embedded in the cert as well.
I intend to use a 64 bit fingerprint (SHA256 truncated) of the resource’s public key as the Resource ID.
If there was a malicious resource that desires to impersonate another’s Resource ID at the time the operational cert is granted, how difficult is it in practice with modern day compute capabilities?
Is it equivalent to the second preimage resistance of the hash? If so, is that 2^64 “trials” to find a match?


texts: What is the difference between the 23 bi-affine and the 39 fully quadratic equations of the rijndael sbox?

texts:
In Cryptanalysis of Block Ciphers with Overdefined Systems of Equations Nicolas Courtois and Josef Pieprzyk define 23 so called bi-affine equations (in Appendix A of the paper) between the input x and the output z of the rijndael sbox.

Then they say in A.1 that it is possible to get "not only" 23 bi-affine but 39 fully quadratic equations.
And they further describe that the additional 16 equations come from a) $x^4y = x^3$ and b) $y^4x = y^3$.
($y = x^{-1}$ is the result of the inversion in the sbox)

I assume they produce these 16 equations in the very same way how they generated the 23 bi-affine equations (which is described here providing more details):

They transform/rearrange the equations a) and b) to have 0 on one side.
Then they "split" each equation a) and b) in 8 equations for each coefficient, so we have 16 equations in total for both a) and b).
Then they substitute all the $y_i$ using the affine transformation of the sbox:
$$
z = M\cdot y + \textrm{63}_{16} \\
y = M^{-1}\cdot z + M^{-1} \cdot \textrm{63}_{16} \\
  = M^{-1}\cdot z + \textrm{05}_{16} \\
$$
which resolves to:
$$\begin{cases}
y_7 = z_{1} + z_{4} + z_{6} \\
y_6 = z_{0} + z_{3} + z_{5} \\
y_5 = z_{2} + z_{4} + z_{7} \\
y_4 = z_{1} + z_{3} + z_{6} \\
y_3 = z_{0} + z_{2} + z_{5} \\
y_2 = z_{1} + z_{4} + z_{7} + 1 \\
y_1 = z_{0} + z_{3} + z_{6} \\
y_0 = z_{2} + z_{5} + z_{7} + 1 \\
\end{cases}
$$

I hope these steps are correct, but this way I get to the same 23 bi-affine equations as listed in the papers 1 and 2.

If I do this with a) and b) I get the following result (only one equation out of 16 as example):
$$
0 = x_{1}^{4} z_{0} + x_{6}^{4} z_{0} + x_{0}^{4} z_{1} + x_{1}^{4} z_{1} + x_{2}^{4} z_{1} + x_{7}^{4} z_{1} + x_{1}^{4} z_{2} + x_{2}^{4} z_{2} + x_{4}^{4} z_{2} + x_{6}^{4} z_{2} + x_{6}^{4} z_{3} + x_{7}^{4} z_{3} + x_{0}^{4} z_{4} + x_{1}^{4} z_{4} + x_{3}^{4} z_{4} + x_{4}^{4} z_{4} + x_{5}^{4} z_{4} + x_{7}^{4} z_{4} + x_{1}^{4} z_{5} + x_{3}^{4} z_{5} + x_{4}^{4} z_{5} + x_{5}^{4} z_{5} + x_{0}^{4} z_{6} + x_{1}^{4} z_{6} + x_{2}^{4} z_{6} + x_{3}^{4} z_{6} + x_{4}^{4} z_{6} + x_{6}^{4} z_{6} + x_{3}^{4} z_{7} + x_{5}^{4} z_{7} + x_{6}^{4} z_{7} + x_{5}^{4} + x_{7}^{4} + x_{2}^{2} x_{3} + x_{1} x_{3}^{2} + x_{3} x_{4}^{2} + x_{4}^{3} + x_{1}^{2} x_{5} + x_{3}^{2} x_{5} + x_{1} x_{5}^{2} + x_{2} x_{5}^{2} + x_{4} x_{5}^{2} + x_{3}^{2} x_{6} + x_{4}^{2} x_{6} + x_{0} x_{6}^{2} + x_{2} x_{6}^{2} + x_{5} x_{6}^{2} + x_{0}^{2} x_{7} + x_{2}^{2} x_{7} + x_{5}^{2} x_{7} + x_{6}^{2} x_{7} + x_{0} x_{7}^{2} + x_{3} x_{7}^{2} + x_{5} x_{7}^{2} + x_{6} x_{7}^{2}\\
$$

I would assume that every exponent $\neq 0$ of any $x_i$ and $z_i$ can be ignored because those variables representent coefficients in $GF(2)$ and can be either $0$ or $1$. *

So when I ignore the exponents this looks very similar to the bi-affine equations (a sum of combinations of $x_i$ and $y_i$, sometimes with terms of only $x_i$ or $y_i$ - the only thing which is new is that there are terms of $x_i$ and $x_j$ multiplied together) and I would like to understand the difference!

So how are these equations "fully quadratic" and what does it mean exactly? What is the difference to the bi-affine equations besides the number of the equations?

*: This was also necessary in the process of generating the 23 bi-affine equations, where the equation $x^{128} = y^{128} x$ was used. This led to $x_i^{128}$ in the result which to my understanding can also be shortened to $x_i$.


texts: What is the point of hash = (prime * hash + b) % 100

texts:
While looking though some code base I found the function which has no explanation and does something like this (pseudocode)

func something(str, num) { // str is a string, num is a number from 0 to 100
   hash = 0
   prime = 17
   for b in byte_array_of_base64decode(str){
       hash = (prime * hash + b) % 100
   }
   return hash < num
}

There is no explanation what the function suppose to do and the name of it also does not give any clue.

I assume that if this does any useful thing, it has something to do with hashing or sampling. Does anyone know the point of this function?


texts: Safe Elliptic curves of prime order according to "safecurves"

texts:
I am currently trying to implement a cryptographic scheme. For this purpose I need a group of prime order in which the discrete logarithm problem is hard.

For now, I have been using a subgroup of prime order q over the Integers mod p, where p=2q+1, p prime, q prime. (p about 2048-4096 bits) The parameters for the groups are based on the primes given in RFC3526.

I would like to also try the scheme over elliptic curves. I'm aware of https://safecurves.cr.yp.to which lists and classifies a lot of different curves. However the information of whether the curve is of prime order is missing there. I've tried some of the popular curves like Curve25519 with Sagemath, however e. g. Curve25519 appears not to be of prime order, only the NIST curve (which have uncertain seed origin) are working.

So my question is basically: Are there any 'safe' and well-established elliptic curves of prime order? (If the answer is yes then where to find them? And if the answer is no, then why not and what's so special about the NIST curves then).

Thanks for your help in advance. I'm quite new to the topic, please don't hesitate asking if anything is unclear.


texts: Is there a flaw in this ECC blind signature scheme?

texts:
Recently I've found the following work on the internet: An ECC-Based Blind Signature Scheme

The paper claims to be an ECDSA blind signature however it seems that their scheme has a flaw in it.

The process they describe is pretty standard:

Requester blinds a message using his key and sends blinded message to signer
The signer signs the message resulting with pair $(r,s)$ which is sent to requester
BUT then the requester unblinds ONLY $s$ component and $r$ component is published unchanged

It seems logical that after publishing $r$ the way it came from signer would allow

the signer to track transactions by keeping a database of all issued $(r,s)$ tokens?

Or am I missing something?


texts: Setting MAC field to all-zero to indicate unencrypted data

texts:
I'm currently working on a project where we transmit data between two systems. The data is generally encrypted before transmission, however there are certain transmissions that are unencrypted.

We use the following data format for transmission:

Encrypted-Data [64Bytes] | MAC [16 Bytes]

The receiving system first decrypts and verifies the authenticity of the messages origin, then the data is processed further.

My solution to this problem is setting all bits of the MAC to zero before transmission, to indicate that the message is unencrypted.

Now my questions:

can a MAC calculation result in zero (we use Poly1305)?
is it good practice to use the MAC set to zero to indicate unencrypted data?


texts: Is lattice-based cryptography relevant in symmetric cryptography?

texts: I've seen that lattice-based cryptography works well with public key cryptography as well as cryptographic hashing algorithms, but does it apply to symmetric key cryptography?


texts: Process of dividing 168bit key into 56bit keys in TripleDES

texts: I used TripleDES so many times but never thought about this. In TripleDES it requires 168bit key in option 1. I don't enter three single 56bit keys while implementing instead I only enter 168bit key.  So, I'm guessing 168bit breaks into three 56bit keys. What it process of this breaking mechanism? is it linear?


texts: Can a secret message be securely transmitted within a MAC tag?

texts:
A sender wants to transmit an ultra secret code $M$ which could be either 'go', 'stop' or 'wait'. This could be any selection of code words really and adopted for any use such as transmitting short commands or short status messages. The code list could also be specific or relevant to a current mission/objective. A limited number of code words will make things a lot faster for the recipient however. I will try explain:

Both sender and recipient know the valid code list $L$ and share a random 256 bit key $K$ beforehand. This exchange is out of scope.
Let $H$ be a secure hash function with an output of 256 bits which also claims to be a secure MAC in the format of $H$($K$ | $M$). Skein and possibly a few others fit this criteria.
Sender generates a random 256 bit nonce $N$ per transmission.
Sender generates a MAC tag $T$ by calculating $H$($K$ | $N$ | $M$);
Sender sends $N$ | $T$ in the clear to the recipient.

The recipient tries each message in the code list with the nonce and key to try get a match with the sent MAC tag and thus decipher the message:

function(K, L, N, T) {
   foreach M in L {
      if (T equals H(K | N | M)) {
         return M
      }
   }
   return invalid
}

You will note there is no separate MAC tag sent to authenticate the nonce and MAC tag sent in the clear. Because there are only 3 valid codes, there are only 3 possible MACs considered valid by the recipient. This increases the attacker's chance of a creating a forgery to 2^256 / 3 = 2^254 but this is still comfortably secure. You could in fact have 1000 code words and the security would still be adequate at 2^246. However shorter code lists would be better to prevent a DOS type attack when an attacker sends fake transmissions causing excess MAC validation work for the receiver. For longer code lists, perhaps a separate MAC of the $N$ and $T$ would fix that.

From what I can ascertain, only the recipient should know the true message. An attacker can if they do a brute force of the key space (2^256 difficulty) or break the hash function. There is practically no chance of the receiver interpreting the transmitted code incorrectly because the odds of a valid code word producing the same MAC tag is extremely unlikely due to the collision resistance of the hash function.

Can a secret message be securely transmitted, authenticated and read like this?


texts: Generating multiple keys based on same password

texts:
I want to generate an encryption key for the user to encrypt their data locally before sending to the server. The server should not have any knowledge, nor be able to compute, this encryption key.

This encryption key should be deterministic, so that regardless of which device they're on, the same key is generated and stored locally.

This makes their password an ideal choice to generate a key from.

At first I thought, easy:

Given user inputted password uip:

encryption_key (ek) = sha256(uip);
password_sent_to_server (pw) = sha224(uip);

This way, the server can never know or receive the user's inputted password, and cannot compute the encryption_key.

However, after asking this question, I've been told to use a key derivation function instead.

The problem is, I'll now need two random salts to generate ek and pw. And these salts cannot be stored on the server. So that means I'll also need to generate two deterministic salts based on either the user's email or password.

What's the right way to go about doing this?

This answer recommends using the email as the salt. So perhaps:

ek = pbkdf2(uip, email, 1)
pw = pbkdf2(uip, sha256(email), 2)

(The sha256(email) for the second salt is questionable. Was just trying to get at a different non-random salt for the second one.)

This answer recommends using pbkdf2 to generate a 512 bit key and splitting it:

output = pbkdf2(uip, email, 1, 512);
ek = firstHalf(output);
pw = secondHalf(output);

Am I interpreting these answers correctly? Any commentary on either approaches?


texts: RSA - PKCS#1 padding - overall correction of algorithm

texts:
From PKCS#1, page 24:

After we create the EM byte string and convert it to an integer, we then encrypt that integer with RSAEP (page 10) to get the ciphertext (as an integer).

My question arrives from the fact that RSAEP demands the input ($m$) to be less than the modulus ($n$).

My question is simple - how are we guaranteed that the integer representation of EM is in fact less than $n$?

Since that 15th bit (starting from the MSB) is $1$ (because the second byte (starting from the MSB) is 0x02), we know that m (the integer representation of EM) must be larger than $2^{8k-15+1}$ (where $k$ is the number of bytes in EM).

So overall, we know that $m\geq 2^{8k-14}$.

What stops $n$ (the modulus) from being less than $2^{8k-14}$?

I don't see a reason why $n$'s first 2 bytes can't be $0$, and the $k-2$ bytes that are left would be 1. In this case, $n=2^{8(k-2)+1}-1 = 2^{8k-15}-1$, and we can clearly see that
$m \geq 2^{8k-14} > 2^{8k-15}-1 = n.$

i.e. $m > n$.

What am I getting wrong here?

P.S. I hope I managed to make my question clear. Please ask me if I didn't explain myself well enough.


texts: Using date stamp down to milliseconds / ticks as a salt?

texts:
As I understand it, the salt is used to ensure that a hash of two of the same strings results in a different hash.
The salt is often stored with the hash, either prepended or as a separate field.
As this just needs to be "different" for every input, would using something like:
DateCreated.ToString("yyyyMMddHHmmssffffff")
To get a number string down to the millisecond - If you can guarantee that you'd not have two requests in the same millisecond. This would be unique per record and provide the means to change the hash.
As an example, if I run a basic hash:
 using (HashAlgorithm algorithm = SHA256.Create())
                return algorithm.ComputeHash(Encoding.UTF8.GetBytes(inputString));

If my input string is BabySharkDoDoDoDo - every time this is hashed, I'll get the same result: 567d01ee59d062ff75435033b4c2593058aed5b5ccca0f29ba92b22c13e084b3
So, to make sure each entry to my shark database is unique, I prepend the inputString with DateTime.ToString("yyyyMMddHHmmssffffff") - so my input to the hash becomes 202104132059471235487BabySharkDoDoDoDo and each time I get a unique hash.
So I can check the input is valid, if someone enters the right record and the string BabySharkDoDoDoDo I need to store the salt, either with the hash or in the separate column.
So, the salt is known to the attacker - always the case right? So making a super strong salt, with crazy random entropy to then go and store it right next to the data it's salted makes me think, is this wasted effort? Or theatre to seem great but really all you need is a unique piece of data to provide the salt?
If I go for it and create a 128 bit salt, from a crypo library, Rijndael or similar - sure it's unique (hopefully), but I then go and prepend it to the saved hash - right? Otherwise, I can never check the hash against a known input.
A timestamp down to the millisecond or tick would also be unique and serve the same purpose?


texts: In (n,n) Shamir secret sharing if n shareholders do not have the public values (X values) can they still obtain the secret with only Y values?


texts: Isn't a simple Vernam cipher as secure as known symmetric key algorithms?

texts:
I have just read little about the Vernam cipher and the problems of implementing it.

But, in practice, would not the key, if generated by a commonly used programming language's Random() function (like Python's or Java's random functions from their standard libraries), be enough to make the message almost uncrackable if the key is as long as the message and the key is only known by the author of the text?


texts: Can we use non-adaptive zero-knowledge proof in group signatures

texts:
Group Signature schemes are used to provide anonymity of the signers. During signature generation, signers provide a NIZK proof to prove that they are certified group members. Verifiers check whether the proof is valid during verification of signature.
Can we use non-adaptive NIZK proof to prove signer is a certified group member?


texts: Do hash collisions persist if a file is modified?

texts:
Suppose I use a relatively insecure hash algorithm to digitally sign a contract. Suppose also that creating a fraudulent contract with the same hash, a collision, is practical. As I understand, in order to take advantage of a hash collision, the black hat is required to introduce some contrived information into the data first to counter the hash affects of their anticipated alterations.

For example, the original contract and hash are:

I will pay you $1.00 -> 12345

and a fraudulent colliding contract:

I will pay you $1,000,000.00 (contrived info) -> 12345

Can I protect myself by including some of my own text before signing?

For example:

I will pay you $1.00 have a nice day -> 67890

Can the attacker simply add the same text to their contrived file and get the same new hash?

I will pay you $1,000,000.00 (contrived info) have a nice day -> 67890

or will the additional text alter the hash such that the files no longer collide?

I will pay you $1,000,000.00 (contrived info) have a nice day -> 37294

I.e. Will my added information counteract the contrived information of the attacker?

In reality, as with SHA1 or MD5 where a practical method for finding collisions has been found, using this algorithm is faster than more secure ones. Could it make sense to use a very fast insecure algorithm coupled with both parties, a third party, or a random automated system, adding some novel, benign information prior to the hash? Does this add sufficient complexity?

I.e. In the case of SHA1 and git, could an attacker add some obscure contrived information in advance (that gets committed and signed or whatever) and then introduce the malicious code later when the timing was right? Or would subsequent commits thwart this plan? I.e. Are code repos with lots of contributors and commits coming from all over somewhat more secure than repos with little change?


texts:
We have got a task with the following content:

Given is a language with 3 letters: A, B, C.

The binary expression is:

A = 000, B = 1111 and C = 0011

Two words were encrypted in this language with the same key:

W1 = 0101001110111010101100100
W2 = 1011001010000000000101011

Determine the possible message pair.

How am I able to do this?


texts:
I want to understand how can I prove that M matrix in AES is MDS. I know that a matrix is MDS if every determinant of every square submatrix is different from 0.

I don't get this. How much submatrix does it have? If I swap rows or columns, does that change something? Do I have to calculate the determinant in a certain mode?


texts: Implementing commitments and challenges for a distributed ElGamal encryption scheme

texts:
I am trying to implement a distributed encryption system by having as a main source of information this book (Introduction to Cryptography by Delfs and Knebl) and this Internet article (More Mix than Net by Wood).

I generate the following variables:

$p$: prime,
$g$: generator,
$x$: random within $[1, p-1]$,
$h$: $g^x \bmod  p$

I can then use these variables to successfully encrypt, re-encrypt, and decrypt a message.

I am now trying to make the system use multiple authorities by following subsection 4.5.5 on Delfs's book that states:

According to this subsection $x$ is computed as a random number between $1$ and $q-1$, yet I am using the range $1$ and $p-1$ as shown in the article. Another difference is that in the book there is no mention of modulo $p$ when computing $h$.

Note that I have also implemented the ElGamal system as described in the book, but I would like to go with the implementation from the article since it makes more sense to me and I would like to not use external libraries).

My question is, what is the commitment I should generate and how can I later verify it?


texts: Honest Verifier Zero-Knowledge (HVZK) composability

texts: Let protocol A and protocol B be HVZK proof systems. If we construct a protocol C composed of protocol A and protocol B, will it be HVZK as well? Is there some formal proof in the literature regarding this?


texts: Geometric Cryptography and Zero-Knowledge Proofs

texts:
Trying to understand zero-knowledge proofs, I came across this page, which provides an excellent example of a simple cryptographic protocol. I will reproduce the protocol here for the sake of completion.

Assumptions: Let us assume that only (classical Greek) geometric construction is allowed. So we can only use a compass and a straight-edge and we can only perform those operations which can be geometrically constructed. Specifically, an arbitrary (given) angle cannot be trisected but any arbitrary angle can be tripled easily.

Initialization: Alice has a secret, an angle $X_A$. Maybe she wants to sell it or use it to prove her identity later. Alice constructs $Y_A=3*X_A$ and publishes it. Because trisecting an angle is impossible, Alice is confident that she is the only one who knows $X_A$.

Identification Protocol: Bob comes along and wants to buy $X_A$ or verify Alice's identity.

Bob initiates a check.
Alice selects an angle $K$ at random. Alice constructs $R = 3*K$ and gives $R$ to Bob.
Bob flips a coin and tells Alice the result.
If Bob says "heads", Alice gives Bob a copy of the angle $K$ and Bob checks that $3*K = R$.
If Bob says "tails", Alice gives Bob a copy of the angle $L = K + X_A$ and Bob checks that $3*L = R + Y_A$.
Bob can rinse and repeat as many times as he wants.

Question: Why are steps three and four a part of the protocol? Specifically, why is step four even necessary? What is wrong with

Bob initiates a check.
Alice come up with a new random $K$ and gives $R=3*K$ to Bob.
Then Alice gives $K+X_A$ to Bob and Bob checks it.
Bob initiates as many checks as he wants and stops when he is satisfied.

Why isn't this enough?


texts: How feasible would it be to generate 300 million public key pairs in 8 hours?

texts:
Assume there is a hypothetical situation where one would need to generate hundreds of millions of public key pairs of reasonable strength in a limited time.

What would be required in terms of entropy and how long would it take? Could it be acheived on a single computer? How few computers could one get away with?

If the demand for the public keys was not uniform, how many keys could be generated in a burst?

What effect would different algorithms (RSA, DSA, EC) have?


texts: What's the difference between DH and DHM?

texts: Is DHM just Diffie-Hellman with Merkle added to the name?


texts: Deletion complexity in a RSA accumulator

texts:
My question is about the existence of a dynamic RSA accumulator with deletion of an element in O(1) time.

Do you know some practical implementation?


texts:
Suppose $R$ is a random challenge sent in the clear from Alice to Bob and $K$ is a symmetric key known only to Alice and Bob. Which of the following are secure session keys and which are not? Justify your answers.
  (i)  $R\oplus K$
  (ii) $E(R,K)$

I believe that $R\oplus K$ is secure because it has one of the requirements of the perfect secrecy which is the key space has to have the same size as message space. As a result, $R\oplus K$ is provably secure.

On the other hand, $E(R,K)$ is a secure method to authenticate on side (sender) but it does not authenticate the other side (receiver). There is a problem which is no mutual authentication. Therefore, this is not secure.

However, I have been told that this answer is not correct. What am I missing?


texts: ECDSA: with knowledge of private key, can we make signatures with partially chosen content?

texts:
In ECDSA, with knowledge of private key, can we make signatures with partially chosen content?
Detailing that: In ECDSA (with secp256r1 curve and SHA-256 hash), assume we know the private key, the message, and can choose the per-signature random. It that helps, assume we can choose the private key, and some of the message, so that it's hash is essentially random. Can we (more efficiently than by trial and error) make a signature $S=(r,s)$ valid for one key and message that, expressed as two 32-byte bytestrings concatenated, contains a bytestring that we can choose, or with certain characteristics?

Context: I'm helping (un-retributed) a standardization working group defining a cryptographically signed 2D code, and I try to make test cases where certain byte strings occur that could trigger incompatibilities between code generators and scanners. A simplified characterization is that there occurs in the signature a sequence of at least $u$ (like 3 to 7) bytes in a set of $v$ (10 to 13) values. That has probability about $(v/256)^u\,(65-u)$ to occur by chance, which gets tiny when $u$ increases. I'm not afraid of forgeries: The overall aim is testing out code encoders that could cause failures on the field (e.g. passengers blocked from boarding) because the combination of data and signature hits a corner case in some decoders.
Off-topic: there's rudimentary data compression built into most 2D codes. In Aztec aka ISO/IEC 24778:2008, encoders are encouraged to switch to Digit mode when long-enough bytestring segments consist of bytes in a set corresponding to ASCII  0123456789,. which get encoded as 4 bit/byte. When other bytes occur between two such sequences, it can be used Byte Shift that "can encode either isolated extended ASCII or control characters or long strings of byte data, possibly filling the whole symbol. At the end of the byte string, encoding returns to the mode from which B/S was invoked". In Digit mode there's no direct way to Byte Shift, this is done thru Upper/Lock or Upper/Shift (the later designed to insert a single uppercase ASCII letter in a sequence of digits). At the end of a Byte Shift entered from Digit mode thru Upper/Shift, decoders vary about if they return to Digit mode or Upper mode, and all hell breaks loose. Below is a minimal example that used to decode to ASCII 333j+33333 for ZXing (before version 3.2.2 of 8 Aug 2016) but 333j+ITIT for NeoReader and some others.
.


texts:
Out of the two deterministic random bit generators defined in section 10.1 of NIST SP 800-90A (i.e. based on hash functions), which one is cryptographically stronger?

Hash-DRBG (Section 10.1.1)
HMAC-DRBG (Section 10.1.2)

Is there any other criteria to select between these two?


texts: Pairings in Identity-based encryption vs. Attribute-based encryption

texts:
The bilinear map in Identity-based encryption should satisfy $e(aP,bQ)=e(P,Q)^{a\cdot b}$ whereas Attribute-based encryption schemes use $e(P^a,Q^a)=e(P,Q)^{a\cdot b}$ with $a,b\in\mathbb{Z}_p$ and $e:\mathbb{G}_1\times\mathbb{G}_2\rightarrow\mathbb{G}_T$.

Why are they different and are there reasons to prefer one over the other? Are they fixed in their purpose?


texts: Signing a message to make sure that it will not be tampered with when forwarded, without trusting the receivers?

texts:
Lets say there are 3 people.

1st signs a message and sends it to 2nd using public key encryption
1st deletes the message
1st tells 2nd to forward his message
2nd forwards the message to 3rd

How can 1st verify the message was forwarded untampered without trusting 2nd or 3rd and without finding out the message contents again?

A terrible idea is to have 3rd give his private key to a 4th who will confirm to 1st that his message was untampered.

I am new to this so if what I want to do is impossible a heads up would be deeply appreciated.


texts: asymmetric encryption with rekeying in an untrusted environment

texts:
Alice can retrieve asymmetric encrypted messages (let's call one of them C1 and the Message itself M) for her from an untrusted environment (let's call it Eve). She owns her private key K1 and has published her public key P1. Bob is just like Alice and uses Eve's platform. He owns his private key K2 and his published public key P2.

Alice now decides to share all her Messages with Bob. Normally she would retrieve each encrypted message C1, decrypt it to M using K1 and encrypt it again to C2 using P2.

However, Alice is in a rush today and doesn't have the time to 'translate' all that messages. She would rather like to create some form of re-encryption key R combining K1 and P2. It is important that you cannot calculate K1 (since it is private for Alice) even when you know R and maybe P2. She would then send Eve R and Eve has to translate all possible messages C1 directly to C2 without ever finding out M.

Does any asymmetric encryption method exist which provides such a 'rekeying' feature?


texts: Should I split a 3MByte block into smaller blocks if using XXTEA?

texts:
Given that I have a 3MByte block of data, a random key and need to use XXTea, is there any advantage in splitting the block of data into smaller blocks and encoding / decoding each separately?
Is there a sensible upper limit to the size of block as far as encryption / decryption is concerned?


texts: How to determine the next number from java's Random method

texts:
I understand a little how Java's Random class works.

I have two random numbers output from calls to nextInt() from a java.util.Random  object in Java. I want to determine the next number output after a third call.

The first two numbers are: $-1952542633$ and $-284611532$, how can I determine the next number given only this information?


texts: Is it possible (how difficult) to find MORE than one valid RSA signature?

texts: Is it possible (how difficult) to find more than one valid RSA signatures for a given message m (after padded) and a public key e (with the private key d known). Apparently signing m with d gives one valid signature. My question is how difficult to find another one. Thanks.


texts: Assuming the difference between success probabilities to be positive

texts:
Context: I am currently studying Theorem 3.1 in the paper Number-Theoretic Constructions of Efficient Pseudo-Random Functions by Naor and Reingold. The theorem basically states the randomized self-reducibility of CDH.

Throughout the proof the authors reach the following statement:

  Let $\mathcal{R}$ be the probabilistic polynomial-time algorithm that is guaranteed to exist by Lemma 3.2. By the definition of $\mathcal{R}$ and our assumption, we have that for any $a, b$ and $c \neq a \cdot b$ in $Z_Q$:  $$ |\Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{a \cdot b})) = 1] - \Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{c})) = 1]| > \epsilon(n).$$

Then the authors go on and state that this implies an algorithm that is able to correctly classify all CDH instances with an error probability of at most $2^{-n}$. I am pretty sure that the core of this last step is just the application of Chernof Bounds like one does to amplify the success probability of  $\mathcal{BPP}$ algorithms, e.g. like here: http://people.csail.mit.edu/madhu/ST07/scribe/lect11.pdf

My problem: However, as I understand this, in order to apply the Chernoff Bounds, I need that (reusing $P, Q, g, a, b$ and $c$ from above) $$\Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{a \cdot b})) = 1]> \Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{c})) = 1] $$
always holds or at least for all $n$ large enough.

It was intuitive to me to assume this without loss of generality and reason it, by stating that the output of $\mathcal A$ can be negated in order to achieve this. But thinking about it for a couple more minutes, I came to the conclusion that this is not enough. $\mathcal{A}$ could follow several patterns to determine on which type of input it outputs 1 with a higher probability. For example: $\mathcal{A}$ could measure the length of the encoding of $P$ in bits. referring to this number as $k$, $\mathcal{A}$ could flip its output if $k$ is even.

One could imagine many more such strategies. In the end, I came to the conclusion, that the function
$$
f(P, Q, g, g^a, g^b, g^c) := \begin{cases}
1 & \text{if } \Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{a \cdot b})) = 1]> \Pr[\mathcal{A}(\mathcal{R}(P, Q, g, g^a, g^b, g^{c})) = 1]\\
0 & \text{otherwise}
\end{cases}
$$
would need to be polynomial time computable.

Question: Assuming $f$ to be polynomial-time computable seems reasonable to me. But I am not 100% sure it holds, because the reason for changes in the function $f$ might also be out of the control of $\mathcal{A}$. So, are there technically sound arguments that $f$ is polynomial-time computable?

Also: I have the impression, that may approach to this might be more complicated than it needs to be. Have I missed a simple explanation? (I already had a look at this question, but it did not answer my question because they limited themselves to concrete $i \in \mathbb{N}$.)

This might be a small technical detail, but I think it's something that appears relatively often and I prefer to understand proofs in detail and not only on a high level.


texts: Prove that you have the data when hash is public

texts:
I am designing an online service where users can upload files (3d models) for processing. I want to speed up things when the same file is uploaded by many different users by allowing them to post a hash (SHA256) of the file before sending the file. If the hash exists they immediately get the processed file otherwise they upload a file.
I worry about this approach that a user can find SHA256 of a file somewhere he may be able to download the processed file without actually owning the file. E.g. SHA256 is somewhere public, but the file is private (e.g. a marketplace made SHA256 for paid 3d models public and someone paid for them and processed them using my service) ... or the metadata is hacked
The questions are:

Is this a genuine concern? Should I be worried about people getting SHA256 and abusing it to get other user's files?
How do I fight this? I was thinking of using HMAC: the server would send a key to the user and ask him to generate HMAC for the file and send it back?
Would it be safe to make HMAC key public so I don't store it for each upload request but the user can just generate HMAC based on this public key?


texts: Counter Mode with a sequence of zeros bits plaintext, is it secure?

texts:
I had a quiz last week in computer security course. There was a confusing question that I am still looking for a good and clear answer.

First, I know that counter mode with a good block cipher is widely accepted and most likely unbreakable as long as the counter (IV) is not being reused.

The question was about using counter mode with a strong block cipher, say AES. The IVs are independently generated. Suppose we encrypt two messages M1 and M2 where M2 is zeros, a sequence of zero bits, and get ciphertexts C1 and C2. Assume C1, M2, C2 are known by an attacker, would it be possible to decrypt, reveal M1?

Since in counter mode C = M ⊕ E(K,(nonce,IV))

for M2, the C2 = E(K,(nonce,IV)) , since M2 is zeros and xoring with zeros does not do anything.

I know that C1 ⊕ C2 = M1 ⊕ M2 but not sure if it is useful here.

My answer was the attacker will not be able to know (M1) because of the strength of the block cipher and the encryption process depends on the key, nonce, and IV which won't be broken if the attacker knows pair of plaintext and it corresponding ciphertext.

I am confused because what I have learned the strength of the counter mode depends on a good block cipher and non-reused IV, but what will happen if the input was zeros, and  E(K,(nonce,IV)) was exposed to attacker?

I did not feel I was right, and still confused about it.

Hopefully I can get a clear answer with appreciation.


texts: Non adjacent form of an integer is unique

texts: I have tried to look up the proof for NAF (Non-adjacent form) being unique for every integer, but as far as I have seen, textbooks only mention it as a property of NAF, but no proof is given. Also I understand that the number of zeroes in NAF representation is more than in its binary representation but how do I prove that NAF representation of an integer has 2k/3 zeroes for a k-bit integer in general. Even a textbook reference that contains these proofs would be appreciated.


texts: Should the most significant byte of a cryptograhic key be nonzero?

texts:
Is it safer to give a non zero value to the most significant byte (MSB) of a cryptographic key to ensure its length (not 31 instead of 32 for an EC private key on a 256-bit curve for example)?

Or is it counterproductive because it decreases the entropy?

I ask the question for the MSB but it could be for several of the first bytes.


texts: How to calculate LOW(b) and HIGH(b) in spritz cryptography

texts:
I try to implement spritz cryptography like this paper . But I don't know how to calculate LOW(b) and HIGH(b). In paper page 7.

low(b) = b mod D
high(b) = b/D

D = square root N
b = D * x+y

I don't khow what is x,y. The example LOW(b) and HIGH(b) of N=256 is

#define LOW(B)  ((B) & 0xf)
#define HIGH(B) ((B) >> 4)

what is LOW(b) and HIGH(b) of N=16.


texts: Problem in understanding Blakley's Secret Sharing Scheme

texts:
I need to implement Blakley's Secret Sharing Scheme. I have read below mentioned two research papers but still unable to understand how to implement it.

Safeguarding cryptographic keys
Two Matrices for Blakley’s Secret Sharing Scheme

The following is the steps I have been able to understand.

We chose positive integers $z$, $a$ and $b$.
We chose a large $p$
A $(a+b+2)\times(b+2)$ matrix $M$ is created satisfying the following conditions:

Random entry in each row is set to $1$.
Another random entry in first row is set to $k$, chosen from $\mathbb F_p$.
All other entries are filled with random values from $\mathbb F_p$.

After this some equation need to be formed and then solved for share.

I am unable to understand how shares are calculated and how can they be verified. Kindly help me understand the remaining process.


texts:
I try to understand the TLS Handshake with DH. I googled the concepts and I think I understood the basics. But there are somethings I'm still struggling with. I also read the following two posts Why does the SSL/TLS handshake have a client random? and Why does the SSL/TLS handshake have a client and server random?

I don't understand how client random, server random, pre-master-secret and master-secret relates to the DH parameters.

Is the Client-Public-DH-Value A (A = g^a mod p) the same as the pre-master-secret? and the master-secret the same as the DH secret/Session Key s (s = A^a mod p)?

There are a lot of images e.gl Wikipedia but I don't see the relation between these steps.


texts: Is it possible to derive an asymmetric algorithm from a symmetric one?

texts: Given the advancements in quantum computing, there's a lot of incentive to move away from the usual asymmetric cryptography. Is there a way to turn a symmetric algorithm (e.g. AES) into an asymmetric one?


texts: Pairing-based cryptography VS ZK-proofs: what's more efficient for threshold systems?

texts:
In some papers (e.g. 1, 2) the authors approve that pairings are more efficient than classic zk-proofs (e.g. proof of discrete logarithm knowledge) for the described applications (threshold encryption, PVSS).

Let's see the differences between these approaches:

Proof:

Pairings: there are no additional steps.
ZK-proofs (non-interactive dlog knowledge): one (sometimes more) multiplication (we consider elliptic curve cryptography) in the group, hash-function,  a couple of additional arithmetic operations.

Verification:

Pairings: pairing, obviously.
ZK-proofs: two (sometimes more) multiplication, one addition, hash-function.

But pairing is more expensive than point multiplication. If we consider a threshold system, verification is more important (because you should make a proof once and verify all other participants). In this case pairing-based cryptography is less efficient than zk-proofs. Am I wrong?


texts:
My professor showed us the basics of DES, and then displayed this slide where the Meet in the Middle attack can be used as a way of cracking DES. I believe at this stage we are doing 2DES, as opposed to DES or 3DES.

Could someone explain the math to me please?


texts: Generating a SHA256 pkcs1v1.5 Blind RSA Signature using Chaum's Blind Signature Scheme

texts:
I am a noob to cryptography in the sense that I have very less understanding as to how RSA encryption schemes work in practice. However I do understand the theoretical foundations of RSA cryptography and also Chaum's Blind Signature scheme as described in the wikipedia article on RSA Blind Signatrures.
I did find an implementation of this scheme that I can use successfully to blindly sign using vanilla RSA.
However my problem is as follows: I need to be able to generate a SHA256 pkcs1v1.5 RSA signature based on the same blinding scheme described in the article I linked to before.
I understand that RSA Blind Signatures are less secure in general. However I do not intend to use the same keypair for encryption.
I have read up a little on pkcs1v1.5 RSA signatures and from what I could gather, they use 'padding', in addition to some other techniques to make RSA more viable.
The pkcs1v1.5 specification has a comment that states

Note.  Another way to implement the signature verification operation
is to apply a "decoding" operation (not specified in this document)
to the encoded message to recover the underlying hash value, and then
to compare it to a newly computed hash value.  This has the advantage
that it requires less intermediate storage (two hash values rather
than two encoded messages), but the disadvantage that it requires
additional code.

I am aware of this post that details that this is possible if the sender, or the 'Signee' does the padding before sending the message to be signed. On similar lines, what kind of padding and other methods do I have to employ in order to generate a pkcs1v1.5 Signature, so that any third party, knowing only N and E can verify this Signature using the normal method or the 'decoding method' quoted above?


texts: In EC with key chaining, is it possible to verify signature made by root private key using public key of derived keypair?

texts:
I am not sure whether crypto.SE is the right place for this question, but I assume this is closest to on-topic here.

I am doing personal research on cryptography using elliptic curves. I can see that many projects starting to utilize deterministic key derivation (my terminology may be off here, see below what I mean by it).

What I am wondering is whether knowing how derivation process is done, is it possible to verify signature made my root private key using child public key?

Assuming:

random -> root keypair (rootPriv, rootPub) -> KDF(rootPriv) = childPriv, KDF(rootPub) = childPub

Then assuming two parties Alice and Bob:

Alice holds rootPriv/rootPub and childPriv/childPub.
Bob holds only childPub.
Alice wants to send message to Bob and ensure Bob receives it untampered. Alice then signs message using rootPriv and sends to Bob message and signature.

How can Bob (if it all possible) verify the signature knowing KDF and childPub without knowing rootPriv/rootPub/childPriv?

If that is possible for EC, does such requirement pose any restrictions on which curve can be used or on KDF? E.g. can any curve be used (Ed25519 or any other?) and would KDF need to be reversible in nature or any other restriction?

PS: This is about EC strictly though


texts: Implementing the Mceliece Encryption - making the Generator Matrix

texts:
I am working on an implementation of the Mceliece Encryption system (MCE) and the Niederreiter encryption system. I have been through the basics of finite fields, polynomial arithmetic and some coding theory to understand it.

In brief given MCE parameters $n, k, t$, such that it is over $GF(2^m)$, $n = 2^m$, $k = n - mt$ is the dimension of the linear code and $t$ is the no. of errors the code will correct, the public key is $X = S.G.P$, where $S$ is a $k$ x $k$ non-singular matrix, $G$ is the $k$ x $n$ generator matrix for the linear code and $P$ is a $n$ x $n$ permutation matrix.

Figuring out how to get $G$ is the reason for the question. I'd like to better understand how the generator matrix is built such that its elements are only $0$ or $1$, once we have the irreducible polynomial of degree $t$, support $L$ and parity check matrix $H$. $L$ & $H$ are composed of the elements of $GF(2^m)$ represented as polynomials in binary form, e.g. $x^4 + x^2 + 1$ is represented as $10101$.

I understand there are many methods of getting to the generator matrix but found limited information online. I'd welcome a simplified explanation of the maths/algorithm or any pointers to sites/books which would help out on this.


texts:
There is some intriguing things about DES and 3DES. Now, I know that DES is weak and 3DES was an attempt to construct a more secure block-cipher from a deprecated one.

Having this in mind, what about the composition of two independent instantiations of block-cipher (t.i.t.s with two independent keys) having a reduced number of rounds. Take the example of AES (with key of 128-bit) which has 10 rounds (and consider that the last round is complete, in the sense that it contains all the operations add-roundkey, mixcolumns, shiftrows and subbytes). If we consider a reduced version of AES with 5 complete rounds, denoted $AES^r$, and we construct a new block cipher in the following way:

$$AES'_{k_1,k_2}(.)=AES^r_{k_1}(AES^r_{k_2}(.))$$

Is this block cipher as secure as the original version of AES ?
It seems to me that it does, since the keys are independant, but I need confirmation.

Edit: Is the following composition also secure ?

$$AE''_{k_1,k_2}(.)=AES^r_{k_1}({AES^{r}}^{-1}_{k_2}(.))$$

where ${AES^r}^{-1}_{k_2}(.)$ denotes the decryption operation.

Thank you.


texts: How complex must round constants be to resist slide attacks?

texts:
A key schedule that generates round keys by XORing a round constant with the key is linear and can be vulnerable to related key attacks, but let's ignore that for now. Constants are necessary to avoid the slide attack. How complex do these constants need to be and how much must they differ?
For example, would a trivial key schedule composed of $r_i = k \oplus c_i$ to generate the $i^\text{th}$ round key $r_i$ using round constant $c_i$ and secret key $k$ be weak to any form of cryptanalysis if $c_i = i$?


texts: Improving security of (authentication) protocol

texts:
I have a basic protocol which tries to authenticate messages going from client to server. Basically it is like this:

Imagine I want to send message M to server.
Client computes a MAC over the message. The MAC is basically DES_ECB encryption of data MAC_DATA length of which is 8 bytes. MAC_DATA is obtained
by XORING the plain message M between each other. Like this

  for (int i = 0; i < dwSize; i += DppGlobals.MAC_SIZE)
  {
        for (int j = 0; j < DppGlobals.MAC_SIZE; j++)
           MAC_DATA[j] ^= plaindata[i + j];
  }

And MAC is

  CALC_MAC = DppDES.EncryptDES_ECB(MAC_DATA, WorkKey);

Finally what client sends to server is:

Client -> Server: CALC_MAC, M

Assume keys are stored securely on client and server, and also they are shared.
Now since DES is insecure I am trying to improve this protocol. My idea is
basically the client will send to server AES encryption of the data it was sending before. So client sends to server

   Client -> Server:  C

Where C = AES_ENCRYPT_CBC(CAL_MAC | M, Key, someIV);

The server will decrypt the data it receives, and perform computations like it was doing before.

So is my modified version (with AES encryption) more secure than the old(current) protocol?

Since this protocol is already implemented, the change I want to add for improving its security should desirably be minimal - to avoid introducing new bugs. Also completely rewriting and using TLS is not an option.


texts:
Reading through the DES Specification it says that the keys are permuted with PC-1 initially and then shifted left both $C$ and $D$. However, before it gets permuted again through PC-2 it does not mention how $C$ and $D$ are put together before going through PC-2.

Is it assumed that $C$ is the lower half of the input to PC-2 with the higher half being $D$ (this comes from it saying that they are $CD$), or are they multiplied together/some other operation is used?


texts:
I'm working on implementing a cryptographic system and I'm trying to understand the Zero Knowledge Password Proof concept. So here's some background:

To generate a secret key I am:

Doing an ECDH key exchange and generating 2 secret keys. One key is to encrypt messages and the other key is to HMAC sign the data. To derive the secret keys I am sending the username from the client along with the public keys and using the password on the client and server to derive the encryption keys by running the ECDH keys through a KDF function so that if the keys were retrieved the passwords could not be known.
Once I have these secret keys I want to use them to encrypt a message that does not include the password to send over to the server to authenticate that the client does indeed have the correct password.

I want to make sure that I implement this properly and I know that if I encrypt something that is preknown to the server that could be insecure because of some attacks that involve knowing the plaintext as well as the cipher. Do I need to just create a random string to encrypt? Any thoughts? Thanks!


texts: Can XTS + checksum be used for authenticated encryption?

texts: Is it possible to use XTS + a checksum for authenticated encryption?  Specifically, it seems like a good $n$ bit checksum applied before encryption should ensure that any change to the ciphertext will be detected by the plaintext checksum with a high probability ($1 - 2^{-n}$).


texts:
I did found an old question which answers exactly this but it is from 2 years ago and i was wondering if there were any changes. I have not been able to find any new information on the cipher and am quite curious seeing as it's extremely fast.

I've tested it against a very fast (fastest I have found so far) AES implementation which took 392μs to encrypt 128 bytes and 400μs to decrypt 128 bytes.

The SEED cipher took 325μs to encrypt the same 128 bytes and 228μs to decrypt. This is enough to make it interesting for me though I still prefer AES since it is more well known and has been through more scrutiny.

Both tests were done with the same CBC method, so there might be some performance to be gained from a better CBC implementation but i think the one i have is already quite good, for those of you who are wondering i'm using the CycloneSSL library on a RX63N board (renesas development board).

So can SEED be trusted? Can i use it for sensitive data?


texts: Could a crypto system that uses non-FIPS crypto but then upgrades complete to FIPS be FIPS certified?

texts:
I know most people around here (including myself) are anti-FIPS, but I have a FIPS related question.

Could a crypto system that is not FIPS, e.g. one based on primitives like Curve25519, achieve FIPS compliance if it is capable of upgrading to FIPS algorithms/implementations in a way that is complete. By complete I mean in the upgraded mode it is using only FIPS compliant crypto and the upgrade occurs in such a way that all the previous security guarantees are re-confirmed using FIPS crypto.

Or would the mere presence of non-FIPS crypto at any stage of the system invalidate it for FIPS certification?


texts: Simple compression functions an sponge functions for educational purposes

texts:
For block ciphers, there are the very well designed schemes of Simple-DES and Simple-AES, which have been created not for security but for teaching the design principles of the real algorithms while maintaining the possibility to calculate them by hand and guarantee an easy demonstration.

Are there any such simplified functions for Merkle-Damgard compression functions or sponge functions available?


texts: Understanding a security error with RC4 using the same key to encrypt on the client/server sides

texts:
This apparently was a bug with WhatsApp a while ago. I am endeavoring to recreate it and understand it.

The bug had to do with the fact that the same key was used to encrypt plaintext on both the client and server sides. However, (A ^ X) ^ (B ^ X) = A ^ B ; ^ is the bitwise XOR function. In other words, if if there are two messages encrypted with the same RC4 key, the key stream cancels out.

To illustrate this with an example: we have a simulator which creates a bunch of messages for both the server and client side. For the sake of simplicity, assume that all the messages are 128 bytes long (i.e. they are always padded to ensure they are that length) so that we do not have to guess where messages start and end.

An example message from the client side is: LOGIN JOHN foo //padding

An example message from the server side is: INVALID PASSWORD //padding

I don't know either of these messages.

Say that with a bit of traffic sniffing, I've come into the possession of two files, ServerSideEncrypted.dat and ClientSideEncrypted.dat.

Reading the first byte from ServerSideEncrypted.dat I discover that Byte1SS_encrypt = 01111100 and reading the first byte from ClientSideEncrypted.dat I discover that Byte1CS_encrypt = 01111001. Now, 01111100 ^ 01111001 = 00000101.

To ensure that this checks out, assuming that I did know the first letters of each of the messages from the client and server sides, I would have Byte1CS_plain (the letter L) = 76 (in ascii) = 01001100 and Byte1SS_plain (the letter I) = 73 (in ascii) = 01001001. 01001100 ^ 01001001 = 00000101. So indeed, the XOR of the two encrypted bytes is equivalent to the XOR of the two plaintext bytes.

At this point is where I become stuck. I know the following things:

Byte1CS_plain ^ Byte1SS_plain = Byte1CS_encrypt ^ Byte1SS_encrypt = 00000101
Byte1CS_encrypt = 01111001
Byte1SS_encrypt = 01111100

However, this still leaves me with 2 unknowns. How do I proceed with this information to decipher the messages? How do I figure out that Byte1CS_plain = 01001100 and Byte1SS_plain = 01001001?


texts: FLT is partly applying to RSA equation, and also relation between ED mod phi and Phi + 1 mod N

texts:
After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions.

1) We generate the keys by doing ed = 1 mod Phi. So when mathematically stating the equation, we know, that M^ed = M Mod N. We also know that M when coprime to N, we have M^Phi + 1 = M (mod N) (ommiting the k). I am a bit confused about the relation between [Phi + 1 and ED mod Phi.] If somebody could help me with that.

2) Lastly the equation works like Fermat's little theorem. When a and p are co primes, a^p = a mod p, which in this case is m^phi + 1 = m mod N, and Fermat's also says that a^p-1 = 1 mod p, but for the second part, when we use m as of the invertible elements of the group U(N), the answer does come 1, but for any element m, the solution to m^phi mod N, is not 1. So a part of Fermat's LT, is applying here as I see. If someone clears me on that part. Thanks...


texts: PBKDF2 with longer than native output length - Will hashing the result help?

texts:
I've seen it mentioned more than once that PBKDF2 should not be used to create a longer key than the native output (such as 160 bits when used with HMACSHA1). Since an attacker could test only the native size and rule out a password. (Example)

But what if we hash the (complete) result one more time? This would seem to solve the problem. Since without the whole calculation - no part will be known.

Am I correct?


texts: Why is the Keyspace of a Substitution Cipher not 2^26 but 2^88

texts:
It is known that a cipher has a keyspace of cryptographic algorithm whose key length is $n$ is given by $2^n$, but the keyspace of the substitution cipher is $2^{88}$ which is an approximation of $26!$. (I am considering an alphabet of 26 letters)

Assuming the key length is 26 (which it should be for the alphabet) Why is it not $2^{26}$?


texts: Are TLS 1.2 AES-CBC and AES-GCM Authenticated Encryption ciphersuites?

texts:
In the answer of the following post: Why was AES CBC removed in TLS 1.3?, I quote the following from the chosen answer:

  After the Lucky13 attack (a timing oracle caused by MAC-then-encrypt),
  it was thought that TLS should change ordering of the operations.
  Changing order of the operations would have affected the backwards
  compatibility with previous implementations so it was after all
  thought that it is more practical to switch to authenticated
  encryption only.

In the answer, it is assumed that AES-CBC in TLS 1.2 is not Authenticated Encryption (reference to the last part of the quote: it is more practical to switch to authenticated encryption only.

My questions:

When can I consider a ciphersuite an Authenticated Encryption?
Is AES-CBC in TLS 1.2 an Authenticated Encryption (it uses MAC-then-Encrypt construction).
Do padding attacks in AES-CBC render it considered non-Authenticated Encryption cipher?


texts: What's a good strategy for the game "spyfall"?

texts:
https://boardgamegeek.com/boardgame/166384/spyfall

There are n players (n > 3), and n-1 of them know a secret string (the location). The nth player is the "spy", and does not know the location.

The non-spies has to guess which player is the spy, and the spy has to determine the location.

Players cannot communicate at arbitrary times. Only one person (the player who's turn it is) can communicate, all players will hear the information this person is communicating. The player who's turn it is also gets to choose the next player.

The tricky part is that there are only 30 locations, so it's easy to iterate over them all. This is why, for example this strategy will not work:

generate a random string r, and, when it's your turn to communicate, say  (r, Hash(r + location)). The person who is unable to say this is the spy.

This will not work because the spy can compute hash(r+location) for each location, and the location that matches the given hash value is the correct location.

The spy can win with probability 1/30 by guessing a location and then acting as if that location is the correct location. Is there a protocol for the non-spies to find the spy with probability negligibly close to 29/30? (assuming that all non-spies follow this protocol but the spy can do whatever they want).


texts: Seed a PRNG with random data and a password

texts:
I'd like to combine a random key file with a password to generate a secure seed for a CSPRNG. The key file is assumed to have very high entropy, but the password will be whatever the user provides. What's the best way to combine the two in order to seed the PRNG? The goal of course is that the output of the PRNG will be difficult to predict unless you have both the key file and the password.

My first thought it to simply use PBKDF-2 to stretch the password so it's the same size as the key file, then XOR them together. I won't be transmitting this seed or anything, so I don't think it matters that this in itself is poor encryption. But are there any other considerations I should make?

I will most likely be using AES in counter mode for the PRNG, but an answer covering a more generic case would be appreciated. Also, I'm assuming that the key file is the same size as the seed that the PRNG will take.


texts: With sufficient randomness, is XOR an acceptable mechanism for encrypting?

texts:
I have heard criticism of various cryptosystems saying that "at their heart, they were just XOR."

Is this just ignorance, or is there something inherently wrong with XOR based ciphers?


texts: Using a bit sequence of zeros followed by one byte in Keccak

texts: For what purpose it is not right to use a bit sequence of 2000+ zeros followed by one byte in Keccak? Is there a possible application of such input for Keccak? If yes, after which transformation?


texts: How to force non-negative int64_t output for blowfish encryption with int32_t input?

texts:
I would like to encrypt a series of small integers one by one. The range of them is about 0~10^8. The output must be non-negative int64_t integers.

Since Blowfish is 64-bit cipher, I prefer to use it as symmetric encryption algorithm.

The problems are:

Since 32-63 bits of input is always 0, do I need to do certain pre-process step to enforce security?
The sign bit of Blowfish's output may be 1. I have to prevent this happen. What should I do?
How to design correct decryption procedure to get original integer int32_t?

Thank you in advance.


texts: Using bcrypt for MAC - is it correct and secure?

texts:
Suppose there is a hashing function:

$$ph = bcrypt(sha256(m + k), salt)$$

Here $ph$ is a password hash obtaining by applying $bcrypt$ on $sha256$ result of concatenating a message $m$ with a secret key $k$. Assuming that

key $k$ is not visible to attacker;
key is a "truly" random sufficiently large string;
the work factor of $bcrypt$ is sufficiently large as well;

The question is how much is this schema secure? Can an attacker obtain the secret key $k$ by issuing messages $m$ and retrieving hashes $ph$ and how much efforts will it take? How much does the strength of this schema depend on the size of the key?

Are there any ways to improve this schema?

I thought such schema may be used for MAC. Should I use HMAC+SHA512 instead?


texts: Why modn and modular exponent g^x mod n are not cryptographic hash functions?

texts:
I have been trying to find a solution to this question and wasn't able.
When it comes to signatures and Hash Functions, how would be possible to show that $\pmod n$ and modular exponent $g^x \pmod n$ are not cryptographic hash functions?

Any help will be very appreciated


texts: Are there any homomorphic first and second preimage resistant (cryptographic) hash functions?

texts: Are there any homomorphic cryptographic hash functions that satisfy $\text{H(A + B)} = \text{H(A)} + \text{H(B)}$ which maintaining pre-image resistance


texts:
As a follow up to the Q/A session:
Small Quantum Signatures - Reality check needed

I have implemented the discussed idea for a new short-quantum-safe signature system using fast-forwarding hash.  It creates 32 byte public keys and 129 byte signatures.
It is as good as I could get it in the little time I had available.

I have uploaded the source code to GitHub (Java) under MIT licence for the benefit of crypto exchange.
https://github.com/MKAXLACOR/FastForwardHashSignatures

My question then is : are there any obvious errors with the algorithm I have chosen to provide the fast-forwarding function?

I wouldn't mind forwarding this on to Bernstein etc so they can also take a crack at it - however if there are any obvious issues that I need to correct first - would appreciate knowing!
Many thanks.


texts:
Oracle DBMS offer builtin random number generator (pseudo to be accurate). DBMS_RANDOM is one of the available packages, it is however considered as insecure for cryptography.
Do we happen to know the algorithm used by this method ?


texts:
I'm looking into implementing a private SILC server for friends (and possibly their friends).

And after visiting the Wikipedia entry for SILC protocol, it seems all the official pages linked at the bottom are dead with only a few anon servers here and there.

Is it still being used nowadays?
And if it is ... where(online) are more resources (howto's and/or daemon software)?

And if it isn't used anymore... are there any security reasons involved?

Is the security model or the used cryptographic protocols and algorithms flawed thanks to exploit XYZ?

A complementary question would be: are there any more current alternatives available now?

another complimentary question would be:are there any public and/or anon servers still online ?

and ..does it use much system ressources on a server let's say for 50 concurrent users ?
(this is just a complimentary question if you feel you can answer :)


texts:
Can the knapsack be used in cryptography in a secure sense (described below)?

Knapsack problem: Given some number $X$ and a set $W$ of weights $w_1, w_2, ... w_n$, find a subset $S$ of $W$ (if it exists) whose weights sum to $X$.

Even though this problem is NP hard, there exist "pseudo-polynomial-time" algorithms for it and the average case hardness is questionable. So I am not sure how secure the knapsack is in reality.

I want to use the knapsack in a symmetric key sense (like a hash function), and NOT in a public key scheme, so there are no restrictions on  $X$ and $W$. Uniqueness of solution is also not required. The only requirement is that finding any such $S$ should be hard.
So my qustions are:

Is there a strategy for choosing $W$ and $X$ that makes the problem hard?
What are the practical values of $W$ and $X$ that make the problem hard?

EDIT: I don't need the strategy to also give me a solution $S$. The solution is never needed. The use-case requires finding any solution to be hard. The person generating the problem need not know the solution. Additionally, given the problem, it should not be easy for anyone to decide if a solution exists or not.


texts:
If we consider the generation of keys as

$$\begin{aligned}
K_0 &= E_K(IV); \\
K_{i+1} &= E_{K_i}(A)
\end{aligned}$$

Where A is a block of zeroes, and the ciphertext blocks are computed as

$$C_i = E_{K_i}(P_i), \quad i \in \{0, 1, 2, \dots\},$$

is there any problem when we encrypt the same message twice with the same key $K$ and different $IV$?


texts: Is XCBC where k2 and k3 might be the identical, secure?

texts:
XCBC paper says all three keys should be independent. It doesn't say they must always be different. However it seems this is necessary to differentiate padded message and message without padding.

Lets say we derive all three keys so that key 2 and key 3 might be the identical (randomly). Is it secure?


texts: Decrypt (homomorphically and symmetrically) encrypted data using (homomorphically) encrypted key?

texts:
Is it possible to do the following?

Generate symmetric key $K$
Encrypt data $D$ with the symmetric key : $E_k{(D)}$
Encrypt the symmetric key and the encrypted data using homomorphic encryption scheme (e.g. Paillier) with FHE key : $E_{paillier}(E_k{(D))}$ and $E_{paillier}(K)$
Send both $E_{paillier}(E_k{(D))}$ and $E_{paillier}(K)$ to the other third party
The third party (symmetric) decrypt using it and outputs $E_{paillier}(D)$


texts: What's the meaning of “family” in “family of hash functions”?

texts:
Many definitions related to universal hashing mention the term

  a family of hash functions, say $H$

What does this 'family' mean exactly? A numerical example would be appreciated. Also, what does it mean to choose a hash function h at random from a hash family $H$?


texts: Given that valid private keys on curve25519 must be less than the order of the curve which is (as I understand) already smaller than 2^256, AND a valid key must be clamped to be divisible by 8 and have its high bit set, what is the actual 2^X number of valid private keys approx?


texts: Can Curve25519 be used for pairing-based cryptography?

texts: We usually need pairing-friendly curves in order to use them for bilinear pairing computation. Is Curve25519 a pairing-friendly curve? If not, can we still use it for pairings and how much more inefficient would a pairing computation on this curve be compared to a BN curve?


texts: Yubico’s take on U2F wrapping: purpose of MAC?

texts:
I've been reading up on Yubico's implementation of U2F.

I am confused on the purpose of the message authentication code (MAC). It prevents an attacker from providing a key handle (particularly a nonce) that wasn’t generated by the U2F device. I get that.

What would an attack involving changing the nonce look like? Since the AppID is also provided to the U2F device, an attacker having taken control of a website (say site-a.com) wouldn’t be able to do a challenge-response for another website (say site-b.com), even if the attacker knew the user’s nonce for site-b.com.


texts:
I was reading the original BGW paper. Great paper. I'm confused about Theorem 2, though.

The Theorem states, "There are functions for which there are no n/2-private protocols."

The proof is simply that two players cannot compute an OR without one of them leaking information.

But the way I see it, that isn't an MPC problem, that's a problem with the function being evaluated. Normally, the security of MPC is evaluated on the basis of whether it accurately simulates a trusted third party who receives inputs, evaluates the function and distributes outputs. Even with a trusted third party, evaluating an OR would always leak information about one of the inputs to the other party.

Similarly, couldn't you just argue by the same logic that if you evaluate the function $f(x_1, ... x_n)=x_1$ for arbitrarily high number of players $n$, then this leaks information about player 1's input?

So you could argue, by the same argument that "There are functions for which there are no 1-private protocols."

Or am I misunderstanding their proof?


texts:
I have an application where it would be advantageous for an attacker to have to spend a long time generating public keys.

To do this, I require that the hash of the public key be less than a certain number.   That way a typical user will take 1 second to generate a public key, and an attacker who is trying to DOS public resources will also have to spend more resources to do so than it costs for us to detect.

There are two mechanisms proposed:

Take a public key, hash it many times with an incrementing salt, and require the result to be less than a certain number.
Generate a public key, hash it once, and if the result is not less than a certain number, add one to the private key and add the generator to the public key.

The first mechanism helps mitigate DOS and spam attacks.   The second mechanism helps mitigate some MITM attacks as well.

I like the features of the second, except for some drawbacks:

This reduces the number of valid public keys that exist, and could reduce search space for an attacker attempting in the process of brute forcing public keys.  Since we're using a secure hash, it seems the DLP remains equally hard with or without this hash.
This relies on the point addition algorithm being highly efficient, and assumes an attacker may not have some new and better way to perform this operation.   But this is as opposed to assuming efficient hashing, an equal assumption?
It's possible that an unprivileged attacker observing the initial POW generation could determine some information about the key.   Not a huge deal since these keys are not frequently generated, but perhaps not.

Are there other things I should be thinking about?   Is there a standard out there in the wild I haven't found?


texts: Can a tree hash with leaf-size of 1 byte support verification of content with elided ranges, at a cost of at most 2 supplied internal-node hashes?

texts:
Perhaps someone can confirm my intuition:

A tree hash with leaves of size 1 (for example Blake2 in a tree-hash mode) would of course not be very efficient.

But it seems that it might be a suitable way (or maybe the only way?) to provide a verifier that's still useful if the underlying content is subject to intentional declared byte-range-elisions later. (That is: a form of digital redaction, where the original verifier still helps to assure that only the declared range has been altered.)

A content host performing elision would record the range, record the one or (usually) two internal tree node hashes that cover the to-be-elided range, then zero (or encrypt) the range.

When other parties want to verify the content is unaltered (except for the declared range), the host would provide the content, the declared range, and the up-to-two internal node hashes to be used in-place of the missing tree-hashed values. A root tree hash value would confirm that all other bytes in the file remain as when originally hashed.

Sound right?

Are there gotchas with this approach?

Any other better way to achieve the same end-result? (That is, use a compact-authentication value from when the content was whole, to still strongly verify unchanged ranges of content after some declared edit-range is removed?)


texts: Authenticated encryption with Enc-Sign-Mac

texts:
I've given a CPA secure private key encryption scheme, an unforgeable private key MAC scheme and an unforgeable public key signature scheme. I want to combine them to protect confidentiality, integrity and authenticity. I have to use the signature scheme, such that some third party can prove authenticity and integrity of the message. I tried it this way:

$c \gets \operatorname{Enc}_{ke}(m)$

$\sigma \gets \operatorname{Sign}_{sk}(c)$

$t \gets \operatorname{MAC}_{km}(c||σ)$

$\operatorname{Output} (c,t,σ)$

Does this protect the mentioned properties or: Is there any problem with Enc-Sign-Mac?


texts: Digital certificate issuing man-in-the-middle attack

texts:
While obtaining digital certificate the applicant trusts the certificate authority (or registering authority) as CA is digitally certified (and applicant  has CA's public key).

To certify a domain the protocol would go like this:

I generate my public-private keys and send the authority my public key encrypted by its public key.
She encrypts a nonce and sends me to put on my website
As I'm in control of the website I put this nonce and encrypt it with her public key
She checks and issues me a digital certificate for that site.

Is there a possibility for MIM attack here as follows:

attacker between me and the CA can pretend to be me and requests certificate for domain I control. He generates his public-private keys
he intercepts the nonce sent back by the CA
he mimics my site and puts on the received nonce
CA issues the certificate to the attacker?


texts: Using enigma and missing one word/sentence

texts:
After you set up all rotors, position and plugs in Enigma machine. If you don´t get the signal of one word or one sentence... your enigma settings are desynchronized. How you can recover from this situation? Do you need to wait until next day?

I imagine some radio guy in the middle of the battle and I find very difficult to keep track of every message.


texts: What is the difference between regular and "twisted" ECC curves?

texts:
When I do:

openssl ecparam -list_curves

I get, among other entries:

brainpoolP512r1: RFC 5639 curve over a 512 bit prime field
brainpoolP512t1: RFC 5639 curve over a 512 bit prime field

Apparently the "t" means it is a twisted ECC curve. Is this slightly more secure or slightly less secure? I'd rather give up a few milliseconds of performance than give up any security margin.


texts: Recovering state of modified RC4 key scheduling algorithm

texts:
Consider this algorithm:

def ksa(k):
    L = length(k)
    j = 0
    for i from 0 to L: #[0..L-1] (non inclusive "to")
            j = (j + k[k[i] % L])%L
            swap(k[i], k[j])

k is an array of integers $0 \leq x < 256$. The questions is how to enumerate all possible arrays k resulting in an array with given prefix $P$. In other words if k'=ksa(k), and if $P=[1,2,3]$, then how to generate all k, so that $prefix(k',length(P))=P$? Enumeration would be best, but constructing just one such k is good too. Solution for a variant with for i from 0 to C where $C \leq L$ would be interesting too.

This is a variation of the key schedule for encryption algorithm RC4.


texts: Is there any non-interactive zero knowledge proof for Diffie-Hellman tuples

texts: I'm aware that Zero-Knowledge for Diffie-Hellman Tuples requires 4 rounds. I wondered if there is any non-interactive version of it.