TMSR-RSA spec, extremely early draft

Wednesday, 16 August, Year 9 d.Tr. | Author: Mircea Popescu

I. As far as extant literature is concerned, Werner Koch is a malevolent imbecile whose shameless parents should nevertheless fucking apologize. Everyone elsei "involved" in "crypto" to date is not far behind, from Zimmermanii onwards.

II. The RSA key shall be a 4096 bitiii entity produced out of two 2048 bit primesiv. The key will be stored as a N, e, C structure, where N is the public modulus, e the chosen exponent, and C a comment field of unspecified length. Key fingerprints will be calculated over this structure through a yet-to-be-specified hash function.v

III. The RSA exponent will be a 4096 bit integer at the option of the user. In principle the user can input any 4096 bit prime, but one of two types are recommended : either the FULL stylevi or else the RNG stylevii.

IV. RSA padding will be provided through Keccak-OAEPviii. Messages longer than 2048 bits will be packeted into 2048 bit chunks. There will be no symmetrical cyphers involved at any point. Signatures will be based on the same padding.

IV. RSA implementation will work in constant time and constant space ; the canonical implementation will be written in Ada. Work is ongoing towards a FFA-based approach.

V. Alternative ciphers. Cramer-Shoup.

———
  1. See the logs re useless antecessors, I won't rehash here. Not so much as a fucking constant - time exp they produced, these useless fucktards that aren't anything else. []
  2. Years prior to the reveal, "Zimmerman" responded to an email encrypted to his key by stating (in plain text) that he "decades ago" lost the corresponding key. 'Nuff said. []
  3. For about a year I strongly supported eccentric length key. I gave up on the idea recently, because the arguments against as presented satisfied me -- and when reason speaks emotion'd better shut the fuck up.

    The user will not get any say in the matter. 2048 keys are too short. 8192 keys are too long. Keys of a length that's not a power of two are no good. RSA keys are 4096 bits and that's the end of the story. []

  4. Primality testing, as well as everything else, will be implemented correctly, as opposed to imperialy. This point fractally and endlessly repeats itself throughout, because everything the pantsuits to is retarded on all levels, recursively. Nevertheless, it won't be repeated here. []
  5. The requirements for this role are a) no blocks and b) unlimited size input. The current candidates for this role are either keccak or mpfhf. []
  6. Something like say 1111111111111111111111111111111111111111111111111111111111000101, or more generally speaking 264 - 59, 83, 95, 179, 189, 257, 279, 323, 353, 363 etc []
  7. 1100111110111010111111000100100010011101001010001000100100011001 , or generally speaking anything with ~half the bits set (that's also a prime number, obviously).

    As Stan aptly puts it,

    No moar 'we heathens have faster RSA because mother dropped us as babies and our RSAtron does different work on different hamming weights'

    Word. []

  8. To pad : 1. Produce M00 by adding 0s on the right of message M until M00 reaches 2048 bits in lenght ; 2. Generate R, 2048 bits of entropy ; 3. Calculate X = M00 xor hash(R) ; 4. Calculate Y = R xor hash(X). The padded message M is X + Y.

    To de-pad : 1. Calculate R as Y xor hash(X) ; 2. Calculate M00 as X xor hash(R) ; 3. Remove 0padding.

    The hash function is yet to be specified. It should be a non-block 2048 to 2048 bit hash function (conceivably, can also use two). []

Category: Bitcoin
Comments feed : RSS 2.0. Leave your own comment below, or send a trackback.

40 Responses

  1. MPFHF dun go with constant-time-constant-space...

  2. Mircea Popescu`s avatar
    2
    Mircea Popescu 
    Wednesday, 16 August 2017

    I thought we were happy with "at every juncture calculate both the 1 and the 0, throw away one of the two" approach to fix that problem ?

  3. Mircea Popescu`s avatar
    3
    Mircea Popescu 
    Wednesday, 16 August 2017

    Meanwhille, tis gone.

  4. So UDP has a "unfragmented packet" limit of 512 bytes. To use UDP for gossipd, would you use keys of only 2048 bits (256 bytes) or only have a message of 256 bytes with 256 bytes padding, or use the whole 512 bytes for a message and 512 bytes for padding and have a possibly fragmented packet, or send the message in one udp packet and the padding in another?

  5. Mircea Popescu`s avatar
    5
    Mircea Popescu 
    Friday, 18 August 2017

    > or send the message in one udp packet and the padding in another?

    This is fucking precious lol.

    But you have a point, last footnote should have quited 2048 not 4096 bits for padding m00 so that 256 bytes of message are OAEP'd and the resulting 512 byte padded message is encrypted in each packet.

  6. IIUC, for RSA encryption the message must be smaller than the modulus.

    So if we pad our message to get a 4096 bit message for encryption, and we have a 4096 bit modulus, how do we ensure that the message is smaller than the modulus?

  7. Mircea Popescu`s avatar
    7
    Mircea Popescu 
    Friday, 15 September 2017

    There's two approaches, one's to chunk it the other's to add a symmetric encryption layer in between (then you just rsa the key, and so it always fits). The republic favours the former over the latter.

  8. I don't think you undrstood the question I am asking. I get the idea of breaking a long message into chunks, I am talking about a single chunk here. After doing OAEP, you have some 4096 bit number. Some of those numbers are less than the modulus, and so are fine, but what do you do with the ones that are greater than the modulus?

  9. Footnote vii reads "(that's also a prime number, obviously)." regarding the public exponent. Does TMSR spec require the public exponent to be prime itself? Isn't it enough if it's co-prime with (p-1)(q-1)? (and obv between 1 and (p-1)(q-1) ).

  10. Mircea Popescu`s avatar
    10
    Mircea Popescu 
    Monday, 6 November 2017

    Coprime works, yes, if the coprimality test is cheaper than the primality test. Is it ?

  11. The coprimality test is GCD and in fact considerably cheaper than any reasonable primality test.

    That being said, I quite dislike the notion of ever using a composite public exponent -- it makes certain types of attack cheaper, while ( at least in FFA-land ) getting nothing useful in return.

  12. Mircea Popescu`s avatar
    12
    Mircea Popescu 
    Monday, 6 November 2017

    If we permit merely coprime exponents randomly generated, about half will be even numbers.

  13. I know of no persuasive reason to permit composite pub-exponents at all.

    Why give the enemy the advantage of getting to use CRT?

  14. Mircea Popescu`s avatar
    14
    Mircea Popescu 
    Monday, 6 November 2017

    The persuasive reason, such as it is, is cheapness.

    It's not clear how we'd calculate the supposed weakness using a coprime but composite large exponent would induce.

  15. The "cheapness" of composite-pub-exp does not exist for you when using a nonleaking (i.e. fixed-spacetime, FFA) rsatron.

    It does however make life easier for the enemy, who is using, e.g., a 'superencryption' brute-force (against a rsa scheme where padding failed -- and a provably-unfailing padding is not known.)

    A composite pub-exp is arguably exactly the same item, cryptologically, as taking the smallest prime factor of it and using ~that~ as the pub-exp.

  16. Mircea Popescu`s avatar
    16
    Mircea Popescu 
    Monday, 6 November 2017

    > The "cheapness" of composite-pub-exp does not exist for you

    It does, in that you don't have to test for it. See above.

    > A composite pub-exp is arguably exactly the same item, cryptologically, as taking the smallest prime factor of it

    I suspect this is correct, in which case it entirely doesn't matter whether the 4096 bit exponent is composite or not, the odds of the largest prime in it being 65537 or smaller literally 0.

  17. > the odds of the largest prime in it being 65537 or smaller literally 0

    Umm, try this yourself ?
    Or see the cached phuctor liquishit keys. It's a ~1, not 0.

  18. Mircea Popescu`s avatar
    18
    Mircea Popescu 
    Monday, 6 November 2017

    My quote discussed the largest prime ; on re-read you were talking about the smallest prime. This makes no sense to me ; are you proposing that exponent 131074 reduces to exponent 2 somehow and you'll be able to apply eg Coppersmith ? I'd like to see this drawn out.

    Other than this conversation, it is brought to my attention that eg https://pdfs.semanticscholar.org/42c9/10ed955236438a5f8d51f1e7f235e9c1f565.pdf : there's an implicit weaknes in very large public exponents (in that they force very small private exponents and private exponents smaller than N 0.292 are known to not be safe).

  19. > exponent 131074 reduces to exponent 2 somehow

    Aha

    > I'd like to see this drawn out

    I'ma put this in the conveyor.

    > very large public exponents ... they force very small private exponents

    How ?!

  20. http://btcbase.org/log/2017-11-02#1732060 is correct by the way, Windows CryptoAPI can't handle exponents larger than 32 bit.

  21. Mircea Popescu`s avatar
    21
    Mircea Popescu 
    Monday, 6 November 2017

    @Stanislav Datskovskiy Wiener's attack, what. Looks for a continued fraction approximation of e/N, lists all the candidates and then tries them all.

    @TP Heh.

  22. Q was, how does large public exponent force the use of a small private exponent ?

  23. Mircea Popescu`s avatar
    23
    Mircea Popescu 
    Monday, 6 November 2017

    Afaik the GPG remnant we're using computes d as the N-symmetric of e. Doesn't it ?

  24. In RSA (incl. Koch's) d = e^-1 mod phi , but this op is not an integer reciprocation! -- it is a ~modular~ multiplicative inverse, and does not have the "large e forces small d" behaviour. Try it by hand.

  25. Mircea Popescu`s avatar
    25
    Mircea Popescu 
    Tuesday, 7 November 2017

    Nevertheless, provided a large e GPG does in fact* produce a small d.

    * To the degree anything meaningful can be said about GPG behaviour in general ; at some point it actually produced random 16 bit exponents for instance, until that feature being taken out in favour of using 65537 in the usual retrospectively-suspicious manner.

  26. Did you try it ?

  27. Mircea Popescu`s avatar
    27
    Mircea Popescu 
    Tuesday, 7 November 2017

    Not yet.

  28. Mircea Popescu`s avatar
    28
    Mircea Popescu 
    Tuesday, 7 November 2017

    Minigame tech dept reports that out of 978 assays 0 produced d < n0.5.

    So I take it you're right.

  29. At Keccak-OAEP the scheme reads:

    "1. Produce M00 by adding 0s on the right of message M until M00 reaches 2048 bits in lenght"

    How many 0s though? If it's a variable number of 0s depending on how many bits M happens to have, it's impossible to trim them back at the end (since M might have some 0s at the end itself).

  30. I think the way this is actually done irl is repeat the last block (byte) of the message, then add the zeroes.

  31. Mircea Popescu`s avatar
    31
    Mircea Popescu 
    Wednesday, 14 February 2018

    Some sort of in-band solution like that, if memory serves, indeed. "Null-terminated strings" etcetera.

  32. Myeah, it is a form of inband such as 0x00||0x02||pseudo-random-non-zero-octets||0x00||M

    Rummaging through GnuPG 1.10 code yielded mainly the usual headaches as the padding itself is a sort of kraken split in 10 files or so, not something that can be clearly pointed out or extracted or followed, why would it be.

    Overall: I don't like this approach at all.

  1. [...] work done this month is an incipient RSAtron conforming as much as possible at the moment with the current TMSR-RSA specification. The sane-mpi package is used as it was provided and linked as a library. In addition, I extracted [...]

  2. [...] to accommodate any number of octets you might wish to give as length of your desired prime MPI, TMSR RSA specification is rather strict on this: RSA keys are meant to be exactly 4096 bits (512 octets) long and made of [...]

  3. [...] bits (256 octets) each. This value is precisely half of the intended key length, as per current TMSR RSA specification. Note that both primes will have top 2 bits set to 1 precisely to ensure that their product is [...]

  4. [...] This condition is a requirement of RSA and since oaep returns a block of the same length of TMSR RSA modulus, it follows that in some cases the oaep block will actually be a number bigger than the [...]

  5. [...] will use Keccak for all its hashing and RSA padding needs, as per TMSR-RSA specification. In this age of ever-mutating labels on top of labels though, I have to clearly state that EuCrypt [...]

  6. [...] discussion of issues encountered and decisions made as well as a better approach to very pointy and very real problems (not a perfect approach, sure; just a few degrees of magnitude better than what one finds for [...]

  7. [...] TMSR-RSA spec, extremely early draft [...]

  8. [...] early draft of TMSR-RSA encryption scheme29 [...]

Add your cents! »
    If this is your first comment, it will wait to be approved. This usually takes a few hours. Subsequent comments are not delayed.