Hello, as soon as you have a provisional residence certificate ( Fiktionsbescheinigung) in accordance with Section 24 (1) of the Residence Act, the competent foreigners authority will also issue you with a work permit. Your certificate of fiction must say "gainful employment permitted" in German: "Erwerbstätigkeit erlaubt".
If you entered the country without a visa (1.12) and have not yet applied for a residence permit: Employment is generally not possible during your short-term, visa-free stay and is only permitted in a few exceptional cases (e.g. persons with management positions in companies).On the topics of employment and social benefits, the Federal Ministry of Labour and Social Affairs has also provided FAQs in German, Ukrainian, Russian and English.
I hope I could help you :)