diff --git a/java/com/google/gerrit/server/permissions/ChangeControl.java b/java/com/google/gerrit/server/permissions/ChangeControl.java
index 6f7d761..e36ce7b 100644
--- a/java/com/google/gerrit/server/permissions/ChangeControl.java
+++ b/java/com/google/gerrit/server/permissions/ChangeControl.java
@@ -216,7 +216,10 @@
     public void check(ChangePermissionOrLabel perm)
         throws AuthException, PermissionBackendException {
       if (!can(perm)) {
-        throw new AuthException(perm.describeForException() + " not permitted");
+        throw new AuthException(
+            perm.describeForException()
+                + " not permitted"
+                + perm.hintForException().map(hint -> " (" + hint + ")").orElse(""));
       }
     }
 
diff --git a/java/com/google/gerrit/server/permissions/ChangePermission.java b/java/com/google/gerrit/server/permissions/ChangePermission.java
index 63b0378..6ceed3e 100644
--- a/java/com/google/gerrit/server/permissions/ChangePermission.java
+++ b/java/com/google/gerrit/server/permissions/ChangePermission.java
@@ -16,7 +16,9 @@
 
 import static java.util.Objects.requireNonNull;
 
+import com.google.gerrit.common.Nullable;
 import com.google.gerrit.extensions.api.access.GerritPermission;
+import java.util.Optional;
 
 public enum ChangePermission implements ChangePermissionOrLabel {
   READ,
@@ -53,24 +55,40 @@
    * <p>Before checking this permission, the caller should first verify the current patch set of the
    * change is not locked by calling {@code PatchSetUtil.isPatchSetLocked}.
    */
-  REBASE,
+  REBASE(
+      /* description= */ null,
+      /* hint= */ "change owners and users with the 'Submit' or 'Rebase' permission can rebase"
+          + " if they have the 'Push' permission"),
   REVERT,
   SUBMIT,
   SUBMIT_AS("submit on behalf of other users"),
   TOGGLE_WORK_IN_PROGRESS_STATE;
 
   private final String description;
+  private final String hint;
 
   ChangePermission() {
     this.description = null;
+    this.hint = null;
   }
 
   ChangePermission(String description) {
     this.description = requireNonNull(description);
+    this.hint = null;
+  }
+
+  ChangePermission(@Nullable String description, String hint) {
+    this.description = description;
+    this.hint = requireNonNull(hint);
   }
 
   @Override
   public String describeForException() {
     return description != null ? description : GerritPermission.describeEnumValue(this);
   }
+
+  @Override
+  public Optional<String> hintForException() {
+    return Optional.ofNullable(hint);
+  }
 }
diff --git a/java/com/google/gerrit/server/permissions/ChangePermissionOrLabel.java b/java/com/google/gerrit/server/permissions/ChangePermissionOrLabel.java
index f59ba02..9254158 100644
--- a/java/com/google/gerrit/server/permissions/ChangePermissionOrLabel.java
+++ b/java/com/google/gerrit/server/permissions/ChangePermissionOrLabel.java
@@ -15,6 +15,17 @@
 package com.google.gerrit.server.permissions;
 
 import com.google.gerrit.extensions.api.access.GerritPermission;
+import java.util.Optional;
 
 /** A {@link ChangePermission} or a {@link AbstractLabelPermission}. */
-public interface ChangePermissionOrLabel extends GerritPermission {}
+public interface ChangePermissionOrLabel extends GerritPermission {
+  /**
+   * A hint that explains under which conditions this permission is permitted.
+   *
+   * <p>This is useful for permissions that are not directly assigned but are indirectly permitted
+   * by the user having other permissions or being the change owner.
+   */
+  default Optional<String> hintForException() {
+    return Optional.empty();
+  }
+}
diff --git a/javatests/com/google/gerrit/acceptance/api/change/RebaseIT.java b/javatests/com/google/gerrit/acceptance/api/change/RebaseIT.java
index 74bd94e..522013e 100644
--- a/javatests/com/google/gerrit/acceptance/api/change/RebaseIT.java
+++ b/javatests/com/google/gerrit/acceptance/api/change/RebaseIT.java
@@ -399,7 +399,11 @@
       String changeId = r2.getChangeId();
       requestScopeOperations.setApiUser(user.id());
       AuthException thrown = assertThrows(AuthException.class, () -> rebaseCall.call(changeId));
-      assertThat(thrown).hasMessageThat().contains("rebase not permitted");
+      assertThat(thrown)
+          .hasMessageThat()
+          .isEqualTo(
+              "rebase not permitted (change owners and users with the 'Submit' or 'Rebase'"
+                  + " permission can rebase if they have the 'Push' permission)");
     }
 
     @Test
@@ -449,7 +453,11 @@
       String changeId = r2.getChangeId();
       requestScopeOperations.setApiUser(user.id());
       AuthException thrown = assertThrows(AuthException.class, () -> rebaseCall.call(changeId));
-      assertThat(thrown).hasMessageThat().contains("rebase not permitted");
+      assertThat(thrown)
+          .hasMessageThat()
+          .isEqualTo(
+              "rebase not permitted (change owners and users with the 'Submit' or 'Rebase'"
+                  + " permission can rebase if they have the 'Push' permission)");
     }
 
     @Test
@@ -473,7 +481,11 @@
       // Rebase the second
       String changeId = r2.getChangeId();
       AuthException thrown = assertThrows(AuthException.class, () -> rebaseCall.call(changeId));
-      assertThat(thrown).hasMessageThat().contains("rebase not permitted");
+      assertThat(thrown)
+          .hasMessageThat()
+          .isEqualTo(
+              "rebase not permitted (change owners and users with the 'Submit' or 'Rebase'"
+                  + " permission can rebase if they have the 'Push' permission)");
     }
 
     @Test