• Konferenz „Privatheit und Demokratie“

    Hallo zusammen,

    am 22.09.2016 werde ich einen Vortrag zu Tracking-Verfahren an der Goethe-Universität FFM halten. Der Slot dazu heisst „Ökonomie der Privatheit in der Informationsgesellschaft“.

    Weitere Infos finden sich hier und das Programm gibt es hier.

  • Kleines Pflaster: Mehr Privacy mit wenigen Klicks

    Hallo zusammen,

    wenn man sich im Web bewegt, hinterlässt man überall Spuren – das ist schon fast jedem bekannt. Aktuelle Studien aus dem Jahr 2015 zeigen, dass durch Einbettungen (wie z.B. ein YouTube-Video) auf 9 von 10 Webseiten Informationen an Dritte weitergegeben werden [1].

    Durch solche Einbettungen in Webseiten werden Drittparteien exakt über die besuchte Webseite informiert. Ein Beispiel um das Problem zu verdeutlichen: Ist auf einer Webseite eine Schriftart, z.B. von googlefonts oder Fonts.com, eingebunden, bewirkt dies eine Weitergabe der IP-Adresse UND der besuchten Webseite an den jeweiligen Anbieter.

    Auch wenn ich dies als klaffende Wunde ansehe, möchte ich jedem ein kleines Pflaster in die Hand geben. Während sich aktive Inhalte, wie z.B. der Facebook „Like“-Button oder das JavaScript von Google Analytics, nur durch Browsererweiterungen vernünftig unterbinden lassen, können andere Formen der Datenweitergabe (z.B. durch ein eingebettetes Bild) schon mit einfachen Mitteln reduziert werden. Damit Google & Co. es also nicht ganz so einfach haben, sollte zumindest ein Teil dieser Weitergabe abgeschaltet werden.

    Dies geht in Firefox (erstellt für 46.0.1) mit nur vier Schritten:

    • Schritt 1: „about:config“ in die Adressleiste eingeben.

      referer_step_1

    • Schritt 2: Den Warnhinweis akzeptieren.

      referer_step_2

    • Schritt 3: Nach „referer“ bzw. dem Einstellungsnamen „network.http.sendRefererHeader“ suchen.

      referer_step_3

    • Schritt 4: „network.http.sendRefererHeader“ auf den Wert „1“ setzen.

      referer_step_4

    Tatsächlich ist die Einstellung „0“ noch restriktiver, kann jedoch zu Komplikationen bei Web-Anwendungen führen, die auf den Referer angewiesen sind (z.B. Formulare). Dies ist bei „1“ nicht zu erwarten. Ich surfe mit dieser Konfiguration schon eine ganze Weile ohne Probleme. Sollte es widererwarten doch Komplikationen geben, kann das Setting zurück auf „2“ und das mit Firefox 28 eingeführte „network.http.referer.XOriginPolicy“ Feld auf „1“ gesetzt werden.

    Für Chrome gibt es beispielsweise das Addon Referer Control. Dies ist jedoch, in meinen Augen, unbedienbar. Der eingebaute Programm-Schalter, der den Referer komplett deaktiviert, ist ebenfalls nicht alltagstauglich. Da Google von der Übermittlung des HTTP-Referer profitiert, ist es nicht so überraschend, dass er im Chrome-Browser nur schwer zu unterbinden ist.

    Zugegeben ist diese Referer-Problematik schon eine sehr alte. Wie jedoch hier schon erwähnt zeigen meine jüngsten Erkenntnisse, dass dies aktuell problematischer ist, als es noch vor 10 Jahren war [2].


    [1] Timothy Libert: Exposing the Hidden Web: An Analysis of Third-Party HTTP Requests on 1 Million Websites. CoRR abs/1511.00619 (2015)
    [2] Wambach T. and Bräunlich K. (2016). Retrospective Study of Third-party Web Tracking. In Proceedings of the 2nd International Conference on Information Systems Security and Privacy ISBN 978-989-758-167-0, pages 138-145. DOI: 10.5220/0005741301380145

     

  • NICHT(kein-APT) im Bundestag

    Hallo zusammen,

    was macht man an einem Feiertag mit schönem Wetter üblicherweise? Richtig, man sieht sich den vom BSI veröffentlichten Bericht zur Lage der IT-Sicherheit in Deutschland 2015 an! Man muss vorab schon mal sagen, dass der Bericht sehr schön ausgestaltet ist – sowohl optisch, als auch inhaltlich.

    Mein persönliches Highlight war der Abschnitt über den Cyber-Angriff auf den Deutschen Bundestag. Nach der Aussage im Dokument wurde dabei nach der „klassischen APT-Methode“ vorgegangen. APT (Advanced Persistent Threat) ist ein Sammelbegriff für professionelle/gezielte Angriffe. Es gibt jedoch keine klare Abgrenzung zu „einfachen“ Angriffen, sondern wird eher über Beispiele definiert: Stuxnet war ein APT – eine Ransomware im Krankenhaus ist kein APT. Durch diese Verknüpfung mit besonders kritischen Beispielen zuckt jeder IT-Verantwortliche innerlich zusammen, wenn er von einem APT hört.

    Das Vorgehen der Angreifer wird auf Seite 26 beschrieben und kann so zusammengefasst werden:

    • Einzelne Arbeitsplatzrechner wurden infiziert.
    • Tools wurden nachgeladen.
    • Backdoors wurden installiert, sowie weitere Schadprogramme und Keylogger.
    • E-Mail-Postfächer wurden sich angesehen.

    Mit anderen Worten: Ein Angreifer erlangt unberechtigt Zugriff, installiert sich weitere Software auf dem System und schaut anschließend was es noch alles gibt.

    Man kann natürlich nicht widerlegen, dass es ein gezielter Angriff sein könnte. Ich bezweifle nur ein wenig die Argumentation dafür im Dokument, Zitat:

    „Bei der Ausbreitung im internen Netz („Lateral Movement“) setzen die Angreifer auf gängige Methoden und öffentlich verfügbare Tools, wie sie auch von weniger professionellen Tätern verwendet werden. Dies kann dadurch begründet sein, dass man eine Zuordnung des Angriffs erschweren wollte.“

    Es war also deshalb ein APT, weil es nicht aussieht wie ein APT. Gut, die Informationen sind hier auch sehr knapp gehalten. Aber ich habe trotzdem die Spur eines Verdachts, dass hier auch politischen Gründe im Spiel waren: Da einfache Angriffe auf einer so kritischen Infrastruktur ja grundsätzlich ausgeschlossen sind, muss es ein professioneller gewesen sein.

    Weiteres aus dem Bericht FYI:

    • Schwachstellen. Abbildung 2 (Seite 10) zeigt eine Auflistung von verbreiteten Softwareprodukten und deren Schwachstellen im Jahr 2015. Wenig überraschend ist Flash mal wieder auf Platz 1. Platz 9 wird euch sicher überraschen … Java. Aus der Hardware-Ecke wird ein Angriff vom Juli 2015 beschrieben, welche über ein USB-Stick eine Fernsteuerung des Rechners durch das Intel-Management-System (vPro) ermöglicht.
    • Kryptographie. Hier gab es im Jahr 2015 wohl wenig Neues (zumindest aus Sicht des BSI). Erwähnt werden die Angriffe FREAK (SSL/TLS) und Logjam.
    • Ransomware im Krankenhaus. Das kennen wir natürlich schon. Immerhin wird der Angriff, wie von mir auch, als „heute Alltag“ eingestuft. Das Wort „Cyber-Kriminelle“ hätte man sich jedoch auch sparen können.
    • Social Engineering per Telefon. Auch in meinem erweiterten Bekanntenkreis ist jemand Opfer von einem „Microsoftmitarbeiter“ geworden, der den naiven Nutzer zur Installation von Fernwartungssoftware aufgefordert hat.
    • Statistiken zu Spam und Botnetzen.
    • Eine Drive-by-Exploit Übersicht (Abbildung 10, Seite 32) hat mir sehr gut gefallen. Es zeigt in einer Zeitleiste die kritischen Exploits und die ausgenutzte Schwachstelle (CVE).
    • Außerdem gibt es noch einen Ausflug ins neue IT-Sicherheitsgesetz, welches seit Mitte 2015 in Kraft ist.

    Es gibt jedoch noch mehr, mal drüberblättern lohnt sich auf jeden Fall.

     

  • Virenanfälligkeit

    Hallo zusammen,

    soziale Netzwerke sind ein endloser Quell der Freude:

    [BLOG] 8 wichtige Gründe, warum du Java lernen solltest. → Nr. 6 wird dich überraschen

    […]

    6) Durch die Programmierung in Bytecode ist Java weniger Virenanfällig

    Java-Programme können vor der Ausführung verifiziert werden, da sie keine Zeiger haben und in Bytecode vorliegen. Die Verifizierung wird von Web-Browsern benutzt, um sicherzustellen, dass keine Viren enthalten sind. Java verwendet nicht Adressen aus Zahlen, sondern Namen für Funktionen und Methoden, die leicht überprüft werden können. So kann kein Java -Applet etwas ausführen oder auf etwas zugreifen, was nicht ausdrücklich im Verifizierungsprozess definiert worden ist.

    Quelle: http://www.javavideokurs.de/blog/8-gruende-warum-du-java-lernen-solltest-336/

    Es stimmt, 6 hat mich überrascht. Wenn man sich anschaut, dass die Java SRE allein 2016 auf sechs 10er CVE-Ratings gekommen ist, ist das schon sehr bezeichnend. Für die, die es nicht kennen: die Skala beschreibt die Schwere der Verwundbarkeit mit einer Zahl zwischen 1.0 (unbedeutend) und 10.0 (katastrophal).

    Es ist zwar schon richtig, dass seit Java 7u51 das Applet gültig signiert sein muss. Aber wenn die darunterliegende Sandbox kompromitiert ist, kann man sich das natürlich sparen. Nicht umsonst bleibt in Browsern wie Firefox das Java-Plugin deaktiviert bis es wirklich gebraucht wird. Außerdem war es noch nie ein Problem an „irgendein“ gültiges Zertifikate zu kommen – man ist ja hier nicht auf ein bestimmtes angewiesen. Sowas kennen wir auch schon aus dem Hause Microsoft.

    Es gibt ganz sicher gute Gründe Java zu lernen, die Security würde ich dabei jedoch nicht anführen.

     

  • Unsicher ist Unsicher

    Hallo zusammen,

    über Facebook bin ich auf einen Wettbewerb gestoßen, den ich euch nicht vorenthalten möchte:

    Deine Aufgabe ist es, ein Programm zu realisieren, mit dessen Hilfe es möglich ist, ausgewählte Dateien (und Verzeichnisse?) zu verschlüsseln und später wieder zu entschlüsseln.

    […]

    • Verschlüsselung von Daten über die Konsole oder ein GUI
    • Implementierung eines Verschlüsselungsalgorithmus (gerne auch ein eigens entwickelter Algorithmus!)
    • Entschlüsselung der Daten über gleiches Programm

    […]

    Quelle: Code Competition: Sicher ist Sicher. https://www.it-talents.de/cms/aktionen/code-competition/code-competition-04-2016

    Bereits in den Kommentaren auf Facebook wurde dem Betreiber von dieser Idee abgeraten. Verschlüsselungsverfahren sollten nur von dafür qualifizierten Personen konzipiert werden. Fehler können bei der Anwendung selbiger ohnehin noch genug gemacht werden. Natürlich ist es eine gute Sache, junge Menschen für die Programmierung zu begeistern. Allerdings werden auf diese Weise die Security Audit Findings von morgen generiert. Ich stelle mir das in 5-7 Jahren so vor:

    Chef: Wir brauchen in unserer Software dringend noch eine Verschlüsselungslösung um die sensiblen Daten der Kunden zu schützen.
    Talentierter Mitarbeiter: Ich habe da im Studium mal etwas gebaut, ist aber vermutlich nicht ganz si…
    Chef: Perfekt!

    Trotzdem hat mich dieser Ausschreibungstext inspiriert, was man wohl alles an „billigen Lösungen“ einreichen könnte, um die 222 € zu gewinnen (oder den Raspberry Pi 3). Mal von einfachen Substitutions- und Permutationslösungen abgesehen, könnte man sich einfach einer Feistelchiffren-Konstruktion bedienen (wie in DES/3DES oder Blowfish). Es hat den Vorteil, dass man sich über die Entschlüsselung keine Gedanken machen muss.

    Noch einfacher wäre es, eine Stromchiffre zu konstruieren. Für den Schlüsselstrom könnte man einfach einen PRNG (Pseudozufallsgenerator) mit einem Seed initialisieren und auf den Klartext auf-XOR-en. Das wäre nur eine Zeile – und sogar die gleiche für Ver- und Entschlüsselung.  Das fiese daran ist, dass das Ergebnis recht zufällig aussieht und ein Blackbox-Audit vermutlich sogar bestehen würde. Hier exemplarisch in Python und nur für Text, aber das geht mit einer Datei natürlich genauso gut:

    >>> import random
    
    >>> text = "hier kann ein beliebig langer Klartext geschrieben werden"
    
    ### Verschlüsselung ###
    >>> random.seed("hier den Schlüssel!"); text="".join([chr(ord(e)^random.getrandbits(8)) for e in text])
    >>> text
    '\xeb\xbdP~0v\xa3\xb8[c\x0f\xb7\xaa\xbe\xaf\x1f\x15#\xd2:\x17\xbeU\xfesJ\x1d\x18\xcbmb\xe256*\x9ct\xc2\rl0\xbb\x9e\xbc0GV\xc5\xadG\xa89\xa0_"\x9f\xaa'
    
    ### Entschlüsselung ###
    >>> random.seed("hier den Schlüssel!"); text="".join([chr(ord(e)^random.getrandbits(8)) for e in text])
    >>> text
    'hier kann ein beliebig langer Klartext geschrieben werden'

    Anstelle des PRNG könnte man auch ein Hash-Verfahren nehmen und mit einem Schlüssel initiieren. Sicher ist daran jedoch nur das Lachen der Auditoren.

    Mich würden die Einreichungen sehr interessieren. Vermutlich wird am Ende die ausgefallenste Lösung gewinnen und die Sicherheit eher auf der Strecke bleiben.

     

  • Wenn Computerviren Kliniken lahmlegen

    Hallo zusammen,

    ein kleiner Beitrag von mir in der Saarbrücker Zeitung (vom 30.03.2016), welcher im „Pfälzischer Merkur“ online verfügbar ist.

    merkur

    Quelle: Wenn Computerviren Kliniken lahmlegen

    Losgelöst vom Kontext Krankenhaus/Klinik gibt es zum Thema Ransomware natürlich sehr viel zu sagen. Das soll nun nicht den Einruck erwecken, dieses Problem wär neu: Ransomware gibt es schon sehr lange. Allerdings war der Geldtransfer ein Problem, welches mit virtuellen Bezahlsystemen wie Bitcoin erst heute so einfach lösbar ist.

    Interessant ist, dass auf diese Weise die Informationssicherheit ein Thema „für alle“ wird. Verfügbarkeitsfragen waren zwar dem Otto Normalbürger schon vorher ein Begriff, z.B. Schutz vor Festplattenausfall. So wurde im neu erworbenen NAS das RAID1 oder RAID5 eingeschaltet und tauschte damit einen Teil der Festplattenkapazität gegen ein Sicherheitsgefühl ein. Und was ist jetzt? Nun kommen akive Bedrohungen hinzu, die deutlich schwieriger zu behandeln sind und ein regelmäßiges manuelles Eingreifen bedürfen.

    Mit einem guten Konzept ist natürlich alles möglich und möglicherweise tuts auch schon eine Zeitschaltuhr an einer Backup-Festplatte. Aber die Arbeit will sich natürlich nicht jeder machen und ich habe die Befürchtung, dass es viele Nutzer noch weiter in die Arme der Cloudanbieter treiben wird. Dort kennt zwar niemand die Lösungen und man hat, hat je nach Anbieter, auch keinerlei Ansprüche … aber die sind ja Profis, die werden daran schon gedacht haben. Irgendetwas stört mich an dieser Logik.

  • Retrospective Study of Third-party Web Tracking

    Hallo zusammen,

    seit vorgestern ist mein Paper zur ICISSP 2016 Konferenz (Februar 2016 in Rom) nun online verfügbar:

    Wambach T. and Bräunlich K. (2016). Retrospective Study of Third-party Web Tracking. In Proceedings of the 2nd International Conference on Information Systems Security and Privacy , ISBN 978-989-758-167-0, pages 138-145. DOI: 10.5220/0005741301380145
    URL: http://scitepress.org

    Das Thema Web-Tracking ist ein aktuelles Forschungsgebiet von mir. In der klassischen Informationssicherheit findet dieses nur wenig Erwähnung und eine Vermutung für diesen Umstand ist, dass diese Bedrohung noch vergleichsweise neu ist. Um diese Vermutung zu belegen, zeigt das Paper wie sich Web-Tracking im Laufe der letzten 15 Jahre verändert hat.

  • Zukunft des Blogs

    Hallo zusammen,

    auch die letzten Jahre habe ich das Thema Informationssicherheit weiterverfolgt. Während meiner Tätigkeit als Security Consultant in München fehlte mir jedoch die Zeit zum Schreiben. Bei meiner aktuellen Tätigkeit als wissenschaftlicher Mitarbeiter muss ich täglich so viel schreiben, dass ich mich in meiner Freizeit doch lieber anderen Beschäftigungen widme.

    Mit Neustart dieser Webseite unter INFSEC.de soll sich dies jedoch ändern und die Gelegenheit genutzt werden, die gesamte Breite der Informationssicherheit hier adressieren zu können.

    Also wird es spannend!

  • Doppelwürfel

    Hallo zusammen,

    ich habe schon recht lange nichts mehr von mir hören lassen; ich war die letzten 6 Monate mit meiner Masterthesis beschäftigt. Wenig überraschend handelt es sich um ein Thema aus der Kryptologie, welches ich euch hiermit vorstellen möchte.

    Schon in einigen Artikeln bin ich auf antike Verschlüsselungstechniken eingegangen – diese waren jedoch schon ausgiebig erforscht. So bin ich jedoch eines Tages auf eine Methode gestoßen, welche sich zwar händisch ausführen lässt, jedoch immer noch eine recht hohe Sicherheit verspricht: der Doppelwürfel. Es handelt sich dabei um die  doppelte Anwendung einer Spaltentransposition, welche in Abhängigkeit eines Schlüssels den Klartext umsortiert (permutiert). Da noch keine automatisierten Angriffe auf diese Verschlüsselung existierten, habe ich mit meiner Arbeit diese Lücke geschlossen. Ich beschrieb die Verschlüsselung über eine Reihe von Ungleichungen und versuchte so, bei bekanntem Klar-/Chiffretext, den Schlüssel zu rekonstruieren. So ist es nun möglich, mit ca. 1/10 des Klartextes, in wenigen Minuten den Schlüssel zu finden.

    Die Verschlüsselungsmethode, Beispiele und das Ergebnis der Arbeit findet sich unter http://cryptblog.de/doppelwuerfel/. Falls jemand noch weitere Informationen möchte, kann er sich gerne mit mir in Verbindung setzen.

  • Von Kühen zu Turing

    Hallo zusammen,

    heute möchte ich präsentieren, welche „Alltagsprobleme“ sich in der Kryptologie wiederfinden.

    Vor kurzem hat mich jemand angeschrieben, er säße vor einem kleinen mathematischen Problem. In seinem Dorf ist ein so genanntes Kuhfladen-Bingo geplant. Dafür muss ein Feld von fester Größe, in eine dynamische Anzahl kleinerer unterteilt werden. Nochmal langsam:

    Wir haben zunächst das große Feld bzw. die Wiese. Diese hat eine konstante Größe bzw. im Falle, dass sie rechteckig ist, eine Länge und eine Breite. Jetzt haben wir x Lose verkauft und wollen dieses Feld in x-viele gleichgroße „kleine“ Felder aufteilen. Die Summe aller kleinen Flächen entspricht der Gesamtgröße – also wir wollen stets einen Gewinner und keine „unbesetzten“ Felder. Es soll also ein Schachbrettmuster auf dieses Feld gelegt werden, wobei in diesem Fall die kleinen Felder nicht quadratisch sein müssen.

    Mathematisch ausgedrückt, suchen wir zwei ganzzahlige n und m, wobei n*m = x und x die Anzahl der verkauften Lose ist. Kennen wir n und m, können wir die Länge bzw. Breites des Feldes durch n bzw. m teilen und erhalten die Größe der „kleinen“ Rechtecke. Ein Beispiel:

    Das Feld ist L=8 x B=16 Meter groß. Es wurden zufällig 1024 Lose verkauft. Also suchen wir:

    n * m = 1024

    Eine Lösung ist: n = 4, m=256. Demnach teilen wir die Länge L=8m durch 4 und erhalten l=2m – außerdem die Breite B=16m durch 256 und erhalten b=0,0625m. Ein kleines Feld hat also die Ausmaße l=4m und b=6,25cm. Wie wir allerdings schnell erkennen, gibt es bei dieser Gleichung mehrere Lösungen. Ebenso wären n=8, m=128 und sogar die triviale Lösung n=1 und m=1024 in der Lösungsmenge enthalten.

    Einen naiven Lösungsalgorithmus finden wir also schnell: wir suchen einen Teiler von x im Intervall [2, sqrt(x)] also zwischen 2 und der Wurzel von x. Bei x=1024 ist das die 2, die 4, die 8, die 16 und die 32. Das lässt sich relativ einfach mit einer Schleife realisieren.

    Daraufhin ergab sich die Frage, ob dafür nicht auch eine bessere bzw. effizientere Lösung existiert. Das Beste wäre eine Formel, in welcher nur die Variablen einzutragen sind und dann ein brauchbares (nichttriviales) Ergebnis präsentiert. An dieser Stelle möchte ich dem Leser Zeit geben um darüber nachzudenken. Auch bezüglich der Frage, warum sich dieses Problem in einem Blog über Kryptologie wiederfindet.

    ~

    Ich habe eben gezeigt, dass wir bei diesem Problem zwei ganzzahlige Teiler suchen: n und m bzw. n*m=x. Ich ändere nun mal die Namen der Variablen: p*q=m. Sei also m ein RSA-Modul, also das Produkt zweier Primzahlen, so sind p und q ganzzahlige Teiler von m. Wir haben also „mehr oder weniger“ nach einem effizienten Algorithmus bzw. einer Formel gesucht, die RSA-Verschlüsselung zu brechen. Wären wir an jenem Abend erfolgreich gewesen, würde ich diesen Blogeintrag an einem Strand in der Karibik zu Ende schreiben.

    Wie schon oft erwähnt, ist die „schwierige“ Suche nach den Primzahlen p und q genau das, was die RSA-Verschlüsselung ausmacht. Und die Tatsache, dass für p*q=m (p,q prim) bisher noch kein effizienter Algorithmus gefunden wurde, bietet uns Schutz bei Online Banking, Zertifikaten (PKI), VPN-Tunneln und vielem mehr.

    Moooooooment. Da steht doch p*q=m (p,q prim) – also wir suchen zwei Primzahlen dessen Produkt m ergibt. Bei unserem Problem oben war jedoch die Rede von einem beliebigen Teiler! Stimmt. Es folgt ein Ausflug in die Zahlentheorie und theoretische Informatik.

    Angenommen wir hätten das oben beschriebene Feldaufteilungsproblem effizient gelöst, dann wären wir im Besitz einer Formel oder eines Algorithmus, den wir einfach F nennen – F für Feld. Wir übergeben dem Algorithmus F also die Anzahl der Lose und selbiges generiert uns zwei ganzzahlige Teiler n und m. Auf der anderen Seite haben wir das RSA-Problem – wir besitzen also einen „langsamen“ Algorithmus für dieses Problem und nennen diesen R. Wir übergeben R ein RSA-Modul (also das Produkt zweier Primzahlen) und es liefert uns das entsprechende p und q.

    Damit sind F und R also informell definiert. Nun übergeben wir, nur aus Spaß, unserem Feldproblem F ein RSA-Modul, sagen wir r(=p*q). Warum auch nicht – es ist ja auch nur eine Zahl. F liefert uns nun also zwei ganzzahlige Teiler n und m wobei gilt: n*m=r. Jetzt wird’s spannend: nach dem Fundamentalsatz der Arithmetik ist die Primfaktorzerlegung eindeutig und stets existent. D.h. das, was wir hier zurückbekommen, müssen p und q sein. Warum? Angenommen es gäbe noch eine andere Aufteilung z.B. a*b=r, dann hätte sowohl a, als auch b eine Primfaktorzerlegung (Existenz!) welche nicht mit p*q übereinstimmt. Das ist ein Widerspruch zur Eindeutigkeit – somit haben wir indirekt p=n und m=q bewiesen. #

    Dieser Teil muss nun nicht unbedingt verstanden worden sein. Wichtig ist nur, dass wir das Problem R, also die Zerlegung eines RSA-Moduls, mit Hilfe von F lösen können. In der Informatik spricht man hier auch von Turingreduzierbarkeit. Wenn wir wissen, dass wir R mittels F lösen können, dann muss R „leichter“ sein als F, bzw. „R ist turingreduzierbar auf F“ oder „F ist Orakel für R“. So lassen sich Probleme in Klassen einteilen, was relativ komfortabel ist: sobald wir einen guten Algorithmus für F gefunden haben, ist auch effizient R gelöst. So müssen wir also nur nach einer Lösung für F suchen, wobei diese auch schwieriger sein könnte als R. Äquivalenz liegt vor, wenn eine Reduktion in beiden Richtungen möglich ist. Um die Frage vorweg zu nehmen: dies ist hier der Fall; F und R sind Turing-Äquivalent (ohne Beweis).

    So sind wir von den Kühen, über die Kryptologie, zur theoretischen Informatik gekommen.