{"id":44,"date":"2024-09-26T17:07:46","date_gmt":"2024-09-26T17:07:46","guid":{"rendered":"https:\/\/retrosatellite.eu\/?p=44"},"modified":"2024-09-29T16:57:43","modified_gmt":"2024-09-29T16:57:43","slug":"videocrypts-fiat-shamir-zkt-fail","status":"publish","type":"post","link":"https:\/\/retrosatellite.eu\/?p=44","title":{"rendered":"VideoCrypt&#8217;s Fiat-Shamir ZKT fail"},"content":{"rendered":"\n<p class=\"has-drop-cap wp-block-paragraph\">Zero knowledge proofs are a way for one party (A) to prove to another party (B) that they know a secret (S). But, and here&#8217;s the very clever part, it provides a way for A to prove to B that it knows S <em>without having to say what S is.<\/em> Now why would that be useful? Well, it can be incredibly useful in electronic communications, because any potential evesdropper (C) can not determine the secret in question simply by observing the communications between A and B.  <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s say A is a smart card and B is a decoder, and we want the decoder to be able to determine whether the smart card knows the secret S, without the decoder itself knowing what S is. If the smart card passes the test it has proven to the decoder it knows S and is a genuine smart card. If on the other hand it fails the test, the decoder knows the smart card is not genuine and the decoder will refuse to descramble the TV channel.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The Fiat-Shamir Zero Knowledge Test is an example of a zero knowledge proof scheme that is well-suited for use in smart cards<sup class='footnote'><a href='#fn-44-1' id='fnref-44-1' onclick='return fdfootnote_show(44)'>1<\/a><\/sup> and was implemented as part of the VideoCrypt conditional access system. But the way that the test was implemented in the VideoCrypt system resulted in a vulnerability that was easy to exploit by makers of pirate smart cards, rendering the test completely useless.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">How Does It Work?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Before we can understand why the Fiat-Shamir heuristic implementation in VideoCrypt was such a fail, we need to know a little bit about how it works. Although I find the theory behind zero knowledge proofs fascinating and ingenious, it&#8217;s just a bit too much beyond the scope of this blog post to go into here.<sup class='footnote'><a href='#fn-44-2' id='fnref-44-2' onclick='return fdfootnote_show(44)'>2<\/a><\/sup> But basically what happens between the decoder and card is this:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The smart card sends a 512-bit random value that it chooses<\/li><li>The decoder sends a challenge bit (either 0 or 1)<\/li><li>The smart card returns a 512-bit solution<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Based on the solution returned by the smart card the decoder can determine whether the smart card knows the secret S and therefore is a genuine smart card <em>or<\/em> whether it failed the test, in which case the decoder refuses to continue to communicate with the card and the TV channel would not be decrypted anymore.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Why Did It Fail?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The first vulnerability was due to a monumental bug in the microcontroller inside the first generation of VideoCrypt decoders that were manufactured.<sup class='footnote'><a href='#fn-44-3' id='fnref-44-3' onclick='return fdfootnote_show(44)'>3<\/a><\/sup> The decoder would accept any solution that the smart card would send. The card could send any 512-bit values and whether the card passed the test or not, the decoder would happily continue functioning and communicating with the card.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Photo of SVA-1 decoder<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The bug in itself was not an insurmountable problem. After all, it could be fixed in future revisions of the decoder microcontroller ROM software. Given the many millions of standalone and integrated VideoCrypt decoders that would end up being manufactured over the years, this particular vulnerability would have been limited to a relatively small subset of the total number of decoders in the field. But alas, there was an even larger vulnerability which was so fundamental, that it turned out to be the final nail in the coffin of the Fiat-Shamir Zero Knowledge Test in the VideoCrypt system&#8230;<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Fundamental flaw<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The vulnerability that definitely put the Fiat-Shamir ZKT out to pasture was the fact that the decoder had no way of remembering previous tests, meaning the smart card could feed the decoder the same &#8220;random&#8221; value every time, including the accompanying solution, thereby passing the test.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Our evesdropper (C) could therefore listen in on the communications between a genuine VideoCrypt smart card (A) and the decoder (B) and record the 512-bit value and the 512-bit solution that A sent to B and simply replay that every time B asks to perform the test without C ever knowing the secret (S)!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">While the aforementioned bug could easily be fixed by changing one line of assembly code, this insecure implementation of the FS-ZKT was a much bigger problem. This was the early 1990s. Consumer electronics appliances of the era, like decoders and satellite receivers, did not have any of the non-volatile storage capacities that modern day devices have, if at all. The microcontroller in the SVA-1 decoder only had a measly 128(?) bytes of RAM, which by its nature wasn&#8217;t non-volatile and was nowhere enough to retain any significant amount of previous test values.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Footnotes<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n<div class='footnotes' id='footnotes-44'><div class='footnotedivider'><\/div><ol><li id='fn-44-1'> Source: How To Prove Yourself: Practical Solutions to Identification and Signature Problems &#8211; Amos Fiat and Adi Shamir (1986) <span class='footnotereverse'><a href='#fnref-44-1'>&#8617;<\/a><\/span><\/li><li id='fn-44-2'> If you&#8217;re really interested in how zero knowledge proofs work, try searching the webs for the Ali Baba Cave problem, which is a great way to explain it. Also check out YouTube and Wikipedia. <span class='footnotereverse'><a href='#fnref-44-2'>&#8617;<\/a><\/span><\/li><li id='fn-44-3'> Source: &#8220;Attacks on Pay-TV Access Control Systems&#8221; &#8211; Markus G. Kuhn University of Cambridge, Computer Laboratory, Security Seminar talk, 1997-12-09. <span class='footnotereverse'><a href='#fnref-44-3'>&#8617;<\/a><\/span><\/li><\/ol><\/div>","protected":false},"excerpt":{"rendered":"<p>Zero knowledge proofs are a way for one party (A) to prove to another party (B) that they know a secret (S). But, and here&#8217;s the very clever part, it provides a way for A to prove to B that it knows S without having to say what S is. Now why would that be [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":75,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-44","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=\/wp\/v2\/posts\/44","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=44"}],"version-history":[{"count":10,"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=\/wp\/v2\/posts\/44\/revisions"}],"predecessor-version":[{"id":54,"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=\/wp\/v2\/posts\/44\/revisions\/54"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=\/wp\/v2\/media\/75"}],"wp:attachment":[{"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=44"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=44"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/retrosatellite.eu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=44"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}