5

I would like to ask about this encryption method that I found: USPTO patent and it is related to this question here: A service that claims beyond army level encryption and Unseen.is encryption claims revisited with their proprietary, patented “xAES” algorithm. Didn't see any updates on this matter for a long time, so after I had found the patent had appeared online, wanted to ask you experts what do you think about this? Have we found an quantum computing resistant encryption method for the future generations? Thank you in advance.

Example chapter from the patent documentation:

[0020] While the example above uses the simple Caesar cipher in association with a key for encryption, more complex encryption algorithms such as NTRU, Advanced Encryption Standard (AES), and extended Advanced Encryption Standard (xAES), also use a key as mentioned above in order to encrypt and decrypt data. It should be noted that the encryption algorithm 106 may use any one of these encryption algorithms in accordance with an embodiment of the present invention. The keys associated with these encryption algorithms are significantly more complex than the Caesar cipher and have considerably more characters. Nonetheless, these advanced encryption algorithms use the same principles as the Caesar cipher during encryption and decryption processes. More specifically, each of these encryption algorithms processes data using the encryption algorithm and a key during encryption and decryption. However, the key used with these encryption algorithms have a finite number of bytes. In many instances, these encryption algorithms use a key having 256 bytes, or 32 characters, that are generated using a random number generator. Based on this finite number of keys, unauthorized third parties may correctly guess the key and then, in conjunction with the encryption algorithm, decrypt the encrypted content. In other words, unauthorized third parties may use the key with the encryption algorithms noted above to decrypt encrypted data.

Patent image 1

forest
  • 65,613
  • 20
  • 208
  • 262
Alyssa Skogs
  • 53
  • 7
  • Just to be clear, you want the community to comment on whether this is a `quantum computing resistent encryption method` based on the description in the patent? – Jedi Jun 29 '16 at 17:26
  • 2
    Hi Jedi. Thank you for pointing that out. What I am searching here is merely of an understanding of what the service "thinks" it is selling. And as a customer, what am I "thinking" I am buying. Because the service presents their encryption to be beyond AES 256 and that they supposedly have been able to create something much stronger than that, which supposedly could even withstand known attacks with even using quantum computing power. For the user of the service, how valid these claims may be? What are they actually selling, that interests me. Unsubstantiated or substantiated claims? – Alyssa Skogs Jun 29 '16 at 17:31
  • Probably relevant: Schneier on [Snake Oil](https://www.schneier.com/crypto-gram/archives/1999/0215.html#snakeoil) and a [Snake Oil contest](https://www.schneier.com/blog/archives/2015/08/snake-oil_crypt.html). The only way this could be substantiated is if they put themselves up for public scrutiny, with an open source implementation, list of tests performed, and set up a public bounty/pentest program. It's unlikely that people will be motivated to spend much time deciphering a USPTO filing. – Jedi Jun 29 '16 at 17:40
  • Thank you Jedi. What you say speaks for the fact that they want to "look professional" in what they are doing and file a patent and then appear more "serious". Or am I completely mistaken? What is the value for patenting an encryption method that nobody else but the patent office can validate? Furthermore; when and if patented, is it then possible to do the public review or does it mean they still can hold it as their "secret" and never reveal any more details of their "patented" encryption? "It's patented, it's secure"? – Alyssa Skogs Jun 29 '16 at 17:53
  • You're right, it's primarily signalling. There's >10000 "[patented encryption algorithms](encryption algorithm site:www.google.com/patents/)"; it isn't feasible to evaluate, even if the method is shared with all. So the USPTO is treated as a source of authority. Honestly, if you want someone to take a look at the algo, you're better off on the [Crypto SE site](https://crypto.stackexchange.com). See [this](http://law.uh.edu/faculty/gvetter/documents/Vetter,%20Patenting%20Cryptographic%20Technology,%2084%20Chi.-Kent%20L.%20Rev.%20757%20(2010).pdf) to understand motivations behind crypto patents. – Jedi Jun 29 '16 at 18:22
  • Thanks Jedi. So in principle, it does not mean that there would not be a strong encryption invention made, but it would also mean that if not openly challenged and evaluated, it might stay as a "selling point" for the product, targetting people who do not necessarily understand the point of open evaluation. Does this work so then that it will most likely stay as a "proprietary" encryption, which would only be shared with most important big paying customers, but for reason or another, not openly offered to be verified? Thank you for the links. – Alyssa Skogs Jun 29 '16 at 19:39
  • 2
    Related post: https://security.stackexchange.com/questions/101841/unseen-is-encryption-claims-revisited-with-their-proprietary-patented-xaes-al/101868#101868 – Jedi Jul 09 '16 at 05:31

2 Answers2

1

An encryption patent is a contradiction in terms these days. Nobody (in the large) is going to spend the effort to evaluate a patented method. At best, you would read the patent filing and determine that it's a cheesy version of something that exists and expose yourself to triple damages because you read a patent that should have been rejected based on an immense amount of prior art that should have been discovered, but wasn't because the filing is basically dishonest about this.

forest
  • 65,613
  • 20
  • 208
  • 262
Rob
  • 639
  • 3
  • 9
  • Thank you Rob. What is the difference to AES having been also patented (http://www.google.com/patents/US7421076) to what Unseen.is tries to do with their Multidimensional-Encryption? Could they become the next "AES"? – Alyssa Skogs Jun 30 '16 at 06:19
  • the environment has changed a lot. people used rsa for a while, and were simultaneously dealing with export issues. if you include legally encumbered anything in your design, it's going to get rejected until there is no other option. – Rob Jun 30 '16 at 06:23
  • i dont think that means that aes is patented at all. that looks like a patent for a particular implementation of it, which hardware vendors are ok with; because they will send their designs to somebody else to manufacture. but these days, the algorithm is not considered interoperable if both sides need to license it. – Rob Jun 30 '16 at 06:39
  • from NIST page on AES: "The call stipulated that the AES would specify an unclassified, publicly disclosed encryption algorithm(s), available royalty-free, worldwide. " – Rob Jun 30 '16 at 06:42
  • Thank you Rob for the more specific details on this. I agree, that is not the AES patent, merely AES+something. Just as if Unseen.is patents their xAES maybe. This means, they have the royalty-free AES included. Can basically anyone then take the AES and make an additional encryption block to accompany it then name the whole thing as whatever xAES, yAES etc and patent it? Why don't you and me do the same and establish a web service and offer "beyond military encryption" and people are like "ooooooh" ;P ? – Alyssa Skogs Jun 30 '16 at 07:06
  • keep in mind that none of the trap doors currently in use are proven secure either (except for one-time-pad with an actual RNG). but novel trap doors cannot claim to have withstood years of attack, by definition. export/patent issues are insane headaches (been there!). the design should be provable up to the well studied trap door. you can hand me a 20x20x20x20 4D rubiks cube and tell me that it's unsolveable because i can't solve it. but that's not how you do crypto. – Rob Jun 30 '16 at 07:14
  • Thanks. It seems a complex world indeed. I found an article that suggests AES should be actually abandoned https://eprint.iacr.org/2007/248.pdf - so, in terms of selling security, there is a lot of talk around encryption methods and especially their possible weaknesses. If I would want to sell an encrypted chat / voice call service, would it be best to "stand taller" and to "spice up" the already known and used encryption method so that for the users it would look a "more secure" option to the original encryption method to make the users also feel more secure, and then ask money for it? – Alyssa Skogs Jun 30 '16 at 07:34
  • total honesty: so i went and took a look. they have a product before a shred of vetting. from the USPTO filing (which are always gibberish to bamboozle an examiner, who is as likely to evaluate some goofy file-system patents on prior art. (he stamps it with "whatever dude, no idea") my own patent (i was asked to...) got turned into such gibberish by lawyers, because the point of patents is to make them generic enough to go perform some cross-licensing stick-ups on people actually making stuff.) that link to Schneier's snake-oil post is spot on. a product before vetting is not crypto. – Rob Jun 30 '16 at 07:49
  • Thank you for this. I was not thinking at all that vetting part. However, does it falsify their cryptographic "invention" - or - method, if not they have vetted their product? You said, a product before vetting is not crypto? Is it like on/off, true/false that a proprietary encryption method with a filed possibly granted patent will not be crypto - or does it merely mean that their version of the "crypto" may well be worth a patent to sell it - or do those buyers only then consist of people who do not actually understand the importance of a vetted crypto product before investing their money..? – Alyssa Skogs Jun 30 '16 at 08:22
  • yes on all points. for one thing, assume that unvetted crypto has a backdoor. the longer people evaluate it, the less likely that is. – Rob Jun 30 '16 at 16:59
  • thanks Rob! =) what guarantee is there, btw, that after the evaluation, when the software goes thru builds and productization - that there would not be a backdoor post-installed? E.g. with this Unseen(dot)is webservice, what guarantee does an user have they do not provide a backdoor towards the intelligence services? Can the user fully trust in a webservice that claims "beyond military encryption" and "xAES" with a patent but still not been publicly vetted and challenged? E.g. Unseen(dot)is chat shows a padlock, you can view the encrypted content to verify it's encrypted..? – Alyssa Skogs Jun 30 '16 at 17:39
  • You get probabilistic assurances. If you have a novel trap-door, it should go through many years of attack before it can even be considered for inclusion in a product. People have been trying to factor large primes for many hundreds of years for instance. We have some trust in AES and RSA due the large number of competent people who tried to crack it, and that the one who does crack it figured out something that none of them could over many years. That paper looks somewhat related to AES, but vetting time can't be skipped - unless selling a product is more important than security. – Rob Jun 30 '16 at 17:54
  • Again,Rob - thank you so much! You help me a lot, because i need to write a study about commercial webservices with proprietary encryption methods. Could it then be, that they could skip the vetting time and go straight into charging bigger clients for only whom they, under an NDA maybe, would disclose the full code and specs? So that the company who wants to take their encryption in use could evaluate it with their own specialists, and then come to either conclusion; to take or to drop? The NDA though would prevent them then revealing any findings outside, whether good or bad...? – Alyssa Skogs Jun 30 '16 at 18:02
  • Everybody recommends reading "Cryptography Engineering". The main thing to take away from it is to only use vetted combinations of primitives, and to assume that anything else is junk until it has been long since proven. Even obvious looking schemes are going to have surprising algebraic properties that allow attackers to just walk around the protection rather than brute forcing them. – Rob Jun 30 '16 at 18:04
  • Thank you Rob! =) Would be fun to check out the Unseen(dot)is together, please add me if you like alyssaskogs@unseen.is - just made an account there, looks to be free. – Alyssa Skogs Jun 30 '16 at 18:39
1

I've tried to analyze the patent, and it seems to address the issue of:

Often In an example where the key has 256 bytes, the algorithm will iteratively guess keys that have 256 bytes. At some point, the algorithm will guess the correct key and the unauthorized third party may access the encrypted data using the correct key.

That's a feature, not a bug - of course one of the 2^256 keys has to decrypt the data!
Since brute-forcing a 256-bit key is essentially impossible, it's a problem that didn't need solving. But as far as it goes...
What the patent itself covers is a key expansion algorithm:

Embodiments of the present invention expand the size of a key that is used with an encryption algorithm to any size extending to infinity that may be used with numerous types of encryption algorithms.

The expansion algorithm appears quite straightforward:

In particular, instead of using a fixed value as the key that is used in conjunction with the encryption algorithm, a variable polynomial is used to generate the key. An example of a polynomial that is used to generate a key is as follows: a(x)=18x 15+11x 14+22x 13+24x 12+10x 11+16x 10+6x 9+22x 8+17x 7+12x 6+6x 5+14x 4+28x 3+5x 2+7x+2

The security of encryption depends on the size of the secret, not the key. When the key is randomly generated and stored, they're the same. When the key is derived from a password, the secret is much smaller (so slow PBKDF and other measures are used to improve security). Since the algorithm should be assumed known to the attacker, the maximum security of the described key would be equivalent to the size of x. The polynomial's coefficients can be seen as a tweak t.

In other words, at best, this invention is appears to be a convoluted form of LRW mode encryption. At worst, the key derivation algorithm employed could reduce the cipher's security.

It definitely isn't a security improvement over known and common encryption modes such as GCM.

Therac
  • 2,610
  • 11
  • 18
  • 1
    The patent says 256 bytes, not 256 bits (just makes it seem more like they don't know what they're talking about). – forest May 14 '18 at 07:15