Jelly, 28 bytes

ØṖœ!95Ż¤,ØṖṗ75Ż¤¤Ẏ€³œ?µḢi⁴ịḢ

Try it online!

Since this code generates all the permutations and therefore would take very long to finish, TIO link is to a limited version that supports characters abcdefg, message length 4 and encoded length 5. I checked that these numbers follow similar constraints as the actual ones. Only the constants are changed, so the true version should also (theoretically) work.

Explanation

ØṖœ!95Ż¤,ØṖṗ75Ż¤¤Ẏ€³œ?µḢi⁴ịḢ   Dyadic link that accepts the boolean flag and message
ØṖ                             ASCII printable characters
  œ!                           Permutations of size
    95Ż¤                       0..95
        ,       ¤              Pair with
         ØṖ                    ASCII printable characters
           ṗ                   Cartesian power
            75Ż¤               0..75
                 Ẏ€            Flatten both lists (non-recursively)
                   ³œ?         Reverse the pair if the boolean flag is set
                      µ        Feed into new monadic link
                       Ḣ       Pop first item of the pair
                        i⁴     Find index of the message
                          ịḢ   Index into the head of what used to be the pair

Jelly, 32 28 27 bytes

ØṖµœ!95Ż¤,ṗ75Ż¤$Ẏ€³œ?µḢi⁴ịḢ

Try it online!

Since this code generates all the permutations and therefore would take very long to finish, TIO link is to a limited version that supports characters abcdefg, message length 4 and encoded length 5. I checked that these numbers follow similar constraints as the actual ones. Only the constants are changed, so the true version should also (theoretically) work.

Explanation

ØṖµœ!95Ż¤,ṗ75Ż¤$Ẏ€³œ?µḢi⁴ịḢ   Dyadic link that accepts the boolean flag and message
ØṖ                            ASCII printable characters
  µ                           Feed into new monadic chain
   œ!                         Permutations of size
     95Ż¤                     0..95
         ,     $              Pair with
          ṗ                   Cartesian power
           75Ż¤               0..75
                Ẏ€            Flatten both lists (non-recursively)
                  ³œ?         Reverse the pair if the boolean flag is set
                     µ        Feed into new monadic chain
                      Ḣ       Pop first item of the pair
                       i⁴     Find index of the message
                         ịḢ   Index into the head of what used to be the pair

Jelly, 32 bytes

32r126Ọµœ!95Ż¤,ṗ75Ż¤$Ẏ€³œ?µḢi⁴ịḢ

Try it online!

Since this code generates all the permutations and therefore would take very long to finish, TIO link is to a limited version that supports characters abcdefg, message length 4 and encoded length 5. I checked that these numbers follow similar constraints as the actual ones. Only the number literals are changed, so the true version should also (theoretically) work.

Jelly, 28 bytes

ØṖœ!95Ż¤,ØṖṗ75Ż¤¤Ẏ€³œ?µḢi⁴ịḢ

Try it online!

Since this code generates all the permutations and therefore would take very long to finish, TIO link is to a limited version that supports characters abcdefg, message length 4 and encoded length 5. I checked that these numbers follow similar constraints as the actual ones. Only the constants are changed, so the true version should also (theoretically) work.

Explanation

ØṖœ!95Ż¤,ØṖṗ75Ż¤¤Ẏ€³œ?µḢi⁴ịḢ   Dyadic link that accepts the boolean flag and message
ØṖ                             ASCII printable characters
  œ!                           Permutations of size
    95Ż¤                       0..95
        ,       ¤              Pair with
         ØṖ                    ASCII printable characters
           ṗ                   Cartesian power
            75Ż¤               0..75
                 Ẏ€            Flatten both lists (non-recursively)
                   ³œ?         Reverse the pair if the boolean flag is set
                      µ        Feed into new monadic link
                       Ḣ       Pop first item of the pair
                        i⁴     Find index of the message
                          ịḢ   Index into the head of what used to be the pair