texts: Minkowski's theorem in lattice-based cryptography

texts:
I am studying basic lattice-based cryptography. In the course given by O. Regev, on page number 7, there is Claim 1 and Corollary 2 (Minkowski's First Theorem), both of which are difficult for me to understand.

In Claim 1, how the volume of a ball with a of radius r is $vol(B(0,r)) \ge \left( \frac {2r}{\sqrt{n}} \right)^n$ ? (Specifically, how does the ball contain a hypercube of side length $\frac{2r}{\sqrt{n}}$) ?
In Corollary 2 (Minkowski's First Theorem), for any full-rank lattice $\Lambda$ of rank n, $\lambda_1(\Lambda) \le \sqrt{n} (<det \ \Lambda)^{\frac{1}{n}}$. How to prove this theorem ?


texts:
I am reading about LoRaWAN 1.0.2 specification. For the confidentiality and integrity of the comunication the protocol generate two session keys, the NwkSKey and the AppSKey (part 6.2.5 of the specification, page 35).

Both, application and network session keys are derived like following, the only difference is the first component (0x01 and 0x02):

AppSKey = aes128_ecb_encrypt(AppKey, 0x02 | AppNonce | NetID |DevNonce | pad_16 )

0x02 is a costant of 8 bit.
AppNonce is a nonce generated by network server of 24 bit.
NetID is network identifier of 24 bit and not change if the join procedure is related on the same network.
DevNonce is a nonce generated by end-device of 16 bit.
The pad_16 function appends zero octets so that the length of the data is a multiple of 16.

I'm not sure of the robustness of this key derivation. Is the variable part inside the block being encrypted not just 40 bits? Furthermore, if you use the same AppSKey for a long period, even 3/4 years, is the solution still robust?

Furthermore, the DevNonce is sent from the end-device in the join request message and the message is not encrypted.


texts: What does it mean the security parameter for a FHE scheme?

texts:
FHE schemes claim to use some security parameter $\lambda$ for deriving the other parameters of the scheme, the size of the key and the possible circuits that can be evaluated. Like in Fully Homomorphic Encryption over the Integers. What does this parameter signify ?

Is something that applies only to FHE schemes and puts them on hierarchy of security ? How does this parameter compare to classical schemes, like RSA or AES ?
How can be compared the security of a FHE scheme with RSA or AES ?


texts: Regular and Efficient doubling in $GF(2^n)$

texts:
A naive approach to compute a multiplication $a \cdot b$ in a Galois field of the form $GF(2^n)$ is the russian peasant algorithm. However, it does not run in constant time and therefore is not safe against timing attack.

Does there exist optimization techniques to implement $2 \cdot a$ for $a \in GF(2^n)$  in a regular way ?

If we consider $GF(2^4)$ defined by the polynomial $X^4 + X + 1$ (represented by 0x13 in hexadecimal), the most efficient solution I found is to compute $2 \cdot a$ as described below (in C code)

 (a<<1) ^ (0x20 - ((a & 0x8) >> 3)) & 0x13

Can we do better in terms of efficiency without precomputations?


texts: Why can't Diffie-Hellman be used for signing?

texts: I understand that signing is often a case of hashing data and then encrypting the hash with the private key. What properties keep Diffie-Hellman from being useful for this?


texts: Could affine transformation mod 2^128 be a side-channel attack problem

texts:
DFC cipher uses affine transformations mod $2^{64}+13$. Soon after DFC's publication, Ian Harvey raised the concern that reduction modulo a 65-bit number was beyond the native capabilities of most platforms, and that careful implementation would be required to protect against side-channel attacks, especially timing attacks.
Consider a cipher which is using affine transformations mod $2^{128}$. Is it still (it was 20 years ago) a problem to implement it securely? Will affine transformations mod $2^{64}$ make a big difference?


texts: Is the identity function a one-way function?

texts:
The definition of the one way function says:

it must be verifiable in polynomial time
probability of inverting it less or equal to negligible

Now, I am not sure I fully understand one way functions.

Can I say that $f(x) = x$ is a one way function?
Do we assume that we know how $f$ is defined?
if $x$ is of length $l$, then the probability of guessing it is: $(1/2)^l$ which is negligible.

I am pretty sure that my reasoning is wrong, any hint?


texts: What is the difference between ECDSA and EdDSA?

texts: As I understand it, both work with elliptic curves, but there seems to be a difference as EdDSA is generally recommended over ECDSA.


texts: Is the term "Elliptic Curve Discrete Logarithm Problem" a misnomer?

texts: I have just started studying Elliptic Curve Cryptography, and I have this doubt. In ECC the group operation is addition (and not multiplication). So, why is ECDLP stated as a variation of the discrete log problem? Wouldn't "discrete multiplier problem" or "discrete factor problem" be more apt?


texts: Is it possible to identify a Serpent encryption key in memory?

texts:
It has been shown that AES keys that are in use can be identified in memory. This identification relies on discovering expected round keys in memory that are contained within the key schedule.

My question is: can we, by extension, assume that the same technique, at least theoretically, can be used to extract Serpent and Twofish keys from memory since they both have a key schedule as well??

(See also Extracting RC4 and 3DES keys from system memory.)


texts: Advantages to knowing $p$ and $q$ in Blum Blum Shub?

texts:
Do you gain any advantage by knowing the factorization of $M$ (over just knowing $M$ itself) in the Blum Blum Shub generator?

The only advantage I see is being able to calculate the $i$-th number directly, as opposed to iterating to it.  This doesn't seem like a very large gain to me.


texts: SHA3 hexadecimal paddig odd length string

texts:
Section B2 of FIPS-202 specification describes the Hexadecimal Form of Padding Bits which is basically the translation of the bit padding 0110*1. However at the beginning they suppose that the message is "byte-aligned, i.e., len(M) = 8m", so what should I do if it is not (ex when the length is odd)?
In section B1 they also suppose the hexadecimal string to be 2m long, but what if it's odd?
If we have "abcd" we pad with ||060*80 so that the first line of the Keccak's state is
$[00\ ..\ 00\ 06\ cd\ ab]$ and that's ok.
However if we have "abc" and we do the same we end up with abc||060*80 that gives a state whose first line is $[00\ ..\ 00\ 06\ c0\ ab]$ which is not the right pad.
I also tried to add just 60*80 and then swap the 6 with the last element of the original string so
\begin{equation*}
  ab\,c  \rightarrow ab\,c6\,0*80 \rightarrow ab\,6c\,0*80 \rightarrow [00 \ ..\ 00\ 00\ 6c\ ab]
\end{equation*}
but this also gives wrong hash compared to SHA3 calculator online. So what is the right way to do it?


texts: How can I take advantage of repeated patterns in non random RSA prime factors?

texts:
I am researching vulnerable RSA moduli which are composed of primes generated with poor entropy. Having a list of these primes I searched for variable sized repeated patterns among them and I noticed the following:

DD93536E58A60B0F56BF95FAEDC7CA42A9C9809A0AAE2FC971C3D9963587ABCEAF2BAB479A68DDC9EFF0E98F0F5FD488A9DD08CC51C01E9A3CFE46CA10BF6AB5
DD93536E58A60B0F56BF95FAEDC7CA42A9C9809A2CF5B9957C2E6FD04E817F03D2E174BB79364A0FC0BF365807A1F9E3286A04EB90FBE9DD52B0A2F12222AB51
DD93536E58A60B0F56BF95FAEDC7CA42A9C9809ABB02D6D274A02869AF059E586EED6DC634FCC33C455504DD40FC43D23544AC4E8F2C5E5C64E3E7530C7EDB07
DD93536E58A60B0F56BF95FAEDC7CA42A9C9809ACEF6287DF02847947530B8CA9A125ACCB53EC922D6E9775A3B0169894ED5A46B281C17AF4583874B715B07BB

Four distinct primes have in common their first 160 bits. Apart from being obvious that these primes have been generated by a weak random number generator how can they be used to derive some other primes generated from the same RNG that are potential factors of other moduli?


texts: what is the state of the art algorithm to encrypt credit card data

texts:
We have a business requirement to keep credit card data. What is today's (Nov 2013) state of the art algorithm to encrypt credit card data that will be saved on disk? Additionally, I'd appreciate pointers to Java libraries that implement these algorithms

Note that we are PCI compliant and we already store credit card data. I am doing a review to make sure that our encryption method remains state-of-the-art


texts:
Ars technica posted an article about the latest in cyber warfare from the stuxnet crew.

They key stretched MD5 by iterating it 10,000 times.  It seems to be effective at handicapping HashCat's gpu acceleration.  Had I been them I would have used bcrypt instead.

Why/When would someone prefer streched-md5 over bcrypt?
How is bcrypt superior to a strectched-MD5?

If you've got the math power $MD5(password)^n = bcrypt(password)$ solve for $N$.


texts:
I'm really in trouble! I'm trying to understand how the T-tables in AES encryption work. But I don't know if I get the point.
What I understood is that they are used to reduce the whole computation of the iteration of AES just looking at the T-boxes and the XOR operation.
Now, what I got is that:

    State                 M Matrix
┏             ┓       ┏             ┓
┃ d4 e0 b8 1e ┃       ┃ 02 03 01 01 ┃
┃ bf b4 41 27 ┃       ┃ 01 02 03 01 ┃
┃ 5d 52 11 98 ┃       ┃ 01 01 02 03 ┃
┃ 30 ae f1 e5 ┃       ┃ 03 01 01 02 ┃
┗             ┛       ┗             ┛

I have my State matrix and M matrix composed by 4X4 bytes. Each t-table should receive in input one byte and give in output 4 bytes.
Now, in order to create the t-tables i will have in the first table:

T0=(d4*02)+(d4*01)+(d4*01)+(d4*03)
   (e0*02)+(e0*01)+(e0*01)+(e0*03)
   (b8*02)+(b8*01)+(b8*01)+(b8*03)
   (1e*02)+(1e*01)+(1e*01)+(1e*03)

Then the second table should be:

T0=(bf*03)+(bf*02)+(bf*01)+(bf*01)
   (b4*03)+(b4*02)+(b4*01)+(b4*01)
   (41*03)+(41*02)+(41*01)+(41*01)
   (27*03)+(27*02)+(27*01)+(27*01)

And so on...until I'll have 4 tables. Am I right? Now...How can I use these tables?


texts: Ring LWE: How can the secret be chosen from the "uniform distribution"?

texts:
The key generation algorithm for Ring-LWE is as follows. Have a ring $R_p =Z_p[x]/(x^n + 1)$.
Then pick a uniformly random $a$ from $R_p$.
Pick $s$ from an appropriate distribution.
Pick $e$ from the error distribution (typically a constant-size Gaussian).
Compute $b = as + e$. Reveal $(a, b)$ as the public key and $s$ is the secret key.

I've been reading The Homomorphic Encryption Standard. It says that $s$ can be picked as a uniform random element from $R_p$. How is this possible? For instance if the (admittedly insecure) choice $n=1$ was picked, then for any values of $a$, $b$ and $e$ there is some value $s$ which satisfies the equation.
More seriously, the LPR scheme, for instance, assumes that $(re - se_1 + e_2)$ is small in order for decryption to be correct. How can it be small if $s$ is chosen uniformly at random from $R_p$?


texts: How does the birthday attack work in AUTH and UF-CMA games?

texts: In the AUTH and UF-CMA games, an adversary is required to forge a ciphertext or message/tag pair to win the game.  Given an encryption scheme $E$ and a PRF $F$, let $\hat{E} = C || F_k(C)$ and $C = E(x)$ (encrypt-then-MAC with PRF as MAC), how is the birthday attack mounted?  I understand it is sufficient to ask ~ $\sqrt{2^n}$ queries to find a collision in a MAC, but it's not clear how we can forge a new ciphertext/tag pair even if we have collision, because if we have found such a collision, we have already asked the oracle the two colliding messages.  I also see how certain block ciphers can be exploited by finding internal collisions, but how is the birthday attack mounted in the general case?


texts: How can one calculate the estimated RSA key life based on Moore's law?

texts: How can someone estimate the number of years needed to factor an RSA key based on the advancement of technology if followed Moore's law?


texts: Is the seed block in Argon2 (H0) 64-bit or 64-byte?

texts:
Is the H0 block in Argon2 64-bits, or 64-bytes? The RFC says bits:

  Establish H0 as the 64-bit value as shown below.

But then it attempts to generate 64-bytes using Blake2

Background

I'm trying to implement Argon2, and the original specs paper, and RFC are not a very friendly to implementors.

I'm stuck on the first step of the Argon2 pseudo-code:

  Establish H0 as the 64-bit value as shown below.

H_0 = H^(64)(LE32(p), LE32(T), LE32(m), LE32(t), LE32(v), LE32(y), LE32(length(P)), P, LE32(length(S)), S, LE32(length(K)), K, LE32(length(X)), X)

There's a lot going on in there, but we can clean it up:

  Establish H0 as the 64-bit value as shown below.

  H0 = H^(64)( [stuff to hash] )

It would seem to indicate that the H^(64)(...) is going to return 64-bits (because of the phrase "...as the 64-bit value...".

But now we go hunting what H^ is, which brings us to the preamble of Section 3.2 in the RFC:

  Argon2 uses an internal hash function H^x(). Here H^x() applied to string a is the BLAKE2b [RFC7693](a,|a|,0,x) hash function

Now we know that: H^(x)(a) = Blake2b(a, |a|, 0, x).

That brings us to RFC 7693 - The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC), in order to figure out what the four paramters are (especially the final paramter x):

The following procedure processes the padded data blocks into an
"nn"-byte final hash value.  See Section 2 for a description of
various variables and constants used.

   FUNCTION BLAKE2( d[0..dd-1], ll, kk, nn )
   |
   ...snip...
   |
   END FUNCTION.

That's a little hard for implementors to read; we can make it a bit more understandable:

Function Blake2(DataToHash, OriginalMessageLength, KeyLength, DigestLength)
   Inputs:
      DataToHash:            Bytes    //array of bytes to be hashed
      OriginalMessageLength: Integer  //length of message in bytes
      KeyLength:             Integer  //length of secret key in bytes (0..64)
      DigestLength:          Integer  //length of desired digest in bytes (1..64)
   Output:
      Digest:                Bytes    //digest that is DigestLength long

   ...snip...

The final parameter to Blake2 (nn in RFC's parlance) is bytes (not bits):

|             | BLAKE2b          |
|-------------|------------------|
|Bits in word | w = 64           |
|Rounds in F  | r = 12           |
|Block bytes  | bb = 128         |
|Hash bytes   | 1 <= nn <= 64    |
|Key bytes    | 0 <= kk <= 64    |
|Input bytes  | 0 <= ll < 2**128 |

Back to Argon

We're looking at Argon2, which says:

H^x() = BLAKE2b(a,|a|,0,x)

So in our case:

  H0 = H^(64)( [stuff to hash] )
  H0 = Blake2b([stuff to hash], |[stuff to hash]|, 0, 64)

Which means that 64 is a number of bytes (not bits), which means that the very first line of the algorithm description should be:

  Establish H0 as the 64-byte value as shown below.

Where am I going wrong? How big is H0? H1?

Bonus

I assume it's a typo when the RFC says:

  Here H^x() applied to string a is the BLAKE2b(a,|a|,0,x) hash function

and that it should read:

  Here H^(x)(a) applied to string a is the BLAKE2b(a,|a|,0,x) hash function

Because later it uses the second syntax:

  H^(64)( [stuff to hash] )


texts: ABE (attribute based encryption) vs ABS (attribute based signature)

texts: I want to know if there is any shortcoming that ABE cannot achieve and that the ABS complete it. I mean why the ABS is included if the authentication and the authorization are already ensured by the ABE. I really need to know the real utility of the ABS and what it brings in more compared to the ABE.


texts:
I was wondering whether this encryption / decryption flow is very solid / secure. I encrypt the data using AES CBC 256 bit with an static IV.

When the user logs in with his Firebase account (first phase of authentication), he gets the option to enter a security password. After that is done, some encryption values will be retrieved like the prefix, suffix and IV. I create the key as following: prefix + given key + suffix. After that I decrypt a retrieved string, and if I get a certain text back, I know it is the right key and start decrypting it for this session.

So to sum it up:

Log in with Firebase
Get encryption values like prefix, suffix, IV and encrypted string
Let user enter password
Create an key in the format prefix + given password + suffix and apply an static IV
Use the generated key to decrypt a string
If it is successfully decrypted, use the key for this session

Note: I won't use public / private key exchange due to reasons.


texts: Why is a random component needed for ECDH key pair generation in Mbed TLS?

texts:
Please forgive me if this is not the right place, however, I encountered this TLS implementation with a function that generates an ECDH key pair on an elliptic curve:
In addition to the private key and a point on the curve, the function also needs random inputs. Why and for what are the random variables required? Why isn't it just $Q=[d]G$?


texts: Can a ciphertext be decrypted to 2 meaningful messages?

texts:
Suppose I have two messages $M_1$ and $M_2$ and I have two different symmetric keys $k_1,k_2$.

Is it possible to achieve this?

$CipherText(M_1)_{k_1}$ = $CipherText(M_2)_{k_2}$

Edit: Im asking for standard ciphers used in practice, not for theorical ones.


texts: Are quantum preimage attacks on hash-based random oracles serious for lattice signatures?

texts:
For most of the lattice-based signature schemes in the hash-based random oracle model (like BLISS), quantum preimage attacks (e.g., Grover's alg) against the random oracle component of the signature are not considered in security estimates and this seems to be reasonable, because a preimage attack does not necessarily violate the unforgeability of the signature. But recently, some papers like Tesla, Tesla# and this,  take this kind of attack into consideration.

My question: is this attack really serious and should we look attentively at them in security estimates?


texts:
How can $g$ be derived from $c = g^r \bmod p$ ?

$g$ and $r$ are not known, but $c$ and $p$ is. And oracle can provide many $c$ but the $r$ and $p$ is always random.

I think this is somewhat related to Decisional Diffie Hellman but I am not sure where to go from there, as the $p$ is always random.


texts: Winternitz hash based signature signing and verification

texts:
In Winternitz hash based signature

There are two functions
$f: \{0,1\}^n \to \{0,1 \}^n$, a one way function
and $g: \{0,1\}^* \to \{0,1 \}^n$, cryptographic hash function

Key Generation steps

First $w$ is selected, where $w$ is number of bits signed simultaneously.
The $t_1$ and $t_2$ is calculated as $t_1 = \lceil \frac{n}{w}\rceil$ and $t_2 = \lceil \frac{\lfloor log_2t_1\rfloor +1+w}{w}\rceil$, $t = t_1 + t_2$
Signature Key (Private key) is then chosen at random $X = (x_{t-1}, ..,x_0)\in \{0,1 \}^{n, t}$
Verification key (public key) $Y$ is calculated by applying $f$ function $2^{w} - 1$ times on each bit of $x_i$

Signing steps

Compute digest of message $d = g(M)$
Prepend minimum number of zero's to make length of $d$ divisible by $w$

My questions are

How is signature $\sigma$ computed? I am unable to understand from Post Quantum cryptography. Explanation with example would be helpful.

Why there is two functions $f$ and $g$, is there can be only one hashing function. What is the role of function $f$?

https://csrc.nist.gov/csrc/media/events/workshop-on-cryptography-for-emerging-technologies/documents/mcgrew-sigs.pdf

https://www.e-reading.club/bookreader.php/135832/Post_Quantum_Cryptography.pdf


texts:
There is some points that I don't understand yet about ransomwares :

the attacker generally put his bitcoin address in the malware, can this address be used to identify and reach him ?
on the assumption that the malware use symmetric encryption, can we use reverse engineering to retrieve the key ?
on the assumption that the malware use asymmetric encryption, can we use the server which deliver the decryption key after payment to reach the attacker ?
as far as I know practically the files themselves aren't encrypted, but another file is created using the secret key then the original file is deleted, so can we use a file recovery program to recover everything ?


texts:
While learning about RSA, I found this example problem. The answer is supposed to be "a 4-digit number that is a pattern of digits." I have computed it to be 16657 twice.

OK, now to see if you understand the RSA decryption algorithm, suppose you are person A, and you have chosen as your two primes $p = 97$ and $q = 173$, and you have chosen $e = 5$. Thus you told B that $N = 16781$ (which is just $pq$) and you told him that $e = 5$.
He encodes a message (a number) for you and tells you that the encoding is 5347. Can you figure out the original message? Hint--well, not really a hint, but a check of your final answer: it is a four-digit number that is a pattern of digits.

I have failed to decode this to a 4-digit number. What am I doing wrong?
p = 97
q = 173
N = 16781
dp = 16512 = (p-1)(q-1)
e = 5
d = ?
C = 5347
M = ?

I computed d = 6605 since that seems to be the smallest value of d possible for:
ed = 1(mod (p-1)(q-1))
5d = 1(mod 96 * 172)
5d = 1(mod 16512)
# I need a multiplier for 16512 that when added to 1 yields a number that
# ends in a 5 or a 0 so it will evenly divide by e=5
# 1 + 2 times dp will yield a number that ends in a 5
d = 6605

Now I need to compute M = C^d(mod N):
M = C^d(mod 16781)

    5347^6605(mod 16781)

6605 = 4096 + 2048 + 256 + 128 + 64 + 8 + 4 + 1

5347^1   (mod 16781)    = 5347
5347^2   (mod 16781)    = 12366   (not included in final math)
5347^4   (mod 16781)    = 9484
5347^8   (mod 16781)    = 96
5347^64  (mod 16781)    = 389
5347^128 (mod 16781)    = 292
5347^256 (mod 16781)    = 1359
5347^1024(mod 16781)    = 3105
5347^2048(mod 16781)    = 8731
5347^4096(mod 16781)    = 11059

5347^6605(mod 16781)    = 16657

I've also computed the same result in Excel by reproducing the same table above one power at a time for 6605 rows.
Update: It turns out to have been a mistake. The original author corrected the problem, but not before the error was copied across the internet.


texts:
Consider this scenario:

Alice gets a Rubik's Cube and peels off the colors from each piece. She then writes a small message on one of the faces of the cube and fills the remaining pieces with random letters. Then, she scrambles the pieces in a way that was pre-determined between Alice and Bob. And finally, she ships the cube to Bob.

Can this be considered as encryption, and, if so, how secure can this encryption scheme be?


texts: homomorphic encryption function representation

texts:
As it known, Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. In various constructions, the computations are represented as either Boolean or arithmetic circuits and can use garbled circuits.

My problem is that I couldn't find explicit documentation on how to outsource the function for computation.
What are the possible and practical techniques to represent the function to be evaluated if we do not use a circuit.


texts:
What would be a good analogue with which to describe Message Authentication Codes to a person who has little to no understanding of cryptography?

For instance, a vault is a reasonable analogue for symmetric authenticated encryption: anyone with the key can open the vault and inspect, alter, or replace the contents. Without the key, you can't know or manipulate what's inside. Similarly, a royal wax seal is an okay one for digital signatures: anyone can validate that a message originated from the person with that particular stamp with assurances that the message hasn't been altered since the envelope was sealed.

Is there a good physical example of something with similar semantics to MACs?


texts: Differential privacy on multiple queries – what is the behavior?

texts:
Differential privacy framework still continue to be obscure in the following case:

If I make a set of queries, I can join their output to restore the original data. For this issue we have composition theorems that grants that every query consume just a "piece" of my $\epsilon$, so we can continue to answer queries for the total query "session" until I have pieces of my $\epsilon$.

So, my question is: what does "session" means? An attacker can make many sessions?

I think that is not very realistic that an user (that can be an attacker) can access just for a single "session" of queries (if we intend for "session" a "set of query that an user can make") . He could find a system to make "many sessions" (for example with different identities or similar, or working together with other attackers).

So, in these cases, how differential privacy works? Is there something that I misunderstand?


texts: Parallel-resistant proof-of-work scheme without hidden knowledge

texts:
Follow-up to: Parallel-resistant proof-of-work scheme?

Is there a proof-of-work scheme that:

can only be solved serially;
given the solution, can be verified in minimal time;
deterministically constructs the problem from some input, where the difficulty varies randomly dependent upon the input;
can be verified by any third-party.

I've looked into Time-lock puzzles and timed-release crypto (1996) [Rivest & Wagner] and Time-Lock Puzzles in the Random Oracle Model (2011) [Mahmoody, Moran & Vadhan], but I don't believe Rivest (1996) satisfies points 3 and 4, and I don't believe Mahmoody (2011) satisfies point 3.


texts: Information Theoretic Oblivious Transfer?

texts: Do we have information theoretic oblivious transfer protocols that are that can not be broken by a computationally unbounded attacker?


texts: In NIST FIPS 186-4 (page 90), it is said that $c$ is the output of SHA-1 on a seed that was chosen randomly. Then the parameter $b$ of the EC is chosen, according to the formula: $$b^2 \times c \equiv -27 \pmod p$$ Why choose $b$ this way? Why, as an example, couldn't $b = c$?


texts: What's a cryptographic primitive, really?

texts:
The more I encounter the term "cryptographic primitive," the less I feel confident that I truly understand what it means.  Is it just me, or is there no universal definition for the term?  Or does the term have some contextual sensitivity that I'm missing?

Some questions that illustrate my confusion:

Does the term refer to algorithms for which we only have heuristic security arguments?
Does it refer to the building blocks invoked by a mode of operation or protocol, independently of the form of their security arguments?
Does it refer to popular security goals like message authentication code, pseudorandom function, collision resistant hash function, etc., that are commonly used as building blocks in modes and protocols?
In Merkle–Damgård hash functions like SHA-2, which is the primitive:

The hash function as a whole?
The compression function?
One but not the other, varying with the context in which we're talking about SHA-2?  (E.g., analyzing the security of SHA-2 vs. analyzing the security of a protocol that uses it.)

Since there are security proofs for HMAC that appeal to properties of the compression function of a Merkle–Damgård hash, which is the "primitive" in this case, the hash function or the compression function?
In SHA-3, which of these are "primitives" or not?

SHA3-256
Keccak sponge functions
Keccak permutations


texts: Static ciphertext length for any plaintext length less or equal than x?

texts:
I am encrypting buffers using AES-256-CTR encryption. My encryption is working but I have a requirement that I want to make sure I implement correctly. The requirement is as follows:

Given any plaintext of length less that x, the ciphertext should always be of length x.

In my example

x is 1 KB but can be anything while consistent.
The plaintext could range between 1 byte to 1 KB, never larger.
The length of the plaintext is not know by decryptor.


texts: Zero knowledge proof for a discrete logarithm

texts:
Say a have a group $G$ chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm for discrete logarithm is as follows:

Pick $g$ as a random element from $Z_N^*$
Pick $x$ as a random element from $(0, N')$ where ${N' =  p' q'}$ where ${p=2p' + 1}$ and ${q=2q' + 1}$
Evaluate ${y = g^x \: mod \: N}$

For public $y$ and $g$, what is the easiest way to construct ZKP that the prover knows $x$ without revealing it?


texts: Why is an Encrypt-and-MAC scheme with deterministic MAC not IND-CPA secure?

texts:
I'm preparing myself to exam, but I have a lot of troubles with rigorous proofs. It's the task from two-years ago exam. At the bottom I reminded one definition.

  Let $(Gen_E,Enc,Dec)$ be an IND-CPA-secure encryption scheme.

  Let $(Gen_M,Mac,Vrfy)$ be a secure MAC.

  Define an encryption scheme as follows:

  $Gen'$ upon input $1^n$, generates $k_1 \leftarrow Gen_E(1^n), k_2 \leftarrow Gen_M(1^n)$,
  $Enc'$ upon input key $(k_1,k_2)$ and message $m \in \lbrace 0,1 \rbrace^*$, computes $c=Enc_{k_1}(m)$ and $t=Mac_{k_2}(m)$ and outputs $(c,t)$.
  $Dec'$ upon input key $(k_1,k_2)$ and ciphertext $(c,t)$, outputs $Dec_{k_1}(c)$ if $Vrfy_{k_2}\left( Dec_{k_1}(c),t \right)=1$ and outputs $\perp \not\in \mathcal{M}_n$ otherwise.

  Prove that this construction is not even IND-CPA-secure when the Mac algorithm is deterministic.

Reminder (IND-CPA-secure).

  An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$ is IND-CPA-secure if for any PPT adversary $\mathcal{A}$ it holds that $Pr[PrivK^{cpa}_{\mathcal{A}}(n)=1]-1/2$ is negligible function, where $PrivK^{cpa}_{\mathcal{A}}(n)$ denotes the output of the following experiment:

  (a) Let $k \leftarrow Gen(1^n)$

  (b) The adversary $\mathcal{A}$ is given input $1^n$ and oracle access to $Enc_k(\cdot)$. It outputs a pair of messages $m_0, m_1 \in \mathcal{M}_n$ of the same length.

  (c) Let $b \in \lbrace 0,1 \rbrace$ be chosen uniformly at random. Then a ciphertext $c \leftarrow Enc_k(m_b)$ is computed and given to $\mathcal{A}$.

  (d) $\mathcal{A}$ is given the challenge ciphertext $c$ and oracle access to $Enc_k(\cdot)$. It outputs a bit $b'$.

  (e) The output of the experiment is $1$ if $b'=b$, and $0$ otherwise.

If you could help me with the rigorous proof, I'd be really grateful for your time.


texts: Is there a malleable pubkey digital signature scheme?

texts:
I'm trying to find a special kind of Digital Signature Scheme.

The scheme should allow me to transform a signature $s=\text{sign}(sk,m)$ (for a private key $sk$ and a message $m$) into a signature $s'=\text{sign}(x,m)$ (for another private key $x$ related to $sk$) such as given $s'$ nobody can state with high probability that $s'$ was obtained by first signing with $sk$ and then transforming. Also one part of the signature must stay unchanged in the transformation.

More formally, the desired property is this:

For every private key $sk$, every other private key $x$, every message $m$, and every signature $s = (s_1,s_2) = \text{sign}(sk,m)$ there is a value $k$ and a value $s_2'$ such that $x = \text{g}(sk,k)$ and $s'= (s_1, s_2') = \text{sign}(x,m)$.
$s_1$ is a random/pseudo-random value whose size should be at least $128$ bits. This should be part of the signature (if this value is changed, the signature should fails to verify)
s2 is a part of the signature that changes after being transformed.

$\text{g}(sk,k)$ is an easy to compute injective function that takes a private key $sk$ and outputs another private key (e.g. $\text{g}(sk,k) = k*sk$ or $\text{g}(sk,k) = (sk^k) \mod p$, etc..)

Of course $\text{g}()$ does not allow you to choose the output key of $\text{g}()$ such that it matches a certain public key, because that would imply being able to create a forgery.

Even having obtained $sk$ (but not $s$, nor $k$), it should be infeasible for an attacker to detect if $s'$ was build by transforming $s$ into $s'$ or it was created using the private key $x$ directly.


texts: What is the difference between, and security of $Z_p$ and $F_p$?

texts:
While reading some papers, I found that sometimes $Z_p$ was used but sometimes $F_p$ was used ($p$ is prime). Usually, the author will only use their subgroups like this: choose a big prime factor of $p-1$ , denote $q$, and set $G=\langle g \rangle$.

My questions are :

Why do we only use the subgroup while $Z_p$ OR $F_p$? Or maybe we can choose a $p$ such that $p-1$ is prime and now if $Z_p^*$ or $F_p^*$ can be directly used?
What's the difference of using $Z_p$ and  $F_p$?


texts: Camellia has 4 SBOX and so does the TwoFish(key dependent 4 Sboxes). Where as AES uses only one. Would it have made AES more secure if AES had 4 or more SBOX too? Does using more Sbox with similar Properties (Non Linearity, Differential Probability, Linear Probability, Strict Avalanche Criteria etc) increase the security as compared using just one for all possible byte positions? What security impact it will gain if 16 Different SBOX are used?


texts: Does the One Time Pad rely on confusion or diffusion?

texts:
From what I could research, XORing a random key adds confusion.

But I do not undertand the rationale for that classification. Shannon's confusion is supposed to obscure the relationship between the ciphertext and key, but the OTP clearly does not do this: unlike many other ciphers, if one has one plaintext and corresponding ciphertext, then there is a trivial relationship between the latter and the key...

Furthermore, what seems to me that OTP actually does is to rely (only) on diffusion: it makes the redundancy of the plaintext harder to notice, but it does not "get rid" (lacking a better expression) of it. In fact, if one obtains two cryptograms enciphered with the same key, one can then obtain the XOR of the corresponding plaintext messages, which must contain some patterns related to the structure of the original messages. (*)

In sum, I'd say the OTP is based on diffusion, and is secure only because of the sui generis requirement that the key be used exactly once. Where am I going wrong?

(*) - Otherwise one could not use the two time pad to recover the original plaintexts.


texts: Are group signatures already in practice?

texts: Even group signautres have been discussed using in practice I could not see any real life application. Ring signatures are already in use for e-voting. I want to know whether group signatures are implemented for use in practice? In which applications?


texts:
I'm self-studying Katz' book (2nd ed), and I have a small question about Theorem 3.32, which says:

  If $F$ is a pseudorandom permutation, then $CTR$ mode is $CPA-$secure.

They present a proof there, but I think that another proof is viable, which is basically a corollary of a theorem they presented earlier.

My proof is the following. Consider Theorem 3.31, which says

  If $F$ is a pseudorandom function, then $m\mapsto \langle r, F_k(r)\oplus m \rangle$ ($k$ is the key, $r$ is uniformly chosen) is a $CPA-$secure encryption scheme.

So, why don't we simply prove that $G_k(\cdot)$ defined as
$$G_k({\tt ctr}) = \langle F_k({\tt ctr}+1), F_k({\tt ctr}+2),\ldots,F_k({\tt ctr}+\ell)\rangle $$
is pseudorandom? we would have by the cited theorem that $CTR$ mode (which is the encryption scheme described in the theorem using $G_k$) would be $CPA-$secure.
Of course, showing that $G_k$ is pseudorandom if $F_k$ is does not impose a problem, since any distinguisher to $G_k$ can be turned into a distinguisher to $F_k$.

Everything makes sense, I don't see why this proof would not work and why did they bother writing a 2 pages long proof for what could be a corollary! (the only thing I think could fail is that the theorem used was proven for length-preserving $F_k$, but -I think- the proof also applies to the general case).

Anyone can point me to a mistake in my argument? btw, this could also prove that $OFB$ mode is $CPA-$secure.

Thanks in advance


texts: Convergent encryption has dictionary attack, but why hash function doesn't?

texts:
Convergent encryption (CE), $E_k(d)$, is a way to encrypt the data $d$, with the characteristic that the encryption key $k$ is $k=h(d)$, where $h(\cdot)$ is a cryptographic hash function.

Consider a cloud storage with client-side deduplication. The common procedures of uploading a file $d$ are to calculate and the send $h(d)$ to cloud. Cloud checks whether it has seen $h(d)$ before. If so, the user doesn't need to upload again. Otherwise, the user uploads $d$ explicitly.

In the above scenario, we don't consider data confidentiality. Honest-but-curious cloud may know the file content. Thus, the user encrypts file before uploading it. However, different users might choose different keys independently, resulting in different ciphertexts even in the case of the same $d$. Hence, CE is used here; instead of uploading $d$ explicitly, the user uploads $E_k(d)$. One may see that different users with the same $d$ must have the same ciphertext, which is deduplicatable.

Recently, researchers found that CE is vulnerable to dictionary attack. In particular, if $d$ is predictable (or say low-entropy), CE is not secure enough. In other words, if the adversary already knows $d\in X=\{x_1, x_2, \dots, x_t\}$ and $X$, then it may calculate CE of each element in $X$ to infer which one is $d$.

A system was recently proposed to fix this problem. http://eprint.iacr.org/2013/429.pdf

Here comes my question eventually:
I agree CE is vulnerable to dictionary attack and the above system is able to fix the problem. However, I am wondering whether the client-side deduplication per se is vulnerable to dictionary attack in the case of predictable file because user needs to send $h(d)$ to cloud.
Because practical hash function (eg., SHA256 in DropBox) is deterministic, the adversary eavesdropping on $h(d)$ can still adopt the hash-and-then-try-to-match strategy (i.e., dictionary attack), with the attempt to recover $d$.

Is my understanding correct?


texts: Oblivious transfer applications: how to apply?

texts:
I have a basic question about the Homomorphic Encryption schemes, garbled circuits, Oblivious Transfer (OT), two-party computation, and multi-party computation. Specifically, I want to understand, how to apply these great techniques, or are these at the theoretical stage?

More specifically, are the OT schemes applied in real-world applications?

Can somebody point me to some good papers in which OT is applied to implement the application? This will help me understand how it can be applied?


texts: Does observing amount of changes in encrypted disk ciphertext have a well-known attack name?

texts:
Let us assume that I have two partitions on my hard disk, and unencrypted one and an encrypted one. Let us also assume that I shut down the computer when sleeping or away, and an attacker has physical access to my computer. In fact, the attacker takes a copy of the disk image every day without me knowing it. Obviously, the attacker does not know the passphrase of the encrypted disk partition, so the attacker can only observe changes in ciphertext (let's assume now that the attacker doesn't know that keyloggers exist or doesn't want to take the risk of me noticing it).

Now, there's a particular 100 MB file that is a copyright and trade secret violation. I don't want to delete it, but I'm becoming slightly suspicious that my computer is used without my permission, so I store it into the encrypted partition, deleting it from the unencrypted partition.

Now, the attacker will observe that 100 MB of the ciphertext of the encrypted partition differs from the old ciphertext. In fact, from the daily disk images, the attacker sees that the amount of changes in the encrypted disk is usually zero, and this was practically the only exception for that. The attacker will also observe that the 100 MB file was deleted from the unencrypted partition. Thus, the attacker concludes that I still have the file.

My question is: does this kind of attack against full disk encryption have a name? Do any full disk encryption schemes offer resistance against this kind of attack, e.g. by randomly rewriting blocks with a new per-block key even if no plaintext block actually changed?


texts: Fast Extended Euclidean Algorithm in Harley's elliptic curves point counting method

texts:
Could you help me with Harley's norm computation algorithm that is based on the Fast Extended Euclidean Algorithm that was suggested by Harley in an email to NMBRTHRY list in 2002 and that described in Vercauteren's thesis pp 87-90:
https://pdfs.semanticscholar.org/c945/c98267db064b272c87a885fc5eeb764b0b2d.pdf

My implementation working correctly and fast for low degree polynomials without modulo and for high degree polynomials with modulo M, where M is a prime number greater than 2^N.
But all I need - it's a resultant modulo 2^N (or 2^(Nc) due to Vercauteren's Remark 3.10.3) of two large polynomials. So I should include in routine mod 2^N (or mod 2^(Nc)...) instructions to avoid exponential coefficients' growing.
But since the 2^N is not prime it's a problem - polynomials contain even coefficients and this leads to some even denominators - and for example multiplicative inverse 1/2 mod 2^N doesn't exist.
Please tell me how to solve this problem?
How to adapt XCGD routine for correct mod 2^N calculation of resultant (norm)?
Thank you.
Best regards,
Vadim


texts: Comparing plaintext to contents of ciphertext

texts:
Given an authenticated mode of encryption, when comparing a plaintext string against the contents of a ciphertext, which approach is typically considered safer?

Encrypt the plaintext and compare against the ciphertext, or
Decrypt the ciphertext and compare against the plaintext in $O(n)$

The former appears better to me since the contents of the ciphertext are never decrypted and loaded into memory. However, given that it's an authenticated mode of encryption, this bypasses the authentication checks that would normally occur during decryption.

So, which is hypothetically worse? Potentially allowing Eve to load decrypted ciphertexts into memory, or potentially allowing Eve to force my system into comparing plaintexts (either under Eve's control or unknown to her) to forged ciphertexts?


texts:
I am searching for a citation of a formula that calculates the proportion of true (1) outcomes in the corresponding truth table of a boolean function. Searching a little bit in the Cryptography literature, I found that the hamming weight of a boolean function is defined as the number of $1$'s, so it is close to the metric I am referring to. I have also seen this metric/property mentioned as 'truth density' in Wolfram, see an example.
Has anybody used this formula in a paper before ~2000-2010s? (a recent paper that defines it as bias is this one). Or maybe provide a proper (older) publication to cite for the hamming weight?


texts: weaknesses in ElGamal with public key of small order

texts:
Suppose $p=29$, $\alpha = 2 \in F_p^*$ is a generator of $F_p^*$. Bob picks $d \in \{2,...,27\}$ such that $\beta = \alpha ^d=28 \pmod{29}$. He then sends his $(p,\alpha ,\beta)$ to Alice who herself picks one $i_j \in \{2,...,27\}$ for eleven different plaintext values $m_j$, $0\leq j\leq 10$ and encrypts these by $c_j=m_j*28^{i_j} \pmod{29}$.
Since $|28|=2$, the only possibilities for the masking key $k_M = 28^{i_j} \pmod{29}$ are $1$ and $28$.

Alice sends the following ciphertext-key pairs in the form $({k_E}_j, c_j)$:
$$(3,15),(19,14),(6,15),(1,24),(22,13),(4,7),(13,24),(3,21),(18,12),(26,5),(7,12)$$
where $a=0, ..., z=25, ä=26, ö=27, ü=28$. We thus have the ciphertext
$$p,o,p,y,n,r,y,v,m,f,m$$
The task is to decrypt the message without computing Bob's private key, by "looking at the ciphertext and using the fact that there are only very few masking keys and a bit of guesswork". Since the only possibilities for $k_M$ are $1$ and $28$, the plaintext corresponding to $c_j$ is either $c_j$ itself or $c_j*28^{-1} \pmod{29}$. This yields two possibilities per $c_j$:
$$p,o,p,y,n,r,y,v,m,f,m$$
$$o,p,o,f,q,m,f,i,r,y,r$$
I could not make sense out of the two, so I computed Bob's private key anyways to check the result. It turns out Bob's private key is $14$ ($2^{14}=28 \pmod{29}$). Computing ${k_M}_j = {k_E}_j^{14}$, the result turned out to be
$$o,p,p,y,n,r,y,i,r,y,m$$which still does not make any sense to me.

So my question is: did I mix something up along the way? If not, where is the "guessing" supposed to happen? Also I have not used the fact that $\alpha = 2$.

EDIT

I seem to have been unclear before. I am asking this because this belongs to an exercise (decrypting the given ciphertext without calculating Bob's private key), and I believe I missed something. The actual result, calculated by using that not allowed key, seems random. So I don't know how guessing should be of any use, or how to decide which is the correct sequence without using the private key.

EDIT2

As suggested in the comments I'll quote the complete exercise here:

We investigate the weaknesses that arise in Elgamal encryption if a public key of small order is used. We look at the following example. Assume Bob uses the group $\mathbb{Z}_{29}^*$ with the primitive element $\alpha = 2$. His public key is $\beta = 28$.

i) What is the order of the public key?

ii) Which masking keys $k_M$ are possible?

iii) Alice encrypts a text message. Every character is encoded according to the simple rule $a=0,...,z=25$. There are three additional ciphertext symbols: $ä=26, ö=27, ü=28$. She transmits the following 11 ciphertexts $(k_E,y):$
(see the 11 pairs above)

Decrypt the message without computing Bob's private key. Just look at the ciphertext and use the fact that there are only very few masking keys and a bit of guesswork.

Thank you


texts: Problem on Elliptic Curve Point Doubling

texts:
Given an elliptical curve e.g. from “Understanding Cryptography” by Parr & Pelzl §9.2 Example 9.5:

$y^2 = x^3 + 2x + 2~~~~ mod~17$

And given a primitive $P = (5, 1)$, the book indicates:

  We compute now all the "powers" of P.

They then provide a table:

$2P = (5, 1) + (5, 1) = (6, 3)$

$3P = 2P + P = (10, 6)$

$...$

$18P = (5, 16)$

Unfortunately it is not apparent to me what action they are performing with the addition ($+$), or what they mean by "powers".  What operation is being performed to go from $(5, 1) + (5, 1)$ to $(6, 3)$, and so on?

The obvious operation (i.e. what Wolfram alpha does) of $(5, 1) + (5, 1) = (5 + 5, 1 + 1)$ yields $(10, 2)$.  There are a plethora of other possible combinations of operations that one could try, but I'd just be guessing.

Generally, given the secret, ordinarily labeled $d$, how ought one calculate $dP = P + P~ +~ ... ~+~ P$?

(This presumably computes the public key $X$ & $Y$ points, from $d$ and the $Gx$ and $Gy$ parameters)

While it is a rather core operation, and likely quite basic, I have found no illustrative examples and at-best convoluted implementations.  I'll keep looking, but I thought that a good answer might be a useful for the next person searching.

Edit

This exact example also appears and is discussed at: https://math.stackexchange.com/questions/430836


texts:
THEIR DIFFERENCE WILL REMAIN, LONG AFTER THEY ARE DEAD
Dear Friend,
IV IV 12 8 14 - 19 14 18 9 13 IV I C C 9 17 IV 17 12 IV 8 14 IV 7 F 14 IV 7 19 D IV 12 15 F 19 E IV 8 17 IV 7 12 15 F 19 13 17 9 E IV 8 17 IV 12 IV 17 15 F 19 IV 7 IV 8 14 IV II 9 17 14 D 9
Only one of them will take you to the finish line and unlock the treasure.
Add to the other one and he will show something important. Remember him, he holds the key.
erugbzqanet lz sb lebzrz av

Can someone help decyphering the above? I thought Ceaser first, but I am lost.


texts: Unable to reproduce correct signature data

texts:
"Skatteetaten" is the Norwegian tax authority.

We're currently trying to implement signing of messages for digital cash registry systems and i'm not able to reproduce the desired signed data.

Went back and forth with different types of padding and hashing algorithms, still unable to reproduce the desired return data.

I'm using their validation tool hosted here on github. Trying to get a private key using RSA 1024 to work (Form in Validator.html).

Example private key:

-----BEGIN RSA PRIVATE KEY-----
MIICXwIBAAKBgQDag84L+pT6OlFZ8kav08ixPdugo6bsqOICJrl8TzGY87Iek9K1
dgbz2sr7r0OBl2/ndz0CoxiyKoiLc5YY6wy5Qg1qNRCc4C71r2A7N+vjhfkSSoS7
RQekuhKSMJ1Wp8RfXB/AccWPdqb0Mm1TjklSizptJAANppC12fijFVTocQIDAQAB
AoGBAMSsIQXzEaduWc4lG64hZd7xF/4rjZAwKMta41OZS8CohkazMdEVXAibglqp
Uo8PKC8iyQzYkt+5HJC3Bf+DfzyMMty5NPJVpNK1fr0ftz1TfAK7A0I5PWOq9DPL
pjNmz8DIGCfoMOsg1plfh2oprqK36shpWzG1jzXizui4u+aBAkEA/A6M8fM01L5r
xeGtppKEY8EtaSImnBc09kONP1vPqexNUA8cORqZn3J1GKhv90zk79IWdTrzPN4C
ZTHGpGR/eQJBAN3u7HyT/HqvvIhZksqKS+DTbjYaKGr3KxiAEAKU0PeQOBD5TQds
JVstZ2vGSbAsCU6VNEh8eQfTpxzy59S2mrkCQQCM8P3zFNGH3GqbHdRh/i+1MAHa
ddQtF/Tvd1p2ATqfg5i/mZNogu0/8Vp0zUq+d+rUBx+zsaDteh7QwwKWTfPRAkEA
x01W5pFnPS4wWypFnsoPVjnJUaCwB08sTnZC6m6GMqw7DVM0j6PY8EaYB7ssVZ9W
RFHNgAL4FcVG38Jr2ySZUQJBAOPa7ScbGi7XTiV3TStW2rhmd9CyKnOeSdjIejGm
R4xrannBqg+ikWXuW0cnuGk2a2a/ymHXq1pSCTFAa2VeryA=
-----END RSA PRIVATE KEY-----

Example public key:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDag84L+pT6OlFZ8kav08ixPdug
o6bsqOICJrl8TzGY87Iek9K1dgbz2sr7r0OBl2/ndz0CoxiyKoiLc5YY6wy5Qg1q
NRCc4C71r2A7N+vjhfkSSoS7RQekuhKSMJ1Wp8RfXB/AccWPdqb0Mm1TjklSizpt
JAANppC12fijFVTocQIDAQAB
-----END PUBLIC KEY-----

When using these keys with the signing data:

0;2014-01-24;23:59:59;123456789;1250.00;1000.00

Performing signing with sha1WithRSAEncryption i get the signed data:

gs1HumV5FxfeUum3Ws9s7ZsczPEtXUq+5/5MgYcbUb3hP9CJ2eg9d6Bm+d+D8HtbfLB3fCV8pfXo1JaluJ0JGtwLzyyC2uLDR+qvxRbCbly4W0/Ab8jPuF2KJHEPT9HLtbfwMEclMdyK+xp+OPwOvCCnREV43KMwisMGaB4TziA=

Which is base64 of the signature.

I've tried various PHP-crypto libraries and the openssl commandline tool to reproduce this signature and i can't just get the desired output.

If their validation library is not broken i must be missing something and all the possible combinations i've tried has not yielded the correct result...

Help would be appreciated to say the least.


texts: Storing Parameters In Argon2 Hash As Potential Security Issue?

texts:
I'm really trying to make sure that I follow best practices when it comes to password storage, and after some looking around for a good algorithm, I found that Argon2 was the "next big thing". I've been testing it out within VB.Net using the NuGet package provided by Liphsoft (Liphsoft.Crypto.Argon2).

By default, it looks like the parameters for the hash algorithm are stored in the hash itself. I understand (or at least I think I do) that this is suppose to make it easier to migrate it to a new hash if you ever decide to change the parameters.

My question is, does it make it less secure by supplying the hash algorithm's parameters in the hash itself? I'm currently thinking of just trimming out the information and just hiding the parameter values within code so that if someone gets a hold of the hash, they can't immediately see that "Oh, they're using Argon2 with these specific parameters." Should I even be concerned about that?

Any feedback is greatly appreciated. Thank you!

I also looked at this question before posting: Argon2 output length and parameter storage?


texts: Why the output of elliptic curve based cryptosystems is smaller than the ordinary public key cryptosystems?

texts:
I am trying to understand how much the output of elliptic curve based cryptosystems (for example elliptic curve ElGamal) is smaller than the ordinary public key cryptosystems.

I know that the security of a EC key size from a moduli of 160 bits is about the security of an RSA cryptosystem with a 1024 bits moduli. But my problem is that we usually have long messages, so we have to partition it into several blocks and then encrypt it. Therefore, when we have a 2048 bits long messages we make around 12 blocks and then encrypt them. Since the output is in the form of pairs, the out put will have a length of 2*13*150= 3900 bits.
Now we consider this example with RSA. in order to use RSA for such a message, since its moduli can accept up to 1024 bits messages, we need only 2 blocks as the input(each one 1024 bits long). RSA output is not in the form of pairs, so the final output will have 2048 bits long.

In conclusion: The output of RSA has the same length as input, while the output of EC base cryptosystems length is as twice as the input.

What's the problem? How EC is said to be smaller?

Based on what I wrote, I think it is smaller only for messages that their whole length is smaller than the moduli!

(Please see Table 5 of this as an example of EC's smaller outputs)


texts: Given non-interactive zero-knowledge proofs as a primitive, wouldn't signatures be easily implemented with hashes?

texts:
Assume a working non-interactive zero-knowledge proof implementation. Would a public key signature scheme implemented as this work:

Bob picks a random a, his private key, and broadcasts A = H(a), his public key.
Bob broadcasts sig : ∃ a . H(a) == A && H(a | 0 | msg) == B), msg, B : {0,1}*.
Alice verifies sig using zk-snarks to convince herself Bob signed msg.

? If so, am I right to think an implementation of non-interactive zero-knowledge proofs with satisfactory characteristics (i.e., no trusted setup, fast and reducible to a known hard problem) would provide an easy replacement for most existing cryptographic techniques?


texts:
I am actually trying to study homomorphic encryption (on lattices) but I'm facing a problem. Every paper that I have read so far talk about writing the function to evaluate on ciphertexts as a circuit, either boolean or arithmetic according to our scheme if I understood this part well. My problem is that I couldn't find explicit documentation on how to turn a function to a circuit.

Especially, in circuits, we can't have loops or conditions and I would have liked to apply my FHE scheme to the weights of a neural network, but I'm kinda stuck on how to represent the activation function (I think I would use the sigmoid, that can be represented with its Taylor expansion) and simple gradient descent.

Does anyone have a clue or a good paper to help me understand how to write such functions to circuits?


texts: Understanding how SHA-512 achieves its design goals

texts:
The Wikipedia entry on SHA-2 contains a usable pseudocode recipe. In the hope of some deeper understanding, I implemented SHA-256 and SHA-512 from it. This was helpful, but I still don't think I have joined together my understanding of how the hashing works, and how it achieves its goals.

In short, I can see some non-linear bit-twiddling and likely chaotic behaviour from the components that SHA-2 strings together, but I'm missing how the whole algorithm results in provably achieving the avalanche effect or anything similar.

In discussions here, posters tend to treat the hash output as essentially a random map from any set of input messages whether they have any correlations or not (e.g. they could be random messages to hash, or they could be from a simple series such as integers from 1 to 1000). I'd like to know whether and how this property of SHA-2 is proven or verified.

Here is my understanding so far:

The initial hash data and round constants, derived from square roots and cube roots of prime numbers, are not relevant. The numbers are chosen this way to demonstrate lack of bias (or hidden backdoors) by the designer. You could equally use the binary expansion of $\pi$ sequentially in each constant.
The main design purpose I see for the hash and round constants is that they will push the non-linear repeated rotations into a more chaotic mode when they are added in; and in combination they basically ensure there is no single input word value that has simple short loops when repeatedly calculating e.g. Sum $s0 = (a \ggg 28) \oplus (a \ggg 34) \oplus (a \ggg 39).$ in each round.
The sums in the round and used to initialise the workspace seem have the effect of "spreading" message bit values throughout each word (either in the workspace, or one of the hash sub-components), and as far as I can see the specific values of amount of rotation (28, 34, 39 in the example) are not highly important, other than each value is different between sums/sigmas and they do not form short loops modulo either each other or with the word size.
I can see that some important pieces of feedback in addition in the rounds (e.g. to create temp1 the value of h is used - if it were not used somehow for either temp1 or temp2, its value would become irrelevant). But in general I have no clue why the results from the sums are combined in the specific way given. For instance, why is e negated as part of creating ch?

I do not expect to go from this level of understanding to full comprehension in one step. I'm also not 100% sure about any of the above. In general, I can see how SHA-2 works its magic in a hand-waving way - I might say "it is a complex system built using a few base algorithms with chaotic behaviour interacting". But I am stuck getting to the next level.

How do I find out why the specific recipes for e.g. ch and maj are used (the names chosen in the Wikipedia article imply they have meaning in the design)?

What form does the proof that SHA-2 does what it intends to do take?


texts: Man-in-the-middle attack on text-book RSA PKE

texts:
I am attempting to solve the following problem:

I know the following:
3 messages are being sent between Alice and Bob, all messages are encrypted with the known public key $(d,N)$:

Alice sends Bob: $m_1=E(R_1);$ $R_1$ is a 28-bit number.
Bob sends Alice: $m_2=E(R_2,R_1);$ $R_2$ is a 28-bit number and $R_1$ follows (i.e,
$p_2 = (2^{28} * R_2 + R_1)$ if i am not mistaken)
Alice sends Bob: $m_3=E(R_2,R_1,R_3);$ $R_3$ is a 156-bit number known in advance.

The goal is to alter $R_3$'s value which is about to be sent to Bob to a new value (first 7 bits only).

The best I could come up with is to precompute all possible 28-bit number encryptions which will allow me to know $R_1$'s value when sent by Alice -> then easily figure out $R_2$'s value -> send my desired $R_3$ value to Bob.

Is there a neater (and more feasible) way to do so?


texts: Example of existentially unforgeable and identity of the signer

texts:
I am Reading "Security Arguments for Digital Signatures and Blind Signatures
"

  Providing a new message-signature pair. This is called existential
  forgery. In many cases this attack is not dangerous, because the output message is likely to be meaningless. Nevertheless, a signature scheme which is not existentially unforgeable does  not guarantee by  itself the identity  of the signer. For example, it cannot be used to certify randomly looking elements, such as keys.

I am trying find an example of a signature that is not existentially unforgeable and does not guarantee by itself the identity of the signer. Could you help me please?


texts: I have a question. If you receive a DES encrypted message for which you would NOT recognize the plaintext if it were decrypted, is there any way to potentially determine the key if all keys are likely? What about for AES?


texts: Comparing two values without revealing them

texts:
Suppose Alice wants to prove to Bob that t1 is less than t2. t1 and t2 represent timestamps. Alice does not want to reveal t1 and t2. However, she needs to receive Bob’s confirmation that t1 < t2. In order to prevent Bob from performing a brute-force attack to find t1 and t2, Alice wants to use some salt with the timestamps.

Any idea how to use cryptographic algorithms in order to solve this problem?


texts: Hill cipher: How to find an unknown key of unknown size

texts:
How would you tackle the problem of finding the key (you don't know the length) to a Hill cipher when knowing only one 12-letter word of plaintext and its corresponding ciphertext?

CONVERSATION has been encoded as SQZHUSSUDYKP with standard alphabet (A=0, Z=25). The key, as I said, is unknown with unknown size.

I am not asking for a solution, but for tips and guidance. Any help will be much appreciated.


texts: I am researching in authentication and access control in IoT. Is there any difference between working in wireless sensor nodes and IoT in the topic authentication and access control as both require lightweight designs?


texts: Finding differentials and space complexity

texts:
In Differential Cryptanalysis of DES-like Cryptosystems by Biham and Shamir, they provide examples using differentials inputs such as $\Omega_p = 00\ 80\ 82\ 00\ 60\ 00\ 00\ 00_x$. Most of article is about differential cryptanalysis and presents the generic method, the way to find subkeys. But I can't find a clear explanation about how to find the differentials used in examples.
I do get the idea about feeding an S-box in order to retrieve the differentials, but these S-boxes only have 6-bit inputs for 4-bit outputs (in DES). So the memory space required in order to do such analysis is $2^6 \times 2^4 = 1024$ integers $\approx 4\ Ko$. This can be easily placed in the RAM. The method is presented in Modern Cryptanalysis (2008, Wiley Publishing; Chapter 4, pp. 122-145) by Christopher Swenson.
However, given an S-box with a bigger input such as the one used in FEAL-X (while remaining broken), we need a table of the following given size : $2^{32} \times 2^{32} = 2^{64}$ integers $\approx 2^{32}\times 16\ Go$. Such a thing is too big to store on one of today's computers.
Hence my question: how is it possible to find the right differential for bigger input round functions without the size constraint of this analysis.


texts:
My problem is the following:

I have an organization with many members. When someone from the outside communicates with this organization, I want any member to be able to decrypt the communication.

On solution I found would be to use CP-ABE: the organization has a master key and a public key related to it. The owner(s) of the organization can then issue secret keys for all members with a dummy policy that always evaluates to true. That way, an outsider won't have to know anything about the internal structure of the organization or its members; he will just have to encrypt using the organization's public key and any on its members will automatically be able to decrypt using his secret key.

The thing is that I really don't need all the attribute policy part of the CP-ABE so this seems overkill to me. I was wondering if there were any key derivation schemes that would allow me to do so, but I couldn't find any.

I remind my constraints:

the encryption should be done with a single public key for the whole organization
each member should have a different derived secret key

If there is such a scheme, how can we enforce key revocation ?


texts:
There are a few posts that I've come across that seem to imply that using regular encryption and a MAC might be better than using the newer AEAD (ie: AES/GCM) modes.

https://www.daemonology.net/blog/2009-06-24-encrypt-then-mac.html

https://blog.cryptographyengineering.com/2011/12/matt-green-smackdown-watch-are-aead.html

My questions are thus:

Is an AEAD more likely to fail (being subject to chosen plaintext attacks, versus HMAC protecting the encrypted part more securely), and if so, does it fail in a more catastrophic way?

Assuming that you have securely generated both the HMAC and encryption keys, is Encrypt+HMAC therefore more secure?


texts: Is there a metric (term) for work required to decrypt a public key?

texts:
Any public key decryption can be decrypted given enough time and computing power. Is there a metric or term for this? Something like

it would require on average 2^43 1024 bit hashes to find private key 'I' based on public key 'U'?

Is there a term that would sum up this average amount of work?


texts:
I am in a case where I can not share a mac key, only the encryption key. I need to provide authentication and integrity with the cipher so I would like to send a mac with the cipher. I cannot use AES-GCM for example, I am limited to AES-CBC.

Is it ok to embed mac key in the cipher in this case in term of security?

For example, like this:

encrypt(text, key)
  mac_key = generateRandom256bitsKey()
  cipher = aes_encrypt(mac_key + text, key)
  return hmac(cipher, mac_key) + cipher

decrypt(cipher, hmac_sig, key)
  decrypted = aes_decrypt(cipher, key)
  mac_key = decrypted[0, 255]
  if (hmac(cipher, mac_key) != hmac_sig)
    return null;
  return decrypted[256, decrypted.length - 1]

Thanks,


texts: Can Secure Multi-party Computation be used to reconstruct secret shares?

texts:
When using Shamir's Secret Sharing is it possible to use Secure Multi-Party Computation to reconstruct the original secret without revealing one's secret share?

When searching I have found results talking about using secret sharing as part of a Multi-Party Computation scheme. But that is not my question.


texts: Does there exist a provably correct and recipient hiding encryption scheme?

texts:
I am looking for an encryption scheme $E$ and a commitment scheme $C$ which allow

encrypting the message $m$ for the public key $y$ as $e = E_y(m)$, so that the ciphertext $e$ does not reveal any information about the recipient public key $y$
committing to $y$ and $m$ as $c_y = C(y)$ and $c_m = C(m)$,
to prove that the ciphertext was correctly formed with respect to committments to $y$ and $m$.

That is, given a ciphertext $e$ and commitments to the message and key, $c_m, c_y$, it should be possible to construct a zk-proof that the ciphertext was correctly formed with respect to the commitment openings:
$PK\{ (y,m): c_m = C(m) \land c_y = C(y) \land e = E_y(m)\}$.
Using elgamal encryption there are known methods for proving correct encryption (e.g. section 3.3 of Stadlers PVSS). However these methods rely on revealing the public key of the recipient, which is not acceptable in my case. Is there away around this problem?


texts: Is a new block cipher harder to design than a new hash?

texts:
I realise that   cipher and  hash primitives are somewhat different.  But they share common requirements like attack resistance amongst others. And I realise that attacks /vulnerabilities are different for each.   However in addition to resisting attacks, a cipher has to be reversible given the correct key. And it has to be very not reversible given a slightly incorrect key.  A hash does not,    simply needing something like what the RadioGatún team called a secure mangling function.

Does this mean that a new secure block cipher is more difficult to develop than a new secure hash? Or are they just     too applely and orangey for objective comparision?

PS. I'm aware of Feistel networks and  stream ciphers. I'm referring to the       block primitives themselves like DES  & AES v. SHAx   & Whirlpool and whatever else is in the pipeline.


texts: How would an attacker perform an exhaustive key search on a block cipher using ECB mode?

texts:
Do you always assume from Kerchoff's principle, that the attacker has access to everything but the decryption key?

That is, am I to assume that to perform an exhaustive key search, the attacker has a plaintext block and ciphertext block pair.

So an attacker would systematically try every possible key by decrypting the ciphertext? Then he would be able to identify when he has found the correct key if it matches the plaintext?

If he only has the ciphertext is an exhaustive key search still possible?

Should I be looking at what information a block cipher running in ECB mode provides?

Please help!


texts: Using similar passwords and salts for PBKDF2

texts:
I'm trying to generate a bunch of pseudo-random keys for AES using PBKDF2, where the AES ciphers will be used in CTR mode as pseudo-random number generators. My goal is to create a 2-dimensional array, where each entry is a pseudo-random sequence generated by a separate PRNG. The reason for using separate PRNGs is simply because I want each cell to have equal cost to calculate (due to the PBKDF).

So I have two random strings, r1 and r2 (user provided), and I'm generating the AES key for cell (x,y) as PBKDF2(i || r1, r2 || j), where i and j are single characters bijectively mapped to x and y respectively, and || denotes concatenation. I'm using HMAC-SHA256 for the PRF, and nominally 1000 iterations of the PBKDF2. Currently r1 and r2 are 16 bytes each, but I can make them basically any size.

So my questions are:

Is there any weakness in using such closely related inputs to PBKDF2, in particular when used as AES keys for CTR more?
Is there any shortcut for calculating the result of the PBKDF2 for different cells that is any faster than having to calculate it from scratch for each cell?


texts: How to perform frequency analysis of a substitution cipher using a Base64 alphabet

texts:
Let's imagine a cipher that works like the following:

Plaintext is encoded to Base64.
The characters in the encoded plaintext are substituted with a randomly shuffled character set(A-z, 0-9, -, _, =).  The shuffled alphabet is, in essence, the key.

Not particularly complex or even secure.  But...

What if I wanted to do frequency analysis?

For example, "RUNFORYOURLIFE" when encoded in Base64 is:

UlVORk9SWU9VUkxJRkU=

When the character set is shuffled, the final cryptext can look something like this:

xv24DYG9qxG2xYg6DYxf

The key being:

yhAc5bTOWeYvBXCpVuoMJLdg8P1jHN3ZIsi67SrK4E_D9-x2qRQmnlkwUaFt0G=zf

Which is a shuffled version of:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_=

Let's also assume that the character set in subsequent messages is in the same order(ie the key is re-used).

Since the bytes are basically split up resulting in different character units that may or may not correspond, is frequency analysis still feasible?  Does encoding plaintext this way before encryption add any form of security?

My question mostly pertains to longer messages, as my example may be too short for any sort of real analysis.


texts: Why does it matter for a signature scheme to be without random oracles?

texts: There is a profusion of articles proposing signature schemes without random oracles (see for yourself). What does that mean, and why does it matter?


texts: How to calculate an IV when I have a shared private key?

texts:
I'm working with a server/client system that has securely negotiated a private key. I need to encrypt/decrypt messages passing in both directions which are typically between 100 bytes to 100 KB. I'm working with AES-128 bit, but I cannot really understand how the private key is to be used with the encryption algorithm.

  "You should ALWAYS use unique IV's every time you encrypt, and they should be random. "

Based on the previous point, how can I calculate a 'unique' IV on the server and client, when all I have is the secure Key on both sides? Or is it fine to calculate a random IV and  send the IV on the wire? Wouldn't this open up a security hole?

Data: Small sized messages, often with repeating data.
Key: I've got a secure key on both sides.
IV: No idea how to calculate this. Key-derivation? Salted hash? PRNG?


texts: Is there any reason why CCM was created with encryption/decryption being done with a counter versus using CBC-then-MAC?


texts: Is zero IV with AES-CBC safe if CPA is not possible and indistinguishability is not an issue?

texts:
Is using zero IVs with AES-CBC safe, if chosen-plaintext attack (CPA) is not possible and ciphertext indistinguishability is not an issue?

Practical example:

Alice operates an online service that stores user data on a cloud-based database.  Alice is worried about the possibility of someone making off with the database, so wants to encrypt certain data to ensure recovery in that eventuality is impossible.

Alice is mainly concerned about data that are sensitive in their own right, such as those that identify an individual, or are tokens such as CC numbers.

Examples are:

Social security numbers
Addresses of residence
Phone numbers
Credit card numbers

Alice knows chosen-plaintext attacks are a concern, so uses a per-user key to prevent an attacker from loading the database with known-plaintexts.

However, Alice thinks ciphertext indistinguishability is a non-issue because knowing two ciphertexts equal doesn't usually lead to knowing the actual plaintext.

Is Alice safe in assuming data benefits from this kind of encryption and is secure from cryptography?  (i.e. Wholesale data breach.)

One problem I can think of is:

If a user's phone number and credit card number are coincidentally identical, attacker can gleam this information from the encrypted database.  They then only need to obtain the former to also get the latter.
If the first 16 bytes of the user's address is somehow identical to their social security number, again, the attacker can determine this from the encrypted database.

Are there any other problems?

Furthermore, is using AES-CBC this way any safer than using AES-ECB?


texts: Using pin code as a lockscreen for a mobile application

texts:
So I am developing an iOS & Android Application where a lock screen is used for authenticate a user.
There are 4 options to unlock the screen: Password, biometric, pin code and nothing.
I wanted to ask someone with better experience than me about my solution for the pin code process.
There process is following:
User choose pin -> pin is hashed with:
PBKDF2(pin, salt, {keySize: 512 / 32, iterations: 1000})
The 32 first bytes from the hashed pin and the 16 following are used as Key & IV for AES-256 encryption.
So I am basically encrypting my local database encryption key through following:
AES.encrypt(realmKey, pinKey, { iv: iv })
I am then storing the encrypted key & the pin's saltin Keychain/Keystore.
My question is regarding if this is a secure way of doing this. I know that using pin code isn't the best solution I am not recommending it for my users but I stil want to include the option for those who want it and I want to minimise the risk of attack as much as possible.
I first thought this was a good solution, but I was later on thinking that the user basically enters the pin and the pin is then run through the code (hashing with the salt) and decrypting the key automatic in the app. Wouldn't this be easy for a hacker to crack by simply trying all possible combinations ? or do you believe this is a good way ?
I would appreciate any advice and feedback on this


texts: How does one implement the Inverse of AES' MixColumns

texts:
I got an answer in the related question about Mixcolumn for encryption, but how about decryption?

what will I do?

Because it said that I will used this:

  During decryption the Mix Column the multiplication matrix is changed
  to:

0E 0B 0D 09
09 0E 0B 0D
0D 09 0E 0B
0B 0D 09 0E

How does one implement this maxtrix multiplication?


texts: Execution speed of AES_128 GMAC operation

texts: I have read about the speed performance of AES_128_GCM on specific processors Intel and AMD that support AES New Instruction set. As compared with CMAC and HMAC is it relatively slow for other processors such as ARM9 board or cryptographic hardware?


texts:
I read about PBKDF2 on Wikipedia and seen few apps. having option to manually enter number of iterations. I am still not clear on this.

(1) With what I understood, key iterations can be used only with symmetric encryption. If a file/text is encrypted using passphrase, HASH is calculated and encrypted with AES for 'n' number of times. If iterations selected is 100 then this is done 100 times. This is done to defend against brute-force attack.

(2) Key iterations have no use with public-key encryption.

(3) Some apps. by default take 100 iterations. Few apps by default takes 2000 iterations when using AES. How many iterations are considered secure with AES-128 and AES-256?


texts: How to fix the issue with Gimli full permutation distinguisher?

texts:
A new paper "New results on Gimli: full-permutation distinguishers and improved collisions" has been published stating a full 24-round permutation distinguisher with a cost of $2^{64}$ and 23-round permutation  with a cost of $2^{32}$ and has been practical implementation. The 23-round distinguisher could be extended if 1 round for free if the rounds were shifted (the linear layer of Gimli is round dependent)
Due to round dependance of linear layer and swaps are applied every two rounds , The permutation will be viewed as SPN with only 12 rounds.
Questions:

How to fix this issue in General ? Does applying swaps in every round will remove the disguiser?
The column swaps in the linear layer is simple , if the column and rows swaps (cells shuffling) will increase the diffusion rate and provide extra security against distinguisher?


texts: Would the Intel SHA extensions help in creating SHA1 collisions? AMD Ryzen and EPYC supports them.


texts: Creating a PKCS#12 file where public key doesn't match the private key

texts:
For testing purpose, I want to create a PKCS#12 file in which the private key doesn't match the certificate. Is there any tool which will help me do this?

If I use openssl pkcs12 -export command line to create the p12 file using a cert and a private key which are mismatched, then openssl gives me an error

No certificate matches private key

Is there an alternate tool/way to do this?


texts: Is it possible to make sense of an unknown language by means of cryptanalysis?

texts:
I was wondering if it was possible to make any sense from an unknown language by using cryptanalysis. My premises are: suppose an analyst that knows nothing about a language (let's suppose chinese but it can be any other as long as it totally unknown to the analyst), but you do know it's a language (in order to avoid responses like codex seraphinianus) and you can have as much samples of the language as you want (imagine literature, tweets, newspapers, ...)

EDIT: This question came to my mind because I read some time ago about how Americans in WWII used navajo speakers to carry coded messages, hence my interest in trying to solve the problem by cryptanalysis. Also, I'm aware that navajo isn't a written language, but I wanted to assume it in my example for simplicity


texts: Is encrypting a file with AES-CTR and then encrypting the AES key with RSA-4096 secure?

texts:
I'm using microsoft visual studio 2019 c++. I have aes-ctr-128 implementation.

Encryption process:

Generate key pair for aes-ctr-128 using CryptGenKey() function
Encrypt whole 16000 bytes array using key\nonce that was generated previously
Encrypt key and nonce with RSA master key
Write encrypted key\nonce in "key.txt" and "nonce.txt"

Decryption process:

Read encrypted key\nonce
Decrypt encrypted key\nonce with RSA master key
Decrypt whole 16000 bytes array using key\nonce that was decrypted from file

The question is: does this algorithm provide secure encryption process?


texts: How realistic is a dictionary attack on a secure remote password protocol (SRP) verifier?

texts:
I'm deploying a secure remote password protocol implementation and I'm wondering what the consequences are when the client generated verifier gets leaked to an attacker.  I've read Thomas Wu's paper and as nice as it is, it doesn't talk about that scenario.  I also read RFC 5054 and it has the assertion:

  If an attacker learns a user's SRP verifier (e.g., by gaining access to a server's password file), the attacker can masquerade as the real server to that user, and can also attempt a dictionary attack to recover that user's password.

If the client is using the verifier as assurance of the server's identity, I can see how that would go badly.  It's the second assertion of a dictionary attack that makes me wonder.

x = H(s, P)
v = g^x mod n

How much effort would it take to solve for P without knowing x?  It seems like the implied mod of n totally obscures x.  And then, there should be many values of P that could generate a v, but a much smaller set that would pass the verification stage.

And if a dictionary attack could find the password, how is this better than a shared secret protocol?  Is the dictionary attack mentioned in the RFC just saying "if I had an infinite speed computer I could really ruin your day?"  Or does it mean it could run a dictionary attack on the client while pretending to be the server?


texts: How to safely sign a 6 characters String?

texts:
I have to decide, whether a document, which I am given, was correctly signed by a private key.

my Ideas is to sign the document id using RSA with the private key and to print the following onto the document:

encrypt(privateKey, id)
id

Which requirenments should be fullfilled by the id, for the encrypt(privateKey, id) to be safe?
Is it safe, to publish both: plaintext and the encryption, when I am choosing the paintext?
Is there a safe cryptography method, which would allow to minimize the encrypt(privateKey, id) String?
In this special case the attacker has a very limited amount of trials (1-2) to verify whether it's fake signature is legal. When the attacker does not provide a text with a valid signature after the second trial - he is identified as a cheater. The public key is not really public here. I think, that a symmetric encryption would be better here, but the limitation to an asymmetric encryption exists due to backward compatibility reasons.

Example:

 id = ABX3193
 privateKey = 12f21te32223523fefff5z....
 encrypt(privateKey, id) = ??????


texts: MOV-attack on ecc: Time complexity and example

texts:
There already is this pretty big post about the MOV-attack. It states, that the discrete logarithm problem on elliptic curves can be transformed to a discrete logarithm problem over a finite field. This is possible by using a mapping to a field extension.
The attack is not useful, if the resulting field extension $F_{p^m}$ has a large $m$. But if $m$ is small, e.g. $m = 2$, the complexity of solving the DLP is singificantly smaller than solving the ECDLP. ( e.g. if $m=2$ the security of a $256$ Bit ECC can be reduced to $60$ Bit )
My questions:

Why is solving the DLP instead of ECDLP easy, when $m$ is small? How to compute the resulting security Bits?
Can someone provide me a simple example including the important steps, in which the MOV attack is useful? ( Input: ECC with $Q = n\cdot P$ -> contructing the bilinear function $e$ -> using $e$ to transform the ECDLP to DLP -> solving DLP )? The main points I don't understand are constructing $e$ and how to solve the DLP faster than ECDLP.


texts:
On page 2  of this article, there is example of FEAL-4.

At round 2, the input to F (Round Function) is 0x80800000. As F accepts only 4 bytes I divide the input by 2 so that (As I assume the result will be 8 bytes firstly) I compute 8080 and after 0000, concating two results will be 8 bytes:

0x8080|0000

x0x1x2x3|x0x1x2x3
1).8080
y1=G1(8,8)
y2=G1(y1,8)
y0=G0(x0,y1)
y3=G1(y2,0)

Counting G0/G1

G0(a,b)=(a+bmod256<<<2)
G1(a,b)=(a+b+1mod256<<<2)

G1(8,8)=(11mod256<<<2)=44    y1
G0(8,44)=(4cmod256<<<2)=130  y0
G0(8,44)=(4cmod256<<<2)=130  y2
G1(130,0)=(131mod256<<<2)=4C4 y3

But even after this the result is not matching as on the  slide (round2) it should be 0x02000000. Is it a mistake ? Thanks!


texts:
This is a question I've been wondering for a while.

Technically these two strings have the same entropy I believe:

fkfnajkfkg%gsddg£5ER£%££££

0110011001101011011001100110111001100001011010100110101101100110011010110110011100100101011001110111001101100100011001000110011111000010101000110011010101000101010100101100001010100011001001011100001010100011110000101010001111000010101000111100001010100011

both 256bits...

My question is, does character encoding affect entropy?

If generated at random, do both the ASCII and binary strings have the same entropy as passwords?

If 256bits is good as an AES key, it's also good as a password right?

I guess a similar question is does hashing a 'weak' password give a lower entropy string than a 'strong' password, consider this:

Blake2B(password) = 7c863950ac93c93692995e4732ce1e1466ad74a775352ffbaaf2a4a4ce9b549d0b414a1f3150452be6c7c72c694a7cb46f76452917298d33e67611f0a42addb8

Blake2B(fkfnajkfkg%gsddg£5ER£%££££) = 03e7415fa598e9062cfd9e3cd269ca618b38b3543501e197b6c095b8749d782234e82779a2e4b489fd9c3b002734763ee3b867835e1a2232a37bf89ef8606d09

Are,

7c863950ac93c93692995e4732ce1e1466ad74a775352ffbaaf2a4a4ce9b549d0b414a1f3150452be6c7c72c694a7cb46f76452917298d33e67611f0a42addb8

and

03e7415fa598e9062cfd9e3cd269ca618b38b3543501e197b6c095b8749d782234e82779a2e4b489fd9c3b002734763ee3b867835e1a2232a37bf89ef8606d09

the same entropy?

If I hadn't told you the first was the hash of password and the second the hash of fkfnajkfkg%gsddg£5ER£%££££, would it change your view?

I also suppose there is a difference between brute forcing a password which is 256bits, and one which is 256 ASCII 1's or 0's, which would be more than 256bit.


texts:
I want am making an application, demonstrating an attack on a weakly performed diffie-hellman. I need to implement an algorithm that can use the shared variables in order to compute the key. Searching for resources, I keep running into the logjam attack. However I can't really filter out the number crunching from all the HTTP protocol information.

If anyone could provide som resources to point me in the right direction, or a formula to how to successfully compute the key from the known variables. It would be greatly appreciated!

Edit

I have found this resource, which seems really promising.
http://index-of.es/Miscellanous/How%20To%20Backdoor%20Diffie-Hellman.pdf

page 6 it says

  To attack a Diffie-Hellman key exchange, one could extract the secret key a from one of the peer's public key
  ya = g
  a
  (mod p). One could then compute the shared key g
  ab (mod p) using the other peer's public key
  yb = g
  b
  (mod p).

  The naive way to go about this is to compute each power of g (while tracking the exponent) until the public
  key is found. This is called trial multiplication and would need on average q
  2
  operations to find a solution (with
  q the order of the base). More efficiently, algorithms that compute discrete logarithm in expected √q steps

I translate this to

  compute each power of g
  g^1 mod(p), g^2 mod(p), g^3 mod(p)..g^n mod(p)

This would work, however it requires to isolate the exponent from the formula to work. Which is pretty difficult to me.

How would you isolate a from p^a mod(p)


texts:
I was reading the Wikipedia page https://en.m.wikipedia.org/wiki/Random_self-reducibility and it states: "If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to Σ3".
I am trying to understand that statement.  It seems to say if we find a problem where a random instance is hard a bunch of complexity classes are equal. Is this correct? Which complexity classes?


texts: What does this notation stand for when describing a code?

texts:
This code has appeared in some online course material.

I understand the $(5, 4, 3)$ refers to (length, num codewords, distance) but no explanation of the $Z_2^5$ notation is given:

  One $(5,4,3)$ code in $Z_2^5$ is given as below:

  $C_3 = \pmatrix{0, 0,  0,  0,  0\\0,1,1,0,1\\1,0,1,1,0\\1,1,0,1,1}$


texts: Practical way to generate random numbers from PRNG which are indistinguishable from true random

texts:
I am working on a project where I want the user to be able to create random data. For that I use a cryptographically random generator (Java's SecureRandom, which uses OS entropy source if available). Additionally I will seed this PRNG with a true 16 byte (or is more needed?) random number (from e.g. random.org). One seed usually only creates less than 1 MB of random data.

Is that a sound approach to generate random data that is indistinguishable from true random data?

Are there any steps to take to strengthen the security? Eg. scramble the seed to make it harder for an attacker who is listening to know what seed was used?


texts: Is there an existing AE protocol with forward secrecy for embedded devices?

texts:
I'm working on an embedded device that is connected to a computer over an untrusted channel. According to my threat model I need authentication and encryption on the wire with perfect forward secrecy. Both endpoints have a pre-shared key and/or each other's authentic public keys, as well as secure random number generators (although not requiring a secure RNG on the device is a plus). All messages on the wire are fixed-length (16 bytes, i.e. 128 bits).

I'm looking for an existing cryptographic protocol satisfying these properties that would be reasonably simple to implement.

The "toy" protocol I've come up so far is performing an Elliptic-curve Diffie-Hellman key exchange (wrapped in AES-CCM with pre-shared key for authentication), then running a key derivation function on ECDH shared secret and using the result as session key for AES-CCM that encrypts and authenticates data. AES-CCM is used to authenticate ECDH because of limited amount of space code on the device, so I have to use as little primitives as possible.

But I don't want to use a protocol that I've just made up (for obvious reasons) and protocols like TLS, OTR and SSH are way too complex for use in embedded devices. Is there a simpler protocol that provides authentication and encryption with forward secrecy that I could use?

Update: to clarify, establishing a connection doesn't have to be fast, so I can afford a lot of computation. The only requirements for asymmetric crypto is keeping the keys short, hence elliptic-curve cryptography instead of discrete logarithms.


texts: Is the polynomial reconstruction problem really "intractable"?

texts:
In the family of the believed (experts haven't come yet with a solution) intractable problems in cryptography belongs the  Polynomial Reconstruction problem in which an attacker is given $n$ points in which at least $t$ belong to the evaluation of a polynomial $p$ of degree $k$ and the attacker wishes to reconstruct $p$. (where $n>t>k$) The problem has been the basing building block for crypto primitives as public key encryption, block cipher, and oblivious polynomial evaluation.

The reduction for the security proof comes from decoding random reed-solomon codes. My question is the following: Why this is treated as an intractable problem as a very naive idea is to reconstruct the polynomial $p$ by simple Lagrange interpolation after picking up all the ${t} \choose{n}$ elements ?


texts: How does NaCl Poly1305 implementation do modular multiplication?

texts:
The NaCl ref implementation of Poly1305 performs modular multiplication to calculate a polynomial $\mod 2^{130} - 5$ using the following modular multiplication function:

static void mulmod(unsigned int h[17],const unsigned int r[17])
{
  unsigned int hr[17];
  unsigned int i, j, u;

  for (i = 0;i < 17;++i) {
    u = 0;
    for (j = 0;j <= i;++j) u += h[j] * r[i - j];
    for (j = i + 1;j < 17;++j) u += 320 * h[j] * r[i + 17 - j];
    hr[i] = u;
  }
  for (i = 0;i < 17;++i) h[i] = hr[i];
  squeeze(h);
}

... where squeeze() is a reduction. A sequence of mulmod() operations is rounded off with a freeze() operation:

static const unsigned int minusp[17] = {
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252
} ;

static void freeze(unsigned int h[17])
{
  unsigned int horig[17];
  unsigned int j, negative;

  for (j = 0;j < 17;++j) horig[j] = h[j];
  add(h,minusp);
  negative = -(h[16] >> 7);
  for (j = 0;j < 17;++j) h[j] ^= negative & (horig[j] ^ h[j]);
}

This implementation has no documentation, and has been copied literally to various projects (the code above is actually from the libsodium fork).

I've compared this to the various multiplication algorithms on Wikipedia, Montgomery Reduction and Daniel Bernsteins explicit CRT method but I don't recognise it as any of them.

The most basic implementation of the overall Poly1305 using gmp simply uses add/mul/mod operations, so there's nothing that esoteric in the main loop.

The reduction and the freeze seem to indicate this is some kind of residue number system but I can't find explicit descriptions of how that would work.

One of Daniel Bernsteins motivations when writing this was probably to have a constant time implementation, if that helps identify the algorithm.

Does anyone recognize the algorithm being used here, and know of/can provide a complete explanation of it (i.e. one that explains how the magic numbers 320 and minusp are derived, and the basis for all xor operations in the freeze)?


texts: an asymmetric encryption scheme with multiple distinct private keys

texts:
Is there a asymmetric encryption scheme that allows for multiple private decryption keys?

where m= plaintext message and c= cyphertext message

c = Ek(m) where K is the public encryption key.

and

m = Dj(c) where J is the private decryption key.

nothing out of the ordinary here, RSA satisfies this basic scenario.

In addition I also want the message to be decrypted by any number of additional keys, ( Dj1 ...  Djn ) such that:

eg.

m = Djn(c)

does such a scheme exist?

note: I am NOT referring to the way GPG/PGP broadcasts a message to many parties.

edit: looks to be similar to One Encryption, Many Decryption Keys

in particular see D.W.'s answer https://crypto.stackexchange.com/a/39403/29315


texts: Confusing terminology about stream ciphers

texts:
In their book, Understanding Cryptography, on page 37, Christof Paar and Jan Pelzel write:

  Definition 2.2.2 One-Time Pad (OTP)

  A stream cipher for which

  the key stream s0,s1,s2,... is generated by a true random number generator, and
  the key stream is only known to the legitimate communicating parties, and
  every key stream bit s[i] is only used once

I have a problem with the third statement. Perhaps I am confused because of the way it is expressed in the English language.

It says every bit s[i] has to be used once.
How come: s[i] is either 0 or 1? So, as soon as I use value 0 for s[12], does it mean I can't use value 0 anymore?

I am confused as to what the authors mean.

Furthermore, they also say:

  Key stream bits cannot be re-used. This implies that we need one key
  bit for every bit of plaintext

Why does it imply that we need one bit for every plain text ?


texts: Using two elliptic curves to do a range proof

texts:
Suppose Alice holds a secret value $a$ to which she has publicly committed to using two elliptic curves of distinct order. The curves are $g$ and $g'$ of orders $q$ and $q'$ (with $q < q'$) and generator points $G$ and $G'$. The commitment would be $(A, A')$, where $A = a⋅G$ and $A' = a ⋅ G'$.

I'm wondering if Alice could use a variation on the method described here to prove to a verifier that $A$ and $A'$ are derived from the same $a$ AND that $a < q$. Specifically, I am thinking Alice could do the following:

Pick a large random value $r$ and map it to both curves as $R = r ⋅ G$ and $R' = r ⋅ G'$
Compute $u = H(G, G', A, A', R, R')$, where $H$ is a hash function
Compute $v = r + a ⋅ u$ such that $\frac{v}{u} < q$. This could require iterating through several values of $r$
The proof then is $(R, R', v)$ (the verifier already has $A$ and $A'$)

To check that $A$ and $A'$ are derived from the same $a$ and that $a < q$, the verifier could do the following:

Compute the value of $u$
Check that $\frac{v}{u} < q$
Check that $v ⋅ G = R + u ⋅ A$ and $v ⋅ G' = R' + u ⋅ A'$

Some limitations of this approach are:

To be secure, $a$ must be large (over 224 bits) high-entropy value
To be practical, $a$ would probably need to be smaller than $\frac{q}{2}$. Otherwise, picking $r$ that satisfies the constraints would be difficult

Are there any other limitations?

This answer from Yehuda Lindell refers to an earlier version of this question which started like:

"Suppose I wanted to prove that $0<a<q$ for some larger integer $a$ and a large prime $q$, without revealing the value of $a$. I'm wondering if I could use a variation on the method described here to do that."


texts: How can I prove that a function F isn't a pseudo random function?

texts:
Let $F$ be a length-preserving pseudorandom function. For the following constructions of a keyed function $F' : \{0, 1\}^n \times \{0, 1\}^{n−1} \to \{0, 1\}^{2n}$, state whether $F'$ is a pseudorandom function. If yes, prove it; if not, show an attack.
$$F'_k(x) = F_k(0 ∥ x) ∥ F_k(1 ∥ x) \tag{a}$$
and
$$F'_k(x) = F_k(0 ∥ x) ∥ F_k(x ∥ 1) \tag{b}$$

I don't want the solution: I want to understand how I can solve this type of exercise.


texts: DES - encrypt 3 times - DES(DES(DES, k), k'), k) - stronger than 2DES with 2 different keys?

texts:
What if were to use DES in the following way:

For a given plaintext x and key k we will perform: DES(DES(DES, k), k'), k), where k' is the complementary of k.

If an adversary has a small amount of text and their ciphertexts, would he still have to run 3 * 2^56 encryptions: for each key perform DES(DES(DES, k), k'), k) and therefore this encryption is stronger than 2DES with 2 keys (meet in the middle requires 2^57 runs) but less than real 3DES which is much more than 2^57 ?

Or is there a smarter way ?


texts: Diffie-Hellman explicit key confirmation

texts:
Suppose I wanted to add explicit key confirmation to Diffie-Hellman key exchange, would the following scheme be secure?

Alice selects a random $a$ and sends $g^a \mod p$ to Bob
Bob selects a random $b$, computes the shared secret $S = (g^a \mod p)^b$
Bob computes two keys using HKDF ($H(k, m)$ denotes the HMAC of message $m$ using key $k$):

Compute $k = H(salt, S)$
Compute $k_1 = H(k, CTX || 0)$ and $k_2 = H(k, CTX || 1)$

Bob sends $g^b \mod p$, $H(k_1, k_2)$, the salt, and the string CTX to Alice
Alice computes the shared secret $S = (g^b \mod p)^a$, computes $k_1$ and $k_2$ using HKDF given the salt and the string CTX
Alice computes $H(k_1, k_2)$ and verifies whether it's the same as the value that she received from Bob.


texts:
Suppose we have identification scheme as such:

Bob takes random $r$, and encrypts it with Alices public RSA key $(n,e)$, sends $r^e$ to Alice.

Alice decrypts $r$ and sends it back to Bob, becomes identified.

Why it might be a bad idea to use same RSA key for following communication afterwards?


texts: How long does a good AES encryption take?

texts:
I am encrypting large file sizes (>1GB) using AES encryption with a key size of 256 and over a 1000 hash iterations. To make the program memory efficient I'm reading the file from the stream, chunk by chunk (of specific buffer lengths) and encrypting them.

However, to encrypt a file of roughly 1GB it just takes me ~6 secs on a Mac with 16GB memory and 2.2 GHz i7 processor. Is it normal that it takes only this much time? Or should I be concerned? does it usually take longer? Or (as I read) is it given AES's quality to be fast?

Any help in understanding the scenario will be appreciated.

Thank You