Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Smalltalk
Antworten
Benutzeravatar
paedubucher
Beiträge: 856
Registriert: 22.02.2009 16:19:02
Lizenz eigener Beiträge: GNU Free Documentation License
Wohnort: Schweiz
Kontaktdaten:

Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von paedubucher » 27.02.2023 21:30:23

Ich bin wieder einmal auf der Suche nach einer Unterrichtsidee. Das Thema Cloud ist ja etwas schwierig an Schulen, zumal einem Cloud-Provider nicht einmal eine Antwort auf Anfragen für Unterrichtsressourcen geben.

Dann mache ich halt meine eigene Cloud! <bender>Mit Black Jack und Nutten!</bender> :wink:

Meine Idee wäre es, die Laborrechner im Schulzimmer zu einem Art Botznetz zusammenzuschliessen, womit man Probleme lösen kann, die von einem einzelnen PC aus eben nicht so einfach zu lösen sind. So soll der Vorteil von Skalierung anschaulich demonstriert werden.

Nun benötige ich noch ein passendes Problem, idealerweise eines, das mit Brute Force recht einfach zu lösen ist und nicht allzu hohe mathematische Anforderungen stellt. Primzahlen bis zu einer bestimmten Grösse faktorisieren beispielsweise.

Oder eine einfache Verschlüsselung basierend auf xor, mit einer wiederkehrenden Passphrase von einer fixen Länge.

Das ganze Setting soll so aufgebaut sein, dass sich die einzelnen Rechner von einem zentralen Server ein Problem selbständig ziehen, es lösen, und dann die Antwort zurückspielen. Oder die einzelnen Rechnen melden sich bei einem Server und bekommen dann von diesem Anfragen zugeschickt. Je fleissiger die einzelnen Rechner arbeiten (z.B. auch parallelisiert), und desto mehr davon im Einsatz sind, desto schneller kann das Problem gelöst werden.

Das Problem sollte auch skalierbar sein: Wenn es zu schnell gelöst wird, sollte man einfach den Schwierigkeitsgrad erhöhen können (z.B. längere Passpharse, grössere Primzahl zum Faktorisieren, usw.)

Das verteilte Knacken von Codes würde auch einige LARP-Aspekte erlauben. ("Wir spielen Alan Turing in Bletchley Park und gewinnen den Zweiten Weltkrieg!") :P

Hätte jemand eine Idee für so ein typisches Brute-Force-Problem, bzw. eine grobe Vorstellung davon, welche Arten von Kryptographie man in so einem Setting ungefähr angreifen könnte? Oder gibt es vielleicht auch sinnvolle Probleme, die man damit lösen könnte? (Die Schulzimmer sind in der Regel schon gut geheizt :wink: )

Ich wäre froh um ein paar Anregungen! (Das Cloud-Modul geht Mitte August wieder los, und bis dahin liesse sich noch etwas auf die Beine stellen.)
Habe nun, ach! Java
Python und C-Sharp,
Und leider auch Visual Basic!
Durchaus programmiert mit heissem Bemühn.
Da steh' ich nun, ich armer Tor!
Und bin so klug als wie zuvor.

tobo
Beiträge: 1990
Registriert: 10.12.2008 10:51:41

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von tobo » 27.02.2023 21:56:56

Das sagt ChatGPT dazu:
Erstelle eine Liste mit Problemen, die sich einfach durch Brute Force lösen lassen.
ChatGPT hat geschrieben: Hier sind einige Beispiele für Probleme, die sich einfach durch Brute Force lösen lassen:

Das Finden der größten/mittleren/kleinsten Zahl in einer Liste von Zahlen
Das Durchsuchen einer Datei nach einem bestimmten Muster
Das Lösen eines Sudoku-Rätsels
Das Finden des kürzesten Weges zwischen zwei Punkten in einem Graphen
Das Überprüfen, ob eine Zahl eine Primzahl ist
Das Durchsuchen eines Textes nach einem bestimmten Wort
Das Finden aller Kombinationen von Elementen in einer Menge
Das Überprüfen, ob eine gegebene Zahl ein Palindrom ist
Das Finden aller Teilfolgen einer Liste
Das Überprüfen, ob eine gegebene Zeichenkette ein Anagramm einer anderen Zeichenkette ist
Das Finden der Lösung eines Schachproblems oder eines anderen Strategiespiels durch Ausprobieren aller möglichen Züge
Das Entschlüsseln einer verschlüsselten Nachricht durch Ausprobieren aller möglichen Schlüssel
Das Überprüfen, ob eine gegebene Zeichenkette ein gültiger Ausdruck in einer gegebenen regulären Sprache ist
Das Bestimmen der Häufigkeit von Buchstaben in einer gegebenen Zeichenkette
Das Lösen einer Gleichung oder eines Systems von Gleichungen durch Ausprobieren aller möglichen Variablenwerte.

Benutzeravatar
paedubucher
Beiträge: 856
Registriert: 22.02.2009 16:19:02
Lizenz eigener Beiträge: GNU Free Documentation License
Wohnort: Schweiz
Kontaktdaten:

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von paedubucher » 27.02.2023 23:01:28

tobo hat geschrieben: ↑ zum Beitrag ↑
27.02.2023 21:56:56
Das sagt ChatGPT dazu:
Erstelle eine Liste mit Problemen, die sich einfach durch Brute Force lösen lassen.
ChatGPT hat geschrieben: Hier sind einige Beispiele für Probleme, die sich einfach durch Brute Force lösen lassen:

Das Finden der größten/mittleren/kleinsten Zahl in einer Liste von Zahlen
Das Durchsuchen einer Datei nach einem bestimmten Muster
Das Lösen eines Sudoku-Rätsels
Das Finden des kürzesten Weges zwischen zwei Punkten in einem Graphen
Das Überprüfen, ob eine Zahl eine Primzahl ist
Das Durchsuchen eines Textes nach einem bestimmten Wort
Das Finden aller Kombinationen von Elementen in einer Menge
Das Überprüfen, ob eine gegebene Zahl ein Palindrom ist
Das Finden aller Teilfolgen einer Liste
Das Überprüfen, ob eine gegebene Zeichenkette ein Anagramm einer anderen Zeichenkette ist
Das Finden der Lösung eines Schachproblems oder eines anderen Strategiespiels durch Ausprobieren aller möglichen Züge
Das Entschlüsseln einer verschlüsselten Nachricht durch Ausprobieren aller möglichen Schlüssel
Das Überprüfen, ob eine gegebene Zeichenkette ein gültiger Ausdruck in einer gegebenen regulären Sprache ist
Das Bestimmen der Häufigkeit von Buchstaben in einer gegebenen Zeichenkette
Das Lösen einer Gleichung oder eines Systems von Gleichungen durch Ausprobieren aller möglichen Variablenwerte.
Also "Das Entschlüsseln einer verschlüsselten Nachricht durch Ausprobieren aller möglichen Schlüssel" hatte ich schon, das wäre mal meine Arbeitshypothese.
Wobei "Das Finden der Lösung eines Schachproblems oder eines anderen Strategiespiels durch Ausprobieren aller möglichen Züge" auch interessant wäre; es müsste halt ein eher einfaches Spiel sein.

Ich habe noch etwas an der Entschlüsselungsidee herumgedacht:

Hintergrund: "Eine fiese Verbrecherbande treibt ihr Unwesen in der Stadt. Sie koordinieren Ihre Aktionen per Textnachrichten, die sie vorher verschlüsseln. Man weiss nur folgendes: Die Leute verwenden eine XOR-Verschlüsselung, und die Schlüssel werden am Kiosk mittels ausgefüllter Lottozettel ausgetauscht. Ein Spion kann die Schlüssellänge jeweils anhand der Menge der angekreuzten Zahlen ermitteln; die Zahlen selber kann er sich aber nicht merken. Die abgefangenen Texte können aber zur Verfügung gestellt werden. Unser Team muss jetzt den Schlüssel vor Feierabend finden, damit wir die nächste Aktion verhindern können!" (*Derrick-Thema erklingt*)

Technisch sähe das dann so aus:
  • Auf einem S3-Storage werden jeden Tag in einem neuen Bucket verschlüsselte Textdateien abgelegt.
  • Die Clients können sich diese Daten rausziehen.
  • Der Client generiert einen n-stelligen, zufälligen Schlüssel.
  • Auf einem Redis-Cache werden alle bereits durchprobierten Schlüssel abgelegt. Der Client kann also sicherstellen, das er keine doppelte Arbeit verrichtet.
  • Der Client macht mit seinem Schlüssel ein XOR vom Ciphertext.
  • Der so entstandene Klartext wird nun auf Wörter abgesucht (z.B. mit /usr/share/dict/ngerman abgeglichen). Hier könnte man mit einer einfachen Schnittmenge probabilistisch arbeiten.
  • Im Erfolgsfall wird der gefundene Schlüssel veröffentlicht, und das System gibt keine weiteren Aufgaben mehr heraus.
Ob das wohl funktioniert? :?
Habe nun, ach! Java
Python und C-Sharp,
Und leider auch Visual Basic!
Durchaus programmiert mit heissem Bemühn.
Da steh' ich nun, ich armer Tor!
Und bin so klug als wie zuvor.

tobo
Beiträge: 1990
Registriert: 10.12.2008 10:51:41

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von tobo » 27.02.2023 23:25:47

paedubucher hat geschrieben: ↑ zum Beitrag ↑
27.02.2023 23:01:28
Wobei "Das Finden der Lösung eines Schachproblems oder eines anderen Strategiespiels durch Ausprobieren aller möglichen Züge" auch interessant wäre; es müsste halt ein eher einfaches Spiel sein.
Vermutlich ist hier eher die Geometrie des Schachbrettes gemeint. Spontan fallen mir direkt diese beiden Probleme dazu ein:
https://de.wikipedia.org/wiki/Springerproblem
https://de.wikipedia.org/wiki/Damenproblem
Andernfalls würde es (bei Schach) auf ein "Matt in n Zügen"-Problem hinauslaufen, welches man eben "durchrechnen" kann. Aber das wäre natürlich viel zu aufwendig.
Aber z.B. "Vier Gewinnt" ist ziemlich primitiv und auch einfach durchzurechen.
Ich habe noch etwas an der Entschlüsselungsidee herumgedacht:
Schlüssellänge und Zeichenvorrat wird gegeben, der Rest entspringt der eigenen Vorstellung...

schwedenmann
Beiträge: 5528
Registriert: 30.12.2004 15:31:07
Wohnort: Wegberg

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von schwedenmann » 27.02.2023 23:38:03

Hallo


Du könntest auch den umgekehrten Weg nehmen.

wsa kann man mi brut force nicht lösen.

z..B.
bestimmte Verschlüsselungen
hieroglyphen
Schrift der Indus (Harappa)-Kultur
verschlüsedlte Briefe der Marai Stuart

etc. pp

Da reciht reine Bruce Fort Attacken nicht aus.

mfg
schwedenmann

Benutzeravatar
GregorS
Beiträge: 2594
Registriert: 05.06.2008 09:36:37
Wohnort: Freiburg
Kontaktdaten:

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von GregorS » 27.02.2023 23:50:30

tobo hat geschrieben: ↑ zum Beitrag ↑
27.02.2023 23:25:47
Vermutlich ist hier eher die Geometrie des Schachbrettes gemeint. Spontan fallen mir direkt diese beiden Probleme dazu ein:
https://de.wikipedia.org/wiki/Springerproblem
https://de.wikipedia.org/wiki/Damenproblem
Ich werfe noch Tic-Tac-Toe in die Runde.

Gruß

Gregor

PS: T-T-T hätte auch den Vorteil, dass es nur sehr wenige „Lösungen“ - einen kleinen „Lösungsbaum“ - gibt, die bzw. der sich vermutlich vollständig auf einem A4-Blatt aufzeichnen lässt.

PPS: In diesem Zusammenhang fällt mir auch https://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens ein. Das hat zwar nichts mit Brute-Force zu tun, aber zeigt IMO eindrucksvoll, zu was für interessanten Dingen schon sehr einfache „Settings“ und Regeln führen können.
Wenn man keine Probleme hat, kann man sich welche machen. ("Großes Lötauge", Medizinmann der M3-Hopi [und sog. Maker])

Benutzeravatar
paedubucher
Beiträge: 856
Registriert: 22.02.2009 16:19:02
Lizenz eigener Beiträge: GNU Free Documentation License
Wohnort: Schweiz
Kontaktdaten:

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von paedubucher » 28.02.2023 07:44:32

tobo hat geschrieben: ↑ zum Beitrag ↑
27.02.2023 23:25:47
paedubucher hat geschrieben: ↑ zum Beitrag ↑
27.02.2023 23:01:28
Wobei "Das Finden der Lösung eines Schachproblems oder eines anderen Strategiespiels durch Ausprobieren aller möglichen Züge" auch interessant wäre; es müsste halt ein eher einfaches Spiel sein.
Vermutlich ist hier eher die Geometrie des Schachbrettes gemeint. Spontan fallen mir direkt diese beiden Probleme dazu ein:
https://de.wikipedia.org/wiki/Springerproblem
https://de.wikipedia.org/wiki/Damenproblem
Andernfalls würde es (bei Schach) auf ein "Matt in n Zügen"-Problem hinauslaufen, welches man eben "durchrechnen" kann. Aber das wäre natürlich viel zu aufwendig.
Aber z.B. "Vier Gewinnt" ist ziemlich primitiv und auch einfach durchzurechen.
Ich habe noch etwas an der Entschlüsselungsidee herumgedacht:
Schlüssellänge und Zeichenvorrat wird gegeben, der Rest entspringt der eigenen Vorstellung...
Bei einem Brettspiel wäre es vielleicht noch ein möglicher Ansatz, dass alle Clients gegen meinen Bot antreten müssten. Ein mögliches Spiel hierzu wäre Reversi, das ich schon einmal in Go implementiert hätte. Das wäre jedoch eher wieder ein Gegeneinander als ein Miteinander.
schwedenmann hat geschrieben: ↑ zum Beitrag ↑
27.02.2023 23:38:03
Hallo


Du könntest auch den umgekehrten Weg nehmen.

wsa kann man mi brut force nicht lösen.

z..B.
bestimmte Verschlüsselungen
hieroglyphen
Schrift der Indus (Harappa)-Kultur
verschlüsedlte Briefe der Marai Stuart

etc. pp

Da reciht reine Bruce Fort Attacken nicht aus.

mfg
schwedenmann
Ich möchte ja mit dem Setup den Vorteil skalierender Architekturen demonstrieren: Was einer mit seinem Rechner nicht in nützlicher Zeit lösen kann, sollen eben alle gemeinsam mit ihren Rechnern lösen können. 48 CPUs sollen hier "besser" sein als bloss 2.
GregorS hat geschrieben: ↑ zum Beitrag ↑
27.02.2023 23:50:30
tobo hat geschrieben: ↑ zum Beitrag ↑
27.02.2023 23:25:47
Vermutlich ist hier eher die Geometrie des Schachbrettes gemeint. Spontan fallen mir direkt diese beiden Probleme dazu ein:
https://de.wikipedia.org/wiki/Springerproblem
https://de.wikipedia.org/wiki/Damenproblem
Ich werfe noch Tic-Tac-Toe in die Runde.

Gruß

Gregor

PS: T-T-T hätte auch den Vorteil, dass es nur sehr wenige „Lösungen“ - einen kleinen „Lösungsbaum“ - gibt, die bzw. der sich vermutlich vollständig auf einem A4-Blatt aufzeichnen lässt.

PPS: In diesem Zusammenhang fällt mir auch https://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens ein. Das hat zwar nichts mit Brute-Force zu tun, aber zeigt IMO eindrucksvoll, zu was für interessanten Dingen schon sehr einfache „Settings“ und Regeln führen können.
Das Game of Life (habe ich auch schon einmal implementiert) wäre schon interessant. Ich frage mich aber, wie man das sinnvoll parallelisieren könnte.

Wo ich gerade auf meiner Webseite herumturne: ich habe mal Pi per Montecarlo-Simulation berechnet. Ob sich solche Simulationen sinnvoll parallelisieren und lassen? Montecarlo-Simulation wäre immerhin ein neues Stichwort...
Habe nun, ach! Java
Python und C-Sharp,
Und leider auch Visual Basic!
Durchaus programmiert mit heissem Bemühn.
Da steh' ich nun, ich armer Tor!
Und bin so klug als wie zuvor.

Benutzeravatar
MSfree
Beiträge: 10752
Registriert: 25.09.2007 19:59:30

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von MSfree » 28.02.2023 08:08:00

Ich werfe mal HTCondor in die Runde. Das ist ein System zum verteilten Rechnen.

Kennst du Distributed Net? Die haben 1997 den RC5-56 Code geknackt. 56 Bit gelten seitdem als unsicher.

Allerdings haben sie dazu 250 Tage mit einer Rechenkapazität äquivalent mit 26000 Pentium-200 CPUs benötigt. Zwar dürfte ein heutiger i3-13100 rund 1000 mal so schnell wir der damalige Pentium 200 sein. Wenn man 20 solche Rechner im Labor vernetzt, würde man immer noch 325 Tage benötigen. Für das Knacken eines Cryptokeys dürfte die Zeit also nicht ausreichen. OK, ich habe nur eine aktuelle Low-End-CPU angesetzt, aber selbst mit 32-Kern Threadrippern wäre man "nur" 8 mal so schnell, würde also immer noch 40 Tage benötigen. Man müßte also noch primitivere Schnlüssel nehmen, um den innerhalb einer akzeptablen Zeit knacken zu können.

Benutzeravatar
TRex
Moderator
Beiträge: 8070
Registriert: 23.11.2006 12:23:54
Lizenz eigener Beiträge: MIT Lizenz
Wohnort: KA

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von TRex » 28.02.2023 08:12:40

Oder einfach nur Aspekte der Verteilung von Resourcen?

- Resilienz gegen Ausfälle/Load Balancing
- ein Passwort-Formular, das sich mit Timeouts und IP-Sperre schützt (... kann immer noch mit einem großen Netzwerk angegriffen werden, welches sich synchronisiert)
Jesus saves. Buddha does incremental backups.
Windows ist doof, Linux funktioniert nichtDon't break debian!Wie man widerspricht

Benutzeravatar
paedubucher
Beiträge: 856
Registriert: 22.02.2009 16:19:02
Lizenz eigener Beiträge: GNU Free Documentation License
Wohnort: Schweiz
Kontaktdaten:

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von paedubucher » 28.02.2023 11:22:02

MSfree hat geschrieben: ↑ zum Beitrag ↑
28.02.2023 08:08:00
Ich werfe mal HTCondor in die Runde. Das ist ein System zum verteilten Rechnen.

Kennst du Distributed Net? Die haben 1997 den RC5-56 Code geknackt. 56 Bit gelten seitdem als unsicher.

Allerdings haben sie dazu 250 Tage mit einer Rechenkapazität äquivalent mit 26000 Pentium-200 CPUs benötigt. Zwar dürfte ein heutiger i3-13100 rund 1000 mal so schnell wir der damalige Pentium 200 sein. Wenn man 20 solche Rechner im Labor vernetzt, würde man immer noch 325 Tage benötigen. Für das Knacken eines Cryptokeys dürfte die Zeit also nicht ausreichen. OK, ich habe nur eine aktuelle Low-End-CPU angesetzt, aber selbst mit 32-Kern Threadrippern wäre man "nur" 8 mal so schnell, würde also immer noch 40 Tage benötigen. Man müßte also noch primitivere Schnlüssel nehmen, um den innerhalb einer akzeptablen Zeit knacken zu können.
Ja, so etwas in der Art wäre ideal. Wir würden es halt massiv vereinfachen, damit man auch selber verstehen kann, was da gerade passiert. Aber was die Architektur betrifft bietet das sicherlich gutes Anschauungsmaterial! :THX:
TRex hat geschrieben: ↑ zum Beitrag ↑
28.02.2023 08:12:40
Oder einfach nur Aspekte der Verteilung von Resourcen?

- Resilienz gegen Ausfälle/Load Balancing
- ein Passwort-Formular, das sich mit Timeouts und IP-Sperre schützt (... kann immer noch mit einem großen Netzwerk angegriffen werden, welches sich synchronisiert)
Das wären sicherlich gute Einstiegsbeispiele, womit man das ganze Setup einmal testen könnte. :THX:
Habe nun, ach! Java
Python und C-Sharp,
Und leider auch Visual Basic!
Durchaus programmiert mit heissem Bemühn.
Da steh' ich nun, ich armer Tor!
Und bin so klug als wie zuvor.

Benutzeravatar
mn77de
Beiträge: 155
Registriert: 23.11.2003 16:53:53
Wohnort: Übersee
Kontaktdaten:

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von mn77de » 28.02.2023 14:09:15

Das Damenproblem finde ich da auch sehr interessant.

Eine andere mögliche Aufgabe ... MD5 gilt ja als unsicher, was man mit BF gut beweisen könnte:
  • Finde eine oder mehrere Zeichen- oder Byte-Ketten, die zu einem gegebenen MD5-Hash führen.
OpenSource! :THX:

schwedenmann
Beiträge: 5528
Registriert: 30.12.2004 15:31:07
Wohnort: Wegberg

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von schwedenmann » 01.03.2023 10:52:33

Hallo

Oder Mastermind mit 4 Positionen und 4 Farben und dann 4 Positionen und 6 Farben.


mfg
schwedenmann

Benutzeravatar
paedubucher
Beiträge: 856
Registriert: 22.02.2009 16:19:02
Lizenz eigener Beiträge: GNU Free Documentation License
Wohnort: Schweiz
Kontaktdaten:

Re: Welche Probleme lassen sich sehr einfach per Brute Force lösen?

Beitrag von paedubucher » 01.03.2023 11:53:07

mn77de hat geschrieben: ↑ zum Beitrag ↑
28.02.2023 14:09:15
Das Damenproblem finde ich da auch sehr interessant.

Eine andere mögliche Aufgabe ... MD5 gilt ja als unsicher, was man mit BF gut beweisen könnte:
  • Finde eine oder mehrere Zeichen- oder Byte-Ketten, die zu einem gegebenen MD5-Hash führen.
Meines Wissens ist eine MD5-Kollision doch recht aufwändig zu erstellen. Oder war es zumindest noch vor ca 7 Jahren :wink:

Unter 3.5 Results:
Based on our complexity analysis and a number of computers available for our collision search, we
estimated that it would take approximately five weeks. As this was feasible enough, we started
the actual search.
It was our fortune that a collision was found a bit earlier, namely after only three weeks.
Vielleicht doch eher etwas für die Hochschule bzw. für den Serverraum :mrgreen:
schwedenmann hat geschrieben: ↑ zum Beitrag ↑
01.03.2023 10:52:33
Hallo

Oder Mastermind mit 4 Positionen und 4 Farben und dann 4 Positionen und 6 Farben.


mfg
schwedenmann
Das wäre interessant; habe ich selber auch noch nie ausprogrammiert. Könnte man auch schön mit JavaScript visualisieren. Ich überlege mir das!
Habe nun, ach! Java
Python und C-Sharp,
Und leider auch Visual Basic!
Durchaus programmiert mit heissem Bemühn.
Da steh' ich nun, ich armer Tor!
Und bin so klug als wie zuvor.

Antworten